Word-Vergleichsalgorithmus

Question

Ich mache ein CSV-Import-Tool für das Projekt arbeite ich an. Der Client muss in der Lage sein, die Daten in Excel exportieren sie als CSV und laden Sie in die Datenbank einzugeben. Zum Beispiel habe ich diesen CSV-Datensatz:

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

Natürlich sind die Unternehmen in einer separaten Tabelle gehalten und mit einem Fremdschlüssel verbunden, also muß ich die richtige Identifizierungsnummer vor dem Einfügen entdecken. Ich plane, dies zu tun, indem Sie die Firmennamen in der Datenbank mit den Firmennamen in der CSV-Vergleich. der Vergleich sollte 0 zurückgeben, wenn die Saiten genau gleich sind, und einen Wert zurückgeben, die größer wird als die Saiten mehr anders, aber strcmp nicht schneidet hier, weil:

"Acme Company" und "Acme Comapny" sollte einen sehr kleinen Unterschied Index haben, aber „Acme Company“ und „RGW Mpnyaco“ sollte einen sehr großen Unterschied Index Oder "Acme Company" und "Acme Comp." sollte auch einen kleinen Unterschied Index haben, auch wenn die Anzahl der Zeichen unterscheidet. Auch "Acme Company" und "Unternehmen Acme" sollte 0 zurück.

Also, wenn der Client eine Art macht, während die Daten eingegeben haben, konnte ich ihn auffordern, den Namen, den er höchstwahrscheinlich einfügen wollte wählen.

Sie haben einen bekannten Algorithmus, dies zu tun, oder vielleicht können wir eine erfinden :) ?

Answer 1

Sie können die Levenshtein Entfernung Algorithmus als Ausgangspunkt zu sehen. Es wird die „Distanz“ zwischen zwei Wörtern bewerten.

Diese SO Thread auf die Implementierung eines Google-Stil "Meinst du...?" System kann einige Ideen als auch bieten.

Answer 2

Ich weiß nicht, welche Sprache Sie Codierung in, aber wenn es PHP ist, sollten Sie die folgenden Algorithmen berücksichtigen:

levenshtein () : Gibt die minimale Anzahl von Zeichen haben Sie ersetzen, einfügen oder löschen eine Zeichenfolge in eine andere zu verwandeln.
soundex () : Gibt die Vier- Zeichen soundex Schlüssel eines Wortes, die die gleiche wie die Schlüssel für alle ähnlich klingendes Wort sein sollte.
Metaphone () : Ähnlich wie soundex, und möglicherweise effektiver für Sie. Es ist genauer als soundex (), da sie die Grundregeln der englischen Aussprache kennt. Die Metaphone erzeugten Schlüssel sind von variabler Länge.
similar_text () : Ähnlich levenshtein (), aber es kann stattdessen einen Prozentwert zurück.

Answer 3

Ich habe einen gewissen Erfolg hatte mit dem Levenshtein Entfernung Algorithmus gibt es auch Soundex .

Welche Sprache setzen Sie diese in? wir können auf spezifische Beispiele

zum Punkt der Lage sein,

Answer 4

Ich habe tatsächlich ein ähnliches System implementiert. Ich benutzte die Levenshtein-Distanz (wie andere Plakate bereits vorgeschlagen), mit einigen Modifikationen. Das Problem mit nicht modifizierten Editierdistanz (auf ganze Strings angewendet wird) ist, dass es zu Wort Neuordnungs empfindlich ist, so „Acme Digitale Incorporated World Company“ entsprechen, werden schlecht gegen „Digital Incorporated World Company Acme“ und solche Umordnungen waren in meinen Daten durchaus üblich.

Ich änderte es, dass dann, wenn die Edit-Distanz von ganzen Strings zu groß war, der Algorithmus, um passende Worte gegeneinander fiel wieder ein gutes Wort zu Wort finden Spiel (quadratisch Kosten, aber es war, wenn ein Cutoff dort zu viele Worte waren, so es funktionierte OK).

Answer 5

Ich habe genommen SoundEx, Levenshtein, PHP Ähnlichkeit und Doppel Metaphone und sie in einer Reihe von Erweiterungsmethoden auf String in C # verpackt werden.

Entire Blog-Post hier .

Answer 6

Es gibt mehrere Algorithmen, genau das zu tun, und die meisten Datenbanken auch eine standardmäßig enthalten. Es ist eigentlich ein recht häufiges Problem.

Wenn sie nur über die englischen Worte, SQL Server beispielsweise enthalten SOUNDEX, die verwendet werden können, auf dem resultierenden Klang des Wortes zu vergleichen.

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

Answer 7

Ich bin die Umsetzung in PHP, und ich bin jetzt ein Stück Code zu schreiben, die zwei Strings in Worten brechen werden und jedes der Worte aus dem ersten String mit den Worten des zweiten Strings vergleichen levenshtein mit und übernehmen die lowes mögliche Werte. Ill post it, wenn ich fertig bin.

Vielen Dank.

Update: Hier ist, was ich habe kommen mit:

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