Algoritmo Strike a Match
Introdução
Um exemplo clássico de recuperação de informações usando pesquisa por similaridade é inserir uma palavra-chave no campo de busca no site da Amazon para recuperar descrições de produtos relacionados a essa palavra-chave. Os algoritmos de correspondência de strings aproximados podem ser classificados como algoritmos de equivalência e algoritmos de classificação de similaridade. Este artigo apresenta um algoritmo de classificação de similaridade, junto com sua métrica de similaridade de string associada. O exemplo de implementação na linguagem Java também é fornecido para que seja facilmente incorporado em aplicativos.O algoritmo foi aplicado com sucesso à recuperação de termos de um tesauro eletrônico de domínio específico, e também à recuperação de nomes de lugares geográficos.
O algoritmo foi conduzido pelos seguintes requisitos:
- O verdadeiro reflexo da semelhança lexical - strings com pequenas diferenças devem ser reconhecidas como semelhantes. Em particular, uma sobreposição significativa da substring deve apontar para um alto nível de similaridade entre as strings.
- Robustez para mudanças na ordem das palavras - duas strings que contêm as mesmas palavras, mas em uma ordem diferente, devem ser reconhecidas como semelhantes. Por outro lado, se uma string for apenas um anagrama aleatório dos caracteres contidos na outra, ela deve (geralmente) ser reconhecida como diferente.
- Independência de idioma - o algoritmo deve funcionar não apenas em inglês, mas em muitos idiomas diferentes.
Por exemplo, 'FRANÇA' deve ser semelhante a 'FRANÇAIS' e 'REPÚBLICA DA FRANÇA', e 'REPÚBLICA DA FRANÇA' deve ser semelhante a 'REPÚBLICA FRANCESA' e 'REPÚBLICA FRANCAISE'. Também podemos fazer declarações relativas de semelhança.
Por exemplo, 'FRANCÊS' deve ser mais semelhante a 'COMIDA FRANCESA' do que a 'COZINHA FRANCESA', porque o tamanho da substring comum é o mesmo em ambos os casos e 'COMIDA FRANCESA' é a mais curta das duas strings.
Alguns outros Algoritmos
Existem algoritmos como o Algoritmo Soundex, Distância de Edição e Substring comum mais longa que não funcionam bem com esses requisitos. O algoritmo Soundex é um algoritmo de equivalência, portanto, simplesmente declara se duas strings são ou não semelhantes. No entanto, não reconheceria qualquer semelhança entre 'FRANÇA' e 'REPÚBLICA DA FRANÇA', uma vez que começam com letras diferentes. O algoritmo de Distância de Edição reconheceria alguma semelhança entre as duas strings, mas classificaria 'FRANÇA' e 'QUEBEC' (com uma distância de 6) como sendo mais semelhantes do que 'FRANÇA' e 'REPÚBLICA DA FRANÇA' (que têm uma distância de 12). A Substring Comum Mais Longa daria a 'FRANÇA' e 'REPÚBLICA DA FRANÇA' uma classificação bastante boa de similaridade (um substring comum de comprimento 6). No entanto, é decepcionante que, de acordo com essa métrica, a string 'REPÚBLICA FRANCESA' seja igualmente semelhante às duas strings 'REPÚBLICA DA FRANÇA' e 'REPÚBLICA DE CUBA'.
Métrica
O presente algoritmo procura corrigir as desvantagens dos algoritmos mencionados através de uma métrica de similaridade de strings que recompensa tanto substrings comuns quanto uma ordenação comum dessas substrings. Além disso, também considera não apenas a única substring comum mais longa, mas também outras substrings comuns.
Os requisitos podem parecer difíceis de satisfazer, mas a solução é aparentemente simples:
A intenção é que, ao considerar os caracteres adjacentes, eu leve em consideração não apenas os caracteres, mas também a ordem dos caracteres na string original, uma vez que cada par de caracteres contém um pouco de informação sobre a ordem original.
Por exemplo, vamos utilizar o algoritmo para comparar duas strings 'France' e 'French'. Primeiro, mapeamos os dois para seus caracteres maiúsculos (tornando o algoritmo insensível às diferenças de maiúsculas e minúsculas) e, em seguida, divido-os em seus pares de caracteres:
FRANCE: {FR, RA, AN, NC, CE}
FRENCH: {FR, RE, EN, NC, CH}
Então, decidimos quais pares de caracteres estão em ambas as strings. Neste caso, a interseção é {FR, NC}. Veja como uma métrica numérica que reflete o tamanho da interseção em relação aos tamanhos das strings originais. Se pares (x) é a função que gera os pares de letras adjacentes em uma string, então minha métrica numérica de similaridade é:
A semelhança entre duas strings s1 e s2 é duas vezes o número de pares de caracteres comuns a ambas as strings dividido pela soma do número de pares de caracteres nas duas strings. (As barras verticais na fórmula significam '? Tamanho de ?'). Observe que a fórmula classifica strings completamente diferentes com um valor de similaridade de 0, uma vez que o tamanho da interseção do par de letras no numerador da fração será zero. Por outro lado, se você comparar uma string (não vazia) com ela mesma, a similaridade é 1. Para nossa comparação de 'FRANCE' e 'FRENCH', a métrica é calculada da seguinte forma:
Dado que os valores da métrica estão sempre entre 0 e 1, também é muito natural expressar esses valores como porcentagens. Por exemplo, a semelhança entre 'FRANCE' e 'FRENCH' é de 40%.
Resultados de Classificação
Normalmente, não queremos apenas saber o quão semelhantes são duas strings. Queremos saber quais de um conjunto de strings conhecidas são mais semelhantes a uma determinada string. Por exemplo, qual das strings 'Heard', 'Healthy', 'Help', 'Herded', 'Sealed' ou 'Sold' é mais semelhante à string 'Healed'?
Tudo o que precisamos fazer para responder à pergunta é encontrar a semelhança entre 'Curado' e cada uma das outras palavras e, em seguida, classificar os resultados na ordem desses valores. Os resultados para este exemplo são apresentados na Tabela 1.
| Palavra | Similaridade |
| Sealed | 80% |
| Healthy | 55% |
| Heard | 44% |
| Herded | 40% |
| Help | 25% |
| Sold | 0% |
Tabela 1: Encontrar a palavra mais semelhante a 'Healed'
Exemplo Real
Agora, um exemplo que está um pouco mais próximo do mundo real. Suponha que estejamos construindo um site que vende livros e queremos permitir que nossos usuários digitem uma string para pesquisar os títulos dos livros em nosso banco de dados. Quando a string do usuário não corresponde exatamente a nenhum dos livros em nosso banco de dados, retornamos uma lista dos livros cujo título é mais semelhante.
A Tabela 2 contém uma lista de títulos de livros em sua primeira coluna. Se pesquisarmos nesses títulos de livros com as strings de consulta 'Web Database Applications', 'PHP Web Applications' e 'Web Aplications' usando a métrica descrita, obteremos os resultados mostrados nas seis colunas mais à direita da tabela. (Observe o erro ortográfico intencional de 'Applications' na terceira string.) As colunas 'Classificação' indicam a ordem em que os livros seriam devolvidos. Cada classificação é qualificada por seu valor de similaridade percentual correspondente (arredondado para o número inteiro mais próximo) na próxima coluna. As três cadeias de caracteres de entrada foram cuidadosamente escolhidas para direcionar o livro 'Web Database Applications with PHP & MySQL', mas com uma qualidade decrescente da cadeia de caracteres de entrada conforme você passa de 'Web Database Applications' para 'Web Aplications'.
| Web Database Applications | PHP Web Applications | Web Aplications | ||||
|---|---|---|---|---|---|---|
| Título do Livro | Classificação | Valor | Classificação | Valor | Classificação | Valor |
| Web Database Applications with PHP & MySQL | 1 | 82% | 1 | 68% | 1 | 59% |
| Creating Database Web Applications with PHP and ASP | 2 | 71% | 3 | 59% | 3 | 50% |
| Building Database Applications on the Web Using PHP3 | 3 | 70% | 4 | 58% | 4 | 49% |
| Building Web Database Applications with Visual Studio 6 | 4 | 67% | 5 | 47% | 5 | 46% |
| Web Application Development With PHP | 5 | 51% | 2 | 67% | 2 | 56% |
| WebRAD: Building Database Applications on the Web with Visual FoxPro and Web Connection | 6 | 49% | 6 | 34% | 6 | 32% |
| Structural Assessment: The Role of Large and Full-Scale Testing | 7 | 12% | 8 | 7% | 8 | 7% |
| How to Find a Scholarship Online | 8 | 10% | 7 | 11% | 7 | 12% |
Tabela 2: Três pesquisas por um livro
Dois resultados principais são mostrados na tabela. Em primeiro lugar, o livro alvo é pontuado como a melhor correspondência em cada caso e, em segundo lugar, os valores de similaridade diminuem à medida que você se move da esquerda para a direita na tabela, refletindo a degradação pretendida na qualidade da entrada.
Ao apresentar os resultados das pesquisas aos usuários, você normalmente definiria um valor limite de, digamos, 20%, e mostraria apenas os 10 principais resultados ou mais que estivessem acima do limite. (Não queremos perder a confiança de nossos usuários exibindo resultados irrelevantes.)
Visão Geral
Este exemplo implementa o algoritmo como uma classe única com três métodos estáticos. Dois desses métodos são privados, portanto, apenas um, compareStrings(), é público aos usuários da classe. Esta é a interface da classe:
import java.util.ArrayList;
public class LetterPairSimilarity {
public static double compareStrings(String str1, String str2) {}
private static ArrayList wordLetterPairs(String str) {}
private static String[] letterPairs(String str) {}
}
Abaixo vamos ver como lidar com os espaços em branco nas strings de entrada. Em geral, descarta-se qualquer par de caracteres que inclua espaços em branco. Isso significa primeiro encontrar as palavras (ou tokens) em suas strings de entrada antes de procurar os pares de caracteres adjacentes.
Em relação à interface apresentada, CompareStrings() chama wordLetterPairs() para cada uma de suas entradas. WordLetterPairs() identifica as palavras em sua string de entrada e usa o método letterPairs() para calcular os pares de caracteres adjacentes em cada uma dessas palavras. Quando compareStrings() coleta os pares de caracteres para cada uma de suas strings de entrada, calcula o valor de retorno de acordo com a métrica de similaridade.
As implementações das funções são apresentadas em ordem bottom-up.
Calculando Pares de Letras
A base do algoritmo é o método que calcula os pares de caracteres contidos na string de entrada. Este método cria uma matriz de Strings para conter seu resultado. Em seguida, itera através da string de entrada, para extrair pares de caracteres e armazená-los na matriz. Finalmente, a array é retornada.
/** @return an array of adjacent letter pairs contained in the input string */
private static String[] letterPairs(String str) {
int numPairs = str.length()-1;
String[] pairs = new String[numPairs];
for (int i=0; i<numPairs; i++) {
pairs[i] = str.substring(i,i+2);
}
return pairs;
}Considerando Espaços em Branco
Este método usa o método split() da classe String para dividir a string de entrada em palavras separadas ou tokens. Em seguida, itera através de cada uma das palavras, computando os pares de caracteres para cada palavra. Os pares de caracteres são adicionados a um ArrayList, que é retornado do método. Um ArrayList é usado, em vez de um array, porque não sabemos com antecedência quantos pares de caracteres serão retornados. (Neste ponto, o programa não sabe quanto espaço em branco a string de entrada contém.)
/** @return an ArrayList of 2-character Strings. */
private static ArrayList wordLetterPairs(String str) {
ArrayList allPairs = new ArrayList();
// Tokenize the string and put the tokens/words into an array
String[] words = str.split("\\s");
// For each word
for (int w=0; w < words.length; w++) {
// Find the pairs of characters
String[] pairsInWord = letterPairs(words[w]);
for (int p=0; p < pairsInWord.length; p++) {
allPairs.add(pairsInWord[p]);
}
}
return allPairs;
}Calculando a Métrica
Esse método público calcula os pares de caracteres das palavras de cada uma das duas strings de entrada e, em seguida, itera por meio de ArrayLists para encontrar o tamanho da interseção. Observe que sempre que uma correspondência é encontrada, esse par de caracteres é removido da segunda lista de vetores para evitar que correspondamos ao mesmo par de caracteres várias vezes. (Caso contrário, 'GGGGG' marcaria uma combinação perfeita contra 'GG'.)
/** @return lexical similarity value in the range [0,1] */
public static double compareStrings(String str1, String str2) {
ArrayList pairs1 = wordLetterPairs(str1.toUpperCase());
ArrayList pairs2 = wordLetterPairs(str2.toUpperCase());
int intersection = 0;
int union = pairs1.size() + pairs2.size();
for (int i=0; i<pairs1.size(); i++) {
Object pair1=pairs1.get(i);
for(int j=0; j<pairs2.size(); j++) {
Object pair2=pairs2.get(j);
if (pair1.equals(pair2)) {
intersection++;
pairs2.remove(j);
break;
}
}
}
return (2.0*intersection)/union;
}