levenshtein - java string similarity master

¿Cuál es una buena métrica para decidir si 2 cadenas son "suficientemente similares"?

Question

Estoy trabajando en un algoritmo muy preliminar de primer borrador para determinar qué tan similares son las 2 cadenas. También estoy usando Levenshtein Distance para calcular la distancia de edición entre las cuerdas.

Lo que estoy haciendo actualmente es básicamente tomar el número total de ediciones y dividirlo por el tamaño de la cadena más grande. Si ese valor está por debajo de algún umbral, actualmente establecido aleatoriamente en 25%, entonces son "suficientemente similares".

Sin embargo, esto es totalmente arbitrario y no creo que sea una buena manera de calcular la similitud. ¿Existe algún tipo de ecuación matemática o enfoque de probabilidad / estadística para tomar los datos de Levenshtein Distance y usarlos para decir "sí, estas cadenas son lo suficientemente similares en función del número de ediciones realizadas y el tamaño de las cadenas"?

Además, la clave aquí es que estoy usando un umbral arbitrario y preferiría no hacerlo. ¿Cómo puedo calcular este umbral en lugar de asignarlo para que pueda decir con seguridad que 2 cadenas son "suficientemente similares" ?

ACTUALIZAR

Estoy comparando cadenas que representan un seguimiento de la pila de Java. La razón por la que quiero hacer esto es agrupar un montón de trazados de pila dados por similitud y usarlo como un filtro para ordenar "cosas" :) Esta agrupación es importante por una razón de nivel superior que no puedo compartir públicamente.

Hasta ahora, mi algoritmo (pseudo código) está más o menos en la línea de:

/*
 * The input lists represent the Strings I want to test for similarity. The
 * Strings are split apart based on new lines / carriage returns because Java
 * stack traces are not a giant one-line String, rather a multi-line String.
 * So each element in the input lists is a "line" from its stack trace.
 */
calculate similarity (List<String> list1, List<String> list2) {

    length1 = 0;
    length2 = 0;
    levenshteinDistance = 0;

    iterator1 = list1.iterator();
    iterator2 = list2.iterator();

    while ( iterator1.hasNext() && iterator2.hasNext() ) {

        // skip blank/empty lines because they are not interesting
        str1 = iterator1.next();    length1 += str1.length();
        str2 = iterator2.next();    length2 += str2.length();

        levensteinDistance += getLevenshteinDistance(str1, str2);
    }

    // handle the rest of the lines from the iterator that has not terminated

    difference = levenshteinDistance / Math.max(length1, length2);

    return (difference < 0.25) ? true : false; // <- arbitrary threshold, yuck!
}

Answer 1

¿Qué hay de usar la similitud de coseno? Esta es una técnica general para evaluar la similitud entre dos textos. Funciona de la siguiente manera:

Toma todas las letras de ambas cadenas y construye una tabla como esta:

Letter | String1 | String2

Esto puede ser una simple tabla hash o lo que sea.

En la columna de letras ponga cada letra y en las columnas de cadena coloque su frecuencia dentro de esa cadena (si una letra no aparece en una cadena, el valor es 0).

Se llama similitud de coseno porque interpreta cada una de las dos columnas de cadena como vectores, donde cada componente es el número asociado a una letra. A continuación, calcula el coseno del "ángulo" entre los vectores como:

C = (V1 * V2) / (|V1| * |V2|)

El numerador es el producto puntual, que es la suma de los productos de los componentes correspondientes, y el denominador es el producto de los tamaños de los vectores.

Qué tan cerca está C de 1 te da cuán similares son las cuerdas.

Puede parecer complicado, pero solo son unas pocas líneas de código una vez que entiendes la idea.

Veamos un ejemplo: consideremos las cuerdas.

s1 = aabccdd
s2 = ababcd

La mesa se ve como:

Letter a b c d
s1     2 1 2 2
s2     2 2 1 1

Y por lo tanto:

C = (V1 * V2) / (|V1| * |V2|) = 
(2 * 2 + 1 * 2 + 2 * 1 + 2 * 1) / (sqrt(13) * sqrt(10)) = 0.877

Así que son "bastante" similares.

Answer 2

Aquí está mi opinión sobre esto: solo una larga historia para considerar y no necesariamente una respuesta a su problema:

He hecho algo similar en el pasado en el que trataría de determinar si alguien estaba plagiando simplemente reorganizando las oraciones manteniendo el mismo tipo de mensaje.

1 "los niños deben jugar mientras cenamos"
2 "mientras cenamos, los niños deben jugar"
3 "deberíamos comer niños mientras jugamos"

Entonces, levenshtein no sería de mucha utilidad aquí porque es lineal y cada una sería considerablemente diferente. La diferencia estándar pasaría la prueba y el estudiante se saldría con la suya.

Así que rompí cada palabra en las oraciones y volví a compilar las oraciones como matrices, luego las comparé para determinar primero si la palabra existía en cada matriz, y dónde estaba en relación con la última. Luego, cada palabra verificará la siguiente en la matriz para determinar si había palabras secuenciales, como en mis oraciones de ejemplo sobre las líneas 1 y 2. Entonces, si hubiera palabras secuenciales, compondría una cadena de cada secuencia común a cada matriz y luego tratar de encontrar diferencias en las palabras restantes. Cuantas menos palabras queden, más probabilidades hay de que rellenen para que parezca menos plagiado.

"Mientras cenamos, creo que los niños deberían jugar"

Luego, "Pienso" se evalúa y se considera un relleno basado en un léxico de palabras clave: esta parte es difícil de describir aquí.

Este fue un proyecto complejo que hizo mucho más que lo que describí y no una simple porción de código que pueda compartir fácilmente, pero la idea anterior no es demasiado difícil de replicar.

Buena suerte. Me interesa lo que otros miembros de SO tienen que decir sobre tu pregunta.

Answer 3

Dado que la distancia de Levenshtein nunca es mayor que la longitud de la cadena más larga, ciertamente cambiaría el denominador de (length1 + length2) a Math.max(length1, length2) . Esto normalizaría la métrica entre cero y uno.

Ahora, es imposible responder lo que es "lo suficientemente similar" para sus necesidades en función de la información proporcionada. Personalmente, trato de evitar funciones de paso como las que tiene con el límite de 0.25, prefiriendo valores continuos de un intervalo conocido. ¿Quizás sería mejor alimentar los valores de "similitud" (o "distancia") continuos en algoritmos de nivel superior en lugar de transformar esos valores en valores binarios?

Answer 4

Las trazas de pila están en un formato susceptible de análisis. Simplemente analizaría los seguimientos de pila utilizando una biblioteca de análisis y luego podrá extraer el contenido semántico que quiera comparar.

Los algoritmos de similitud serán más lentos y difíciles de depurar cuando las cadenas no se comparan como se espera.