Existe-t-il un algorithme de force meilleur que brute pour générer un graphique dont la relation est la chaîne d'édition de chaîne= 1?

Question

Je suis intéressé à créer un graphique dont les sommets sont des chaînes et dont les bords représentent la relation d'une distance d'édition de 1 sous une métrique de chaîne donnée.

Une approche évidente consiste à faire tout $ \ frac {n ^ 2-n} {2} $ comparaisons parmi la $ N $ sommets, nous donnant $ o (n ^ 2) $ complexité du temps.

à l'exclusion de la parallèle des comparaisons, existe-t-il un meilleur algorithme en termes de complexité de temps?

Je suis intéressé par des métriques à chaîne où les chaînes de longueur différente sont autorisées.

Answer 1

Dans le pire cas, tout algorithme de ce type fonctionnera $ omega (n ^ 2) $ car votre graphique peut avoir $ \ Oméga (n ^ 2) $ bords.

Au fait, êtes-vous intéressé par une métrique de chaîne particulière?

Answer 2

Il est possible d'utiliser BK-Trees pour accélérer ce problème. Insertionner $ N $ Éléments dans l'arborescence prend $ O (n \ journal n) $ temps. Après cela, vous pouvez interroger l'arborescence de toutes les chaînes dont la distance d'édition est exacte de votre entrée. Faire cela pour toutes les chaînes prend à nouveau $ o (n ^ 2) $ complexité, cependant avec un très petit facteur constant ( Cette page mentionne seulement 5-8% de l'arbre doit être inspecté par requête ).

Voici une brève description de la façon dont cela fonctionne:

Structure de données

Un arbre BK est soit

• vide
• un nœud avec une valeur racine $ R $ et un ensemble d'enfants indexés $ c_i $ , chacun un arbre BK (implémenté à l'aide de la carte de hachage, de la matrice dynamique ou similaire)

une fonction métrique (importante!) Distance $ D (x, y) $ est utilisé pour l'insertion et les requêtes.

Insertion de chaîne $ S $

• Si l'arbre est vide, faites-en un nouveau nœud avec $ S $ comme valeur racine et aucun enfant
• Si l'arborescence est un nœud avec racine $ r $ et enfants $ C_I $ , let < SPAN CLASSE="MATH-CONTENEUR"> $ K= D (R, S) $ .
  • si $ k= 0 $ , saute insertion comme $ s $ est déjà à la racine < / li>
  • insérez sinon une insérer de manière récursive $ s $ dans la $ k $ -ème arbre enfant $ C_K $ .

La dernière étape garantit que tous les nœuds de $ c_i $ ont une distance $ i $ au racine

String de requête $ S $

• Si l'arbre est vide, retournez aucun résultat
• Si l'arborescence est un nœud avec racine $ r $ et enfants $ C_I $ , let < SPAN CLASSE="MATH-CONTENEUR"> $ K= D (R, S) $ .
  • si $ k= 1 $ , ajoutez $ r $ En conséquence ( Note : cette étape est différente des requêtes habituelles BK-Tree)
  • En outre, Requête de manière récursive $ S $ de l'enfant $ C_ {D-1} $ , $ C_D $ et $ c_ {d + 1} $ . Renvoie tous les résultats de ces requêtes aussi bien

La dernière étape Il y a la magie des arbres BK, car il n'a pas besoin de vérifier les autres enfants en raison de la distance d'être métrique. Voici une preuve partielle de la raison pour laquelle les autres n'ont pas besoin d'être vérifiés:

supposons qu'il y ait une chaîne $ x $ qui a une distance une de notre requête, donc $ d (s, x)= 1 $ , mais c'est dans l'arbre enfant $ c_ {k + 2} $ . Nous savons que $ D (r, x)= k + 2 $ de la procédure d'insertion. C'est cependant (avec l'inégalité du triangle pour les espaces métriques) donne

$$ K + 2= D (R, X) \ LEQ D (R, S) + D (S, X)= K + 1 $$

Mais c'est une contradiction! Similaire peut être fait pour tous les enfants avec $ i> k + 1 $ et $ i . Cela signifie que toutes les cordes d'autres enfants n'auront pas la distance à la construction, nous n'avons donc pas besoin de les vérifier, ce qui permet d'économiser du temps de traitement.

EDIT: une autre explication: https://signal-to-noise.xyz / post / bk-arbre /