Substring index: Difference between revisions

Revision as of 08:34, 12 December 2024

Latest revision as of 08:19, 10 January 2025

(6 intermediate revisions by one other user not shown)

Line 13:

| year = 2012}}</ref>

The phrase '''full-text index''' is often used for substring indexes. 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]].

These data structures typically treat their text and pattern as [[string (computer science)|strings]] over a fixed alphabet, and search for locations where the pattern occurs as a substring of the text. The symbols of the alphabet may be characters (for instance in [[Unicode]]) but in practical applications for [[text retrieval]] it may be preferable to treat the ([[Stemming|stemmed]]) words of a document as the symbols of its alphabet, because doing this reduces the lengths of both the text and pattern as measured in letters of their alphabet.<ref>{{citation

==General considerations==

These data structures typically treat their text and pattern as [[string (computer science)|strings]] over a fixed alphabet, and search for locations where the pattern occurs as a substring of the text. The symbols of the alphabet may be characters (for instance in [[Unicode]]) but in practical applications for [[text retrieval]] it may be preferable to treat the ([[Stemming|stemmed]]) words of a document as the symbols of its alphabet, because doing this reduces the lengths of both the text and pattern as measured in lettersnumbers of their alphabetsymbols.<ref>{{citation

| last = Risvik | first = Knut Magne

| editor-last = Farach-Colton | editor-first = Martin | editor-link = Martin Farach-Colton

Line 23 ⟶ 26:

| title = Combinatorial Pattern Matching, 9th Annual Symposium, CPM 98, Piscataway, New Jersey, USA, July 20–22, 1998, Proceedings

| volume = 1448

| year = 1998}}</ref>| isbn = 978-3-540-64739-3

}}</ref>

The phrase '''full-text index''' is often used for substring indexes. 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]].

==Examples==

Specific data structures that can be used as substring indexes include:

* The [[suffix tree]], a [[radix tree]] of the suffixes of the string, allowing substring search to be performed symbol-by-symbol<ref name=bst/><ref name=gv/>

* The [[suffix automaton]], the minimal [[deterministic finite automaton]] that recognizes substrings of a given text, closely related to the suffix tree and constructable by variants of the same algorithms.<ref>{{citation

* The [[suffix array]], a sorted array of the starting positions of suffixes of the string, allowing substring search to be performed by [[binary search]]<ref name=bst/><ref name=gv/>

| last1 = Blumer | first1 = Anselm

| last2 = Blumer | first2 = J.

| last3 = Ehrenfeucht | first3 = Andrzej | author3-link = Andrzej Ehrenfeucht

| last4 = Haussler | first4 = David | author4-link = David Haussler

| last5 = McConnell | first5 = Ross M.

| editor-last = Paredaens | editor-first = Jan

| contribution = Building the minimal DFA for the set of all subwords of a word on-line in linear time

| doi = 10.1007/3-540-13345-3_9

| pages = 109–118

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Automata, Languages and Programming, 11th Colloquium, Antwerp, Belgium, July 16–20, 1984, Proceedings

| volume = 172

| year = 1984| isbn = 978-3-540-13345-2

}}</ref>

* The [[suffix array]], a sorted array of the starting positions of suffixes of the string, allowing substring search to be performed by [[binary search]]<ref name=bst/><ref name=gv/> Augmenting a suffix array with an [[LCP array]] of the lengths of common prefixes of consecutive suffixes allows the search to be performed symbol-by-symbol, matching the search time of the suffix tree.<ref>{{citation

| last1 = Manber | first1 = Udi | author1-link = Udi Manber

| last2 = Myers | first2 = Gene | author2-link = Eugene Myers

| doi = 10.1137/0222058

| issue = 5

| journal = [[SIAM Journal on Computing]]

| mr = 1237156

| pages = 935–948

| title = Suffix arrays: a new method for on-line string searches

| volume = 22

| year = 1993}}</ref>

* The [[compressed suffix array]], a data structure that combines [[data compression]] with the suffix array, allowing the structure to be stored in space sublinear in the text length<ref name=bst/><ref name=gv>{{citation

| last1 = Grossi | first1 = Roberto

Line 41 ⟶ 70:

| url = https://www.di.unipi.it/~grossi/PAPERS/sicomp05.pdf

| volume = 35

| year = 2005}}<| hdl = 1808/ref>18962

}}</ref>

* The [[FM-index]], another compressed substring index based on the [[Burrows–Wheeler transform]] and closely related to the suffix array<ref>{{citation

| last1 = Ferragina | first1 = Paolo

Line 47 ⟶ 77:

| doi = 10.1145/1082036.1082039

| issue = 4

| journal = [[Journal of the ACM]]

| mr = 2164632

| pages = 552–581

Line 57 ⟶ 87:

{{reflist}}

{{Strings|state=collapsed}}

[[Category:Algorithms on strings]]

[[Category:String data structures]]