Substring index

Substring index

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 S of length n, or a set of documents D={S^1,S^2, dots, S^d} of total length n, you can locate all occurrences of a pattern P in o(n) time. (o(n) means less than O(n). 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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • String searching algorithm — String searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. Let Σ be… …   Wikipedia

  • Comparison of programming languages (string functions) — String functions redirects here. For string functions in formal language theory, see String operations. Programming language comparisons General comparison Basic syntax Basic instructions Arrays …   Wikipedia

  • Ancient Macedonian language — For the unrelated modern Slavic language, see Macedonian language. language name=Ancient Macedonian region=Macedon ( extinct language ) extinct=absorbed by Attic Greek in the 4th century BC familycolor=Indo European fam2= possibly Greek… …   Wikipedia

  • ISO 13616 — ISO 13616:2003 est une norme internationale intitulée Banque et services financiers connexes Numéro de compte bancaire international (IBAN) élaborée par l Organisation internationale de normalisation (ISO) et le European Committee for Banking… …   Wikipédia en Français

  • Knuth–Morris–Pratt algorithm — The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a word W within a main text string S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to… …   Wikipedia

  • Suffix array — In computer science, a suffix array is an array giving the suffixes of a string in lexicographical order.DetailsConsider the string abracadabra , of length 11. It has eleven suffixes: abracadabra , bracadabra , racadabra , and so on down to a .… …   Wikipedia

  • Маточные рожки — ? Спорынья Спорынья на ржи Научная классификация Царство: Грибы Отдел: Аскомицеты Подотдел …   Википедия

  • Западные кыпчаки — Половецкая степь. Евразийские территории кыпчаков, конец XI начало XII вв. Карта Азии в XII веке, показывает половецкие земли и их соседей См. также статью: Кыпчаки Половцы (в европейских и византийских источниках  куманы, в восточных источниках  …   Википедия

  • Чебурашка и крокодил Гена (мультсериал) — Чебурашка. Кадр из мультфильма «Крокодил Гена» Чебурашка вымышленный зверёк с огромными ушами, большими глазами и коричневой шерстью, ходящий на задних лапах. Персонаж книг Эдуарда Успенского, экранизированных Романом Качановым. Известный сегодня …   Википедия

  • Чебуран-пати — Чебурашка. Кадр из мультфильма «Крокодил Гена» Чебурашка вымышленный зверёк с огромными ушами, большими глазами и коричневой шерстью, ходящий на задних лапах. Персонаж книг Эдуарда Успенского, экранизированных Романом Качановым. Известный сегодня …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”