Compte tenu d'une liste de chaînes, trouvez chaque paire $ (x, y) $ où $ x $ est une subséquente de $ $ $.Possible de faire mieux que $ o (n ^ 2) $?

Question

Considérez le problème algorithmique suivant: donné une liste de chaînes $ l= [s_1, s_2, \ dots, s_n] $ , nous voulons connaître toutes les paires < span classe="math-conteneur"> $ (x, y) $ où $ x $ est une ultérieurement de $ y $ . Nous pouvons supposer que toutes les chaînes sont de longueur au maximum $ M $ , où $ m << n $ et sont tous sur un alphabet fini $ \ sigma $ avec $ | \ sigma | << N $ . Nous pouvons également supposer que le nombre de paires $ (x, y) $ où $ x est un Sousecence de $ y $ est beaucoup plus petit que $ n $

.

.

Un algorithme trivial serait ceci:

1. foreach x in L:
2.   foreach y in L:
3.      if x is subsequence of y:
4.         OUTPUT x,y

Cependant, cela a une complexité $ o (n ^ 2 \ cdot m) $ - Je suis curieux de savoir s'il y a un algorithme plus rapide (plus vite étant donné que le nombre de paires $ (x, y) $ est beaucoup plus petit que $ n $ , donc par exemple un algorithme avec une complexité en fonction du nombre de paires de sortie).

Notez que cette question est un suivi de Cette question , qui concerne le même problème, mais pour les sous-chaînes (non des sous-séquences). Là-bas, l'algorithme Aho-Corasick a résolu votre problème parfaitement - y a-t-il peut-être quelque chose de quelque chose comme celui-ci, mais pour les sous-courances?

Answer 1

Non, il n'est pas possible de faire mieux que si la forte hypothèse de temps exponentielle (Seth) échoue. Si nous pouvions résoudre ce problème sensiblement plus vite que $ O (N ^ 2) $ Nous obtiendrions immédiatement un algorithme beaucoup plus rapide pour résoudre la satisfaction des problèmes de NP-complète. Ceci est vrai même pour $ m $ légèrement plus que $ \ journal (n) $ et le cas dans que nous voulons décider si une telle paire $ (x, y) $ existe du tout.

voir, par exemple, Ces notes de cours sous la section 3 "serré Limites inférieures pour les vecteurs orthogonaux ». La preuve est analogue à la preuve du théorème 2 dans ces notes de cours.

Tout d'abord, nous considérons le problème plus général de deux ensembles de chaînes $ x, y $ , constatant si une chaîne dans $ X $ est une recherchetenue d'une chaîne dans $ y $ .

Compte tenu d'une formule SAT, nous avons divisé sa N $ N $ VARIABLES EN DEUX ENSEMBLES ÉQUIPES DE $ N / 2 $ < / span> variables. Dans $ \ sigma $ Nous prenons un caractère correspondant à chaque clause. Dans $ x $ Nous ajoutons une chaîne pour chaque affectation possible à la première moitié des variables, avec un caractère correspondant à chaque clause pas satisfait par ces variables. Pendant ce temps, dans $ y $ , nous ajoutons une chaîne pour chaque affectation à la seconde moitié des variables, avec un caractère pour chaque clause satisfaite par ces variables. Clairement, la formule est satisfiatable si et seulement si une chaîne dans $ x $ est une ultérieurement de certaines chaînes dans $ y $ .

Si ce problème peut être résolu sensiblement plus vite que $ O (N ^ 2) $ , cela donne un algorithme sensiblement plus rapide de la satisfaction que 2 $ ^ N $ . Supposons que le problème puisse être résolu dans $ o (n ^ {1,99}) $ temps, puis la satisfaction pourrait être résolue dans $ (2 ^ {n / 2}) ^ {1.99}= O (2 ^ {0,996n}) $ qui contredit Seth.

Dans votre problème, il n'y a qu'un seul ensemble de chaînes, ce qui peut tout ce qui peut être une subséquation les uns des autres. Ce n'est cependant pas un problème, car nous pouvons simplement modifier les chaînes dans notre exemple, de sorte qu'aucune chaîne $ y $ est une subséquence de toute autre chaîne (par exemple par remplissage Toutes les chaînes dans $ y $ avoir la même longueur) et un remplissage similaire à chaque chaîne dans $ x / span> à la même longueur que les autres chaînes de $ x $ (mais sensiblement plus courte que les chaînes dans $ y $ ) .

Cela peut probablement également être fait avec une alphabet de taille constante (probable même binaire), mais cela nécessite plus d'encodage intelligent.