Segmenter en un minimum de mots, compter les segmentations

Séquences et chaînes de caractères · niveau 2

Énoncé

On note $N (j)$ le nombre minimum de mots d'une segmentation du $j$ -préfixe de $C$ ( $+ \infty$ s'il n'est pas segmentable). Donner la récurrence de $N (j)$ et écrire le programme qui affiche une segmentation en un minimum de mots.
On note $K (j)$ le nombre de segmentations du $j$ -préfixe. Donner la récurrence de $K (j)$ .
Calculer $N$ et $K$ sur l'exemple de l'exercice 8.5 et énumérer les segmentations de artarien.

Corrigé

Le dernier mot $C [i : j]$ coûte un mot de plus que la meilleure segmentation du $i$ -préfixe : $N (0) = 0$ et, pour $1 \leq j < n + 1$ , $N (j) = min {N (i) + 1 : 0 \leq i < j, C [i : j] \in D}$ ( $+ \infty$ si l'ensemble est vide).


static int[][] calculerNA(String C, Set<String> D) { int n = C.length();
    int[] N = new int[n + 1], A = new int[n + 1];
    N[0] = 0;                                         // base : zéro mot
    for (int j = 1; j < n + 1; j++) {
        N[j] = INFINI; A[j] = -1;
        for (int i = 0; i < j; i++)
            if (D.contains(C.substring(i, j)) && N[i] + 1 < N[j]) { N[j] = N[i] + 1; A[j] = i; }
    }
    return new int[][] {N, A};
}

L'affichage est celui du cours (segmentation(C, A, n)).

Les segmentations du $j$ -préfixe se répartissent selon leur dernier mot : $K (0) = 1$ (la segmentation vide) et $K (j) = \sum {K (i) : 0 \leq i < j, C [i : j] \in D}$ .
Exécution :


N = [0, 1, 1, 1, 1, 2, 2, inf, 2]
minimum : arta rien
K = [1, 1, 1, 2, 3, 2, 4, 0, 7]

Les $7$ segmentations : arta rien, arta ri en, art a rien, art a ri en, ar tari en, ar t a rien, ar t a ri en. Une seule est en deux mots.