webdevqa.jp.net

オートコンプリートのためにPHPでMYSQLの会社名のあいまい一致を行うにはどうすればよいですか?

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

企業名の一意のcompany_idを持つ既存および成長中のMYSQLデータベースがあります。

文字列を解析して、ユーザーが入力した各会社名にあいまい一致を割り当てることができるようにしたいと思います。

現在、まっすぐに文字列を一致させるだけでも遅いです。 ** Soundexのインデックス作成は高速になりますか?入力中にユーザーにいくつかのオプションを与えるにはどうすればよいですか? **

たとえば、誰かが書いている:

 Microsoft-> Microsoft 
 Bare Essentials-> Bare Escentuals 
 Polycom、Inc.-> Polycom 

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

大きな文字列データベースの文字列に最適なファジー一致を見つける方法

Javaでの不正確な会社名のマッチング

44
AFG

SOUNDEX() を使用して開始することができます。これはおそらく必要なことを行います(ユーザーが入力しているものの既存の選択肢の自動提案ボックスを想像します)。

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

  • 長い文字列を区別できない。最初の数文字のみが考慮され、最後に発散する長い文字列は同じSOUNDEX値を生成します
  • 最初の文字が同じでなければならないという事実、または簡単に一致を見つけることができません。 SQL Serverには、2つのSOUNDEX値がどれだけ離れているかを示すDIFFERENCE()関数がありますが、MySQLにはそのような組み込みのものは何もないと思います。
  • mySQLの場合、少なくとも the docs によると、SOUNDEXはUnicode入力に対して壊れています

例:

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

/* all of these return 'M262' */

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

主な欠点は、それらの間の距離を計算するために両方の文字列が必要なことです。 SOUNDEXを使用すると、事前に計算されたSOUNDEXをテーブルに保存し、その上で比較/ソート/グループ/フィルターすることができます。レーベンシュタイン距離を使用すると、「Microsoft」と「Nzcrosoft」の違いはわずか2ですが、その結果を得るにはさらに時間がかかります。

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

52
Tomalak

SOUNDEXはこれに適したアルゴリズムですが、このトピックに関しては最近の進歩があります。 Metaphoneと呼ばれる別のアルゴリズムが作成され、後にダブルMetaphoneアルゴリズムに改訂されました。私は個人的にJava Apacheコモンダブルメタフォンの実装を使用しましたが、カスタマイズ可能で正確です。

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

ウィキペディアから盗まれた: http://en.wikipedia.org/wiki/Soundex

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

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

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

22
Cheese Daneish

まず、任意の形式の音声/ファジーマッチングアルゴリズムを使用するときは、この種のロジックがまさにファジーであるため、非常に簡単に言うと、非常に注意する必要があることを付け加えます。潜在的に不正確。会社名の一致に使用する場合は特にそうです。

良い方法は、住所情報、郵便番号、電話番号、地理座標など、他のデータから確証を求めることです。これにより、データが正確に一致する確率を確認できます。

B2Bデータマッチングに関連するさまざまな問題が多すぎてここでは対処できません。ブログで Company Name Matching について詳しく説明しましたが、要約すると重要な問題は次のとおりです。

  • 会社名の最も重要な部分が会社名の先頭にあるとは限らないため、文字列全体を見るのは役に立ちません。つまり、「The Proctor and Gamble Company」または「United States Federal Reserve」
  • 会社名の略称は、HP、GM、GE、P&G、D&Bなどです。
  • 一部の企業は、ブランドの一部として、また他の企業との差別化のために、故意に名前を間違って綴っています。

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

Match2Lists.comを構築する前は、あいまいな一致の検証に不健康な時間を費やしていました。 Match2Listsに強力な視覚化ツールを組み込み、完全に一致しない試合をレビューできるようになりました。これは、試合の検証の点で真のゲームチェンジャーであり、コストを削減し、結果をより迅速に提供できるようになりました。

ベストオブラッキー!!

9
Derren

これは、soundex関数のphpディスカッションへのリンクです mysqlおよびphpで。そこから始めてから、それほど明確に定義されていない他の要件に展開します。

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

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

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

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

4
dkretz

ファジーマッチングに最適な関数はレベンシュタインです。これは伝統的にスペルチェッカーによって使用されているため、その方法があります。ここにはUDFがあります: http://joshdrew.com/

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

0
longneck

この回答により、2文字または3文字以上の入力を使用して、ほぼすべてのエンティティのインデックス付きルックアップが行われます。

基本的に、Wordとキーの2つの列を持つ新しいテーブルを作成します。ファジー検索する列を含む元のテーブルでプロセスを実行します。このプロセスは、元の列から個々のWordをすべて抽出し、これらの単語を元のキーとともにWordテーブルに書き込みます。このプロセスでは、「the」、「and」などの一般的な単語は破棄する必要があります。

次のように、Wordテーブルにいくつかのインデックスを作成します...

  • Word +キーの通常の小文字インデックス
  • 2番目から5番目の文字+キーのインデックス
  • 3番目から6番目の文字+キーのインデックス

    または、Word列にSOUNDEX()インデックスを作成します。

これを設定したら、ユーザー入力を取得し、通常のWord = inputまたはLIKE input%を使用して検索します。 LIKE%inputを実行することはありません。最初の3文字のいずれかと一致するものを常に探しているためです。

元のテーブルが大規模な場合は、アルファベットのチャンクでWordテーブルをパーティション分割して、ユーザーの入力が候補行にすぐに絞り込まれるようにすることができます。

0