pdf : pour impression

Recherche textuelle #

Pourquoi parler de recherche textuelle ? #

Qu’est-ce qu’un texte ? #

Quelques exemples :

101010101010001
ATCGTTTATGCGAA
un texte
la concaténation de toutes les pages web

Définition #

Un texte est une suite finie de symboles.

Recherche dans un texte connu à l’avance (livres, sites…) #

On dispose alors généralement d’un index

. index

L’index peut-être vu comme un dictionnaire : on repère la clé qui nous intéresse et sa valeur nous indique la position du motif.

L’usage est alors simpliste et peu coûteux, tout le travail a été réalisé en amont.

Recherche des occurences d’un motif dans un texte. #

L’objectif est de retourner les positions du motif (exemple ‘Robert’) dans le texte : ‘Bonjour Robert, ça va Robert ? Robert Robert !’

L’algorithme doit retourner : [8, 22, 30, 37]

Recherche naïve d’un motif dans un texte #

Puis-je trouver le mot P = atatac ? dans T = a t a g a c a c a a t a t a c t g a c a c g a t

Tester la présence de P à chaque position de T

Au pire : $|T|\times |P|$ comparaisons.

Algorithme de Boyer-Moore-Horspool #

Dernière occurrence #

On commence par créer un tableau associant chaque caractère possible à la longueur du motif.

Ensuite, pour chaque caractère d’indice i du motif, la distance est donnée par taille - 1 - i

ce qui donne :

pseudo code : dernière occurrence #

dernière occurrence (motif)
  m = longueur du motif
  créer un dictionnaire associant chaque lettre à m
  pour i allant de 0 à m-2,
      dictionnaire [ motif[i] ] = m - 1 - i
  fin du pour
  retourner le dictionnaire

Boyer-Moore-Horspool #

on commence avec j = 0
on itère jusqu’à ce que j = taille du texte - taille du motif

on parcourt le motif à partir de la fin, donc i = taille du motif.

on recule sur i jusqu’à arriver à 0 ou jusqu’à ce que les caractères ne se correspondent plus.
- si i = -1 alors
  
  le motif commence en j et on augmente j de 1
- sinon
  
  on augmente j de la distance correspondant à cette position différente dans le texte.

Pseudo-code Boyer-Moore-Horspool #

Algorithme Boyer-Moore-Horspool(x, t):
  '''
  x : motif, t : texte, m : longueur motif, n : celle du texte
  d : tableau des dernières occurrences du motif
  '''
  tant que j <= n - m,
    i = m - 1
    tant que i >= 0 et t[j + i] = x[i]:
      i = i-1
    fin tant que
    si i = -1 alors
      j est une occurrence de x
      j = j + 1
    sinon
      j = j + d[ t[j + i] ]
    fin du si
  fin du tant que

Compléments #

Cet algorithme comporte deux des trois idées principales de la version complète, dîtes de Boyer-Moore :

comparer en parcourant le motif par la droite,
utiliser un tableau de distances pré-calculé sur les motifs,
utiliser un autre tableau, dît du bon préfixe.

Resume