Algoritmo di confronto delle parole

Question

Sto realizzando uno strumento di importazione CSV per il progetto a cui sto lavorando. Il client deve essere in grado di inserire i dati in Excel, esportarli come CSV e caricarli nel database. Ad esempio ho questo record CSV:

   1,   John Doe,     ACME Comapny   (the typo is on purpose)

Ovviamente, le società sono tenute in una tabella separata e collegate con una chiave esterna, quindi devo scoprire l'ID azienda corretto prima di inserirlo. Ho intenzione di farlo confrontando i nomi delle società nel database con i nomi delle società nel CSV. il confronto dovrebbe restituire 0 se le stringhe sono esattamente le stesse, e restituire un valore che aumenta man mano che le stringhe diventano più diverse, ma strcmp non lo taglia qui perché:

" Acme Company " e "Acme Comapny" dovrebbe avere un indice di differenza molto piccolo, ma " Acme Company " e "Cmea Mpnyaco" dovrebbe avere un indice di differenza molto grande Oppure "Azienda Acme" e "Comp. Acme". dovrebbe anche avere un piccolo indice di differenza, anche se il conteggio dei caratteri è diverso. Inoltre, " Acme Company " e "società Acme" dovrebbe restituire 0.

Quindi se il client crea un tipo durante l'inserimento dei dati, potrei spingerlo a scegliere il nome che molto probabilmente voleva inserire.

Esiste un algoritmo noto per farlo, o forse possiamo inventarne uno :) ?

Answer 1

Potresti dare un'occhiata all'algoritmo Levenshtein Distance come punto di partenza. Valuterà la "distanza" tra due parole.

Questa discussione SO sull'implementazione di uno stile Google " Vuoi dire ...? " il sistema può fornire anche alcune idee.

Answer 2

Non so in quale lingua stai codificando, ma se è PHP, dovresti considerare i seguenti algoritmi:

levenshtein () : restituisce il numero minimo di caratteri che devi sostituire, inserire o eliminare per trasformare una stringa in un'altra.
soundex () : restituisce quattro- chiave soundex carattere di una parola, che dovrebbe essere la stessa chiave di qualsiasi parola dal suono simile.
metafono () : simile a soundex, e forse più efficace per te. È più preciso di soundex () in quanto conosce le regole di base della pronuncia inglese. Le chiavi generate dal metafono sono di lunghezza variabile.
similar_text () : simile a levenshtein (), ma può invece restituire un valore percentuale.

Answer 3

Ho avuto qualche successo con l'algoritmo Levenshtein Distance , c'è anche Soundex .

In che lingua lo stai implementando? potremmo essere in grado di indicare esempi specifici

Answer 4

Ho effettivamente implementato un sistema simile. Ho usato la distanza di Levenshtein (come già suggerito da altri poster), con alcune modifiche. Il problema con la distanza di modifica non modificata (applicata a intere stringhe) è che è sensibile al riordino delle parole, quindi "Acme Digital Incorporated World Company" corrisponderà male a "quotazione Digital Incorporated World Company Acme" e tali riordini erano abbastanza comuni nei miei dati.

L'ho modificato in modo che se la distanza di modifica di intere stringhe fosse troppo grande, l'algoritmo tornasse ad abbinare le parole l'una contro l'altra per trovare una buona corrispondenza parola-parola (costo quadratico, ma se ci fosse un limite erano troppe parole, quindi ha funzionato bene).

Answer 5

Ho preso SoundEx, Levenshtein, somiglianza PHP e doppio metafono e li ho impacchettati in C # in un set di metodi di estensione su String.

Intero post sul blog qui .

Answer 6

Ci sono più algoritmi per fare proprio questo, e la maggior parte dei database ne include anche uno per impostazione predefinita. In realtà è una preoccupazione abbastanza comune.

Se si tratta solo di parole inglesi, ad esempio SQL Server include SOUNDEX che può essere utilizzato per confrontare il suono risultante della parola.

http://msdn.microsoft.com /en-us/library/aa259235%28SQL.80%29.aspx

Answer 7

Lo sto implementando in PHP e ora sto scrivendo un pezzo di codice che spezzerà 2 stringhe in parole e confronterà ciascuna delle parole della prima stringa con le parole della seconda stringa usando levenshtein e accetterà il abbassa i possibili valori. Lo pubblicherò quando ho finito.

Grazie mille.

Aggiornamento: ecco cosa ho escogitato:

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