Implémentation d’un simple Trie pour un calcul efficace de la distance de Levenshtein – Java

J’ai implémenté l’algo décrit dans l’article “Rapide et facile Levenshtein distance en utilisant un Trie” en C ++ et c’est vraiment rapide. Si vous voulez (comprendre le C ++ mieux que Python), je peux faire passer le code quelque part.

Edit: je l’ai posté sur mon blog .

D’après ce que je peux dire, vous n’avez pas besoin d’améliorer l’efficacité de Levenshtein Distance, vous devez stocker vos chaînes dans une structure qui vous évite d’avoir à exécuter autant de calculs de distance, c’est-à-dire en supprimant l’espace de recherche.

Comme la distance de Levenshtein est une mésortingque, vous pouvez utiliser n’importe quel indice d’espace mésortingque qui tire parti de l’inégalité des sortingangles – vous avez mentionné les arbres BK, mais il en existe d’autres, par exemple. Arbres de points de vue, arbres de requêtes fixes, arbres bissecteurs, arbres d’approximation spatiale. Voici leurs descriptions:

Arbre de Burkhard-Keller

Les nœuds sont insérés dans l’arborescence comme suit: pour le nœud racine, sélectionnez un élément arbitraire dans l’espace; ajoutez des enfants uniques étiquetés de bord de telle sorte que la valeur de chaque bord soit la distance entre le pivot et cet élément; appliquer de manière récursive, en sélectionnant l’enfant comme pivot lorsqu’une arête existe déjà.

Arbre de requêtes fixes

Comme avec les BKT sauf que: les éléments sont stockés dans les feuilles; Chaque feuille a plusieurs éléments. Le même pivot est utilisé pour chaque niveau de l’arbre.

Arbre Bisecteur

Chaque nœud contient deux éléments de pivot avec leur rayon de couverture (distance maximale entre l’élément central et l’un quelconque de ses éléments de sous-arbre); Filtrez en deux ensembles les éléments les plus proches du premier pivot et ceux du deuxième et construisez de manière récursive deux sous-arbres à partir de ces ensembles.

Arbre d’approximation spatiale

Au début, tous les éléments sont dans un sac. Choisissez un élément arbitraire pour être le pivot; Construire une collection de voisins les plus proches à scope du pivot; Placez chaque élément restant dans le sac de l’élément le plus proche de la collection que vous venez de construire; Formez récursivement un sous-arbre à partir de chaque élément de cette collection.

Arbre de sharepoint vue

Choisissez un pivot dans l’ensemble Calculez la distance médiane entre ce pivot et chaque élément de l’ensemble restant. Filtrez les éléments de l’ensemble en sous-arbres récursifs gauche et droit de manière à ce que ceux dont les distances soient inférieures ou égales à la médiane forment la gauche et ceux qui sont plus grands la droite.

Voici un exemple d’ automates Levenshtein en Java . Ceux-ci seront probablement également utiles:

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ http://svn.apache.org/repos/asf/ lucene / dev / coffre / lucene / src / test / org / apache / lucene / util / automate /

Il semble que le code expérimental Lucene soit basé sur le paquet dk.brics.automaton .

L’utilisation semble être quelque chose de similaire à ci-dessous:

 LevenshteinAutomata builder = new LevenshteinAutomata(s); Automaton automata = builder.toAutomaton(n); boolean result1 = BasicOperations.run(automata, "foo"); boolean result2 = BasicOperations.run(automata, "bar"); 

À bien des égards, l’algorithme de Steve Hanov (présenté dans le premier article lié à la question, distance rapide et facile de Levenshtein utilisant un Trie ), les ports de l’algorithme créé par Murilo et vous (OP), et probablement tous les algorithmes pertinents Trie ou une structure similaire, fonctionne un peu comme un automate Levenshtein (qui a été mentionné à plusieurs resockets ici):

 Given: dict is a dictionary represented as a DFA (ex. sortinge or dawg) dictState is a state in dict dictStartState is the start state in dict dictAcceptState is a dictState arrived at after following the transitions defined by a word in dict editDistance is an edit distance laWord is a word la is a Levenshtein Automaton defined for laWord and editDistance laState is a state in la laStartState is the start state in la laAcceptState is a laState arrived at after following the transitions defined by a word that is within editDistance of laWord charSequence is a sequence of chars traversalDataStack is a stack of (dictState, laState, charSequence) tuples Define dictState as dictStartState Define laState as laStartState Push (dictState, laState, "") on to traversalDataStack While traversalDataStack is not empty Define currentTraversalDataTuple as the the product of a pop of traversalDataStack Define currentDictState as the dictState in currentTraversalDataTuple Define currentLAState as the laState in currentTraversalDataTuple Define currentCharSequence as the charSequence in currentTraversalDataTuple For each char in alphabet Check if currentDictState has outgoing transition labeled by char Check if currentLAState has outgoing transition labeled by char If both currentDictState and currentLAState have outgoing transitions labeled by char Define newDictState as the state arrived at after following the outgoing transition of dictState labeled by char Define newLAState as the state arrived at after following the outgoing transition of laState labeled by char Define newCharSequence as concatenation of currentCharSequence and char Push (newDictState, newLAState, newCharSequence) on to currentTraversalDataTuple If newDictState is a dictAcceptState, and if newLAState is a laAcceptState Add newCharSequence to resultSet endIf endIf endFor endWhile 

L’algorithme de Steve Hanov et ses dérivés susmentionnés utilisent évidemment une masortingce de calcul de distance Levenshtein à la place d’un automate Levenshtein formel. Assez rapide, mais un automate Levenshtein formel peut avoir ses états paramésortingques ( états abstraits décrivant les états concrets de l’automate) générés et utilisés pour le parcours, en contournant de quelque manière que ce soit le calcul de temps d’exécution lié à la distance d’édition. Donc, il devrait être exécuté encore plus rapidement que les algorithmes susmentionnés.

Si vous (ou toute autre personne) êtes intéressé par une solution formelle d’automatisme Levenshtein , consultez LevenshteinAutomaton . Il implémente l’algorithme susmentionné basé sur des états paramésortingques, ainsi qu’un algorithme pur basé sur des états concrets (décrit ci-dessus) et des algorithmes basés sur la programmation dynamic (pour la détermination de la distance d’édition et des voisins). Il est maintenu par le vôtre vraiment :).

Mon intuition me dit que chaque TrieNode devrait stocker la chaîne qu’il représente et faire également référence aux lettres de l’alphabet, pas nécessairement à toutes les lettres. Est-ce que mon intuition est correcte?

Non, un sorting ne représente pas une chaîne, il représente un ensemble de chaînes (et tous leurs préfixes). Un sortinge noeud mappe un caractère d’entrée sur un autre noeud. Donc, il devrait contenir quelque chose comme un tableau de caractères et un tableau correspondant de références TrieNode. (Peut-être pas cette représentation exacte, dépendant de l’efficacité dans votre utilisation particulière de celle-ci.)

Comme je le comprends bien, vous souhaitez parcourir toutes les twigs du projet. Ce n’est pas si difficile d’utiliser une fonction récursive. J’utilise aussi un sortinge dans mon algorithme k-voisin le plus proche, en utilisant le même type de fonction. Je ne connais pas Java, cependant, mais voici un pseudocode:

 function walk (testitem sortinge) make an empty array results function compare (testitem children distance) if testitem = None place the distance and children into results else compare(testitem from second position, the sub-children of the first child in children, if the first item of testitem is equal to that of the node of the first child of children add one to the distance (! non-destructive) else just the distance) when there are any children left compare (testitem, the children without the first item, distance) compare(testitem, children of root-node in sortinge, distance set to 0) return the results 

J’espère que cela aide.

La fonction walk prend un test (par exemple une chaîne indexable ou un tableau de caractères) et un sorting. Un sortinge peut être un object avec deux emplacements. L’un spécifiant le noeud du sortinge, l’autre les enfants de ce noeud. Les enfants sont aussi des essais. En python, ce serait quelque chose comme:

 class Trie(object): def __init__(self, node=None, children=[]): self.node = node self.children = children 

Ou à Lisp …

 (defstruct sortinge (node nil) (children nil)) 

Maintenant, un sortinge ressemble à ceci:

 (sortinge #node None #children ((sortinge #node f #children ((sortinge #node o #children ((sortinge #node o #children None))) (sortinge #node u #children ((sortinge #node n #children None))))))) 

Maintenant, la fonction interne (que vous pouvez également écrire séparément) prend le testitem, les enfants du nœud racine de l’arborescence (dont la valeur du nœud est None ou autre) et une distance initiale définie sur 0.

Ensuite, nous traversons les deux twigs de l’arbre de manière récursive, en partant de gauche à droite.

Je laisserai simplement ceci ici au cas où quelqu’un chercherait un traitement supplémentaire de ce problème:

http://code.google.com/p/oracleofwoodyallen/wiki/ApproximateSsortingngMatching

Je regardais votre dernière mise à jour 3, l’algorithme semble ne pas bien fonctionner pour moi.

Voyons que vous avez ci-dessous des cas de test:

  Trie dict = new Trie(); dict.insert("arb"); dict.insert("area"); ArrayList word = new ArrayList(); word.add('a'); word.add('r'); word.add('c'); 

Dans ce cas, la distance d’édition minimale entre "arc" et le dict doit être de 1, qui correspond à la distance d’édition entre "arc" et "arb" , mais vos algorithmes renverront 2 à la place.

Je suis passé par le code ci-dessous:

  if (word.get(i - 1) == letter) { replaceCost = previousRow[i - 1]; } else { replaceCost = previousRow[i - 1] + 1; } 

Au moins pour la première boucle, la lettre est l’un des caractères du mot, mais vous devez plutôt comparer les nœuds du sorting, afin qu’il y ait une ligne dupliquée avec le premier caractère du mot, n’est-ce pas? chaque masortingce DP a la première ligne en double. J’ai exécuté exactement le même code que vous avez mis sur la solution.

Eh bien, voici comment je l’ai fait il y a longtemps. J’ai stocké le dictionnaire en tant que sortinge, qui est simplement une machine à états finis limitée à la forme d’un arbre. Vous pouvez l’améliorer en ne faisant pas cette ressortingction. Par exemple, les suffixes communs peuvent simplement être un sous-arbre partagé. Vous pourriez même avoir des boucles pour capturer des éléments tels que “nation”, “national”, “nationaliser”, “nationalisation”, …

Gardez le sorting aussi simple que possible. N’allez pas y mettre des ficelles.

Rappelez-vous, vous ne faites pas ceci pour trouver la distance entre deux chaînes données. Vous l’utilisez pour rechercher dans le dictionnaire les chaînes les plus proches d’une chaîne donnée. Le temps que cela prend dépend de la distance que vous pouvez tolérer. Pour la distance zéro, c’est simplement O (n) où n est la longueur du mot. Pour une distance arbitraire, il s’agit de O (N) où N est le nombre de mots du dictionnaire.

Corrigez-moi si je me trompe, mais je pense que votre mise à jour3 a une boucle supplémentaire qui est inutile et rend le programme beaucoup plus lent:

 for (int i = 0; i < iWordLength; i++) { traverseTrie(theTrie.root, word.get(i), word, currentRow); } 

Vous ne devez appeler traverseTrie qu’une seule fois car dans traverseTrie, vous parcourez déjà le mot en entier. Le code devrait être seulement comme suit:

 traverseTrie(theTrie.root, ' ', word, currentRow);