Ressource pédagogique : 3.7. Index and suffix trees

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

We have seen with the Boyer-Moore algorithm how we can increase the efficiency of spin searching through the pre-processing of the pattern to be searched. Now we will see that an alternative way of improving the performance is to pre-process the text itself,the searchable text itself and we will, for that, study two methods, the construction of indexes of fixed length words and the algorithm which uses prefix trees. An index of fixed lengthword, what does it mean? Imagine you have a text, a searchable text, that is a text in which you want to search a pattern,here is quite a short text, the sequence is 14 correctors. We will build an index of allthe three letters which appear, a succession of three letters,which appear in the text. Here is the index. Howdoes it work now? Imagine you want to search for occurrences of this triplet, you look up in your index if you can find this triplet. Here and what do you read? You read that this triplet occurred in position Six and Ten. You do not have to make anycomparison on the text because the text has been processed, thisindex table has been built so that immediately from the triplets to be searched for, we can deduce the two positions of interest.

"Domaine(s)" et indice(s) Dewey

• biologie application informatique (570.285)

Thème(s)