Segmentation à la main — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 8)

Segmentation à la main

Séquences et chaînes de caractères · niveau 1 (application)

Énoncé

Le dictionnaire est $D = {a, ar, art, arta, t, tari, ri, rien, en}$ et la chaîne est $C = artarien$ ( $n = 8$ ).

Un algorithme glouton lit la chaîne de gauche à droite et isole à chaque étape le plus court mot du dictionnaire en tête de ce qui reste. Que se passe-t-il ?
Calculer les valeurs $s (j)$ et $a (j) = ar g s (j)$ pour $0 \leq j < 9$ (on prend pour $a (j)$ le plus petit indice $i$ qui convient, et $a (j) = - 1$ si $s (j)$ est faux).
En déduire une segmentation de $C$ .

Le glouton isole a, puis cherche un mot commençant rtarien : il n'y en a pas (ri et rien commencent par ri). Il conclut à tort que la chaîne n'est pas segmentable.
$s (0)$ est vrai, $a (0) = 0$ . Pour $j \geq 1$ , on cherche le premier $i < j$ tel que $s (i)$ soit vrai et $C [i : j] \in D$ :


A = [0, 0, 0, 0, 0, 3, 2, -1, 4]

On remonte depuis $j = 8$ : dernier mot $C [4 : 8] = rien$ , puis $C [0 : 4] = arta$ . Segmentation : arta rien.


nom : A
valeurs : 0 0 0 0 0 3 2 -1 4
vert : 0 4 8
fleches-bas : 8->4 4->0
legende : on remonte : a(8) = 4, puis a(4) = 0


nom : C
valeurs : a r t a r i e n
zone : 0..3 arta
zone : 4..7 rien