4511
правок
Сжатие и индексация дерева: различия между версиями
Перейти к навигации
Перейти к поиску
→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 94: | Строка 94: | ||
Первый пример касается суффиксных деревьев – важнейшего блока алгоритмов для многих приложений для обработки строк, от биоинформатики до добычи данных и сжатия данных до поисковых машин. Стандартные реализации суффиксных деревьев требуют не менее 80 бит памяти на одну вершину. Сжатое суффиксное дерево для строки S[1, s] состоит из трех компонентов: топологии дерева, значений глубины строк, хранящихся во внутренних вершинах суффиксного дерева, и суффиксных указателей, хранящихся в листьях суффиксного дерева (также называемых суффиксным массивом S). Сокращенное представление дерева, предложенное в [11], может использоваться для кодирования топологии суффиксного дерева и глубины строк, что требует 4s + o(s) бит (предполагая без потери общности, что \ | Первый пример касается суффиксных деревьев – важнейшего блока алгоритмов для многих приложений для обработки строк, от биоинформатики до добычи данных и сжатия данных до поисковых машин. Стандартные реализации суффиксных деревьев требуют не менее 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, для каждой операции выполняя декомпрессию только небольшого фрагмента данных. Предыдущим решениям требовалось несколько секунд на операцию! | Второй пример относится к формату XML, который нередко моделируется при помощи помеченного дерева. Сжатые и сокращенные индексы, описанные в работах [1, 2, 5], разработаны с теоретической точки зрения, однако оказываются вполне релевантными для практических систем обработки XML-файлов. К примеру, в [6] были опубликованы первые обнадеживающие экспериментальные результаты, подчеркивающие эффективность преобразования XBW-Transform на реальных базах данных XML. Авторы показали, что качественная адаптация алгоритма XBW-Transform позволяет сжимать данные в формате XML до самых современных XML-совместимых компрессоров, обеспечивая доступ к контенту, навигацию вверх и вниз по структуре XML-дерева и поиск простых выражений и подстрок в виде путей за несколько миллисекунд на данных в формате MB или XML, для каждой операции выполняя декомпрессию только небольшого фрагмента данных. Предыдущим решениям требовалось несколько секунд на операцию! | ||
== Открытые вопросы == | == Открытые вопросы == | ||