Substring index: Difference between revisions

Revision as of 11:00, 2 December 2024

Revision as of 01:39, 12 December 2024

Line 3:

In [[computer science]], a '''substring index''' is a [[data structure]] which gives [[substring]] search in a text or text collection in [[sublinear]] time. If you have a document <math>S</math> of length <math>n</math>, or a set of documents <math>D=\{S^1,S^2, \dots, S^d\}</math> of total length <math>n</math>, you can locate all occurrences of a pattern <math>P</math> in <math>o(n)</math> time. (See [[Big O notation|Big ''O'' notation]].)

The phrase '''full-text index''' is also often used for an index of all substrings of a text.<ref>{{Cite conference |author1=Pei, J. |author2=Wu, W. C.-H. |author3=Yeh, M.-Y. |year=2013 |title=On shortest unique substring queries |conference=2013 IEEE 29th International Conference on Data Engineering (ICDE) |___location=Brisbane, QLD, Australia |publisher=IEEE |pages=937–948 |doi=10.1109/ICDE.2013.6544887}}</ref> But this is ambiguous, as it is also used for regular word indexes such as [[inverted file]]s and [[document retrieval]]. See [[full text search]].

Substring indexes include: