Soient m1 et m2 deux chaînes de caractères.
m1 est une sous-séquence de m2 si tous les caractères de m1 apparaissent dans le même ordre, mais éventuellement séparés par d´autres, caractères dans m2.
Ainsi, la chaîne « argh » est une sous-séquence de la chaîne « a really ghastly hack » mais elle n´est pas une sous-séquence de la chaîne « a ghastly hack » ni de la chaîne « a ghastly but real hack »
Lorsqu´on se trouve en présence de deux chaînes m1 et m2, une question judicieuse est donc : est-ce que m1 est une sous-séquence de m2 ?
Un automate d´états fini permet de répondre à cette question.
L´automate peut aisément être implémenté sous la forme d´une méthode Java :
public static boolean subseq(String m1, String m2) {
int i, j;
for (i = j = 0; i < m2.length(); i++)
if (j < m1.length())
if (m1.charAt(j) == m2.charAt(i))
j++;
if ((i >= m2.length()) && (j >= m1.length())) return true;
else return false;
}
|
Cette méthode retourne la valeur booléenne « vrai » si la chaîne m1 est une sous-séquence de la chaîne m2. Sinon, elle retourne la valeur « faux ».
Soient m1, m2 et m3 trois chaînes de caractères.
m1 est une sous-séquence commune de m2 et m3 si m1 est, à la fois, une sous-séquence de m2 et une sous-séquence de m3.
Lorsqu´on est en présence de 3 chaînes m1, m2 et m3, la réponse à la question : « est-ce que m3 est une sous-séquence commune de m1 et m2 » est fournie par la méthode Java :
public static boolean commonSubseq(String m1, String m2, String m3) {
return subseq(m1, m2) && subseq(m1, m3);
}
|
Cette méthode retourne la valeur booléenne « vrai » si la chaîne m1 est une sous-séquence commune des chaînes m2 et m3. Sinon, elle retourne la valeur « faux ».
Soit m une chaîne de caractères.
l(m) = nombre de caractères de la chaîne m.
Soient m1, m2 et m3 trois chaînes de caractères.
m1 est la sous-séquence commune la plus longue (longest common subsequence, lcs) de m2 et m3 si :
Lorsqu´on se trouve en présence de deux chaînes m1 et m2, on peut se poser deux questions judicieuses :
Pour le correcteur orthographique, seule la réponse à la seconde question est pertinente. Nous allons donc focaliser la suite des discussions sur ce point. Signalons que le problème de la sous-séquence commune la plus longue a de nombreuses applications. Ces applications vont de la comparaison de séquences d´ADN à la gestion de versions de codes source. Nous l´avons simplement appliqué à la correction orthographique.
Soient Xm, Yn et Zk, trois chaînes de caractères :
Xm = (x1, x2, x3, ..., xm-1, xm)
Yn = (y1, y2, y3, ..., yn-1, yn)
Zk = (z1, z2, z3, ..., zk-1, zk)
où Zk est une des sous-séquences communes les plus longues de Xm et Yn (car il peut y en avoir plusieurs différentes mais de même longueur). Xm et Yn étant données, quelle est la séquence Zk ?
On peut raisonner sur Xm et Yn de la gauche vers la droite ou inversement, le résultat sera identique. Le raisonnement ci-dessous examine les chaînes de la droite vers la gauche.
Si xm = yn, alors
zk = xm = yn et Zk-1 est une des sous-séquences
communes les plus longues de Zm-1 et Yn-1
Démontrons par l´absurde que cette conclusion est correcte.
Supposons donc que zk ≠ xm = yn. De ce fait,
Zk doit être une
sous-séquence commune de Xm-1 et Yn-1. Or, ceci signifie qu´on
pourrait construire une nouvelle chaîne Qk+1 tel que :
Qk+1 = (z1, z2, z3, ..., zk-1, zk, xm)
Cette chaîne serait une sous-séquence commune de Xm et de Yn
et aurait un caractère de plus que Zk, elle serait donc plus longue.
Par définition, ceci est exclu car, Zk étant une des sous-séquences
communes les plus longues de Xm et Yn, il n´existe aucune autre
sous-séquence commune ayant une taille plus élevée.
Si xm ≠ yn, alors
zk ≠ xm, implique que Zk est une des sous-séquences communes les plus longues de Xm-1 et de Yn
zk ≠ yn, implique que Zk est une des sous-séquences communes les plus longues de Xm et de Yn-1
De ce raisonnement se dégage l´algorithme récursif suivant pour déterminer la sous-séquence la plus longue de deux séquences :
lcs: (Xm, Yn) → Zk = lcs(Xm, Yn)
où :
Cet algorithme peut aisément être implémenté en Java comme suit :
public static String lcs(String x, String y) {
int m = x.length() - 1, n = y.length() - 1;
if (m < 0 || n < 0) return "";
if (x.charAt(m) == y.charAt(n))
return lcs(x.substring(0, m), y.substring(0, n)) +
x.substring(m);
String lcs1 = lcs(x.substring(0, m), y);
String lcs2 = lcs(x, y.substring(0, n));
if (lcs1.length() > lcs2.length())
return lcs1;
return lcs2;
}
|
Toutefois, la question qui nous occupe primordialement est celle de la longueur de la sous-séquence la plus longue. Elle peut être déterminée comme suit :
Ce calcul peut être implémenté en Java comme suit :
public static int lcsLen(String x, String y) {
int m = x.length() - 1, n = y.length() - 1;
if (m < 0 || n < 0) return 0;
if (x.charAt(m) == y.charAt(n))
return lcsLen(x.substring(0, m), y.substring(0, n)) + 1;
return Math.max(lcsLen(x.substring(0, m), y),
lcsLen(x, y.substring(0, n)));
}
|
On pourrait se contenter de cette solution. Malheureusement elle est fort inefficace (du point de vue du temps de calcul) car on procède souvent à des calculs redondants. Le diagramme suivant illustre cet état de faits :
La figure montre que pour calculer lcs(Xm, Yn), on calcule d´un côté lcs(Xm-1, Yn) et de l´autre lcs(Xm, Yn-1). Ensuite, pour calculer lcs(Xm-1, Yn), on va calculer lcs(Xm-2, Yn) et lcs(Xm-1, Yn-1) tandis que pour calculer lcs(Xm, Yn-1), on va calculer lcs(Xm-1, Yn-1) et lcs(Xm, Yn-2). On constate donc qu´on calcule deux fois lcs(Xm-1, Yn-1) ce qui constitue du gaspillage de temps de calcul. De plus, chaque appel récursif entraîne la copie d´arguments sur la pile, le saut vers et le retour de sous-routine.
Il semble donc naturel qu´on cherche à améliorer cette solution. On va procéder par étapes et nous focaliser sur la question de la longueur de la sous-séquence.
L´amélioration que nous allons apporter consistera à mémoriser les longueurs des sous-séquences que nous avons déjà calculées afin d´éviter tout recalcul superflu. Comme nous parcourons deux chaînes Xm et Yn, il nous faudra une matrice de m x n éléments pour toutes les combinaisons imaginables. Ainsi, avant de calculer une longueur, nous consulterons ce tableau pour savoir si elle a déjà été calculée ou non et nous ne la calculerons que dans ce dernier cas. Or, pour accéder une telle matrice, il nous faut des indices. Nous devons donc d´abord modifier notre méthode Java de façon à ce qu´elle travaille uniquement sur les deux chaînes de d´origine au moyen d´indices, plutôt que sur de nouvelles instances de sous-chaînes des chaînes d´origine. Enfin, nous pouvons procéder à des optimisations finales.
Dans un premier temps, essayons d´éliminer les chaînes de caractères de la liste des arguments de la méthode et de les remplacer par des indices, les chaînes étant transformées en variables globales. De plus, pour des raisons de lisibilité du code, on va parcourir les chaînes de la gauche vers la droite. En Java, on obtient alors :
static String x, y;
public static int lcsLen(String x, String y) {
LCSLenInd.x = x;
LCSLenInd.y = y;
return subProblem(0, 0);
}
public static int subProblem(int i, int j) {
if (i >= x.length() || j >= y.length()) return 0;
if (x.charAt(i) == y.charAt(j))
return subProblem(i+1, j+1) + 1;
return Math.max(subProblem(i+1, j), subProblem(i, j+1));
}
|
Il est à noter que les sous-problèmes se calculent toujours, pour l´instant, indépendamment les uns des autres.
Dans un deuxième temps, nous allons stocker les longueurs déjà calculées dans un tableau. Comme nous parcourons deux chaînes Xm et Yn, il nous faudra une matrice de m x n éléments pour toutes les combinaisons imaginables. Ainsi, avant de calculer une longueur, nous consulterons ce tableau pour savoir si elle a déjà été calculée ou non. Nous ne la calculerons que dans ce dernier cas. En Java, on obtient alors :
static String x, y;
static int[][] len;
public static int lcsLen(String x, String y) {
LCSLenMem.x = x;
LCSLenMem.y = y;
len = new int[x.length() + 1][y.length() + 1];
for (int i = 0; i <= x.length(); i++)
for (int j = 0; j <= y.length(); j++)
len[i][j] = -1;
return subProblem(0, 0);
}
public static int subProblem(int i, int j) {
if (len[i][j] < 0) {
if (i >= x.length() || j >= y.length()) len[i][j] = 0;
else if (x.charAt(i) == y.charAt(j))
len[i][j] = subProblem(i+1, j+1) + 1;
else len[i][j] = Math.max(subProblem(i+1, j),
subProblem(i, j+1));
}
return len[i][j];
}
|
Dans la solution précédente, on ne calcule plus les longueurs que si on ne les a pas encore calculées. Malheureusement, l´algorithme est récursif, ce qui est élégant mais en général peu efficace. En effet, la récursivité entraîne la copie d´arguments ainsi que le saut vers et le retour de sous-routine à chaque niveau d´appel. Il est donc préférable de transformer cet algorithme récursif en un algorithme itératif.
On peut faire cela en remplissant le tableau de mémoïsation de manière systématique au lieu de le faire selon les appels récursifs. En examinant l´algorithme ci-dessus, on constate qu´une longueur stockée dans la matrice aux coordonnées (i, j) ne dépend que des longueurs stockées aux coordonnées (i+1, j), (i, j+1) ou (i+1, j+1). Chaque ligne de la matrice dépend donc de la ligne immédiatement inférieure et chaque colonne de la colonne qui se trouve à sa droite. Par conséquent, on peut remplir le tableau de mémoïsation en partant de l´élément en bas à droite de la matrice. On calcule les éléments de la dernière ligne de la droite vers la gauche. Ensuite, on passe à la ligne immédiatement supérieure qu´on remplit à nouveau de la droite vers la gauche et ainsi de suite jusqu´à ce que la premiére ligne soit remplie. En Java, on obtient :
static String x, y;
static int[][] len;
public static int lcsLen(String x, String y) {
LCSLenIt.x = x;
LCSLenIt.y = y;
len = new int[x.length() + 1][y.length() + 1];
for (int i = x.length() - 1; i >= 0; i--)
for (int j = y.length() - 1; j >= 0; j--) {
if (i >= x.length() || j >= y.length()) len[i][j] = 0;
else if (x.charAt(i) == y.charAt(j))
len[i][j] = len[i+1][j+1] + 1;
else len[i][j] = Math.max(len[i+1][j], len[i][j+1]);
}
return len[0][0];
}
|
Cette solution peut encore être améliorée du point de vue de l´espace mémoire consommé. En effet, en examinant la solution ci-dessus, on se rend compte que, lorsqu´on a rempli une ligne de la matrice, la ligne inférieure n´a plus d´utilité. Dans ce cas, il ne sert à rien de la conserver. L´algorithme peut donc être optimisé en ne conservant que deux lignes, la ligne remplie à l´itération précédente ainsi que la ligne en cours de remplissage. En Java, on obtient :
static String x, y;
static int[] len1, len2;
public static int lcsLen(String x, String y) {
LCSLenItOpt.x = x;
LCSLenItOpt.y = y;
len1 = new int[y.length() + 1];
len2 = new int[y.length() + 1];
for (int i = x.length() - 1; i >= 0; i--) {
int[] temp = len1;
len1 = len2;
len2 = temp;
for (int j = y.length() - 1; j >= 0; j--) {
if (i >= x.length() || j >= y.length()) len1[j] = 0;
else if (x.charAt(i) == y.charAt(j))
len1[j] = len2[j+1] + 1;
else len1[j] = Math.max(len2[j], len1[j+1]);
}
}
return len1[0];
}
|
C´est ce dernier algorithme qui est utilisé dans le correcteur orthographique développé dans le cadre du projet CORTINA.
Nous tenons encore à signaler que les algorithmes présentés sur cette page ne constituent pas une contribution originale des collaborateurs du projet CORTINA mais qu´il s´agit d´algorithmes maîtrisés depuis des années et largement discutés dans des publications spécialisées.