cómo calcular la similitud entre dos cadenas en MySQL

Question

si tengo dos cadenas en MySQL:

 
@a="Welcome to Stack Overflow" 
@b=" Hello to stack overflow"; 

¿Hay una manera de obtener el porcentaje de similitud entre los dos cuerdas usando MySQL? aquí por ejemplo 3 palabras son similares y por lo tanto la similitud debería ser algo así como:
count (palabras similares entre @a y @b)/(cuenta (@a) + conteo (@b) - count (intersección))
y por lo tanto el resultado es 3/(4 + 4 - 3) = 0.6
¡cualquier idea es muy apreciada!

Answer 1

puede utilizar esta función (cop^H^H^Hadapted de http://www.artfulsoftware.com/infotree/queries.php#552):

CREATE FUNCTION `levenshtein`(s1 text, s2 text) RETURNS int(11) 
    DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; 
    DECLARE s1_char CHAR; 
    DECLARE cv0, cv1 text; 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
    IF s1 = s2 THEN 
     RETURN 0; 
    ELSEIF s1_len = 0 THEN 
     RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
     RETURN s1_len; 
    ELSE 
     WHILE j <= s2_len DO 
     SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
     END WHILE; 
     WHILE i <= s1_len DO 
     SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
     WHILE j <= s2_len DO 
      SET c = c + 1; 
      IF s1_char = SUBSTRING(s2, j, 1) THEN 
      SET cost = 0; ELSE SET cost = 1; 
      END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
      IF c > c_temp THEN SET c = c_temp; END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
      IF c > c_temp THEN 
       SET c = c_temp; 
      END IF; 
      SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
     END WHILE; 
     SET cv1 = cv0, i = i + 1; 
     END WHILE; 
    END IF; 
    RETURN c; 
    END 

y para conseguirlo como el uso XX% esta función

CREATE FUNCTION `levenshtein_ratio`(s1 text, s2 text) RETURNS int(11) 
    DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, max_len INT; 
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2); 
    IF s1_len > s2_len THEN 
     SET max_len = s1_len; 
    ELSE 
     SET max_len = s2_len; 
    END IF; 
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2)/max_len) * 100); 
    END 

Answer 2

Puede probar el algoritmo de SOUNDEX, echa un vistazo aquí :)

SOUNDEX MySQL

EDIT 1:

Tal vez este enlace sobre el procesamiento del lenguaje natural con MySQL podría ser útil

Natural Language Full-Text Searches

How to find similar results and sort by similarity?

HTH!

Answer 3

Esto podría ser de ayuda para usted si usted no quiere escribir sus propios algoritmos:

http://dev.mysql.com/doc/refman/5.0/en/fulltext-natural-language.html

Answer 4

No creo que hay una buena, de un solo paso forma de consulta para hacer esto - la el material de lenguaje natural está diseñado principalmente para la búsqueda de "google-like", que suena diferente a lo que estás tratando de hacer.

Dependiendo de lo que en realidad está tratando de hacer - Asumo que ha dejado una gran cantidad de detalle - yo:

• crear una tabla en la que se divide cada cadena en palabras, toda en minúsculas, excluyendo espacios y puntuacion - en su ejemplo, que terminarías con:

  string_id    word 
  
  1      hello 
  1      from 
  1      stack 
  1      overflow 
  2      welcome 
  2      from 
  2      stack 
  2      overflow 
  

a continuación, puede ejecutar consultas en esa mesa - por ejemplo,

select count(*) 
from stringWords 
where string_id = 2 
and word in 
    (select word 
    from stringWords 
    where string_id = 1); 

le ofrece la intersección.

A continuación, puede crear una función o similar para calcular la similitud de acuerdo con su fórmula.

No muy limpio, pero debe funcionar bastante rápido, es principalmente relacional, y debe ser en gran medida independiente del lenguaje. Para tratar posibles errores tipográficos, podría calcular el soundex, esto le permitiría comparar "stack" con "stak" y ver qué tan similares son en realidad, aunque esto no funciona de manera confiable para otros idiomas además del inglés.