Algorithmique 2 : Chapitre 1 : Algorithmique du texte Introduction

Sommaire général

  • Chapitre 1 : Algorithmique du texte
  • Chapitre 2 : Calcul formel (entier) ⟶ liens avec crypto

  • Chapitre 3 : Codage

  • Chapitre 4 : Algorithmes d’approximation
  • Chapitre 5 : Algorithmes probabilistes
  • Chapitre 6 : Programmation linéaire

Chapitre 1 : Algorithmique du texte

  • $P$ : motif de longueur $m$
$P[i]$ :

$i$-ème caractère

$P[i,j]$ :

sous-mot entre les indices $i$ et $j$ (vide si $i>j$)

  • $T$ : texte de longueur $n$

  • Problème : Recherche du motif dans le texte.

Conseil : faire des dessins

$T$ :

||$P[1]$|$P[2]$|$P[1]$|||$P[1]$|$P[2]$|$P[1]$|$P[2]$| |-|-|-|-|-|-|-|-|-|-|

M1

On calcule les $T[1,i]∈𝛴^\ast P$ ⟶ puis, on construit l’automate déterministe complet qui reconnaît le langage ⟶ puis, en $O(n)$ une fois l’automate construit.

M2

Algorithme naïf :

for i in range(n-m+1):
  j = 0
  while 0 < j <= len(P) :
    if T[i+j] == P[j]:
      j+=1
    else:
      j = 0
  if j>m:
    print(i+1)

En $O(m(n-m))$

$𝛴$ alphabet.

$𝛴^\ast P$ expression rationnelle.

⟶ on construit l’automate déterministe complet qui reconnaît $P$.

digraph {
  rankdir = LR;
  splines=line;
  subgraph cluster_0 {
    label="A";
    q_0; q_1; q_2; ⋯; q_f;
  }


  q_0 -> q_1[label="a"];
  q_0 -> q_2[label="b"];
  q_1 -> ⋯;
  q_2 -> ⋯;
  ⋯ -> q_f;

}
\[𝛿(q_0, T[1,i])∈Finals ⟺ P \text{ est un suffixe de T[1,i]}\]

⟶ reconnaissance en $O(n)$, une fois la construction de l’automate faite

  • Problème : FA qui reconnaît une expression rationnelle est de taille polynomiale, mais quand on le déterminise ⟶ de taille exponentielle
\[x∈𝛴^\ast, 𝜎(x) = \max \lbrace k \mid \text{il existe un suffixe de } x \text{ préfixe de } P[1,k] \rbrace\]

$k= 𝜎(x)$

\[𝜎(xa) = 𝜎(x[n-k+1, n]a)\]

Dém :

  1. \(𝜎(xa) ≥ 𝜎(x[n-k+1, n]a)\) est immédiat.

2.

  • Cas 1 : si $𝜎(xa)=0$ : \(0 = 𝜎(xa) ≤ 𝜎(x[n-k+1, n]a)\)

  • Cas 2 : sinon si $𝜎(xa)>0$ :

    Par l’abs : supposons qu’il existe un préfixe de $P$ suffixe de $xa$ strictement plus grand que $x[n-k+1, n]a$ : impossible, car $x[n-k+1, n]$ est le plus grand préfixe de $P$ qui est suffixe de $x$

Ex :

$𝛴=\lbrace a,b,c \rbrace, ababaca$

\[𝛿(i,\underbrace{a}_{∈𝛴}) \\ 0≤i≤n\] 
for i in range(m+1):
  for a in 𝛴:
    j = min(i+1,m)
    while Suff(P[1:i]a) not in P[1:j]:
      j-=1
    𝛿(i,a)=j

Complexité en $O(m \vert 𝛴 \vert m m) = O(m^3 \vert 𝛴 \vert)$ pour construire cet objet de taille $m \vert 𝛴 \vert$

$𝜋(i) ≝ \max \lbrace j<i \mid P[1,j] \text{ suffixe de } P[1,i] \rbrace$

\[𝜋^\ast(i) ≝ \bigcup\limits_{k≥0} 𝜋^{(k)}(i)\]

On peut calculer $𝜋$ en $O(m)$ ⟶ précalcul de l’automate + algo en $O(m \vert 𝛴 \vert)$

MAIS : on aimerait en $O(m+n)$ ⟹ automate étendu

Automate étendu :

transition étiquetées par des formules logiques (ex : $a, \lnot a, b, \lnot b$, etc…), et une flèche :

  • vers la droite si on consomme le caractère (on avance dans l’automate)
  • vers le bas, si on ne consomme pas le caractère (on revient en arrière dans l’automate).

Construction en $O(m)$, borne sup sur le nombre de transitions au cours d’une exécution de l’algo : $2n$

⟹ Morris-Pratt en $O(m+n)$

KNUTH-Morris-Pratt : clôture transitive pour les suites d’arcs de la manière suivante :

  digraph {
    rankdir=LR;
    kr[label="k+r"];
    k -> ⋯[label="¬x, ↓"];
    ⋯ -> kr[label="¬x, ↓"];
  }

⇓

  digraph {
    rankdir=LR;
    kr[label="k+r"];
    k -> kr[label="¬x, ↓"];
  }

ET :

  digraph {
    rankdir=LR;
    kr[label="k+r"];
    kr[label="k+r+1"];
    k -> ⋯[label="¬x, ↓"];
    ⋯ -> kr[label="¬x, ↓"];
    kr -> kr1[label="¬x, →"];
  }

⇓

  digraph {
    rankdir=LR;
    kr1[label="k+r+1"];
    k -> kr1[label="¬x, →"];
  }

On calcule

$𝜋’(i) ≝ \max \lbrace j<i \mid P[1,j] \text{ suffixe de } P[1,i] \text{ ET } P[1,j+1]≠P[1,i+1] \rbrace$ à valeurs dans $⟦-1,m-1⟧$

à partir de $𝜋$ avec

\[\begin{cases} 𝜋'(0) = -1 \\ 𝜋'(i)=𝜋(i) \text{ si } P[1,𝜋(i)+1]≠P[1,i+1] \\ 𝜋'(i)=𝜋'(𝜋(i)) \text{ sinon} \end{cases}\]

Algorithme de Simon

Amplitude d’une transition retour de $i$ à $j≤i$ :

$i-j$

Toutes les transitions ont une amplitude unique

Comme les transitions sont à valeurs dans $⟦0,m-1⟧$ : il y a au plus $m$ transitions retour.

Automate de Simon :

  • on supprime les transitions allant vers $0$
  • la liste des transitions sortantes est triée par état d’arrivée décroissant

Pour toutes transitions distinctes $p⟶^a q$ (avec $q≤p$) et $p’⟶^{a’} q’$ (avec $q’≤p’$),

\[p-q ≠ p'-q'\]

Preuve : Par l’absurde supposons qu’elles aient la même amplitude.

  • Si $0<p=p’$, alors $q=q’$ (même amplitude) :

    nécessairement : $a≠a’$, mais c’est absurde, puisque

    \[a = P[q-1] = a'\]

  • Si $p’>p$ :

    faire un dessin : problème avec $a ≠ P[p+1]$ d’une part et $P[p+1] = a$ d’autre part.

Automate de Simon : se construit en $O(m)$ avec $𝜋’$ et le fait qu’il y a au plus $m$ transitions.

⟶ algo en $O(m+n)$

Comparaison Simon vs KMP

Simon va toujours plus vite que KMP (au sens large).

NB : on peut construire l’automate en $O(m)$ au lieu de $O(m \vert 𝛴 \vert)$ avec l’initialisation paresseuse de tableau (les valeurs par défaut étant les transitions vers $0$).

Algorithmes optimistes de Boyer-Moore

optimisation du déplacement pour qu’il soit le plus grand possible :

  • avec comparaison de droite à gauche

  • calcul d’un déplacement maximal $d$

de droite à gauche : mieux que de gauche à droite, car une comparaison pourra servir plusieurs fois (vs. de gauche à droite : les comparaisons faites ne servent plus à rien après).

⟶ algorithme sous-linéaire

$d$ : dernière occurrence de la lettre $x$ dans $P[1,m-1]$ ⟶ $dist = m - occurrence$

avec $occurrence(x) = 0$ si $x$ n’apparaît pas

Algo en $O(m+\vert 𝛴 \vert)$


for x∈𝛴:
  occ(x) = 0

for i in range(1,n):
  occ(P[i]) = i

Récapitulatif

→ KMP, Simon : se basent sur des automates :

  • en $O(m+n)$ en pire cas
  • dans le meilleur des cas : $𝛺(m+n)$

→ Boyer-Moore (amélioration de l’algo naïf)

  • $O(m(n-m))$ en pire cas
  • $𝛺(n/m)$ en meilleur cas : sous-linéaire

la subtilité : ajuster le motif au texte pour comparer de droite à gauche plutôt que de gauche à droite.

Idée générale : faire des comparaisons judicieuses de telle sorte que les informations acquises au cours de ces comparaison reservent par la suite.

NB : en pratique, ce sont plutôt ces algos qui sont implémentés

$d_1$ : Première heuristique de déplacement :

  • Si la dernière lettre (disons $a$) échoue : on déplace le motif jusqu’au dernier $a$ à droite

    \[d_1 = m - \text{position de la dernière position dans } P[1,m-1]\]
    • ⟶ on dresse une table indicée par l’alphabet des dernières occurrences
    • ex : $P=a^m, T=(a^{m-1}b)^{n/m}$

$d_2$

Petit déplacement

  • Calcul, pour toute position $i$ du motif, du plus grand “suffixe” (qui se termine en position $i$) qui peut être ajusté

Sinon :

Grand déplacement

  • Calculé à l’aide de $𝜋$

Petit déplacement ⟶ on passe au miroir, pour chercher le plus grand “préfixe” démarrant en chaque position (et qui coïncide avec un vrai préfixe).

Algo naïf :

Pref = [None, None]
for i in range(2,m+1):
  j = 0
  while i+j<= m and P[i+j]=P[1+j]:
    j+=1
  Pref[i]=j

En $𝛳(m^2)$ : ne peut-on pas avoir un algo linéaire ?

# x < y
Scan(x,y):
  z=0
  while y+z<=m and P[x+z]=P[y+z]:
    z+=1
  return z

Complexité en nombre de comparaisons de caractères, sauf qu’elles n’ont pas toutes le même poids : comparaisons positives (renvoient “vrai”) et comparaisons négatives (renvoient “faux”).

⟶ Plusieurs comparaisons positives, au plus une comparaison négative.

Principe :

  1. Calcul de la fonction Pref par indices croissants

  2. Maintenir un seul indice $s∈⟦1, i-1⟧$ qui maximise $\underbrace{j + Pref[j]}_{\text{premier indice où la comparaison est négative, à partir de} j}$ pour $j<i ∧ Pref[j]>0$ (= indice pour lequel on a pu faire le plus loin possible des comparaisons positives)

    Sinon, si cet indice n’existe pas (ensemble vide), $s=1, Pref[s] = 0$

Dorénavant :

  • toutes les comparaisons font appel la fonction Scan.
  • au plus 1 appel à Scan par position
Une position $i$ est touchée par l’algorithme :

lorsqu’elle a fait l’objet d’une comparaison positive avec une position plus petite.

Invariant :

  • Toute position $i<s+Pref(s)$ a fait l’objet d’au plus une comparaison positive
  • Toute position $i≥s+Pref[s]$ n’a fait l’objet d’aucune comparaison positive

Donc en tout :

  • au plus $n-1$ comparaisons négatives (1 appel à Scan par position)
  • au plus $n-1$ comparaisons positives (invariant)

Examen de la position $i$

  • Cas 1 : $i≥ s + Pref[s]$

    Pref[i] = Scan(1,i)
if Pref[i]>0:
  s = i

Sinon, si : $s< i< s + Pref[s]$

  • Cas 2 : $i+Pref[k]-1 < s+Pref[s]$

    Pref[i] = Pref[k]

  • Cas 3 : $i+Pref[k]-1 > s+Pref[s]$

    Pref[i] = s + Pref[s] - i

  • Cas 4 : $i+Pref[k]-1 = s+Pref[s]$

    Pref[i] = Pref[k] + Scan(Pref[k], s+Pref[s])
s=i

Leave a comment