14

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

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

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

「AcmeCompany」と「AcmeComapny」の差指数は非常に小さいはずですが、「AcmeCompany」と「CmeaMpnyaco」の差指数は非常に大きいか、「AcmeCompany」と「AcmeComp」です。文字数が異なっていても、差指数も小さいはずです。また、「AcmeCompany」と「CompanyAcme」は0を返す必要があります。

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

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

4

7 に答える 7

18

出発点として、レーベンシュタイン距離アルゴリズムを確認することをお勧めします。2 つの単語間の「距離」を評価します。

Google スタイルの実装に関するこの SO スレッド「ということですか...?」システムもいくつかのアイデアを提供する場合があります。

于 2009-01-23T16:25:23.200 に答える
9

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

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

于 2009-01-23T16:32:06.383 に答える
2

私はレーベンシュタイン距離アルゴリズムである程度の成功を収めました.Soundexもあります。

これをどの言語で実装していますか？具体例を挙げることができるかもしれません

于 2009-01-23T16:26:44.353 に答える
2

私は、SoundEx、Levenshtein、PHP の類似性、および double metaphone を取り上げ、String の 1 つの拡張メソッド セットとして C# にパッケージ化しました。

ブログ投稿全体はこちら.

于 2009-01-26T18:40:38.893 に答える
2

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

文字列全体の編集距離が大きすぎる場合、アルゴリズムが単語同士の照合に戻り、適切な単語間の一致を見つけるように変更しました (二次コストですが、多すぎる場合はカットオフがありました)。言葉なので、うまくいきました）。

于 2009-01-23T16:35:33.990 に答える
0

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

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

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

于 2009-01-23T16:29:13.583 に答える