Similitud de cadenas -> distancia de Levenshtein

Question

Estoy usando el algoritmo de Levenshtein para encontrar la similitud entre dos cadenas. Esta es una parte muy importante del programa que estoy haciendo, por lo que debe ser efectiva. El problema es que el algoritmo no encuentra los siguientes ejemplos como similares:

Conair
AIRE ACONDICIONADO

El algoritmo dará una distancia de 6. Así, por esta palabra de 6 letras (Miras la palabra con la mayor cantidad de letras), la diferencia es de 100% => la similitud es 0%.

Necesito encontrar una manera de encontrar las similitudes entre dos cadenas, pero también teniendo en cuenta casos como el que presenté antes.

¿Hay algún algoritmo mejor que pueda usar? ¿O qué me recomiendan?

EDITAR: También he estudiado el algoritmo "Damerau-Levenshtein", que agrega transposiciones. El problema es que estas transposiciones son solo para caracteres adyacentes (y no para una cantidad de caracteres).

Answer 1

Divido el término en unigrams, bigrams y trigrams, luego calculo la similitud del coseno.

Answer 2

Parece que es posible que desee intentar hacer la distancia de Levenshtein usando sílabas o fonemas en lugar de letras.

Answer 3

Teóricamente, el enfoque que está utilizando es correcto para el problema que está tratando de resolver. Pero Levenstein consideraría solo los personajes individuales los dos conjuntos.

La similitud de la cadena también se puede encontrar utilizando el método Longest Common Subsequence y luego se puede ver Levenstein en el resto de la inigualable.

En caso de que quiera hacer un enfoque agrupado, the following answer parece tener algunos detalles, pero obviamente es más difícil de implementar.

Answer 4

Ordenar las palabras y encontrar a Levenshtein daría una coincidencia del 100% para su ejemplo, pero también daría una coincidencia del 100%, por ej.

CONAIR 
RCIAON 

que podría no ser lo que usted quiere.

La otra forma de definir la similitud sería encontrar subcadenas comunes para 2 cadenas. Puede crear un Suffix Tree y descubrir todas las subcadenas comunes e intentar determinar qué tan similares son. Entonces para su e.g. el árbol de sufijos daría subcadenas comunes como CON & AIR que cubre la palabra completa (para sus 2 cadenas) y por lo tanto las concluye como similares.

Answer 5

creo que esto puede resolverse fácilmente mediante el empleo del/Subsequence algoritmo común más larga subcadena en una de las cadenas (por ejemplo, "Conair") y la otra cadena adjunta a sí mismo una vez (por ejemplo, "aire acondicionado" -> "airconaircon ").

código de ejemplo en C:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

// Returns the length of the longest common substring (LCS) 
// between two given strings. 
// 
// This recursive implementation can be replaced by a 
// more performant dynamic programming implementation. 
size_t llcs(const char* s1, const char* s2) 
{ 
    size_t len[3]; 

    if (*s1 == '\0' || *s2 == '\0') return 0; 

    len[0] = (*s1 == *s2) + llcs(s1 + 1, s2 + 1); 
    len[1] = llcs(s1 + 1, s2); 
    len[2] = llcs(s1, s2 + 1); 

    if (len[0] < len[1]) len[0] = len[1]; 
    if (len[0] < len[2]) len[0] = len[2]; 

    return len[0]; 
} 

// Returns similarity of two given strings in the range 
// from 0.0 to 1.0 (1.0 for equal strings). 
double similarity(const char* s1, const char* s2) 
{ 
    size_t s1len = strlen(s1); 
    size_t s2len = strlen(s2); 
    double sim; 

    if (s1len == 0 && s2len == 0) 
    { 
    // Two empty strings are equal 
    sim = 1; 
    } 
    else 
    { 
    size_t len; 
    // Append s1 to itself in s1s1 (e.g. "aircon" -> "airconaircon") 
    char* s1s1 = malloc(s1len * 2 + 1); 
    strcpy(s1s1, s1); 
    strcpy(s1s1 + s1len, s1); 

    // Find the length of the LCS between s1s1 and s2 
    // (e.g. between "airconaircon" and "conair") 
    len = llcs(s1s1, s2); 
    // We need it not longer than s1 (e.g. "aircon") 
    // since we're actually comparing s1 and s2 
    if (len > s1len) len = s1len; 

    len *= 2; 

    // Prevent 100% similarity between a string and its 
    // cyclically shifted version (e.g. "aircon" and "conair") 
    if (len == s1len + s2len && strcmp(s1, s2) != 0) len--; 

    // Get the final measure of the similarity 
    sim = (double)len/(s1len + s2len); 

    free(s1s1); 
    } 

    return sim; 
} 

int main(int argc, char** argv) 
{ 
    if (argc == 3) 
    printf("Similarity of \"%s\" and \"%s\" is %.2f%%\n", 
      argv[1], argv[2], 100 * similarity(argv[1], argv[2])); 
    else 
    printf("Usage:\n %s string1 string2\n", 
      argv[0]); 
    return 0; 
} 

Resultado de muestra:

Similarity of "123" and "123" is 100.00% 
Similarity of "123" and "1234" is 85.71% 
Similarity of "0123" and "123" is 85.71% 
Similarity of "a" and "aa" is 66.67% 
Similarity of "aa" and "a" is 66.67% 
Similarity of "aaaaaaa" and "aaaaaa" is 92.31% 
Similarity of "aaaaaa" and "aaaaaaa" is 92.31% 
Similarity of "aircon" and "conair" is 91.67% 
Similarity of "spit" and "pits" is 87.50% 
Similarity of "pits" and "spit" is 87.50% 
Similarity of "spits" and "pits" is 88.89% 
Similarity of "pits" and "spits" is 88.89% 

Answer 6

echar un vistazo para Needleman-Wunsch, o algoritmos de Smith-Waterman. Se utilizan para manejar la coincidencia de cadenas a través de una distancia de edición adaptada para secuencias de ADN, donde cualquier tipo de inserciones, reversiones, transposones pueden ocurrir, a cualquier longitud, en cualquier lugar. Al decir esto, necesito agregar que para una cadena suficientemente larga no hay una solución óptima. Y no olvide que el costo de edición depende del contexto de uso del algoritmo (un problema de semántica), mientras que cualquier algoritmo es siempre una máquina sintáctica.

Answer 7

Use otras medidas de similitud como Sorenson, Jaccard y jaro_winkler

Personalmente soy gran fan de Winkler Jaro ya que sirvió mi propósito muchas veces.

from Levenshtein import jaro_winkler 
In [2]: jaro_winkler("conair","aircon") 
Out[2]: 0.8333333333333334