Implémentation d'un Trie simple pour un calcul efficace de la distance de Levenshtein-Java

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 empêche d'exécuter des calculs de distance tant de fois, c'est-à-dire en élaguant l'espace de recherche.

Puisque la distance de Levenshtein est une métrique, vous pouvez utiliser n'importe lequel des indices d'espaces métriques qui tirent parti de l'inégalité des triangles - vous avez mentionné BK-Trees, mais il y en a d'autres, par exemple. Arbres De Point De Vue, Arbres Fixes-Requêtes, Arbres Bissectrices, Rapprochement Des Arbres. Voici leurs descriptions:

Arbre Burkhard-Keller

Les nœuds sont insérés dans l'arborescence comme suit: Pour le nœud racine choisissez un élément arbitraire de l'espace; ajouter unique bord-marqué enfants tels que la valeur de chaque bord est la distance entre le pivot qui élément; appliquer récursivement, en sélectionnant enfant comme pivot quand un bord déjà exister.

Arbre De Requêtes Fixes

Comme avec BKTs sauf: les éléments sont stockés à feuilles; chaque feuille a plusieurs éléments; Pour chaque niveau de l'arbre le même pivot est utiliser.

Arbre Bissectrice

Chaque nœud contient deux éléments de pivot avec leur rayon de couverture (maximum distance entre l'élément central et L'un de ses éléments de sous-arbre); filtrer en deux définit les éléments les plus proches de le premier pivot et ceux les plus proches de la deuxièmement, et construire récursivement deux sous-arbres à partir de ces ensembles.

Spatiale Rapprochement Arbre

Initialement, 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 dans plage du pivot; mettre chaque restant élément dans le sac du plus proche élément de la collection vient de construire; Former récursivement un sous-arbre de chaque élément de cette collection.

Arbre De Point De Vue

Choisissez un pivot dans l'ensemble abitrarily; Calculer la distance médiane entre cette pivot et chaque élément du restant set; éléments filtrants de l'ensemble vers la gauche et à droite sous arbres récursifs tels que ceux dont les distances sont inférieures ou égales à la médiane forme la gauche et les plus grandes formulaire de droite.

Voici un exemple de Levenshtein Automates 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/trunk/lucene/src/test/org/apache/lucene/util/automaton/

Il semble que le code Lucene expérimental soit basé sur dk.BRIC.automate paquet.

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 Levenshtein rapide et facile en utilisant un Trie ), les ports de L'algorithme fait par Murilo et vous (OP), et très probablement tout algorithme pertinent impliquant un trie ou une structure similaire, fonctionnent un peu comme un automate Levenshtein]}

Given:
       dict is a dictionary represented as a DFA (ex. trie 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 mentionnés ci-dessus utilisent évidemment un Levenshtein calcul de la matrice en place d'une structure officielle de Levenshtein Automate. assez rapide, mais un automate Levenshtein formel peut avoir ses États paramétriques (États abstraits qui décrivent les États concrets de l'automate) générés et utilisés pour la traversée, en contournant tout calcul 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 quelqu'un d'autre) est intéressé par un officiel Levenshtein Automaton solution , jetez un oeil à LevenshteinAutomaton . Il implémente l'algorithme basé sur l'état paramétrique susmentionné, ainsi qu'un algorithme basé sur la traversée d'état concret pur (décrit ci-dessus) et des algorithmes basés sur la programmation dynamique (pour la détermination de la distance d'édition et du voisin). Il est maintenu par le vôtre vraiment :).

Mon intuition me dit que chaque TrieNode doit stocker la chaîne qu'il représente et aussi des références aux lettres de l'alphabet, pas nécessairement toutes les lettres. Mon intuition est-elle correcte?

Non, un trie ne représente pas une chaîne, il représente un ensemble de chaînes (et tous leurs préfixes). Un nœud trie mappe un caractère d'entrée à un autre nœud trie. Il devrait donc contenir quelque chose comme un tableau de caractères et un tableau correspondant de références TrieNode. (Peut-être pas exact représentation, en fonction de l'efficacité dans votre utilisation de l'informatique.)

Comme je le vois bien, vous voulez faire une boucle sur toutes les branches de la trie. Ce n'est pas si difficile d'utiliser une fonction récursive. J'utilise également un trie dans mon algorithme K-le plus proche voisin, en utilisant le même type de fonction. Je ne connais pas Java, cependant, mais voici un pseudocode:

function walk (testitem trie)
   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 trie, distance set to 0)
    return the results

J'espère que ça aide.

La marche de fonction prend un testitem (par exemple une chaîne indexable, ou un tableau de caractères) et un trie. Un trie peut être un objet avec deux emplacements. L'un spécifiant le nœud du trie, l'autre les enfants de ce nœud. Les enfants sont essaie tant bien. En python, ce serait quelque chose comme:

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

Ou en Lisp...

(defstruct trie (node nil) (children nil))

Maintenant, un trie ressemble à ceci:

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

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

Ensuite, nous traversons récursivement les deux branches de l'arbre, en commençant à gauche puis à droite.

Je vais juste laisser ceci ici au cas où quelqu'un cherche un autre traitement de ce problème:

Http://code.google.com/p/oracleofwoodyallen/wiki/ApproximateStringMatching

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

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

    Trie dict = new Trie();
    dict.insert("arb");
    dict.insert("area");

    ArrayList<Character> word = new ArrayList<Character>();
    word.add('a');
    word.add('r');
    word.add('c');

Dans ce cas, la distance d'édition minimale entre "arc" et le dict devrait être 1, qui est la distance d'édition entre "arc" et "arb", mais vos algorithmes retourneront 2 à la place.

Je suis passé par le morceau de 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 à la place, vous devriez être comparez les nœuds dans le trie, donc il y aura une ligne dupliquée avec le premier caractère dans le mot, est-ce vrai? chaque matrice 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 comme un trie, qui est simplement une machine à états finis limitée à la forme d'un arbre. Vous pouvez l'améliorer en ne faisant pas cette restriction. Par exemple, les suffixes communs peuvent simplement être un sous-arbre partagé. Vous pourriez même avoir des boucles, pour capturer des trucs comme "nation", "national", "nationaliser", "nationalisation", ...

Gardez le trie aussi simple que possible. Ne va pas fourrer des cordes il.

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

Corrigez-moi si je me trompe mais je crois que votre update3 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 devriez appeler traverseTrie une seule fois parce que dans traverseTrie vous êtes déjà en boucle sur le mot entier. Le code devrait être seulement comme suit:

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