Levenshtein distância: a melhor forma de palavras punho trocando posições?

StackOverflow https://stackoverflow.com/questions/828132

Pergunta

Eu tive algum sucesso comparando strings usando o PHP levenshtein função.

No entanto, para duas cordas que contêm substrings que trocaram de posições, o algoritmo contagem dessas como um todo novos substrings.

Por exemplo: 

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

são tratados como tendo menos em comum que: 

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

Eu prefiro um algoritmo que viu que o dois primeiros foram mais similares.

Como eu poderia ir sobre a vinda acima com uma função de comparação que pode identificar substrings que mudaram posição como sendo distinta para edições?

Uma possível abordagem que eu pensava é colocar todas as palavras do string em ordem alfabética, antes da comparação. Isso leva a ordem original das palavras completamente fora da comparação. A desvantagem para isso, porém, é que a mudança apenas a primeira letra de uma palavra pode criar uma perturbação muito maior do que a mudança de uma única letra deve causar.

O que eu estou tentando alcançar é para comparar dois fatos sobre as pessoas que são seqüências de texto livre, e decidir qual a probabilidade de esses fatos são para indicar o mesmo fato. Os fatos pode ser a alguém escola frequentada, o nome do empregador ou editor, por exemplo. Dois registros podem ter a mesma escola escritas de forma diferente, palavras em uma ordem diferente, palavras extras, etc, de modo que a correspondência tem que ser um pouco confuso, se quisermos fazer um bom palpite de que eles se referem à mesma escola. Assim agora ele está trabalhando muito bem para erros de ortografia (estou usando um algoritmo phoenetic semelhante ao metaphone no topo de tudo isso), mas muito mal se você mudar a ordem das palavras em torno do qual parece comum em uma escola: "faculdade xxx" vs "faculdade de xxx".

Foi útil?

Solução

N-gramas

Use N-gramas , que suporte múltipla transposições carácter em todo o texto .

A idéia geral é que você dividir as duas cordas em questão em todos os possíveis substrings 2-3 caracteres (n-gramas) e tratar o número de compartilhados n-gramas entre as duas cadeias como sua semelhança métrica. Este pode ser então normalizado dividindo o número partilhada pelo número total de n-gramas na cadeia mais longa. Esta é trivial para calcular, mas bastante poderoso.

Para as frases de exemplo: 

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

A e B share 18 2 gramas

A e C acção apenas 8 2-gramas

fora do 20 possível total.

Este foi discutido em mais detalhe na Gravano et al. papel .

tf-idf e co-seno similaridade

Uma alternativa não tão trivial, mas fundamentada na teoria da informação seria a de usar o termo frequência-inverso termo frequência de documento (tf-IDF) para pesar os símbolos, vectores de frases construo e, em seguida, usar o cosseno semelhança como a semelhança métrica.

O algoritmo é:

  1. Calcule 2 caracteres freqüências simbólicas (TF) por sentença.
  2. freqüências Calcular inversa sentença (IDF), que é um logaritmo de um quociente do número de todas as sentenças no corpus (neste caso 3) dividido pelo número de vezes que um particular parece simbólicos em todas as frases. Neste caso, th é em todas as frases que ele tem zero conteúdo da informação (log (3/3) = 0). fórmula IDF
  3. Produzir a matriz tf-IDF multiplicando células correspondentes nas tabelas tf e IDF. tfidf
  4. Finalmente, matriz de similaridade calcular co-seno para todos os pares de frases, onde A e B são os pesos da tabela de TF-IDF para os símbolos correspondentes. O intervalo é de 0 (não similar) a 1 (igual).
    co-seno similaridade
    matriz de similaridade

Levenshtein modificações e Metaphone

Com relação a outras respostas. Damerau-levenshtein suportes modificication somente a transposição de duas adjacentes caracteres. Metaphone foi projetado para combinar com palavras que soam o mesmo e não para a correspondência de similaridade.

Outras dicas

Seu fácil. Basta usar a Damerau-Levenshtein distância sobre as palavras em vez de letras.

Explode em espaços, tipo matriz, implode, em seguida, fazer o Levenshtein.

Você também pode tentar isso. (Apenas uma sugestão adicional) 

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

Isso vai mostrar que o 1º e 2º são mais semelhantes do que um e três e dois e três.

Eu tenho vindo a implementar levenshtein em um corretor ortográfico.

O que você está pedindo está contando transposições como uma edição.

Isso é fácil se você só deseja contar transposições de uma palavra de distância. No entanto, para a transposição de palavras 2 ou mais de distância, a adição ao algoritmo é pior !(max(wordorder1.length(), wordorder2.length())) cenário. Adicionando um subalgorithm não-linear a um algoritmo já quadrática não é uma boa idéia.

Esta é a forma como ele iria trabalhar. 

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

Apenas para transposições tocantes. Se você quiser que todos transposições, você teria que para cada trás trabalho posição a partir desse ponto comparando 

1[n] == 2[n-2].... 1[n] == 2[0]....

Assim, você vê por que eles não incluem isso no método padrão.

esta resposta e faça a seguinte alteração: 

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

Isto é para dicionário de pesquisa em um trie, mas para a correspondência a uma única palavra, que é a mesma ideia. Você está fazendo branch-and-bound, e em qualquer momento, você pode fazer qualquer mudança que você quiser, contanto que você dar-lhe um custo.

Elimine palavras duplicadas entre as duas cordas e então usar Levenshtein.

Creio que este é um excelente exemplo para usar um espaço vetorial motor de busca .

Nesta técnica, cada documento torna-se, essencialmente, um vector com o maior número de dimensões, como não são palavras diferentes em todo o corpo; documentos similares, em seguida, ocupam as áreas vizinhas em que o espaço vetor. uma agradável propriedade deste modelo é que as consultas também são apenas documentos: para responder a uma consulta, basta calcular a sua posição no espaço vetorial, e seus resultados são os documentos mais próximo que você pode encontrar. Estou certo de que existem soluções obter-and-go para PHP lá fora.

para fuzzify resultados de espaço vetorial, você poderia considerar fazer decorrente técnica / semelhante linguagem natural de processamento e uso levenshtein construir consultas secundárias para palavras semelhantes que ocorrem em seu vocabulário geral.

Se a primeira string é A e o segundo é B:

  1. Split A e B em palavras
  2. Para cada palavra A, encontrar a melhor palavra correspondente em B (usando levenshtein)
  3. Remova a palavra de B e colocá-lo no B * no mesmo índice que a palavra correspondente em um.
  4. Agora compare A e B *

Exemplo: 

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

Você poderia melhorar a etapa 2 por fazê-lo em vários passes, encontrando apenas correspondências exatas no início, em seguida, encontrar correspondências próximas palavras em um que não têm um companheiro em B * ainda, então partidas menos próximos, etc.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top