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:

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 à jour minCost si il y a un mot qui se termine au niveau de ce nœud, de sorte que le bon est if (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 avez if ((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 à la min_cost et un ou plusieurs mots de finition au niveau de ce nœud, nous devons mettre à jour le min_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.

InformationsquelleAutor Hristo | 2011-02-01