Plus longue sous-séquence commune

Une sous-séquence préserve l'ordre, mais ses éléments n'ont pas besoin d'être contigus. Étant données deux séquences $X$ et $Y$, le problème de la plus longue sous-séquence commune (LCS) demande une séquence de longueur maximale qui soit une sous-séquence des deux.

Le cours du MIT sur la LCS présente la LCS comme une programmation dynamique sur des états de séquences.

Soit $dp[i][j]$ la longueur de la LCS des préfixes $X[:i]$ et $Y[:j]$ :

$$dp[i][j] = \begin{cases} dp[i-1][j-1]+1, & X[i-1]=Y[j-1],\\ \max(dp[i-1][j],dp[i][j-1]), & \text{otherwise}. \end{cases}$$

Les lignes et colonnes correspondant à un préfixe vide valent zéro.

def lcs_length(left: str, right: str) -> int:
    previous = [0] * (len(right) + 1)
    for left_item in left:
        current = [0]
        for j, right_item in enumerate(right, start=1):
            if left_item == right_item:
                current.append(previous[j - 1] + 1)
            else:
                current.append(max(previous[j], current[-1]))
        previous = current
    return previous[-1]

Coût et résultat

• Table complète : $O(mn)$ en temps et $O(mn)$ en espace.
• Longueur seule : $O(mn)$ en temps et $O(\min(m,n))$ en espace après avoir choisi la séquence la plus courte comme largeur de ligne.
• Reconstruire une LCS exige de conserver les choix, une table complète ou une méthode de reconstruction plus spécialisée par division et conquête.

La plus longue sous-chaîne commune est un autre problème, car les symboles correspondants doivent y être contigus.

Déduire et lire la table

Si les derniers symboles diffèrent, une sous-séquence commune ne peut pas les utiliser tous deux comme dernière correspondance : il faut en écarter au moins un, d'où le maximum des deux états de préfixes plus courts. S'ils sont égaux, un optimum peut utiliser cette dernière correspondance ; l'ajouter à un optimum des deux préfixes plus courts donne la transition diagonale. Toutes les dépendances ont des préfixes plus courts, ce qui fonde l'induction et la terminaison.

Pour left="ABC", right="AC", les lignes, préfixe vide compris, sont [0,0,0], [0,1,1], [0,1,1], [0,1,2]. La longueur est donc 2, avec AC comme solution. Une chaîne vide donne une longueur nulle. Pour reconstruire depuis une table complète, partez de (m,n) : si les symboles sont égaux, notez le symbole et avancez en diagonale ; sinon, passez à un voisin conservant la valeur optimale. Inversez les symboles recueillis. Les égalités peuvent produire plusieurs sous-séquences de même longueur.

Tel quel, le code occupe O(len(right)) en espace. Échangez les entrées lorsque right est plus longue pour obtenir O(min(m,n)).

assert lcs_length("ABC", "AC") == 2
assert lcs_length("", "AC") == 0

Source

• MIT OpenCourseWare : programmation dynamique II

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.