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

Сжатая структура данных для сопоставления с образцом

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

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

Первоначальное представление сжатого массива суффиксов ^[1] решило давнюю открытую проблему, показав, что быстрое сопоставление с образцом возможно с использованием только линейной структуры данных, а именно, пропорциональной размеру текста T , которая занимает биты. Обычный массив суффиксов и дерево суффиксов используют биты, что существенно больше. Основой структуры данных является рекурсивное разложение с использованием «функции соседа», которая позволяет представить массив суффиксов одним из половины его длины. Построение повторяется несколько раз, пока результирующий массив суффиксов не будет использовать линейное число битов. Последующая работа показала, что фактическое пространство хранения связано с энтропией -порядка и что индекс поддерживает самоиндексацию. ^[4] Ограничение пространства было дополнительно улучшено для достижения конечной цели энтропии более высокого порядка; сжатие достигается путем разбиения функции соседа контекстами более высокого порядка и сжатия каждого раздела с помощью вейвлет-дерева . ^[3] Использование пространства на практике чрезвычайно конкурентоспособно по сравнению с другими современными компрессорами, ^[5] а также поддерживает быстрое сопоставление образцов на месте . $O(n\,{\log |\Sigma |})$ $\Omega (n\, {\log n})$ $0^{й}$

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

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

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

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

Ссылки

^ abc R. Grossi и JS Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 35(2), 2005, 378–407. Более ранняя версия появилась в Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397–406.
^ ab Паоло Феррагина и Джованни Манзини (2000). «Оппортунистические структуры данных с приложениями». Труды 41-го ежегодного симпозиума по основам компьютерной науки. стр. 390.
^ ab R. Grossi, A. Gupta и JS Vitter, Текстовые индексы с высоким уровнем энтропии, Труды 14-го ежегодного симпозиума SIAM/ACM по дискретным алгоритмам, январь 2003 г., 841–850.
^ К. Садакане, Сжатые текстовые базы данных с эффективными алгоритмами запросов на основе сжатых массивов суффиксов, Труды Международного симпозиума по алгоритмам и вычислениям , Lecture Notes in Computer Science, т. 1969, Springer, декабрь 2000 г., 410–421.
^ Л. Фоскини, Р. Гросси, А. Гупта и Дж. С. Виттер, Индексирование равно сжатию: эксперименты с массивами суффиксов и деревьями , ACM Transactions on Algorithms , 2(4), 2006, 611–639.
^ В.-К. Хон, Р. Шах, С.В. Танкачан и Дж.С. Виттер, Об индексации текста с энтропийным сжатием во внешней памяти, Труды конференции по обработке строк и поиску информации , август 2009 г.
^ MP Ferguson, FEMTO: быстрый поиск больших коллекций последовательностей, Труды 23-й ежегодной конференции по комбинаторному сопоставлению образов , июль 2012 г.

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

Реализации:

Галстук-бабочка и галстук-бабочка2
Библиотека краткой структуры данных (SDSL)
ФЕМТО
Сайт Pizza&Chili.

[GV00-1] R. Grossi и JS Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 35(2), 2005, 378–407. Более ранняя версия появилась в Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397–406.

[opportunistic_2000-2] Паоло Феррагина и Джованни Манзини (2000). «Оппортунистические структуры данных с приложениями». Труды 41-го ежегодного симпозиума по основам компьютерной науки. стр. 390.

[GGV03-3] R. Grossi, A. Gupta и JS Vitter, Текстовые индексы с высоким уровнем энтропии, Труды 14-го ежегодного симпозиума SIAM/ACM по дискретным алгоритмам, январь 2003 г., 841–850.

[4] К. Садакане, Сжатые текстовые базы данных с эффективными алгоритмами запросов на основе сжатых массивов суффиксов, Труды Международного симпозиума по алгоритмам и вычислениям , Lecture Notes in Computer Science, т. 1969, Springer, декабрь 2000 г., 410–421.

[5] Л. Фоскини, Р. Гросси, А. Гупта и Дж. С. Виттер, Индексирование равно сжатию: эксперименты с массивами суффиксов и деревьями , ACM Transactions on Algorithms , 2(4), 2006, 611–639.

[6] В.-К. Хон, Р. Шах, С.В. Танкачан и Дж.С. Виттер, Об индексации текста с энтропийным сжатием во внешней памяти, Труды конференции по обработке строк и поиску информации , август 2009 г.

[7] MP Ferguson, FEMTO: быстрый поиск больших коллекций последовательностей, Труды 23-й ежегодной конференции по комбинаторному сопоставлению образов , июль 2012 г.