Mise en œuvre d'une simple Trie efficace de calcul de la Distance de Levenshtein - Java
Mise à JOUR 3
Fait. Ci-dessous le code que finalement passé tous mes tests. Encore une fois, c'est calquée sur Murilo Vasconcelo version modifiée de Steve Hanov de l'algorithme. Merci à tous qui ont aidé!
/**
* Computes the minimum Levenshtein Distance between the given word (represented as an array of Characters) and the
* words stored in theTrie. This algorithm is modeled after Steve Hanov's blog article "Fast and Easy Levenshtein
* distance using a Trie" and Murilo Vasconcelo's revised version in C++.
*
* http://stevehanov.ca/blog/index.php?id=114
* http://murilo.wordpress.com/2011/02/01/fast-and-easy-levenshtein-distance-using-a-trie-in-c/
*
* @param ArrayList<Character> word - the characters of an input word as an array representation
* @return int - the minimum Levenshtein Distance
*/
private int computeMinimumLevenshteinDistance(ArrayList<Character> word) {
theTrie.minLevDist = Integer.MAX_VALUE;
int iWordLength = word.size();
int[] currentRow = new int[iWordLength + 1];
for (int i = 0; i <= iWordLength; i++) {
currentRow[i] = i;
}
for (int i = 0; i < iWordLength; i++) {
traverseTrie(theTrie.root, word.get(i), word, currentRow);
}
return theTrie.minLevDist;
}
/**
* Recursive helper function. Traverses theTrie in search of the minimum Levenshtein Distance.
*
* @param TrieNode node - the current TrieNode
* @param char letter - the current character of the current word we're working with
* @param ArrayList<Character> word - an array representation of the current word
* @param int[] previousRow - a row in the Levenshtein Distance matrix
*/
private void traverseTrie(TrieNode node, char letter, ArrayList<Character> word, int[] previousRow) {
int size = previousRow.length;
int[] currentRow = new int[size];
currentRow[0] = previousRow[0] + 1;
int minimumElement = currentRow[0];
int insertCost, deleteCost, replaceCost;
for (int i = 1; i < size; i++) {
insertCost = currentRow[i - 1] + 1;
deleteCost = previousRow[i] + 1;
if (word.get(i - 1) == letter) {
replaceCost = previousRow[i - 1];
} else {
replaceCost = previousRow[i - 1] + 1;
}
currentRow[i] = minimum(insertCost, deleteCost, replaceCost);
if (currentRow[i] < minimumElement) {
minimumElement = currentRow[i];
}
}
if (currentRow[size - 1] < theTrie.minLevDist && node.isWord) {
theTrie.minLevDist = currentRow[size - 1];
}
if (minimumElement < theTrie.minLevDist) {
for (Character c : node.children.keySet()) {
traverseTrie(node.children.get(c), c, word, currentRow);
}
}
}
Mise à JOUR 2
Enfin, j'ai réussi à obtenir que cela fonctionne pour la plupart de mes cas de test. Mon application est pratiquement une traduction directe de l' Murilo du C++ version de Steve Hanov de l'algorithme de. Alors, comment dois-je refactoriser cet algorithme et/ou de faire des optimisations? Ci-dessous est le code...
public int search(String word) {
theTrie.minLevDist = Integer.MAX_VALUE;
int size = word.length();
int[] currentRow = new int[size + 1];
for (int i = 0; i <= size; i++) {
currentRow[i] = i;
}
for (int i = 0; i < size; i++) {
char c = word.charAt(i);
if (theTrie.root.children.containsKey(c)) {
searchRec(theTrie.root.children.get(c), c, word, currentRow);
}
}
return theTrie.minLevDist;
}
private void searchRec(TrieNode node, char letter, String word, int[] previousRow) {
int size = previousRow.length;
int[] currentRow = new int[size];
currentRow[0] = previousRow[0] + 1;
int insertCost, deleteCost, replaceCost;
for (int i = 1; i < size; i++) {
insertCost = currentRow[i - 1] + 1;
deleteCost = previousRow[i] + 1;
if (word.charAt(i - 1) == letter) {
replaceCost = previousRow[i - 1];
} else {
replaceCost = previousRow[i - 1] + 1;
}
currentRow[i] = minimum(insertCost, deleteCost, replaceCost);
}
if (currentRow[size - 1] < theTrie.minLevDist && node.isWord) {
theTrie.minLevDist = currentRow[size - 1];
}
if (minElement(currentRow) < theTrie.minLevDist) {
for (Character c : node.children.keySet()) {
searchRec(node.children.get(c), c, word, currentRow);
}
}
}
Merci à tous ceux qui ont contribué à cette question. J'ai essayé de faire la Levenshtein Automates de travail, mais je ne pouvais pas y arriver.
Donc je suis à la recherche de suggestions sur la refactorisation et/ou des optimisations concernant le code ci-dessus. S'il vous plaît laissez-moi savoir si il n'y a aucune confusion. Comme toujours, je peux fournir le reste du code source en tant que de besoin.
Mise à JOUR de 1
J'ai donc mis en place un simple Trie de structure de données et j'ai essayé de suivre Steve Hanov du tutoriel python pour calculer la Distance de Levenshtein. En fait, je suis intéressé dans le calcul de la minimum Levenshtein entre un mot et les mots dans la Trie, donc j'ai suivi Murilo Vasconcelos la version de Steve Hanov de l'algorithme de. Il ne fonctionne pas très bien, mais voici mon Trie classe:
public class Trie {
public TrieNode root;
public int minLevDist;
public Trie() {
this.root = new TrieNode(' ');
}
public void insert(String word) {
int length = word.length();
TrieNode current = this.root;
if (length == 0) {
current.isWord = true;
}
for (int index = 0; index < length; index++) {
char letter = word.charAt(index);
TrieNode child = current.getChild(letter);
if (child != null) {
current = child;
} else {
current.children.put(letter, new TrieNode(letter));
current = current.getChild(letter);
}
if (index == length - 1) {
current.isWord = true;
}
}
}
}
... et la TrieNode classe:
public class TrieNode {
public final int ALPHABET = 26;
public char letter;
public boolean isWord;
public Map<Character, TrieNode> children;
public TrieNode(char letter) {
this.isWord = false;
this.letter = letter;
children = new HashMap<Character, TrieNode>(ALPHABET);
}
public TrieNode getChild(char letter) {
if (children != null) {
if (children.containsKey(letter)) {
return children.get(letter);
}
}
return null;
}
}
Maintenant, j'ai essayé de mettre en œuvre la recherche en tant que Murilo Vasconcelos a elle, mais quelque chose est éteint et j'ai besoin de l'aide de débogage ce. Veuillez donner des suggestions sur la façon de refactoriser le présent et/ou le point d'où les bugs sont. La première chose que je tiens à refactoriser est le "minCost" variable globale, mais c'est la moindre des choses. De toute façon, voici le code...
public void search(String word) {
int size = word.length();
int[] currentRow = new int[size + 1];
for (int i = 0; i <= size; i++) {
currentRow[i] = i;
}
for (int i = 0; i < size; i++) {
char c = word.charAt(i);
if (theTrie.root.children.containsKey(c)) {
searchRec(theTrie.root.children.get(c), c, word, currentRow);
}
}
}
private void searchRec(TrieNode node, char letter, String word, int[] previousRow) {
int size = previousRow.length;
int[] currentRow = new int[size];
currentRow[0] = previousRow[0] + 1;
int replace, insertCost, deleteCost;
for (int i = 1; i < size; i++) {
char c = word.charAt(i - 1);
insertCost = currentRow[i - 1] + 1;
deleteCost = previousRow[i] + 1;
replace = (c == letter) ? previousRow[i - 1] : (previousRow[i - 1] + 1);
currentRow[i] = minimum(insertCost, deleteCost, replace);
}
if (currentRow[size - 1] < minCost && !node.isWord) {
minCost = currentRow[size - 1];
}
Integer minElement = minElement(currentRow);
if (minElement < minCost) {
for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
searchRec(node, entry.getKey(), word, currentRow);
}
}
}
Je m'excuse pour le manque de commentaires. Donc, ce que je fais mal?
POST INITIAL
J'ai lu un article, Rapide et Facile Levenshtein à l'aide d'un Trie, dans l'espoir de trouver un moyen efficace pour calculer la Levenshtein entre deux Chaînes de caractères. Mon objectif principal avec c'est, étant donné un ensemble de mots, pour être en mesure de trouver le minimum de la Distance de Levenshtein entre un mot d'entrée(s) et ce jeu de mots.
Dans mon implémentation triviale, je calcule la Distance de Levenshtein entre un mot d'entrée et l'ensemble des mots, pour chaque mot d'entrée et de retour que le minimum. Cela fonctionne, mais il n'est pas efficace...
J'ai été à la recherche pour les implémentations d'un Trie, en Java, et je suis venu à travers deux apparemment de bonnes sources:
- Koders.com version
- code.google.com version
(EDIT: Cela semble avoir été déplacé à github.com/rkapsi)
Cependant, ces implémentations semble trop compliqué pour ce que je suis en train de faire. Comme je viens de lire à travers eux, à comprendre comment ils fonctionnent et comment les Trie les structures de données de travail en général, j'ai deviendra de plus en plus confus.
Alors, comment aurais-je mettre en œuvre un simple Trie de la structure de données en Java? Mon intuition me dit que chaque TrieNode doit stocker la Chaîne de caractères qu'elle représente et des références à des lettres de l'alphabet, pas nécessairement toutes les lettres. Est mon intuition correcte?
Une fois que c'est mis en œuvre, la tâche suivante consiste à calculer la Distance de Levenshtein. J'ai lu le code Python exemple dans l'article ci-dessus, mais je ne parle pas de Python, et mon Java mise en œuvre à court de mémoire dans la mémoire une fois que j'ai frappé à la recherche récursive. Alors, comment aurais-je calculer la Distance de Levenshtein, à l'aide de la Trie structure de données? J'ai une implémentation simple, calqué sur le ce code source, mais il n'utilise pas de Trie... il est inefficace.
Il serait vraiment agréable de voir un peu de code en plus de vos commentaires et suggestions. Après tout, ce est un processus d'apprentissage pour moi... je n'ai jamais mis en œuvre un Trie... j'ai donc beaucoup à apprendre de cette expérience.
Grâce.
p.s. Je peux fournir le code source en cas de besoin. Aussi, j'ai déjà lu et essayé d'utiliser un BK-Arbre comme suggéré dans Nick Johnson blog, mais ce n'est pas aussi efficace que je pense que ça peut être... ou peut-être que mon application est mauvais.
- Vous avez mentionné Nick Johnson blog, donc peut-être que vous avez déjà vu son Levenshtein Automates code. Levenshtein Automates code est le plus efficace que j'ai couru à travers jusqu'à présent. Vous auriez juste besoin de convertir sa version de Python Java. Voir ceci: blog.notdot.net/2010/07/...
- Voici un résumé de Levenshtein Automates: gist.github.com/491973
- La seule façon que je peux penser qu'un Trie serait de vous aider si vous êtes essentiellement de cours pour mettre en œuvre la même chose que le Levenshtein Automates de toute façon. Un trie est qu'un cas particulier d'un DFA qui reconnaît les mots.
if (currentRow[size - 1] < minCost && !node.isWord) {
cette ligne est fausse. Vous ne pouvez mettre à jourminCost
si il y a un mot qui se termine au niveau de ce nœud, de sorte que le bon estif (currentRow[size - 1] < minCost && node.isWord) {
- que les résultats de modifications dans un
StackOverflowError
, je crois à cause de trop de la récursivité. Dans votre version C++, vous avezif ((current_row[sz-1] < min_cost) && (tree->word != ""))
... exactement ce que fait la deuxième partie de cette si signifie? Ce n' "" représenter? tree->word == ""
signifie qu'aucun mot de finition au niveau de ce nœud. Donc, si le coût est inférieur à lamin_cost
et un ou plusieurs mots de finition au niveau de ce nœud, nous devons mettre à jour lemin_cost
avec le coût actuel.StackOverflowError
peut-être parce que vos mots sont très grandes. Savez-vous quelle est la longueur maximum de vos mots? Aussi, vous pouvez essayer d'exécuter mon code avec vos données et de voir si la même erreur se produit.- le dictionnaire-je utiliser a ~180k mots et la longueur maximum de mots dans ce dictionnaire est de 15 caractères. Mais l'entrée peut être plus long, mais pas garanti.
- Ainsi, le
StackOverflowError
n'est pas à cause de la récursivité... Votre maximum de profondeur de récursion est 15 qui est petit.
Vous devez vous connecter pour publier un commentaire.
J'ai mis en place l'algo décrite dans "Facile et Rapide de Levenshtein à l'aide d'un Trie" article en C++ et il est vraiment très rapide. Si vous le souhaitez (comprendre C++ mieux que Python, j'ai passé le code en quelque part.
Edit:
Je l'ai posté sur mon blog.
De ce que je peux dire, vous n'avez pas besoin d'améliorer l'efficacité de Levenshtein, vous avez besoin de stocker vos chaînes dans une structure qui vous empêche d'avoir à exécuter les calculs de distance tant de fois j'.e par élagage de l'espace de recherche.
Depuis Levenshtein est une mesure, vous pouvez utiliser la métrique des espaces indices qui profitent du triangle de l'inégalité - vous avez mentionné BK-Arbres, mais il y a d'autres par exemple. Point De Vue Des Arbres, Fixe Les Requêtes Des Arbres, Bissectrice Des Arbres, De L'Espace D'Approximation Des Arbres. Voici leur description:
Burkhard-Keller Arbre
L'insertion des nœuds dans l'arbre comme suit:
Pour le nœud racine de choisir un élément arbitraire
à partir de l'espace; ce qui ajoute une pointe marqué
les enfants, tels que la valeur de chaque arête est
la distance entre le pivot qui
élément; appliquer de manière récursive, en sélectionnant l'
les enfants du pivot lorsqu'une limite déjà
existe.
Fixe Requêtes Arbre
Comme avec BKTs exception: les Éléments sont stockés
à feuilles, Chaque feuille a plusieurs éléments;
Pour chaque niveau de l'arbre de la même pivot est
utilisé.
Bissectrice De L'Arbre
Chaque nœud contient deux éléments de pivot
avec leur revêtement de rayon (maximum
la distance entre le centre de l'élément et
l'un de ses sous-arborescence d'éléments); Filtre en deux
définit les éléments qui sont les plus proches
le premier pivot et les plus proches de la
deuxièmement, et de manière récursive la construction de deux sous-arbres
à partir de ces ensembles.
Spatiale Rapprochement Arbre
Initialement, tous les éléments sont dans un sac; Choisir
l'arbitraire d'un élément à être le pivot; Construire
une collection des plus proches voisins dans un délai de
gamme de pivot; Mettre chacun restant
élément dans le sac de la plus proche
élément de la collection vient de construire;
De manière récursive forme une sous-arborescence de chaque
élément de cette collection.
Point De Vue De L'Arbre
Choisir un pivot de l'ensemble abitrarily;
Calculer la distance médiane entre ce
pivot et chaque élément du reste
ensemble; les éléments de Filtre à partir de l'ensemble dans la gauche
et à droite récursive, les sous-rubriques telles que
ceux avec des distances de moins de ou égal à
la médiane de la gauche et de plus
formulaire de droite.
Voici un exemple de Levenshtein Automates en Java (EDIT: déplacé à github).Ces sera probablement utile:
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/
EDIT: Les liens ci-dessus semblent avoir été déplacé vers github:
https://github.com/apache/lucene-solr/tree/master/lucene/core/src/java/org/apache/lucene/util/automaton
https://github.com/apache/lucene-solr/tree/master/lucene/core/src/test/org/apache/lucene/util/automaton
Il ressemble à l'expérimental Lucene code est basé sur de l' dk.brics.automate paquet.
Utilisation semble être quelque chose de similaire à ci-dessous:
Lev1ParametricDescription
etLev2ParametricDescription
... et d'autres classesDans beaucoup de façons, Steve Hanov de l'algorithme présenté dans le premier article lié à la question, Rapide et Facile Levenshtein à l'aide d'un Trie), les ports de l'algorithme faite par Murilo et vous (OP), et très probablement tous pertinents algorithme impliquant un Trie ou une structure similaire, fonctionnent beaucoup comme un Levenshtein Automate (qui a été mentionné à plusieurs reprises ici) n':
Steve Hanov de l'algorithme et de ses dérivés susmentionnés évidemment utiliser un Levenshtein calcul de la matrice en place d'une structure officielle de Levenshtein Automate. Assez rapide, mais un officiel Levenshtein Automate peut avoir son paramétrique états (états abstraits qui décrivent le béton les états de l'automate) généré et utilisé pour la traversée, sans passer par une distance de vérification liées à l'exécution de calcul que ce soit. Donc, il doit être exécuté même plus rapide que celle de ladite algorithmes.
Si vous (ou quelqu'un d'autre) est intéressé par un officiel Levenshtein Automate solution, jetez un oeil à LevenshteinAutomaton. Il met en œuvre ladite paramétrique de l'état de l'algorithme, ainsi que d'un pur béton à l'état d'-traversée de base de l'algorithme décrit ci-dessus) et dynamique-programmation basée sur les algorithmes (pour modifier la distance et le voisin de détermination). Il est maintenu par votre serviteur 🙂 .
Non, un trie de ne pas représenter une Chaîne de caractères, il représente un ensemble de chaînes de caractères (et tous leurs préfixes). Un trie nœud cartes une entrée de caractères à un autre trie nœud. Il devrait donc tenir quelque chose comme un tableau de caractères, et un tableau de TrieNode références. (Peut-être pas l'exacte représentation, en fonction de l'efficacité dans votre utilisation de l'informatique.)
Comme je le vois à droite, vous souhaitez faire une boucle sur toutes les branches de la trie. Ce n'est pas que difficile à l'aide d'une fonction récursive. Je suis à l'aide d'un trie bien dans ma k-plus proche voisin de l'algorithme, en utilisant le même type de fonction. Je ne sais pas Java, cependant, mais voici quelques pseudo-code:
Espère que cela aide.
La fonction de marche, un testitem (par exemple une fraise de chaîne ou un tableau de caractères) et d'un trie. Un trie peut être un objet avec les deux fentes. Un spécifiant le nœud de la trie, les autres enfants de ce nœud. Les enfants sont essaie tant bien. En python, il serait quelque chose comme:
Ou en Lisp...
Maintenant un trie ressemble à quelque chose comme ceci:
Maintenant la fonction interne (que vous pouvez aussi écrire séparément) prend la testitem, les enfants du nœud racine de l'arbre (dont la valeur du nœud est pas ou peu importe), et une distance initiale à 0.
Alors que nous venons de parcourir récursivement les deux branches de l'arbre, en commençant à gauche et puis à droite.
Je vais juste laisser ça ici au cas où quelqu'un est à la recherche d'encore un autre traitement de ce problème:
http://code.google.com/p/oracleofwoodyallen/wiki/ApproximateStringMatching
J'ai été à la recherche à votre dernière mise à jour 3, l'algorithme ne semblent pas très bien fonctionner pour moi.
Soit s le voyez, vous avez ci-dessous les cas de test:
Dans ce cas, le minimum de la distance d'édition entre
"arc"
et le dict devrait être de 1, qui est la distance d'édition entre"arc"
et"arb"
, mais vous les algorithmes de retour 2 à la place.Je suis allé à travers le morceau de code ci-dessous:
Au moins pour la première boucle, la lettre est l'un des personnages de la parole, mais au lieu de cela, vous devriez comparer les nœuds dans la trie, donc il y aura une ligne en double avec le premier caractère d'un mot, est-ce que le droit? chaque DP de la matrice a la première ligne comme un doublon. J'ai exécuté exactement le même code que vous mettez sur la solution.
Bien, voici comment je l'ai fait il y a longtemps.
J'ai stocké le dictionnaire comme un trie, qui est simplement un fini de machine d'état limitée à la forme d'un arbre.
Vous pouvez l'améliorer en ne faisant pas cette restriction.
Par exemple, les suffixes courants peut être simplement un partage de la sous-arborescence.
Vous pourriez même avoir des boucles, pour capturer des trucs comme "nation", "national", "nationaliser", "nationalisation", ...
Garder la trie comme absolument simple que possible. Ne pas aller à la farce des chaînes en elle.
Rappelez-vous, vous ne faites pas cela pour trouver la distance entre deux chaînes de caractères. Vous pouvez l'utiliser pour trouver les chaînes dans le dictionnaire qui sont les plus proches l'une chaîne donnée. Le temps nécessaire dépend de la façon dont beaucoup de levenshtein vous pouvez tolérer. Pour la distance de zéro, il est tout simplement O(n) où n est la longueur du mot. Pour arbitraire à distance, il 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 unnecesary et rend le programme beaucoup plus lent:
Vous devez appeler traverseTrie qu'une seule fois, parce que dans traverseTrie vous êtes déjà en boucle sur l'ensemble de la parole. Le code doit être seul comme suit: