Plus longue sous-séquence commune de 3+ chaînes

Je suis en train d'essayer de trouver la plus longue sous-suite commune de 3 ou plus de chaînes. L'article de Wikipédia a une grande description de comment faire pour les 2 chaînesmais je suis un peu incertain de la façon de prolonger ce de 3 ou plus de chaînes.

Il ya beaucoup de bibliothèques pour trouver la CL de 2 cordes, donc je voudrais utiliser l'un d'eux si possible. Si j'ai 3 chaînes A, B et C, est-il valide pour trouver la CL de A et B de X, et ensuite trouver la CL de X et C, ou est-ce la mauvaise façon de le faire?

J'ai implémenté en Python comme suit:

import difflib

def lcs(str1, str2):
    sm = difflib.SequenceMatcher()
    sm.set_seqs(str1, str2)
    matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
    return "".join(matching_blocks)

print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])

Ce sorties "ba", mais elle doit être "baa".

source d'informationauteur del

Simplement généraliser la relation de récurrence.

Pour les trois chaînes:

dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if A[i] = B[j] = C[k]
              max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise

Devrait être facile de généraliser à plus de cordes à partir de ce.

À trouver la plus Longue sous-suite Commune (LCS) de 2 chaînes A et B, vous pouvez parcourir un tableau en 2 dimensions, en diagonale, comme indiqué dans le Lien que vous avez posté. Chaque élément du tableau correspond à la difficulté de trouver la CL de la chaˆ ıne A' et B' (Une coupe par son numéro de ligne, B coupé par son numéro de colonne). Ce problème peut être résolu par le calcul de la valeur de tous les éléments du tableau. Vous devez être certain que lorsque vous calculez la valeur d'un élément de tableau, tous les sous-problèmes requis pour calculer cette valeur a déjà été résolu. C'est pourquoi vous traversez le tableau en 2 dimensions en diagonale.

Cette solution peut être mise à l'échelle à la recherche de la plus longue sous-suite commune entre la N des chaînes, mais cela exige qu'un moyen pour parcourir un tableau à N dimensions telle que tout élément est atteint que lorsque tous les sous-problèmes de l'élément nécessite une solution a été résolu.

Au lieu de l'itération N-dimensions tableau dans un ordre particulier, vous pouvez également résoudre le problème de manière récursive. Avec la récursivité, il est important d'enregistrer les solutions intermédiaires, depuis de nombreuses branches, les mêmes solutions intermédiaires. J'ai écrit un petit exemple en C# qui fait cela:

string lcs(string[] strings)
{
if (strings.Length == 0)
return "";
if (strings.Length == 1)
return strings[0];
int max = -1;
int cacheSize = 1;
for (int i = 0; i < strings.Length; i++)
{
cacheSize *= strings[i].Length;
if (strings[i].Length > max)
max = strings[i].Length;
}
string[] cache = new string[cacheSize];
int[] indexes = new int[strings.Length];
for (int i = 0; i < indexes.Length; i++)
indexes[i] = strings[i].Length - 1;
return lcsBack(strings, indexes, cache);
}
string lcsBack(string[] strings, int[] indexes, string[] cache)
{
for (int i = 0; i < indexes.Length; i++ )
if (indexes[i] == -1)
return "";
bool match = true;
for (int i = 1; i < indexes.Length; i++)
{
if (strings[0][indexes[0]] != strings[i][indexes[i]])
{
match = false;
break;
}
}
if (match)
{
int[] newIndexes = new int[indexes.Length];
for (int i = 0; i < indexes.Length; i++)
newIndexes[i] = indexes[i] - 1;
string result = lcsBack(strings, newIndexes, cache) + strings[0][indexes[0]];
cache[calcCachePos(indexes, strings)] = result;
return result;
}
else
{
string[] subStrings = new string[strings.Length];
for (int i = 0; i < strings.Length; i++)
{
if (indexes[i] <= 0)
subStrings[i] = "";
else
{
int[] newIndexes = new int[indexes.Length];
for (int j = 0; j < indexes.Length; j++)
newIndexes[j] = indexes[j];
newIndexes[i]--;
int cachePos = calcCachePos(newIndexes, strings);
if (cache[cachePos] == null)
subStrings[i] = lcsBack(strings, newIndexes, cache);
else
subStrings[i] = cache[cachePos];
}
}
string longestString = "";
int longestLength = 0;
for (int i = 0; i < subStrings.Length; i++)
{
if (subStrings[i].Length > longestLength)
{
longestString = subStrings[i];
longestLength = longestString.Length;
}
}
cache[calcCachePos(indexes, strings)] = longestString;
return longestString;
}
}
int calcCachePos(int[] indexes, string[] strings)
{
int factor = 1;
int pos = 0;
for (int i = 0; i < indexes.Length; i++)
{
pos += indexes[i] * factor;
factor *= strings[i].Length;
}
return pos;
}

Mon exemple de code peut être optimisé en outre. De nombreuses chaînes de la mise en cache sont des doublons, et certains sont des doublons avec juste un personnage supplémentaire ajouté. Il utilise plus d'espace que nécessaire lors de l'entrée des chaînes de devenir grand.

Sur entrée: "666222054263314443712", "5432127413542377777", "6664664565464057425"

Le LCS retournée est "54442"

3

J'ai juste eu à le faire pour des devoirs à faire, alors voici ma dynamique de la solution de programmation en python qui est assez efficace. Il est O(lnm) où n, m et l sont les longueurs des trois séquences.

La solution passe par la création d'un tableau 3D et ensuite l'énumération de tous les trois séquences pour calculer le chemin de la plus longue sous-suite. Ensuite, vous pouvez revenir en arrière à travers le tableau de reconstruire le réel sous-suite de son chemin.

Donc, vous initialiser le tableau à tous les zéros, puis énumérer les trois séquences. À chaque étape de l'énumération, vous pouvez ajouter un à la longueur de la plus longue sous-suite (si il y a correspondance) ou de report de la plus longue sous-suite de l'étape précédente de l'énumération.

Une fois que l'énumération est terminée, vous pouvez maintenant remonter à travers le tableau de reconstruire la sous-suite des mesures que vous avez prises. c'est à dire comme vous le voyage à rebours à partir de la dernière entrée dans le tableau, chaque fois que vous rencontrez un match, vous rechercher dans l'une quelconque des séquences (en utilisant les coordonnées de la matrice) et l'ajouter à la sous-suite.
```
def lcs3(a, b, c):
m = len(a)
l = len(b)
n = len(c)
subs = [[[0 for k in range(n+1)] for j in range(l+1)] for i in range(m+1)]
for i, x in enumerate(a):
for j, y in enumerate(b):
for k, z in enumerate(c):
if x == y and y == z:
subs[i+1][j+1][k+1] = subs[i][j][k] + 1
else:
subs[i+1][j+1][k+1] = max(subs[i+1][j+1][k], 
subs[i][j+1][k+1], 
subs[i+1][j][k+1])
# return subs[-1][-1][-1] #if you only need the length of the lcs
lcs = ""
while m > 0 and l > 0 and n > 0:
step = subs[m][l][n]
if step == subs[m-1][l][n]:
m -= 1
elif step == subs[m][l-1][n]:
l -= 1
elif step == subs[m][l][n-1]:
n -= 1
else:
lcs += str(a[m-1])
m -= 1
l -= 1
n -= 1
return lcs[::-1]
```

Vous devez vous connecter pour publier un commentaire.