Substring Index

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Substring index" – news · newspapers · books · scholar · JSTOR (December 2021) (Learn how and when to remove this template message)

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]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math], or a set of documents [math]\displaystyle{ D=\{S^1,S^2, \dots, S^d\} }[/math] of total length [math]\displaystyle{ n }[/math], you can locate all occurrences of a pattern [math]\displaystyle{ P }[/math] in [math]\displaystyle{ o(n) }[/math] time. (See Big O notation.)

The phrase full-text index is also often used for an index of all substrings of a text. But this is ambiguous, as it is also used for regular word indexes such as inverted files and document retrieval. 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^[1]
• FM-index
• LZ-index

References

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Substring index. Read more