Індекс підрядків

Індекс підрядків — структура даних, що дозволяє здійснювати пошук підрядка в тексті або наборі текстів за сублінійний час. Це означає, що маючи документ $S$ довжини $n$ або набір документів $D=\{S^{1},S^{2},\dots ,S^{d}\}$ загальної довжини $n$, ви можете знайти всі входження зразка $P$ за $o(n)$ (Див. O-нотація). Словосполучення повнотекстовий індекс також іноді використовується для позначення індексу всіх підрядків тексту, але є неоднозначним, так як також використовується для позначення звичайних індексів слів, наприклад, інвертованого індексу.

Деякі індекси підрядків:

• Суфіксний автомат
• Суфіксне дерево
• Суфіксний масив
• Індекс N-грам
• FM-індекс

Джерела

• R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching [Архівовано 19 листопада 2008 у Wayback Machine.], SIAM Journal on Computing, 35(2), 2005, 378-407. (англ.)