単語比較アルゴリズム

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

質問

現在取り組んでいるプロジェクトのCSVインポートツールを実行しています。 クライアントは、Excelでデータを入力し、CSVとしてエクスポートし、データベースにアップロードできる必要があります。 たとえば、次のCSVレコードがあります：

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

もちろん、会社は別のテーブルに保持され、外部キーとリンクされているため、挿入する前に正しい会社IDを見つける必要があります。 これを行うには、データベース内の会社名とCSV内の会社名を比較します。 比較は、文字列がまったく同じ場合は0を返し、文字列が異なるほど大きくなる値を返しますが、strcmpはここでそれをカットしません。

<！> quot; Acme Company <！> quot;および<！> quot; Acme Comapny <！> quot;差分インデックスは非常に小さいはずですが、 <！> quot; Acme Company <！> quot;および<！> quot; Cmea Mpnyaco <！> quot;非常に大きな差分インデックスが必要です または<！> quot; Acme Company <！> quot;および<！> quot; Acme Comp。<！> quot;文字数が異なっていても、小さな差分インデックスが必要です。 また、<！> quot; Acme Company <！> quot;および<！> quot; Company Acme <！> quot; 0を返す必要があります。

したがって、クライアントがデータの入力中にタイプを作成した場合、挿入する可能性が最も高い名前を選択するように促すことができます。

これを行うための既知のアルゴリズムはありますか、それとも発明することができます:)

役に立ちましたか？

解決

出発点としてレーベンシュタイン距離アルゴリズムをチェックアウトすることをお勧めします。 <！> quot; distance <！> quot;を評価します。 2つの単語の間。

Googleスタイルの実装に関するこのSOスレッド <！> quot;という意味ですか？<！> quot;システムもいくつかのアイデアを提供する場合があります。

他のヒント

どの言語でコーディングしているのかわかりませんが、PHPの場合は、次のアルゴリズムを検討する必要があります。

levenshtein（） ：必要な最小文字数を返しますある文字列を別の文字列に変換するには、置換、挿入、または削除します。
soundex（） ：4つの値を返します。単語の文字soundexキー。類似した発音の単語のキーと同じである必要があります。
metaphone（） ：soundexと同様、おそらくあなたにとってより効果的です。英語の発音の基本的なルールを知っているので、soundex（）よりも正確です。 Metaphoneで生成されたキーは可変長です。
similar_text（） ：に類似levenshtein（）が、代わりにパーセント値を返すことができます。

レーベンシュタイン距離アルゴリズムでいくつかの成功を収めましたが、 Soundex 。

これをどの言語で実装していますか？特定の例を指すことができるかもしれません

実際に同様のシステムを実装しました。レーベンシュタイン距離を（他のポスターがすでに示唆しているように）いくつかの修正を加えて使用しました。変更されていない編集距離（文字列全体に適用される）の問題は、単語の並べ替えに敏感であるため、<！> quot; Acme Digital Incorporated World Company <！> quot; <！> quot; Digital Incorporated World Company Acme <！> quot;とはあまり一致しません。そのような並べ替えは私のデータでは非常に一般的でした。

文字列全体の編集距離が大きすぎる場合、アルゴリズムは単語と単語の一致を見つけるために互いに一致する単語にフォールバックするように修正しました（2次コストがありますが、言葉が多すぎたので、うまくいきました）。

SoundEx、Levenshtein、PHP類似、およびダブルmetaphoneを取得し、Stringの拡張メソッドの1つのセットでC＃にパッケージ化しました。

ブログの投稿全体をここに。

これを行うには複数のアルゴリズムがあり、ほとんどのデータベースにはデフォルトで1つも含まれています。実際には非常に一般的な懸念事項です。

たとえば英語の単語の場合、SQL ServerにはSOUNDEXが含まれており、これを使用して単語の発音を比較できます。

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

これをPHPで実装していますが、2つの文字列を単語に分割し、最初の文字列の各単語を2番目の文字列の単語とlevenshteinを使用して比較し、受け入れるコードを記述しています可能な値を下げます。完了したら投稿します。

どうもありがとう。

更新：ここに私が思いついたものがあります：

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;
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top