Описание тега suffix-array

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

Формальные определения

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

Суффикс: дана строка T длины n, суффикс T определяется как подстрока, которая начинается в любой позиции T и заканчивается в позиции n (конец T).

Пример: Пусть T:=abc, тогда abc,bc а также c суффиксы T, но a а также ab не.

Замечание: Любая строка T длины n имеет ровно n различных суффиксов (столько, сколько в ней символов), потому что любой символ является началом ровно одного суффикса.

Массив суффиксов: учитывая строку T длины n и линейный порядок в алфавите, массив суффиксов T представляет собой лексикографически отсортированный список всех суффиксов T.

Пример: Пусть T:=abcabx и предположим "естественный" алфавитный порядок, т.е. a < b < c < d... < x < y < z. Тогда суффиксный массив T выглядит следующим образом.

abcabx
abx
bcabx
bx
cabx
x

Реализация

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

abcabx 012345

Пример: Учитывая T, как определено выше, и предполагаем, что его позиции пронумерованы от 0 до 5, массив суффиксов представлен в виде списка[0,3,1,4,2,5].

В suffix-array тег

Многие вопросы отмечены suffix-array относятся к одной из тем ниже.

• Как эффективно создавать массивы суффиксов
• Как их эффективно хранить и, возможно, сжимать
• Как использовать их для различных целей, таких как полнотекстовый поиск, обнаружение закономерностей в строках и сжатие текста
• Как они используются в различных областях применения, в частности в биоинформатике, генетике и обработке естественного языка
• Какие существующие и / или готовые к использованию реализации любого из вышеперечисленных известны
• Наихудший случай, средний случай и эмпирические сравнения требований к пространству и времени для существующих алгоритмов и реализации