Сжатый массив суффиксов - Compressed suffix array

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

Учитывая текст Т из п символов из алфавита Σ, сжатый массив суффиксов поддерживает поиск произвольных шаблонов в Т. Для шаблона ввода п из м символов, время поиска обычно составляет O (м) или O (м + журнал (п)). Используемое пространство обычно , куда это эмпирическая энтропия k-го порядка текста Т. Время и пространство для создания сжатого массива суффиксов обычно .

Первоначальное создание сжатого массива суффиксов[1] решил давнюю открытую проблему, показав, что быстрое сопоставление с образцом возможно с использованием только линейной структуры данных, а именно структуры, пропорциональной размеру текста Т, который занимает биты. Обычный массив суффиксов и суффиксное дерево используют бит, что существенно больше. Основой для структуры данных является рекурсивная декомпозиция с использованием «функции соседа», которая позволяет представлять массив суффиксов половиной своей длины. Построение повторяется несколько раз, пока в результирующем массиве суффиксов не будет использоваться линейное количество битов. Последующая работа показала, что фактическое пространство для хранения связано с энтропией нулевого порядка и что индекс поддерживает самоиндексирование.[4] Ограничение по объему было дополнительно улучшено для достижения конечной цели энтропии более высокого порядка; сжатие достигается путем разделения функции соседа на контексты высокого порядка и сжатия каждого раздела с вейвлет-дерево.[3] Использование пространства на практике чрезвычайно конкурентоспособно с другими современными компрессорами,[5] а также поддерживает быстрое сопоставление с образцом.

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

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

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

Смотрите также

Рекомендации

  1. ^ а б c Р. Гросси и Дж. С. Виттер, Сжатые массивы суффиксов и деревья суффиксов, с приложениями для индексирования текста и сопоставления строк, Журнал SIAM по вычислениям, 35 (2), 2005, 378-407. Более ранняя версия появилась в Труды 32-го симпозиума ACM по теории вычислений, Май 2000, 397-406.
  2. ^ а б Паоло Феррагина и Джованни Манзини (2000). «Оппортунистические структуры данных с приложениями». Материалы 41-го ежегодного симпозиума по основам компьютерных наук. стр.390.
  3. ^ а б Р. Гросси, А. Гупта, Дж. С. Виттер, Энтропийно сжатые текстовые индексы высокого порядка, Материалы 14-го ежегодного симпозиума SIAM / ACM по дискретным алгоритмам, Январь 2003 г., 841-850.
  4. ^ К. Садакане, Базы данных со сжатым текстом с эффективными алгоритмами запросов на основе массивов сжатых суффиксов, Материалы Международного симпозиума по алгоритмам и вычислениям, Конспект лекций по информатике, т. 1969, Springer, декабрь 2000 г., 410-421.
  5. ^ Л. Фошини, Р. Гросси, А. Гупта и Дж. С. Виттер, Индексирование равного сжатия: эксперименты с суффиксными массивами и деревьями, ACM-транзакции на алгоритмах, 2(4), 2006, 611-639.
  6. ^ W.-K. Хон, Р. Шах, С. В. Саккачан и Дж. С. Виттер, Об индексировании сжатого энтропией текста во внешней памяти, Материалы конференции по обработке строк и поиску информации, Август 2009 г.
  7. ^ М. П. Фергюсон, FEMTO: быстрый поиск в больших коллекциях последовательностей, Труды 23-й ежегодной конференции по комбинаторному сопоставлению с образцом, Июль 2012 г.

внешняя ссылка

Реализации: