Probleme – Un banc d'essai : naïf, Boyer-Moore, Rabin-Karp

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 18 — Algorithmique des textes

Énoncé

On veut savoir lequel des trois algorithmes choisir, et sur quel critère.

Mesurer les trois sur un texte français de $225$ caractères, pour des motifs de longueur $1$ , $3$ et $5$ .
Mesurer les trois sur $T = a^{200}$ avec $P = a^{5}$ , puis avec $P = a^{4} b$ .
Conclure : quand choisit-on lequel ?

Corrigé

1. Sur du texte français. On compte les comparaisons de caractères. Pour Rabin-Karp, ce sont uniquement celles des vérifications — s'y ajoutent $Θ (n)$ opérations arithmétiques, une par fenêtre, que la colonne ne montre pas.

Motif	$m$	occ.	naïf	Boyer-Moore	Rabin-Karp
`motif`	5	4	$238$	$67$	$20$ (4 vérif.)
`texte`	5	4	$259$	$80$	$20$ (4 vérif.)
`un\ `	3	7	$243$	$104$	$21$ (7 vérif.)
`e`	1	33	$225$	$225$	$33$ (33 vérif.)

Boyer-Moore divise par $3, 5$ à $m = 5$ et par $2, 3$ à $m = 3$ ; à $m = 1$ il ne gagne rien, ce qui est logique : il ne peut jamais sauter plus que $m$ .

Rabin-Karp ne fait aucune comparaison inutile : sur ce texte, il n'y a eu aucune collision, et le nombre de comparaisons vaut exactement $m \times$ le nombre d'occurrences. Mais il a lu les $225$ caractères pour maintenir son empreinte.

2. Sur un alphabet dégénéré.

	naïf	Boyer-Moore	Rabin-Karp
$T = a^{200}$ , $P = a^{5}$	$980$	$980$	$980$ (196 vérif.)
$T = a^{200}$ , $P = a^{4} b$	$980$	$196$	$0$ (0 vérif.)

La première ligne est le pire cas commun aux trois : $196$ occurrences, chacune coûtant $5$ comparaisons, soit $980$ — incompressible, puisqu'il faut bien lire chaque occurrence pour la certifier. Aucun algorithme ne peut faire mieux quand la sortie est de taille $Θ (n)$ .

La seconde ligne les sépare radicalement. Boyer-Moore échoue immédiatement sur le b et saute de $1$ à chaque fois — d'où $196$ comparaisons, une par alignement. Rabin-Karp, lui, n'a aucune collision : $H (aaaaa) \neq = H (aaaab)$ , et il ne compare jamais un seul caractère. C'est son meilleur cas.

3. La conclusion, en trois règles.

Naïf quand le texte est court ou le motif rare : il n'a aucun précalcul, et sur du langage naturel il est en $Θ (n)$ de fait. Sur un texte de $225$ caractères, le précalcul de $256$ cases de Boyer-Moore coûte plus que la recherche entière.
Boyer-Moore pour un motif long dans un grand texte à alphabet riche. Le gain croît avec $m$ et avec $∣Σ∣$ , et s'annule quand l'un des deux est petit.
Rabin-Karp pour plusieurs motifs de même longueur, ou quand la comparaison de caractères est chère (motifs longs, structures comparées champ par champ, recherche à deux dimensions dans une image). Pour un seul motif, il ne bat presque jamais Boyer-Moore, car il lit tout le texte alors que Boyer-Moore en saute une partie.

Et une règle de méthode. Ce tableau a été produit par des compteurs placés dans les trois fonctions, sur les mêmes entrées. C'est la seule manière honnête de comparer : les mesures de temps dépendent du cache et du compilateur, les bornes asymptotiques ne distinguent pas $67$ de $238$ . On instrumente ce qu'on veut comparer, et l'on dit ce que le compteur ne compte pas — ici, l'arithmétique de Rabin-Karp et le précalcul de Boyer-Moore.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.