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

Question

J'ai deux très grandes chaînes et j'essaie de trouver leur Longest Common Substring.

Une façon utilise arbres suffixe (censé avoir une très bonne complexité, bien qu'une mise en œuvre complexe), et l'autre est la méthode de programmation dynamique (les deux sont mentionnés sur la page Wikipedia 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 cordes). Ce que je veux savoir (avant de sauter pour implémenter des arborescences de suffixes): 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 sous-chaîne commune elle-même)?

Answer 1

Sera-t-il plus rapide en pratique? Oui. Sera-t-il plus rapide en ce qui concerne Big-Oh? La solution de programmation dynamique est toujours O (n * m). Le problème que vous pourriez rencontrer avec les arborescences de suffixes est que vous échangez l'analyse linéaire de l'arbre de suffixes pour une pénalité énorme dans l'espace. Les arbres de suffixes sont généralement beaucoup plus grands que la table que vous devez implémenter pour une version de programmation dynamique de l'algorithme. Selon la longueur de vos chaînes, il est tout à fait possible que la programmation dynamique soit 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 Remarquant 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)). L'idée est de ne garder que deux lignes - la ligne actuelle que vous traitez, et la rangée précédente que vous venez de traiter, et jetez le reste.

Answer 3

Myer's bit vector algorithm peut vous aider. Il fonctionne en utilisant la manipulation de bits et est une approche beaucoup plus rapide.

Answer 4

Voici un algorithme simple qui peut finir dans O ((m + n) * log (m + n)), et beaucoup plus facile à implémenter par rapport à l'algorithme de l'arbre de suffixes O (m + n) runtime. Commençons par la longueur commune minimale (minL) = 0 et la longueur commune maximale (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];