В информатике , А сжатый массив суффикса [1] [2] [3] является сжата структурой данных для сравнения с шаблоном . Сжатые массивы суффиксов - это общий класс структур данных, которые улучшают массив суффиксов . [1] [2] Эти структуры данных позволяют быстро искать произвольную строку со сравнительно небольшим индексом.
Учитывая текст Т из п символов из алфавита а, а сжатый суффикс массив поддерживает поиск произвольных моделей в T . Для входного шаблона P из m символов время поиска обычно составляет O ( m ) или O ( m + log ( n )). Используемое пространство обычно, где является к-го порядка эмпирического энтропии текстового T . Время и пространство для создания сжатого массива суффиксов обычно.
Первоначальная реализация сжатого массива суффиксов [1] решила давнюю открытую проблему, показав, что быстрое сопоставление с образцом возможно с использованием только структуры данных линейного пространства, а именно структуры, пропорциональной размеру текста T , которая занимаетбиты. Обычный массив суффиксов и суффиксное дерево используютбит, что существенно больше. В основе структуры данных лежит рекурсивная декомпозиция с использованием «функции соседа», которая позволяет представлять массив суффиксов половиной своей длины. Построение повторяется несколько раз, пока в результирующем массиве суффиксов не будет использоваться линейное количество битов. Последующая работа показала, что фактическое пространство для хранения связано с энтропией нулевого порядка и что индекс поддерживает самоиндексирование. [4] Граница объема была дополнительно улучшена для достижения конечной цели энтропии более высокого порядка; сжатие достигается путем разделения функции соседа на контексты высокого порядка и сжатия каждого раздела с помощью вейвлет-дерева . [3] Использование пространства на практике является чрезвычайно конкурентоспособным по сравнению с другими современными компрессорами [5], а также поддерживает быстрое сопоставление с образцом.
Доступы к памяти, осуществляемые сжатыми массивами суффиксов и другими сжатыми структурами данных для сопоставления с образцом, обычно не локализованы, и, следовательно, эти структуры данных, как известно, было сложно эффективно спроектировать для использования во внешней памяти . Недавний прогресс в использовании геометрической двойственности использует преимущества блочного доступа, предоставляемого дисками, для значительного ускорения времени ввода-вывода [6]. Кроме того, была продемонстрирована потенциально практическая производительность поиска для сжатого массива суффиксов во внешней памяти. [7]
Реализации с открытым исходным кодом
Доступно несколько реализаций сжатых суффиксных массивов с открытым исходным кодом (см. Ниже внешние ссылки ). Bowtie и Bowtie2 - это реализации алгоритма выравнивания чтения со сжатым массивом суффиксов с открытым исходным кодом для использования в биоинформатике . Библиотека кратких структур данных (SDSL) - это библиотека, содержащая множество сжатых структур данных, включая сжатые массивы суффиксов. FEMTO - это реализация сжатых массивов суффиксов для внешней памяти. Кроме того, на веб-сайте Pizza & Chili доступны различные реализации, включая оригинальные реализации FM-индекса (см. Внешние ссылки).
Смотрите также
Рекомендации
- ^ a b c Р. Гросси и Дж. С. Виттер, Сжатые массивы суффиксов и деревья суффиксов, с приложениями для индексирования текста и сопоставления строк, SIAM Journal on Computing, 35 (2), 2005, 378-407. Более ранняя версия появилась в Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397-406.
- ^ a b Паоло Феррагина и Джованни Манзини (2000). «Оппортунистические структуры данных с приложениями». Материалы 41-го ежегодного симпозиума по основам информатики. стр.390.
- ^ a b Р. Гросси, А. Гупта и Дж. С. Виттер, Энтропийно сжатые текстовые индексы высокого порядка, Труды 14-го ежегодного симпозиума SIAM / ACM по дискретным алгоритмам, январь 2003 г., 841-850.
- ^ К. Садакане, Базы данных со сжатым текстом с эффективными алгоритмами запросов, основанными на сжатых массивах суффиксов, Труды Международного симпозиума по алгоритмам и вычислениям , Конспект лекций по информатике, том. 1969, Springer, декабрь 2000 г., 410-421.
- ^ Л. Фошини, Р. Гросси, А. Гупта и Дж. С. Виттер, Индексирование равного сжатия: эксперименты с суффиксными массивами и деревьями , Транзакции ACM по алгоритмам , 2 (4), 2006, 611-639.
- ^ W.-K. Хон, Р. Шах, С.В. Танкачан и Дж. С. Виттер, Об индексировании сжатого текста во внешней памяти, Труды конференции по обработке строк и поиску информации , август 2009 г.
- ^ MP Ferguson, FEMTO: быстрый поиск в больших коллекциях последовательностей , Труды 23-й ежегодной конференции по комбинаторному сопоставлению с образцом , июль 2012 г.
Внешние ссылки
Реализации: