algoritmo de comparação de palavra

Question

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 :) ?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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).

Answer 5

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.

Todo o post aqui .

Answer 6

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

Answer 7

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;
}