algoritmo de comparação de palavra
-
19-08-2019 - |
Pergunta
Estou fazendo uma ferramenta de importação CSV para o projeto que estou trabalhando. As necessidades do cliente para ser capaz de inserir os dados no Excel, exportá-los como CSV e enviá-los para o banco de dados. Por exemplo, eu tenho este registro CSV:
1, John Doe, ACME Comapny (the typo is on purpose)
Claro, as empresas são mantidos em uma tabela separada e ligado com uma chave estrangeira, então eu preciso descobrir o ID da empresa correta antes de inserir. Eu pretendo fazer isso comparando os nomes de empresa no banco de dados com os nomes empresa no CSV. a comparação deve retornar 0 se as cordas são exatamente o mesmo, e retornar algum valor que aumenta à medida que as cordas obter mais diferente, mas strcmp não cortá-la aqui porque:
"Acme Company" e "Acme Comapny" deve ter um pequeno índice de diferença, mas "Acme Company" e "Comecon Mpnyaco" deve ter um índice de diferença muito grande Ou "a Empresa Acme" e "Acme Comp." também deve ter um pequeno índice de diferença, embora a contagem de caracteres é diferente. Além disso, "Acme Company" e "Empresa Acme" deve retornar 0.
Então, se o cliente faz um tipo enquanto se introduzem dados, eu poderia levá-lo a escolher o nome que ele provavelmente queria inserção.
Existe um algoritmo conhecido para fazer isso, ou talvez podemos inventar um :) ?
Solução
Você pode querer verificar o algoritmo Levenshtein Distância como um ponto de partida. Ele vai avaliar a "distância" entre duas palavras.
Este SO enfiar na implementação de um estilo Google "Você quer dizer...?" sistema pode fornecer algumas idéias também.
Outras dicas
Eu não sei o idioma que você está programando, mas se for PHP, você deve considerar os seguintes algoritmos:
levenshtein () : Retorna o número mínimo de caracteres que você tem que substituir, inserir ou excluir para transformar uma string em outra.
soundex () : Retorna a quatro personagem-chave soundex de uma palavra, o que deve ser o mesmo que a chave para qualquer palavra de som semelhante.
metaphone () : Similar a soundex, e possivelmente mais eficaz para você. É mais preciso do que soundex (), uma vez que conhece as regras básicas de Inglês pronúncia. As chaves metafone gerados são de tamanho variável.
similar_text () : Semelhante ao levenshtein (), mas pode retornar um valor por cento em seu lugar.
Eu tive algum sucesso com o algoritmo Levenshtein Distância , também há Soundex .
Que linguagem você está implementando isso em? que pode ser capaz de apontar exemplos específicos
Eu realmente implementado um sistema similar. Eu usei a distância Levenshtein (como outros cartazes já sugerido), com algumas modificações. O problema com a distância de edição não modificada (aplicada às cordas inteiras) é que ele é sensível a palavra reordenamento, por isso "Acme Digital Incorporated World Company" irá corresponder mal contra o "Digital Incorporated World Company Acme" e tais reordenações foram bastante comum em meus dados.
eu modifiquei para que se a distância de edição de seqüências inteiras era muito grande, o algoritmo caiu para trás de combinar palavras uns contra os outros para encontrar um bom jogo palavra-a-palavra (custo quadrática, mas houve um corte se houver eram muitas palavras, por isso funcionou OK).
Eu tomei Soundex, Levenshtein, PHP similaridade, e dê um duplo metaphone e embalados-los em C #, em um conjunto de métodos de extensão em cadeia.
Há vários algoritmos para fazer exatamente isso, ea maioria das bases de dados até mesmo incluir um por padrão. É realmente uma preocupação bastante comum.
Se o seu apenas cerca de palavras em inglês, SQL Server, por exemplo, inclui SOUNDEX que pode ser usado para comparar o som resultante da palavra.
http://msdn.microsoft.com /en-us/library/aa259235%28SQL.80%29.aspx
Estou implementando-o em PHP, e agora estou escrevendo um pedaço de código que irá romper 2 cordas em palavras e comparar cada uma das palavras do primeiro string com as palavras da segunda corda usando levenshtein e aceitar o LOWES valores possíveis. Ill postá-lo quando eu terminar.
Muito obrigado.
Update: Aqui está o que eu vim acima com:
function myLevenshtein( $str1, $str2 )
{
// prepare the words
$words1 = explode( " ", preg_replace( "/\s+/", " ", trim($str1) ) );
$words2 = explode( " ", preg_replace( "/\s+/", " ", trim($str2) ) );
$found = array(); // array that keeps the best matched words so we don't check them again
$score = 0; // total score
// In my case, strings that have different amount of words can be good matches too
// For example, Acme Company and International Acme Company Ltd. are the same thing
// I will just add the wordcount differencre to the total score, and weigh it more later if needed
$wordDiff = count( $words1 ) - count( $words2 );
foreach( $words1 as $word1 )
{
$minlevWord = "";
$minlev = 1000;
$return = 0;
foreach( $words2 as $word2 )
{
$return = 1;
if( in_array( $word2, $found ) )
continue;
$lev = levenshtein( $word1, $word2 );
if( $lev < $minlev )
{
$minlev = $lev;
$minlevWord = $word2;
}
}
if( !$return )
break;
$score += $minlev;
array_push( $found, $minlevWord );
}
return $score + $wordDiff;
}