Me informaron que la distancia de Levenshtein es simétrica. Cuando utilicé la herramienta diffMatchPatch de Google, que calcula la distancia de Levenshtein entre otras cosas, los resultados no implican que la distancia de Levenshtein sea simétrica. es decir, Levenshtein (x1, x2) no es igual a Levenshtein (x2, x1). ¿Levenshtein no es simétrico o hay algún problema con esa implementación en particular? Gracias.Levenshtein distancia simétrica?
Respuesta
sólo mirar el algoritmo básico que sin duda es simétrica dado el mismo costo para las operaciones - el número de adiciones, eliminaciones y sustituciones para llegar de una palabra de A a una palabra B es lo mismo que ir de la palabra B a la palabra A.
Si hay un costo diferente en cualquiera de las operaciones, puede haber una diferencia, por ejemplo, si la suma tiene un costo de 2 y la eliminación un costo de 1 para obtener de Zombie
a Zombies
resulta en una distancia de 2, a la inversa sería 1 - no simétrica.
Sí, la distancia levenshtein es una distancia en el sentido correcto, es decir dist(a,b)==dist(b,a)
es una parte de la definición de una distancia. Si una función no tiene esta propiedad, no es una función de distancia. Esto sugiere un problema con esa implementación.
El algoritmo clásico de Levenshtein es simétrico; lo que es una inserción que va de x1 a x2 es una eliminación que va de x2 a x1.
Lamentablemente, el algoritmo es O (longitud (x1) * longitud (x2)). Después de una breve mirada a la biblioteca de Google, parece que intenta algunas heurísticas para asegurar que el tiempo de ejecución no sea demasiado grande. Creo que yace tu discrepancia.
siga el código que se implmented por myselef
public class {ReadTextFile
static void readFile(String filepath){
CharSequence sequence1 = null;
CharSequence sequence2 = null;
int levenshteinDistance = 0;
String line1 = "";
String line2 = "";
int minLevenshteinDistance = -1;
try {
BufferedReader br = new BufferedReader(new FileReader(filepath));
String line = "";
while((line=br.readLine())!=null)
{
if(sequence1==null){
line = line.split(" ")[1];
sequence1 = line;
if((line=br.readLine())!=null){
line = line.split(" ")[1];
sequence2 = line;
}
}else{
sequence1 = sequence2;
line = line.split(" ")[1];
sequence2 = line;
}
if(null!=sequence1 && null!=sequence2){
levenshteinDistance = StringUtils.getLevenshteinDistance(sequence1,sequence2);
if(minLevenshteinDistance==-1){
minLevenshteinDistance = levenshteinDistance;
line1= sequence1.toString();
line2= sequence2.toString();
}else if(levenshteinDistance < minLevenshteinDistance){
minLevenshteinDistance = levenshteinDistance;
line1= sequence1.toString();
line2= sequence2.toString();
}
}
}
br.close();
System.out.println("line1 "+line1);
System.out.println("line2 "+line2);
System.out.println("minlevenshteinDistance "+minLevenshteinDistance);
}catch (IOException e) {
System.out.println(e.getMessage());
}
}
}
- 1. Levenshtein Distancia en VBA
- 2. OCR: distancia Levenshtein ponderada
- 3. Fast Levenshtein distancia en R?
- 4. Damerau-Levenshtein distancia (Editar distancia con transposición) c implementación
- 5. Distancia de Levenshtein en T-SQL
- 6. Similitud de cadenas -> distancia de Levenshtein
- 7. distancia de Levenshtein en la expresión regular
- 8. ¿Cómo se implementa la distancia de Levenshtein en Delphi?
- 9. calculando distancia de Levenshtein usando listas de palabras
- 10. Porcentaje de coincidencia de coincidencia con Levenshtein Coincidencia de distancia
- 11. La forma más eficiente de calcular la distancia de Levenshtein
- 12. Métodos basados en la distancia de Levenshtein Vs Soundex
- 13. Levenshtein Algoritmo de distancia mejor que O (n * m)?
- 14. Implementación de la distancia de Levenshtein para búsqueda mysql/fuzzy?
- 15. levenshtein alternative
- 16. Determina de manera eficiente "cómo está ordenada" una lista, p. Ej. Distancia de Levenshtein
- 17. Concordancia exacta de la palabra de búsqueda posiblemente usando la distancia de Levenshtein
- 18. Numpy matriz simétrica 'inteligente'
- 19. Damerau-Levenshtein php
- 20. Algoritmo de línea ultra simétrica?
- 21. ¿Cómo almacenar una matriz simétrica?
- 22. Acelerando levenshtein/similar_text en PHP
- 23. Cuerda distancia, transposiciones única
- 24. Algoritmo de cifrado de clave simétrica
- 25. cómo representar simétrica de muchos a muchos
- 26. ¿Qué algoritmo de clave simétrica usa SSL?
- 27. SSL es mitad simétrica y mitad asimétrica?
- 28. ¿Cómo modelo una relación simétrica con django?
- 29. Algoritmo para medir la distancia entre las secuencias desordenadas
- 30. Comparar 5000 cadenas con PHP Levenshtein