Индекс подстроки - Substring index

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

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

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

• Суффиксное дерево
• Массив суффиксов
• Индекс N-грамма, инвертированный файл для всех N-граммы текста
• Сжатый массив суффиксов^[1]
• FM-индекс
• LZ-индекс

Рекомендации

1. Р. Гросси и Дж. С. Виттер, Сжатые массивы суффиксов и деревья суффиксов с приложениями для индексирования текста и сопоставления строк, Журнал SIAM по вычислениям, 35(2), 2005, 378-407.