Comment accélérer le calcul de la longueur de la plus longue chaîne commune?

Question

J'ai deux très grandes chaînes et je suis en train de trouver leur Longest Common Substring .

Une façon est en utilisant des arbres suffixe (censé avoir une très bonne complexité, mais une mise en œuvre complexe), et l'autre est la méthode de programmation dynamique (les deux sont mentionnés sur la page de Wikipédia lien ci-dessus).

en utilisant la programmation dynamique

Le problème est que la méthode de programmation dynamique a un énorme temps de fonctionnement (complexité est O(n*m), où n et m sont des longueurs des deux chaînes).

Ce que je veux savoir (avant de sauter à mettre en œuvre les arbres suffixe): Est-il possible d'accélérer l'algorithme si je veux seulement connaître la longueur de la sous-chaîne commune (et non la commune elle-même sous-chaîne)

Answer 1

est-il plus rapide dans la pratique? Oui. Sera-ce plus rapide au sujet de Big-Oh? Non. La solution de programmation dynamique est toujours O (n * m).

Le problème que vous pourriez rencontrer avec des arbres suffixe est que vous négociez scan temps linéaire de l'arbre suffixe pour une pénalité énorme dans l'espace. les arbres sont généralement Suffixe beaucoup plus grande que la table que vous auriez besoin de mettre en œuvre pour une version de programmation dynamique de l'algorithme. En fonction de la longueur de vos chaînes, il est tout à fait possible que la programmation dynamique sera plus rapide.

Bonne chance:)

Answer 2

Ceux-ci feront courir plus vite, mais il sera toujours O(nm).

Une optimisation est dans l'espace (qui pourrait vous faire économiser un peu de temps d'allocation) est de remarquer que LCSuff ne dépend que de la ligne précédente - donc si vous ne vous préoccupez la longueur, vous pouvez optimiser l'espace O(nm) jusqu'à O(min(n,m)) <. / p>

L'idée est de garder seulement deux lignes -. La ligne actuelle que vous traitez, et la ligne précédente que vous venez de traités, et jeter le reste

Answer 3

Voici un algorithme simple qui peut se termine en O ((m + n) * log (m + n)), et beaucoup plus facile à réaliser par rapport à suffixe algorithme d'arbre qui est O (m + n) d'exécution.

laisser commencer par min Longueur du commun (minG) = 0, et la longueur de courant max (MAXL) = min (m + n) +1.

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

Le problème est de savoir comment restant pour hacher tout sous-chaîne de longueur L dans le temps O (n). Vous pouvez utiliser une formule polynomiale comme suit:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];

Answer 4

algorithme vecteur de bits de Myer peut vous aider. Il fonctionne en utilisant la manipulation et une approche beaucoup plus rapide peu.