Массив суффиксов - Suffix array

Рассмотрим текст ${ displaystyle S}$=банан $ для индексации:

я	1	2	3	4	5	6	7
${ Displaystyle S [я]}$	б	а	п	а	п	а	$

Текст заканчивается специальным дозорным письмом. $ который уникален и лексикографически меньше любого другого символа. Текст имеет следующие суффиксы:

Эти суффиксы можно отсортировать в порядке возрастания:

Массив суффиксов ${ displaystyle A}$ содержит начальные позиции этих отсортированных суффиксов:

я =	1	2	3	4	5	6	7
${ Displaystyle А [я]}$ =	7	6	4	2	1	5	3

Массив суффиксов с суффиксами, написанными вертикально внизу для ясности:

я =	1	2	3	4	5	6	7
${ Displaystyle А [я]}$ =	7	6	4	2	1	5	3
1	$	а	а	а	б	п	п
2		$	п	п	а	а	а
3			а	а	п	$	п
4			$	п	а		а
5				а	п		$
6				$	а
7					$

Так, например, ${ Displaystyle А [3]}$ содержит значение 4 и, следовательно, относится к суффиксу, начинающемуся с позиции 4 внутри ${ displaystyle S}$, который является суффиксом ана $.

Соответствие суффиксным деревьям

Массивы суффиксов тесно связаны с суффиксные деревья:

• Массивы суффиксов можно построить, выполнив обход в глубину суффиксного дерева. Массив суффиксов соответствует листовым меткам, заданным в порядке их посещения во время обхода, если ребра посещаются в лексикографическом порядке их первого символа.
• Суффиксное дерево можно построить за линейное время, используя комбинацию суффиксного массива и LCP массив. Описание алгоритма см. В соответствующий раздел в LCP массив статья.

Было показано, что каждый алгоритм дерева суффиксов может быть систематически заменен алгоритмом, который использует массив суффиксов, расширенный дополнительной информацией (например, LCP массив ) и решает ту же проблему при той же временной сложности.^[4]Преимущества суффиксных массивов над суффиксными деревьями включают улучшенные требования к пространству, более простые алгоритмы построения линейного времени (например, по сравнению с Алгоритм Укконена ) и улучшенная локальность кеша.^[5]

Эффективность использования пространства

Массивы суффиксов были введены Манбер и Майерс (1990) чтобы улучшить требования к пространству суффиксные деревья: Хранилище суффиксных массивов ${ displaystyle n}$ целые числа. Предполагая, что целое число требует ${ displaystyle 4}$ байтов, массив суффиксов требует ${ displaystyle 4n}$ всего байтов. Это значительно меньше, чем ${ displaystyle 20n}$ байты, необходимые для тщательной реализации дерева суффиксов.^[6]

Однако в некоторых приложениях требования к пространству для массивов суффиксов могут быть чрезмерно высокими. При анализе в битах массив суффиксов требует ${ Displaystyle { mathcal {O}} (п журнал п)}$ пробел, тогда как исходный текст поверх алфавита размера ${ displaystyle sigma}$ требуется только ${ Displaystyle { mathcal {O}} (п журнал сигма)}$ бит. Для генома человека с ${ displaystyle sigma = 4}$ и ${ Displaystyle п = 3,4 раз 10 ^ {9}}$ поэтому массив суффиксов будет занимать примерно в 16 раз больше памяти, чем сам геном.

Такие несоответствия мотивировали тенденцию к сжатые массивы суффиксов и BWT сжатые полнотекстовые индексы, такие как FM-индекс. Эти структуры данных требуют места в пределах размера текста или даже меньше.

Алгоритмы построения

Суффиксное дерево может быть построено в ${ Displaystyle { mathcal {O}} (п)}$ и может быть преобразован в массив суффиксов путем обхода дерева в глубину также в ${ Displaystyle { mathcal {O}} (п)}$, поэтому существуют алгоритмы, которые могут построить массив суффиксов в ${ Displaystyle { mathcal {O}} (п)}$.

Наивный подход к построению массива суффиксов - использовать алгоритм сортировки на основе сравнения. Эти алгоритмы требуют ${ Displaystyle { mathcal {O}} (п журнал п)}$ сравнения суффиксов, но сравнение суффиксов выполняется в ${ Displaystyle { mathcal {O}} (п)}$ время, поэтому общее время выполнения этого подхода ${ Displaystyle { mathcal {O}} (п ^ {2} журнал п)}$.

Более продвинутые алгоритмы используют тот факт, что сортируемые суффиксы не являются произвольными строками, а связаны друг с другом. Эти алгоритмы стремятся достичь следующих целей:^[7]

• минимальная асимптотическая сложность ${ Displaystyle Theta (п)}$
• легкий в пространстве, что означает небольшую рабочую память или ее отсутствие рядом с текстом и сам массив суффиксов
• быстро на практике

Одним из первых алгоритмов для достижения всех целей является алгоритм SA-IS. Нонг, Чжан и Чан (2009). Алгоритм также довольно прост (<100 LOC ) и может быть расширен для одновременного построения LCP массив.^[8] Алгоритм SA-IS - один из самых быстрых известных алгоритмов построения массива суффиксов. Осторожный реализация Юта Мори превосходит большинство других линейных или суперлинейных подходов к построению.

Помимо требований по времени и пространству, алгоритмы построения суффиксных массивов также различаются поддерживаемыми алфавит: постоянные алфавиты где размер алфавита ограничен константой, целочисленные алфавиты где символы - это целые числа в диапазоне, зависящем от ${ displaystyle n}$ и общие алфавиты где разрешены только сравнения символов.^[9]

Большинство алгоритмов построения суффиксных массивов основаны на одном из следующих подходов:^[7]

• Удвоение префикса алгоритмы основаны на стратегии Карп, Миллер и Розенберг (1972). Идея состоит в том, чтобы найти префиксы, учитывающие лексикографический порядок суффиксов. Оценка длины префикса удваивается на каждой итерации алгоритма до тех пор, пока префикс не станет уникальным и не обеспечит ранг соответствующего суффикса.
• Рекурсивный алгоритмы следуют подходу алгоритма построения суффиксного дерева Фарач (1997) для рекурсивной сортировки подмножества суффиксов. Это подмножество затем используется для вывода массива суффиксов из оставшихся суффиксов. Затем оба этих массива суффиксов объединяются для вычисления окончательного массива суффиксов.
• Вынужденное копирование Алгоритмы похожи на рекурсивные алгоритмы в том смысле, что они используют уже отсортированное подмножество для быстрой сортировки оставшихся суффиксов. Разница в том, что эти алгоритмы предпочитают итерацию рекурсии для сортировки выбранного подмножества суффиксов. Обзор этой разнообразной группы алгоритмов был составлен Пуглиси, Смит и Терпин (2007).

Хорошо известным рекурсивным алгоритмом для целочисленных алфавитов является DC3 / перекос алгоритм Кярккяйнен и Сандерс (2003). Он работает в линейном времени и успешно используется в качестве основы для параллельного^[10] и внешняя память^[11] алгоритмы построения суффиксных массивов.

Недавние работы Salson et al. (2010) предлагает алгоритм для обновления массива суффиксов отредактированного текста вместо восстановления нового массива суффиксов с нуля. Даже если теоретическая временная сложность наихудшего случая равна ${ Displaystyle { mathcal {O}} (п журнал п)}$, похоже, он хорошо работает на практике: экспериментальные результаты авторов показали, что их реализация динамических массивов суффиксов, как правило, более эффективна, чем перестроение, если рассматривать возможность вставки разумного количества букв в исходный текст.

В практике Открытый исходный код work, обычно используемой процедурой для построения массива суффиксов была qsufsort, основанная на алгоритме Ларссона-Садакане 1999 года.^[12] Эта процедура была заменена DivSufSort Юты Мори, «самым быстрым из известных алгоритмов сортировки суффиксов в основной памяти» по состоянию на 2017 год. Его также можно изменить для вычисления массива LCP. Он использует индуцированное копирование в сочетании с Ито-Танака.^[13]

Приложения

Массив суффиксов строки может использоваться как показатель чтобы быстро найти каждое вхождение шаблона подстроки ${ displaystyle P}$ внутри строки ${ displaystyle S}$. Поиск каждого вхождения шаблона эквивалентен поиску каждого суффикса, который начинается с подстроки. Благодаря лексикографическому упорядочению эти суффиксы будут сгруппированы вместе в массиве суффиксов, и их можно будет эффективно найти с помощью двух бинарный поиск. Первый поиск определяет начальную позицию интервала, а второй определяет конечную позицию:^{[нужна цитата ]}

п = len(S)def поиск(п: ул) -> Кортеж[int, int]:    """    Возвращает индексы (s, r) такие, что интервал A [s: r] (включая конец    index) представляет все суффиксы S, начинающиеся с шаблона P.    """    # Найти начальную позицию интервала    л = 0  # в Python массивы индексируются начиная с 0    р = п    в то время как л < р:        середина = (л + р) // 2  # округление деления до ближайшего целого числа        # суффиксAt (A [i]) - i-й наименьший суффикс        если п > суффикс(А[середина]):            л = середина + 1        еще:            р = середина    s = л        # Найти конечную позицию интервала    р = п    в то время как л < р:        середина = (л + р) // 2        если суффикс(А[середина]).начинается с(п):            л = середина + 1        еще:            р = середина    вернуть (s, р)

Поиск шаблона подстроки ${ displaystyle P}$ длины ${ displaystyle m}$ в строке ${ displaystyle S}$ длины ${ displaystyle n}$ берет ${ Displaystyle { mathcal {O}} (м журнал п)}$ время, учитывая, что для сравнения одного суффикса необходимо ${ displaystyle m}$ символы. Манбер и Майерс (1990) опишите, как эту оценку можно улучшить до ${ Displaystyle { mathcal {O}} (м + журнал п)}$ время используя LCP Информация. Идея состоит в том, что сравнение шаблонов не требует повторного сравнения определенных символов, когда уже известно, что они являются частью самого длинного общего префикса шаблона и текущего интервала поиска. Абуэльода, Курц и Охлебуш (2004) Ошибка harvtxt: несколько целей (2 ×): CITEREFAbouelhodaKurtzOhlebusch2004 (Помогите) улучшить границу еще больше и добиться времени поиска ${ Displaystyle { mathcal {O}} (м)}$ как известно из суффиксные деревья.

Алгоритмы суффиксной сортировки могут использоваться для вычисления Преобразование Барроуза – Уиллера (BWT). В BWT требует сортировки всех циклических перестановок строки. Если эта строка заканчивается специальным символом конца строки, который лексикографически меньше, чем все остальные символы (например, $), то порядок сортировки с поворотом BWT матрица соответствует порядку суффиксов в массиве суффиксов. В BWT следовательно, можно вычислить за линейное время, сначала построив массив суффиксов текста, а затем выведя BWT нить: ${ Displaystyle BWT [я] = S [A [я] -1]}$.

Массивы суффиксов также можно использовать для поиска подстрок в машинный перевод на основе примеров, требуя гораздо меньшего объема памяти, чем полный таблица фраз как используется в Статистический машинный перевод.

Многие дополнительные приложения массива суффиксов требуют LCP массив. Некоторые из них подробно описаны в раздел приложения последнего.

Примечания

использованная литература

• Манбер, Уди; Майерс, Джин (1990). Массивы суффиксов: новый метод поиска строк в Интернете. Первый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. С. 319–327.CS1 maint: ref = harv (ссылка на сайт)
• Манбер, Уди; Майерс, Джин (1993). «Массивы суффиксов: новый метод поиска строк в Интернете». SIAM Журнал по вычислениям. 22 (5): 935–948. Дои:10.1137/0222058. S2CID  5074629.CS1 maint: ref = harv (ссылка на сайт)
• Ли, Чжизе; Ли, Цзянь; Хо, Хунвэй (2016). Оптимальная сортировка суффиксов на месте. Материалы 25-го Международного симпозиума по обработке строк и поиску информации (SPIRE). Конспект лекций по информатике. 11147. Springer. С. 268–284. arXiv:1610.08305. Дои:10.1007/978-3-030-00479-8_22. ISBN  978-3-030-00478-1.CS1 maint: ref = harv (ссылка на сайт)
• Абуэльода, Мохамед Ибрагим; Курц, Стефан; Охлебуш, Энно (2004). «Замена деревьев суффиксов расширенными массивами суффиксов». Журнал дискретных алгоритмов. 2 (1): 53–86. Дои:10.1016 / S1570-8667 (03) 00065-0.CS1 maint: ref = harv (ссылка на сайт)
• Gonnet, G.H; Baeza-Yates, R.A; Снайдер, Т. (1992). «Новые индексы для текста: деревья PAT и массивы PAT». Поиск информации: структуры данных и алгоритмы.CS1 maint: ref = harv (ссылка на сайт)
• Курц, S (1999). «Уменьшение занимаемой площади для суффиксных деревьев». Программное обеспечение - практика и опыт. 29 (13): 1149–1171. Дои:10.1002 / (SICI) 1097-024X (199911) 29:13 <1149 :: AID-SPE274> 3.0.CO; 2-O. HDL:10338.dmlcz / 135448.CS1 maint: ref = harv (ссылка на сайт)
• Абуэльода, Мохамед Ибрагим; Курц, Стефан; Охлебуш, Энно (2002). Расширенный массив суффиксов и его приложения для анализа генома. Алгоритмы в биоинформатике. Конспект лекций по информатике. 2452. п. 449. Дои:10.1007/3-540-45784-4_35. ISBN  978-3-540-44211-0.CS1 maint: ref = harv (ссылка на сайт)
• Puglisi, Simon J .; Smyth, W. F .; Терпин, Эндрю Х. (2007). «Таксономия алгоритмов построения суффиксных массивов». Опросы ACM Computing. 39 (2): 4. Дои:10.1145/1242471.1242472. S2CID  2653529.CS1 maint: ref = harv (ссылка на сайт)
• Нонг, Ге; Чжан, Сен; Чан, Вай Хун (2009). Построение линейного массива суффиксов с помощью почти чистой индуцированной сортировки. Конференция по сжатию данных 2009 г. п. 193. Дои:10.1109 / DCC.2009.42. ISBN  978-0-7695-3592-0.CS1 maint: ref = harv (ссылка на сайт)
• Фишер, Йоханнес (2011). Индукция LCP-Array. Алгоритмы и структуры данных. Конспект лекций по информатике. 6844. п. 374. arXiv:1101.3448. Дои:10.1007/978-3-642-22300-6_32. ISBN  978-3-642-22299-3.CS1 maint: ref = harv (ссылка на сайт)
• Salson, M .; Lecroq, T .; Léonard, M .; Мушар, Л. (2010). «Динамические расширенные массивы суффиксов». Журнал дискретных алгоритмов. 8 (2): 241. Дои:10.1016 / j.jda.2009.02.007.CS1 maint: ref = harv (ссылка на сайт)
• Буркхард, Стефан; Кярккяйнен, Юха (2003). Быстрое легкое построение и проверка массива суффиксов. Комбинаторное сопоставление с образцом. Конспект лекций по информатике. 2676. п. 55. Дои:10.1007/3-540-44888-8_5. ISBN  978-3-540-40311-1.CS1 maint: ref = harv (ссылка на сайт)
• Карп, Ричард М .; Миллер, Раймонд Э .; Розенберг, Арнольд Л. (1972). Быстрая идентификация повторяющихся шаблонов в строках, деревьях и массивах. Материалы четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72. п. 125. Дои:10.1145/800152.804905.CS1 maint: ref = harv (ссылка на сайт)
• Фарач, М. (1997). Оптимальное построение суффиксного дерева с большими алфавитами. Труды 38-го ежегодного симпозиума по основам информатики. п. 137. Дои:10.1109 / SFCS.1997.646102. ISBN  0-8186-8197-7.CS1 maint: ref = harv (ссылка на сайт)
• Кярккяйнен, Юха; Сандерс, Питер (2003). Простое линейное построение массива рабочих суффиксов. Автоматы, языки и программирование. Конспект лекций по информатике. 2719. п. 943. Дои:10.1007/3-540-45061-0_73. ISBN  978-3-540-40493-4.CS1 maint: ref = harv (ссылка на сайт)
• Дементьев, Роман; Кярккяйнен, Юха; Менерт, Йенс; Сандерс, Питер (2008). «Лучшее построение суффиксного массива внешней памяти». Журнал экспериментальной алгоритмики. 12: 1–24. Дои:10.1145/1227161.1402296. S2CID  12296500.CS1 maint: ref = harv (ссылка на сайт)
• Кулла, Фабиан; Сандерс, Питер (2007). «Построение масштабируемого параллельного массива суффиксов». Параллельные вычисления. 33 (9): 605. Дои:10.1016 / j.parco.2007.06.004.CS1 maint: ref = harv (ссылка на сайт)

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

• Массив суффиксов в Java
• Модуль сортировки суффиксов для BWT в коде C
• Реализация массива суффиксов в Ruby
• Библиотека и инструменты массива суффиксов
• Проект, содержащий различные реализации c / c ++ массивов суффиксов с унифицированным интерфейсом
• Быстрая, легкая и надежная библиотека C API для создания массива суффиксов
• Реализация массива суффиксов в Python
• Реализация линейного массива суффиксов времени в C с использованием дерева суффиксов