Canal-U

Mon compte
Inria

3.7. Index and suffix trees


Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/3_7_index_and_suffix_trees.35101?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Auteur(s) :
RECHENMANN Francois

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

3.7. Index and suffix trees

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.

  •  
    Label UNT : UNIT
  •  
    Date de réalisation : 5 Février 2015
    Lieu de réalisation : Grenoble
    Durée du programme : 8 min
    Classification Dewey : biologie application informatique
  •  
    Catégorie : Vidéocours
    Niveau : 1er cycle, 2ieme cycle
    Disciplines : Biologie cellulaire, Informatique, Informatique, Mathématiques et informatique
    Collections : 3. Gene prediction
    ficheLom : Voir la fiche LOM
  •  
    Auteur(s) : RECHENMANN Francois
  •  
    Langue : Anglais
    Mots-clés : DNA, Genome, algorithm, cell, bioinformatics
    Conditions d’utilisation / Copyright : Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
 

commentaires


Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)
 

Dans la même collection

FMSH
 
Facebook Twitter Google+
Mon Compte