Substring index: Difference between revisions

Revision as of 11:14, 10 November 2005

Revision as of 01:26, 6 February 2006

Line 1:

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 occurencesoccurrences 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 [[signature file]]s. See [[full text search]].