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

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

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

• Суфіксний автомат
• Суфіксне дерево
• Суфіксний масив
• Індекс N-грам
• Шаблон:Не перекладено

Джерела

• R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching Шаблон:Webarchive, SIAM Journal on Computing, 35(2), 2005, 378-407. Шаблон:Ref-en