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.

PropertyValue
dbpprop:abstract
  • 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</math> means less than <math>O</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 files and signature files. See full text search. Substring indexes include: Suffix tree Suffix array N-gram index, an inverted file for all N-grams of the text Compressed suffix array FM-index LZ-index
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • 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.
rdfs:label
  • Substring index
owl:sameAs
skos:subject
foaf:page
is owl:sameAs of