como calcular a similaridade entre duas seqüências de caracteres no MYSQL

Se eu tiver duas seqüências no mysql:

 @ a = "Bem-vindo ao estouro de pilha"
 @ b = "Olá para empilhar estouro";

Existe uma maneira de obter a porcentagem de similaridade entre essas duas seqüências usando MYSQL? aqui, por exemplo, 3 palavras são semelhantes e, portanto, a semelhança deve ser algo como:
contagem (palavras semelhantes entre @a e @b) / (contagem (@a) + contagem (@b) – contagem (interseção))
e assim o resultado é 3 / (4 + 4 – 3) = 0,6
qualquer ideia é muito apreciada!

você pode usar esta function (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 

e para obtê-lo como XX% use esta function

 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 

Eu não acho que haja uma maneira simples de fazer uma única etapa para fazer isso – o material da linguagem natural é projetado principalmente para a pesquisa “parecida com o google”, que soa diferente do que você está tentando fazer.

Dependendo do que você está realmente tentando fazer – eu suponho que você deixou de lado muitos detalhes – eu gostaria de:

  • crie uma tabela na qual você divide cada string em palavras, tudo em letras minúsculas, retirando espaços e pontuação – no seu exemplo, você acabaria com:

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

Você pode então executar consultas nessa tabela – por exemplo

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

dá a interseção.

Você pode então criar uma function ou similar para calcular a similaridade de acordo com sua fórmula.

Não muito limpo, mas deve ter um bom desempenho, é principalmente relacional e deve ser amplamente independente do idioma. Para lidar com possíveis erros de digitação, você poderia calcular o soundex – isso permitiria comparar “stack” com “stak” e ver como eles são parecidos, embora isso não funcione de forma confiável para outros idiomas além do inglês.

Você pode tentar o algoritmo SOUNDEX, dê uma olhada aqui 🙂

SOUNDEX MySQL

EDIT 1:

Talvez este link sobre o processamento de linguagem natural com o MySQL possa ser útil

Pesquisas de Texto Completo em Linguagem Natural

Como encontrar resultados semelhantes e classificar por semelhança?

HTH!

Isso pode ser útil se você não quiser escrever seus próprios algoritmos:

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