Content deleted Content added
No edit summary |
m L "signature file" to document retrieval |
||
Line 1:
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. (<math>o(n)</math> means less than <math>O(n)</math>. See [[Big O notation]].)
The phrase '''full-text index''' is also often used for an index of all substrings of a text. But is ambiguous, as it is also used for regular word indexes such as [[inverted file]]s and [[
Substring indexes include:
| |||