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

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