distancias - Implementando un Trie simple para un cálculo eficiente de distancia de Levenshtein-Java
distancias de levenshtein (11)
ACTUALIZACIÓN 3
Hecho. Debajo está el código que finalmente pasó todas mis pruebas. De nuevo, esto se basa en la versión modificada de Murilo Vasconcelo del algoritmo de Steve Hanov. ¡Gracias a todos los que ayudaron!
/**
* 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);
}
}
}
ACTUALIZACIÓN 2
Finalmente, logré que esto funcione en la mayoría de mis casos de prueba. Mi implementación es prácticamente una traducción directa de la versión C ++ de Murilo del algoritmo de Steve Hanov . Entonces, ¿cómo debería refactorizar este algoritmo y / o hacer optimizaciones? Debajo está el código ...
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);
}
}
}
Gracias a todos los que contribuyeron a esta pregunta. Intenté hacer funcionar los Levenshtein Automata, pero no pude lograrlo.
Así que estoy buscando sugerencias sobre refactorización y / u optimizaciones con respecto al código anterior. Por favor, avíseme si hay alguna confusión. Como siempre, puedo proporcionar el resto del código fuente según sea necesario.
ACTUALIZACIÓN 1
Así que he implementado una estructura de datos Trie simple y he estado tratando de seguir el tutorial de python de Steve Hanov para calcular la distancia de Levenshtein. En realidad, estoy interesado en calcular la distancia mínima de Levenshtein entre una palabra dada y las palabras en Trie, así que he estado siguiendo la versión de Murilo Vasconcelos del algoritmo de Steve Hanov . No está funcionando muy bien, pero aquí está mi clase de Trie:
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;
}
}
}
}
... y la clase TrieNode:
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;
}
}
Ahora, he intentado implementar la búsqueda como lo tiene Murilo Vasconcelos , pero algo no funciona y necesito ayuda para depurar esto. Proporcione sugerencias sobre cómo refactorizar esto y / o señalar dónde están los errores. Lo primero que me gustaría refactorizar es la variable global "minCost", pero esa es la más pequeña de las cosas. De todos modos, aquí está el código ...
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);
}
}
}
Me disculpo por la falta de comentarios. Entonces, ¿qué estoy haciendo mal?
POST INICIAL
He estado leyendo un artículo, distancia rápida y fácil de Levenshtein usando un Trie , con la esperanza de encontrar una forma eficiente de calcular la distancia de Levenshtein entre dos cadenas. Mi principal objetivo con esto es, dado un gran conjunto de palabras, poder encontrar la distancia mínima de Levenshtein entre una palabra (s) de entrada y este conjunto de palabras.
En mi implementación trivial, calculo la distancia de Levenshtein entre una palabra de entrada y el conjunto de palabras, para cada palabra de entrada, y devuelvo el mínimo. Funciona, pero no es eficiente ...
He estado buscando implementaciones de un Trie, en Java, y me he encontrado con dos fuentes aparentemente buenas:
Sin embargo, estas implementaciones parecen demasiado complicadas para lo que estoy tratando de hacer. A medida que los he estado leyendo para comprender cómo funcionan y cómo funcionan las estructuras de datos de Trie en general, solo me he vuelto más confundido.
Entonces, ¿cómo implementaría una estructura de datos Trie simple en Java? Mi intuición me dice que cada TrieNode debe almacenar la Cadena que representa y también las referencias a las letras del alfabeto, no necesariamente todas las letras. ¿Mi intuición es correcta?
Una vez que se implementa, la siguiente tarea es calcular la distancia de Levenshtein. Leí el ejemplo del código Python en el artículo anterior, pero no hablo Python, y mi implementación Java se queda sin memoria Heap una vez que toco la búsqueda recursiva. Entonces, ¿cómo calcularía la Distancia Levenshtein usando la estructura de datos Trie? Tengo una implementación trivial, modelada según este código fuente , pero no usa un Trie ... es ineficiente.
Sería realmente agradable ver algunos códigos además de sus comentarios y sugerencias. Después de todo, este es un proceso de aprendizaje para mí ... Nunca he implementado un Trie ... así que tengo mucho que aprender de esta experiencia.
Gracias.
ps Puedo proporcionar cualquier código fuente si es necesario. Además, ya lo leí e intenté usar un BK-Tree como se sugiere en el blog de Nick Johnson , pero no es tan eficiente como creo que puede ser ... o tal vez mi implementación es incorrecta.
Mi intuición me dice que cada TrieNode debe almacenar la Cadena que representa y también las referencias a las letras del alfabeto, no necesariamente todas las letras. ¿Mi intuición es correcta?
No, un trie no representa una Cadena, representa un conjunto de cadenas (y todos sus prefijos). Un nodo trie mapea un carácter de entrada a otro nodo trie. Por lo tanto, debe contener algo así como una matriz de caracteres y una matriz correspondiente de referencias TrieNode. (Tal vez no esa representación exacta, dependiendo de la eficiencia en su uso particular de ella).
Aquí hay un ejemplo de Levenshtein Automata en Java . Probablemente también sean útiles:
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/
Parece que el código Lucene experimental se basa en el paquete dk.brics.automaton .
El uso parece ser algo similar a lo siguiente:
LevenshteinAutomata builder = new LevenshteinAutomata(s);
Automaton automata = builder.toAutomaton(n);
boolean result1 = BasicOperations.run(automata, "foo");
boolean result2 = BasicOperations.run(automata, "bar");
Bueno, así es como lo hice hace mucho tiempo. Guardé el diccionario como un trie, que es simplemente una máquina de estados finitos restringida a la forma de un árbol. Puede mejorarlo al no hacer esa restricción. Por ejemplo, los sufijos comunes pueden ser simplemente un subárbol compartido. Incluso podría tener bucles, capturar cosas como "nación", "nacional", "nacionalizar", "nacionalización", ...
Mantenga el trie tan simple como sea posible. No vayas rellenando cadenas.
Recuerde, no hace esto para encontrar la distancia entre dos cadenas dadas. Lo usa para encontrar las cadenas en el diccionario que están más cerca de una cadena dada. El tiempo que toma depende de la distancia de distancia que pueda tolerar. Para la distancia cero, es simplemente O (n) donde n es la longitud de la palabra. Para la distancia arbitraria, es O (N) donde N es el número de palabras en el diccionario.
Como lo veo bien, quieres recorrer todas las ramas del trie. Eso no es tan difícil usando una función recursiva. Estoy usando un trie también en mi algoritmo vecino k-más cercano, usando el mismo tipo de función. No conozco Java, pero aquí hay un pseudocódigo:
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
Espero eso ayude.
Corrígeme si me equivoco, pero creo que tu actualización3 tiene un bucle adicional que es innecesario y hace que el programa sea mucho más lento:
for (int i = 0; i < iWordLength; i++) {
traverseTrie(theTrie.root, word.get(i), word, currentRow);
}
Deberías llamar a traverseTrie solo una vez porque dentro de traverseTrie ya estás recorriendo toda la palabra. El código debe ser solo de la siguiente manera:
traverseTrie(theTrie.root, '' '', word, currentRow);
Dejaré esto aquí en caso de que alguien esté buscando otro tratamiento de este problema:
http://code.google.com/p/oracleofwoodyallen/wiki/ApproximateStringMatching
En muchos sentidos, el algoritmo de Steve Hanov (presentado en el primer artículo vinculado en la pregunta, Levenshtein distancia rápida y fácil usando un Trie ), los puertos del algoritmo hecho por Murilo y usted (OP), y muy posiblemente todos los algoritmos pertinentes que involucran un Trie o una estructura similar, funciona muy parecido a un autómata Levenshtein (que se ha mencionado varias veces aquí):
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
El algoritmo de Steve Hanov y sus derivados antes mencionados obviamente usan una matriz de cálculo de distancia Levenshtein en lugar de una Automaton Levenshtein formal. Bastante rápido, pero un Automaton de Levenshtein formal puede tener sus estados paramétricos ( estados abstractos que describen los estados concretos del autómata) generados y utilizados para el cruce, eludiendo cualquier cálculo de tiempo de ejecución relacionado con el tiempo de ejecución. Por lo tanto, debe ejecutarse incluso más rápido que los algoritmos antes mencionados.
Si usted (o cualquier otra persona) está interesado en una solución formal de Automaton de Levenshtein , eche un vistazo a LevenshteinAutomaton . Implementa el algoritmo basado en el estado paramétrico antes mencionado, así como un algoritmo puro basado en el estado concreto transversal (descrito anteriormente) y algoritmos basados en la programación dinámica (tanto para la distancia de edición como para la determinación del entorno). Lo mantiene tuyo verdaderamente :).
Estaba viendo tu última actualización 3, el algoritmo parece no funcionar bien para mí.
Veamos que tienes los casos de prueba a continuación:
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'');
En este caso, la distancia mínima de edición entre "arc" y dict debe ser 1, que es la distancia de edición entre "arc" y "arb" , pero los algoritmos devolverán 2 en su lugar.
Revisé la siguiente pieza de código:
if (word.get(i - 1) == letter) {
replaceCost = previousRow[i - 1];
} else {
replaceCost = previousRow[i - 1] + 1;
}
Al menos para el primer bucle, la letra es uno de los caracteres de la palabra, pero en su lugar, debe comparar los nodos en el trie, por lo que habrá una línea duplicada con el primer carácter de la palabra, ¿verdad? cada matriz DP tiene la primera línea como duplicado. Ejecuté exactamente el mismo código que pones en la solución.
Implementé el algoritmo descrito en el artículo "Rápido y fácil Levenshtein distance using a Trie" en C ++ y es muy rápido. Si quieres (entiendo C ++ mejor que Python), puedo pasar el código en algún lugar.
Editar: Lo publiqué en mi blog .
La caminata de función toma un elemento de prueba (por ejemplo, una cadena indexable o una matriz de caracteres) y un trie. Un trie puede ser un objeto con dos ranuras. Uno que especifica el nodo del trie, el otro los hijos de ese nodo. Los niños también lo intentan. En Python sería algo así como:
class Trie(object):
def __init__(self, node=None, children=[]):
self.node = node
self.children = children
O en Lisp ...
(defstruct trie (node nil) (children nil))
Ahora un trie se ve así:
(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)))))))
Ahora la función interna (que también puede escribir por separado) toma el elemento de prueba, los elementos secundarios del nodo raíz del árbol (cuyo valor de nodo es Ninguno o lo que sea) y una distancia inicial establecida en 0.
Luego recorremos recursivamente ambas ramas del árbol, comenzando a la izquierda y luego a la derecha.
Por lo que puedo decir, no es necesario mejorar la eficiencia de Levenshtein Distance, necesita almacenar sus cadenas en una estructura que le impida ejecutar cálculos de distancia tantas veces, es decir, al podar el espacio de búsqueda.
Como la distancia de Levenshtein es una métrica, puede usar cualquiera de los índices de espacios métricos que aprovechan la desigualdad de triángulo: mencionó BK-Trees, pero hay otros, por ejemplo. Árboles de miradores, árboles de consultas fijas, árboles bisectores, árboles de aproximación espacial. Aquí están sus descripciones:
Árbol Burkhard-Keller
Los nodos se insertan en el árbol de la siguiente manera: para el nodo raíz, elija un elemento arbitrario del espacio; agregar elementos únicos con etiqueta de borde de manera que el valor de cada borde sea la distancia desde el pivote hasta ese elemento; aplicar recursivamente, seleccionando al niño como pivote cuando ya existe un borde.
Árbol de consultas fijas
Como con los BKT excepto que: los elementos se almacenan en las hojas; Cada hoja tiene múltiples elementos; Para cada nivel del árbol se usa el mismo pivote.
Bisector Tree
Cada nodo contiene dos elementos de pivote con su radio de cobertura (distancia máxima entre el elemento central y cualquiera de sus elementos de subárbol); Filtre en dos conjuntos los elementos que están más cerca del primer pivote y los más cercanos al segundo, y recursivamente construya dos subárboles de estos conjuntos.
Árbol de aproximación espacial
Inicialmente todos los elementos están en una bolsa; Elija un elemento arbitrario para ser el pivote; Construya una colección de vecinos más cercanos dentro del alcance del pivote; Ponga cada elemento restante en la bolsa del elemento más cercano a él de la colección recién construida; Recursivamente formar un subárbol de cada elemento de esta colección.
Árbol de Vantage Point
Elija un pivote del conjunto de forma ab initual; Calcule la distancia media entre este pivote y cada elemento del conjunto restante; Filtre los elementos del conjunto en los subárboles recursivos izquierdo y derecho de modo que aquellos con distancias menores o iguales a la mediana formen la izquierda y los que forman el derecho.