Массив суффиксов

Массив суффиксов
Тип	Множество
Изобретенный	Манбер и Майерс (1990)
Сложность времени в большой нотации O
	В среднем	Худший случай
Космос	${\ Displaystyle {\ mathcal {O}} (п)}$	${\ Displaystyle {\ mathcal {O}} (п)}$
Строительство	${\ Displaystyle {\ mathcal {O}} (п)}$	${\ Displaystyle {\ mathcal {O}} (п)}$

В информатике , массив суффиксов представляет собой отсортированный массив всех суффиксов в виде строки . Это структура данных, используемая, среди прочего, в полнотекстовых индексах, алгоритмах сжатия данных и в области библиометрии .

Массивы суффиксов были введены Манбером и Майерсом (1990) как простая и эффективная альтернатива деревьям суффиксов . Они были независимо обнаружены Гастоном Гоннетом в 1987 году под названием PAT array ( Gonnet, Baeza-Yates & Snider 1992 ).

Ли, Ли и Хуо (2016) представили первый алгоритм построения массива суффиксов времени на месте, который является оптимальным как по времени, так и по пространству, где на месте означает, что алгоритму требуется только дополнительное пространство за пределами входной строки и массива выходных суффиксов.${\ Displaystyle {\ mathcal {O}} (п)}$${\ Displaystyle {\ mathcal {O}} (1)}$

Расширенные массивы суффиксов (ESA) - это массивы суффиксов с дополнительными таблицами, которые воспроизводят полную функциональность деревьев суффиксов, сохраняя при этом то же время и сложность памяти. ^[1] Массив суффиксов для подмножества всех суффиксов строки называется разреженным массивом суффиксов . ^[2] Несколько вероятностных алгоритмов были разработаны для минимизации использования дополнительной памяти, включая алгоритм оптимального времени и памяти. ^[3]

Определение [ править ]

Позвольте быть -строкой и обозначить подстроку в диапазоне от до .${\ Displaystyle S = S [1] S [2] ... S [n]}$${\ textstyle n}$${\ Displaystyle S [я, j]}$${\ displaystyle S}$${\ displaystyle i}$${\ displaystyle j}$

Суффикс массив из теперь определяются как массив целых чисел , обеспечивающих исходные позиции суффиксов из в лексикографическом порядке . Это означает, что запись содержит начальную позицию -го наименьшего суффикса и , следовательно , для всех : .${\ displaystyle A}$${\ displaystyle S}$${\ displaystyle S}$${\ Displaystyle А [я]}$${\ displaystyle i}$${\ displaystyle S}$${\ Displaystyle 1 <я \ Leq п}$${\ Displaystyle S [A [я-1], n] <S [A [i], n]}$

Каждый суффикс из шоу в точности один раз. Суффиксы - это простые строки. Эти строки сортируются (как в бумажном словаре) перед сохранением их начальных позиций (целочисленных индексов) в .${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle A}$

Пример [ править ]

Считайте, что текст = будет проиндексирован:${\ displaystyle S}$banana$

я	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					$

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

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

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

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

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

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

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

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

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

Алгоритмы построения [ править ]

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

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

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

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

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

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

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

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

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

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

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

Приложения [ править ]

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

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

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

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

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

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

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с массивом суффиксов .

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