Сжатый массив суффиксов

редактировать

В информатике, сжатый массив суффиксов - это сжатая структура данных для сопоставления с образцом. Сжатые массивы суффиксов - это общий класс структуры данных , улучшенный по сравнению с массивом суффиксов . Эти структуры данных позволяют быстро искать произвольную строку со сравнительно небольшим индексом.

Учитывая текст T из n символов из алфавита Σ, сжатый массив суффиксов поддерживает поиск произвольных шаблонов в T. Для входного шаблона P из m символов время поиска обычно составляет O (m) или O (т + журнал (п)). Обычно используется пространство $O (n H k (T)) + o (n) {\ displaystyle O (nH_ {k} (T)) + o (n)}$ $O (nH_ {k} (T)) + o (n)$ , где $H k (T) {\ displaystyle H_ {k} (T)}$ $H_ {k} (T)$ - это эмпирическая энтропия k-го порядка текста T. Время и пространство для построения сжатый массив суффиксов обычно $O (n) {\ displaystyle O (n)}$ $O (n)$ .

Первоначальное создание сжатого массива суффиксов решило давнюю открытую проблему, показав, что быстрое сопоставление с образцом возможно с использованием только линейного -пространственная структура данных, а именно, пропорциональная размеру текста T, которая принимает $O (n log ⁡ | Σ |) {\ displaystyle O (n \, {\ log | \ Sigma |})}$ $O (n \, {\ log | \ Sigma | })$ бит. Традиционный массив суффиксов и дерево суффиксов используют $Ω (n log ⁡ n) {\ displaystyle \ Omega (n \, {\ log n})}$ $\ Omega (n \, {\ log n})$ бит, который значительно больше. Основой для структуры данных является рекурсивная декомпозиция с использованием «функции соседа», которая позволяет представить массив суффиксов половиной своей длины. Построение повторяется несколько раз, пока в результирующем массиве суффиксов не будет использоваться линейное количество битов. Последующие исследования показали, что фактическое пространство для хранения связано с энтропией нулевого порядка и что индекс поддерживает самоиндексирование. Ограничение по объему было дополнительно улучшено для достижения конечной цели энтропии более высокого порядка; сжатие достигается путем разделения функции соседа по контекстам высокого порядка и сжатия каждого раздела с помощью вейвлет-дерева. Использование пространства на практике является чрезвычайно конкурентоспособным по сравнению с другими современными компрессорами, а также поддерживает быстрое сопоставление с образцом.

Доступы к памяти, осуществляемые сжатыми массивами суффиксов и другими сжатыми структурами данных для сопоставления с образцом, обычно не локализованы, и, таким образом, эти структуры данных, как известно, было сложно эффективно спроектировать для использования во внешней памяти. Недавний прогресс в использовании геометрической двойственности использует преимущества блочного доступа, предоставляемого дисками, для значительного ускорения времени ввода-вывода. Кроме того, была продемонстрирована потенциально практическая производительность поиска для сжатого массива суффиксов во внешней памяти.

Содержание

1 Реализации с открытым исходным кодом
2 См. Также
3 Ссылки
4 Внешние ссылки

Реализации с открытым исходным кодом

Доступно несколько реализаций с открытым исходным кодом сжатых массивов суффиксов (см. Внешние Ссылки ниже). Bowtie и Bowtie2 - это реализации сжатого массива суффиксов с открытым исходным кодом выравнивания чтения для использования в биоинформатике. Библиотека кратких структур данных (SDSL) - это библиотека, содержащая множество сжатых структур данных, включая сжатые массивы суффиксов. FEMTO - это реализация сжатых массивов суффиксов для внешней памяти. Кроме того, на веб-сайте Pizza Chili доступны различные реализации, включая оригинальные реализации FM-index (см. Внешние ссылки).

См. Также

Ссылки

^ R. Гросси и Дж. С. Виттер, Сжатые массивы суффиксов и деревья суффиксов, с приложениями для индексирования текста и сопоставления строк, SIAM Journal on Computing, 35 (2), 2005, 378-407. Более ранняя версия появилась в Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397-406.
^ Паоло Ферражина и Джованни Манзини (2000). «Оппортунистические структуры данных с приложениями». Материалы 41-го ежегодного симпозиума по основам компьютерных наук. стр.390.
^ Р. Гросси, А. Гупта и Дж. С. Виттер, Энтропийно-сжатые текстовые индексы высокого порядка, Материалы 14-го ежегодного симпозиума SIAM / ACM по дискретным алгоритмам, январь 2003 г., 841-850.
^К. Садакане, Базы данных со сжатым текстом с эффективными алгоритмами запросов на основе массивов сжатых суффиксов, Труды Международного симпозиума по алгоритмам и вычислениям, Конспект лекций по информатике, т. 1969, Springer, декабрь 2000 г., 410-421.
^Л. Фошини, Р. Гросси, А. Гупта и Дж. С. Виттер, Индексирование равного сжатия: эксперименты с суффиксными массивами и деревьями, Транзакции ACM по алгоритмам, 2 (4), 2006, 611-639.
^У.-К. Хон, Р. Шах, С. В. Танкачан и Дж. С. Виттер, Об индексировании сжатого текста во внешней памяти, Труды конференции по обработке строк и поиску информации, август 2009 г.
^М. П. Фергюсон, FEMTO: быстрый поиск в больших коллекциях последовательностей, Труды 23-й ежегодной конференции по комбинаторному сопоставлению шаблонов, июль 2012 г.

Внешние ссылки

Реализации: