Описание тега 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
относятся к одной из тем ниже.
- Как эффективно создавать массивы суффиксов
- Как их эффективно хранить и, возможно, сжимать
- Как использовать их для различных целей, таких как полнотекстовый поиск, обнаружение закономерностей в строках и сжатие текста
- Как они используются в различных областях применения, в частности в биоинформатике, генетике и обработке естественного языка
- Какие существующие и / или готовые к использованию реализации любого из вышеперечисленных известны
- Наихудший случай, средний случай и эмпирические сравнения требований к пространству и времени для существующих алгоритмов и реализации