string - para - levenshtein postgres

Similitud de cuerdas-> Levenshtein distancia

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 eficaz. El problema es que el algoritmo no encuentra los siguientes ejemplos como similares:

AIRE ACONDICIONADO
AIRE

El algoritmo dará una distancia de 6. Entonces, para esta palabra de 6 letras (mira 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 cuerdas, pero también teniendo en cuenta casos como el que presenté anteriormente.

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

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

Answer 1

Creo que esto se puede resolver fácilmente empleando el algoritmo más largo de subcadena / subsecuencia común en una de las cadenas (por ejemplo, "conair") y la otra cadena que se anexa a sí misma una vez (por ejemplo, "aircon" -> "airconaircon").

Código de muestra 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;
}

Salida 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 2

Dividiría el término en unigramas, bigramas y trigramas, y luego calcularía la similitud del coseno.

Answer 3

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

Answer 4

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

CONAIR
RCIAON

que puede que no sea lo que quieres.

La otra forma de definir similitud sería encontrar subcadenas comunes para 2 cadenas. Puede crear un árbol de sufijos y descubrir todas las subcadenas comunes y tratar de determinar qué tan similares son. Entonces, por ejemplo, su árbol de sufijos daría subcadenas comunes como CON y AIR que cubren toda la palabra (para sus 2 cadenas) y, por lo tanto, las concluyen como similares.

Answer 5

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

Answer 6

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

La similitud de la cadena también se puede encontrar usando el método de Subsecuencia Común Más Larga y luego puedes ver a Levenstein en el resto de lo no coincidente.

En caso de que quiera hacer un enfoque en grupo, la siguiente respuesta parece tener algunos detalles, pero obviamente es más difícil de implementar.

Answer 7

intente usar otras medidas de similitud como sorenson, jaccard y jaro_winkler

personalmente soy un gran fan de jaro winkler ya que cumplió mi propósito muchas veces.

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