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

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

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

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

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

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