Индекс подстрок
Индекс подстрок — это структура данных, позволяющая производить поиск подстроки в тексте или наборе текстов за сублинейное время. Это значит, что имея документ длины или набор документов общей длины , вы можете найти все вхождения образца за (См. O-нотация). Словосочетание полнотекстовый индекс также иногда используется для обозначения индекса всех подстрок текста, но является неоднозначным, так как также используется для обозначения обычных индексов слов, например, инвертированного индекса.
Некоторые индексы подстрок:
- Суффиксный автомат
- Суффиксное дерево
- Суффиксный массив
- Индекс N-грамм
- FM-индекс
- LZ-индекс