56

ユーザーは、会社名を含む大きな文字列をカット アンド ペーストしてインポートします。

会社名の既存の MYSQL データベースがあり、それぞれに一意の company_id があります。

文字列を解析して、ユーザーが入力した会社名のそれぞれにあいまい一致を割り当てられるようにしたいと考えています。

現在、単純な文字列マッチを行うだけでも遅いです。** Soundex のインデックス作成は高速になりますか? ユーザーが入力しているときに、ユーザーにいくつかのオプションを与えるにはどうすればよいですか? **

たとえば、誰かが次のように書いています。

マイクロソフト -> マイクロソフト
ベアエッセンシャル -> ベアエッセンシャル
ポリコム株式会社 -> ポリコム

この質問に似ていると思われる次のスレッドを見つけましたが、投稿者は承認しておらず、それらのユースケースが適用可能かどうかはわかりません:

大規模な文字列データベースで文字列の最もあいまいな一致を見つける方法

Java での不正確な会社名の照合

4

9 に答える 9

60

を使用することから始めることができますSOUNDEX()。これはおそらく必要なものに対応します (ユーザーが入力しているものに対する既存の代替案の自動提案ボックスを想像します)。

の欠点は次のSOUNDEX()とおりです。

  • 長い文字列を区別できない。最初の数文字のみが考慮され、最後に分岐する長い文字列は同じ SOUNDEX 値を生成します
  • 最初の文字が同じでないと、簡単に一致するものを見つけることができません。SQL Server には、2 つの SOUNDEX 値がどれだけ離れているかを示す DIFFERENCE() 関数がありますが、MySQL にはそのようなものは何も組み込まれていないと思います。
  • MySQLの場合、少なくともドキュメントによると、SOUNDEXはユニコード入力で壊れています

例：

SELECT SOUNDEX('Microsoft')
SELECT SOUNDEX('Microsift')
SELECT SOUNDEX('Microsift Corporation')
SELECT SOUNDEX('Microsift Subsidary')

/* all of these return 'M262' */

より高度なニーズについては、2 つの文字列のレーベンシュタイン距離(「編集距離」とも呼ばれます)を見て、しきい値を操作する必要があると思います。これはより複雑な (=遅い) ソリューションですが、柔軟性が向上します。

主な欠点は、それらの間の距離を計算するために両方の文字列が必要であることです。SOUNDEX を使用すると、事前に計算された SOUNDEX をテーブルに保存し、それを比較/並べ替え/グループ化/フィルター処理できます。レーベンシュタイン距離を使用すると、"Microsoft" と "Nzcrosoft" の違いはわずか 2 であることがわかるかもしれませんが、その結果が得られるまでにはさらに多くの時間がかかります。

いずれにしても、MySQL のレーベンシュタイン距離関数の例は、codejanitor.com: MySQL ストアド関数としてのレーベンシュタイン距離 (2007 年 2 月 10 日) にあります。

于 2008-12-15T21:56:17.580 に答える
24

SOUNDEX はこれに適したアルゴリズムですが、このトピックに関しては最近進歩が見られます。Metaphone と呼ばれる別のアルゴリズムが作成され、後に Double Metaphone アルゴリズムに改訂されました。私は個人的に double metaphone の Java Apache Commons 実装を使用しましたが、これはカスタマイズ可能で正確です。

ウィキペディアのページにも、他の多くの言語での実装があります。この質問には回答済みですが、アプリケーションに表示される SOUNDEX で特定された問題が見つかった場合は、オプションがあることを知っておいてください。場合によっては、まったく異なる 2 つの単語に対して同じコードを生成することがあります。Double metaphone は、その問題を解決するために作成されました。

ウィキペディアからの引用: http://en.wikipedia.org/wiki/Soundex

Soundex アルゴリズムの欠陥への対応として、Lawrence Philips は同じ目的で Metaphone アルゴリズムを開発しました。Philips は後に Metaphone の改良版を開発し、これを Double-Metaphone と呼んだ。Double-Metaphone には、前任者よりもはるかに大きなエンコーディング ルール セットが含まれており、非ラテン文字のサブセットを処理し、英語の 1 つの単語の異なる発音を考慮してプライマリおよびセカンダリ エンコーディングを返します。

double metaphone ページの下部に、あらゆる種類のプログラミング言語の実装があります: http://en.wikipedia.org/wiki/Double-Metaphone

Python と MySQL の実装: https://github.com/AtomBoy/double-metaphone

于 2008-12-18T23:07:49.103 に答える
11

まず、どの形式の音声/ファジー マッチング アルゴリズムを使用する場合も、非常に注意する必要があることを付け加えておきます。不正確な可能性があります。会社名の照合に使用する場合は特にそうです。

良い方法は、住所情報、郵便番号、電話番号、地理座標など、他のデータから裏付けを求めることです。これは、データが正確に一致する可能性を確認するのに役立ちます。

B2B データ マッチングに関連する問題は多岐にわたり、ここで取り上げるには多すぎます。会社名のマッチングについては、ブログ (更新された記事でもあります) で詳しく説明していますが、要約すると、主な問題は次のとおりです。

  • 会社名の最も重要な部分は必ずしも会社名の先頭にあるとは限らないため、文字列全体を見るのは役に立ちません。例: 「The Proctor and Gamble Company」または「United States Federal Reserve」</li>
  • 会社名には、HP、GM、GE、P&G、D&B などの略語がよく使われます。
  • 一部の企業は、ブランディングの一環として、また他の企業との差別化を図るため、故意に名前のスペルを間違っています。

正確なデータの照合は簡単ですが、正確でないデータの照合には時間がかかる可能性があるため、正確でないデータを検証して、これらが許容できる品質であることを確認する方法を検討することをお勧めします。

Match2Lists.com を構築する前は、あいまい一致の検証に非常に多くの時間を費やしていました。Match2Lists には強力な視覚化ツールが組み込まれており、正確ではない一致を確認できるようになりました。これは、一致検証の点で真のゲームチェンジャーであることが証明され、コストが削減され、結果をより迅速に提供できるようになりました。

頑張ってください!!

于 2012-08-17T16:13:47.293 に答える
4

これは、mysql および phpの soundex 関数に関する php の議論へのリンクです。そこから始めて、他のあまり明確に定義されていない要件に拡張します。

あなたの参照は、マッチングのためのレーベンシュタインの方法論を参照しています。2 つの問題。1. 検索ではなく、2 つの既知の単語の違いを測定するのに適しています。2. スペルミス (ユーザーが「Levenshtein」と入力して「Levenshtein」と入力する方法がわからない場合) ではなく、校正エラー (「Levenshtein」に「Levenshtien」を使用) などを検出するように設計されたソリューションについて説明します。 . 私は通常、データベースのキー値ではなく、書籍のフレーズを探すことと関連付けます。

編集：コメントへの応答で--

  1. 少なくとも、ユーザーに会社名を複数のテキスト ボックスに入力してもらうことはできますか。2. または明確な名前の区切り記号 (バックスラッシュなど) を使用します。3. 冠詞 (「The」) と一般的な略語を除外します (または、これらをフィルター処理できます)。4. スペースを押しつぶして一致させます (つまり、Micro Soft => microsoft、Bare Essentials => Bareessentials)。5. 句読点を除外します。6. 単語に対して「OR」検索を実行します (「bare」または「essentials」)。人は必然的にどちらか一方を除外することがあります。

狂ったようにテストし、ユーザーからのフィードバック ループを使用します。

于 2008-12-15T21:28:29.510 に答える
0

あいまい一致に最適な関数はレーベンシュタインです。伝統的にスペルチェッカーによって使用されているため、それが適している可能性があります。ここで利用可能な UDF があります: http://joshdrew.com/

レーベンシュタインを使用することの欠点は、スケールがうまくいかないことです。テーブル全体をスペル チェッカーのカスタム ディクショナリ ファイルにダンプし、データベース層ではなくアプリケーション層から提案を行うことをお勧めします。

于 2008-12-19T16:35:29.750 に答える