В информатике , индекс подстроки представляет собой структуру данных , которая дает подстроку поиска в коллекции текста или текста в сублинейное время. Если у вас есть документ длины , или комплект документов общей длины , вы можете найти все вхождения шаблона в время. (См. Обозначение Big O. )
Полнотекстовый индекс фразы также часто используется для индекса всех подстрок текста. Но это неоднозначно, так как он также используется для обычных указателей слов, таких как инвертированные файлы и поиск документов . См. Полнотекстовый поиск .
Индексы подстроки включают:
- Суффиксное дерево
- Массив суффиксов
- Индекс N-граммов, перевернутый файл для всех N-граммов текста
- Сжатый массив суффиксов [1]
- FM-индекс
- LZ-индекс
Рекомендации
- ^ Р. Гросси и Дж. С. Виттер, Сжатые массивы суффиксов и деревья суффиксов, с приложениями для индексирования текста и сопоставления строк , SIAM Journal on Computing, 35 (2), 2005, 378-407.