Индекс подстроки

В информатике индекс подстроки — это структура данных , которая обеспечивает поиск подстроки в тексте или текстовой коллекции в сублинейном времени. Если у вас есть документ $S$ длины $n$или комплект документов $D=\{S^{1},S^{2},\dots ,S^{d}\}$ общей длины $n$, вы можете найти все вхождения шаблона $P$ в $o(n)$ время. (См. Big O. обозначение )

Фраза « полнотекстовый индекс» также часто используется для индекса всех подстрок текста. Но это неоднозначно, поскольку оно также используется для обычных индексов слов, таких как инвертированные файлы и поиск документов . Смотрите полнотекстовый поиск .

Индексы подстрок включают в себя:

• Суффиксное дерево
• Суффиксный массив
• Индекс N-грамм, инвертированный файл для всех N-грамм текста.
• Сжатый массив суффиксов
• FM-индекс
• Индекс ЛЗ