Сжатие и индексация дерева: различия между версиями

Первый пример касается суффиксных деревьев – важнейшего блока алгоритмов для многих приложений для обработки строк, от биоинформатики до добычи данных и сжатия данных до поисковых машин. Стандартные реализации суффиксных деревьев требуют не менее 80 бит памяти на одну вершину. Сжатое суффиксное дерево для строки S[1, s] состоит из трех компонентов: топологии дерева, значений глубины строк, хранящихся во внутренних вершинах суффиксного дерева, и суффиксных указателей, хранящихся в листьях суффиксного дерева (также называемых суффиксным массивом S). Сокращенное представление дерева, предложенное в [11], может использоваться для кодирования топологии суффиксного дерева и глубины строк, что требует 4s + o(s) бит (предполагая без потери общности, что <math>| \Sigma | = 2 \;</math>). Суффиксный массив может быть сжат вплоть до энтропии k-го порядка S при помощи любого решения из перечисленных в работе [14]. Общий результат никогда не превышает 80 бит на вершину, а для строк с высоким уровнем сжимаемости может оказаться значительно ниже.

Второй пример относится к формату XML, который нередко моделируется при помощи помеченного дерева. Сжатые и сокращенные индексы, описанные в работах [1, 2, 5], разработаны с теоретической точки зрения, однако оказываются вполне релевантными для практических систем обработки XML-файлов. К примеру, в [6] были опубликованы первые обнадеживающие экспериментальные результаты, подчеркивающие эффективность преобразования XBW-Transform на реальных базах данных XML. Авторы показали, что качественная адаптация алгоритма XBW-Transform позволяет сжимать данные в формате XML до самых современных XML-совместимых компрессоров, обеспечивая доступ к контенту, навигацию вверх и вниз по структуре XML-дерева и поиск простых выражений и подстрок в виде путей за несколько миллисекунд на данных в формате MB или XML, для каждой операции выполняя декомпрессию только небольшого фрагмента данных. Предыдущим решениям требовалось несколько секунд на операцию!