問題タブ [fuzzy-search]

私は〜300.000行のテーブルを持っています。これには専門用語が含まれます。PHPおよびMySQL+FULLTEXTインデックスを使用してクエリを実行します。しかし、間違ったタイプの用語を検索すると、たとえば、「hyperpext」。当然結果は出ません。

小さな書き込みエラーを「補償」し、データベースから最も近いレコードを取得する必要があります。どうすればそのような機能を実現できますか？私はレーベンシュタイン距離、Soundex、Metaphoneアルゴリズムについて知っていますが、現在、データベースに対するクエリにこれを実装するための確固たるアイデアを持っていません。

ありがとう

何年も前にメンバーだったメーリングリストを見つける目的で、メールの件名の長いリストをダウンロードしていて、Gmailアカウントからそれらを削除したいと思っています（かなり遅くなっています）。

私は特に同じアドレスから来ることが多いニュースレターを考えており、件名に製品/サービス/グループの名前を繰り返しています。

特定の電子メールアドレスからのアイテムの一般的な出現によって検索/並べ替えることができることは知っていますが（そして私はそうするつもりです）、そのデータを繰り返しの件名と関連付けたいと思います...。

これで、多くの件名が文字列の一致に失敗しますが、「Google Friends：最新ニュース」「GoogleFriends：今日行っていること」は、ランダムな件名よりも互いに似ています。「VirginAirlinesは今日の素晴らしいセール」「ヴァージン航空で飛行機に乗る」

だから-どうすればもっと似ているかもしれない文字列の傾向/例を自動的に抽出し始めることができますか？

私が検討して破棄したアプローチ（「もっと良い方法があるはずだから」）：

• 可能なすべての部分文字列を抽出し、それらが表示される頻度で並べ替え、関連する部分文字列を手動で選択します
• 最初の1つまたは2つの単語を取り除き、各サブ文字列の出現をカウントします
• エントリ間のレーベンシュタイン距離の比較
• ある種の文字列類似性インデックス..。

これらのほとんどは、膨大な量の手動介入が必要となるという非常に非効率的または可能性があるために拒否されました。ある種のあいまい文字列マッチングが必要だと思います。

結局、これを行うための厄介な方法を考えることができますが、より一般的なものを探しているので、このデータセットの特別なケーシングではなく、ツールのセットに追加しました。

この後、特定の件名文字列の発生を「From」アドレスと照合します-2つのメッセージが同じ電子メールの一部である可能性/低いことを表すデータ構造を構築する良い方法があるかどうかはわかりませんリスト」またはすべての電子メールの件名/アドレスから「関連する」可能性のある電子メールのプールにフィルタリングしますが、これはこの後解決する問題です。

任意のガイダンスをいただければ幸いです。

TextMate には、ファイル ナビゲーションに使用される「ファイルに移動」という機能があります。これは、プロジェクト内のファイルの名前を入力するボックスであり、あいまい一致を使用して、選択できる候補ファイルのリストを生成します。

他のエディターにもこの機能がありますが、それぞれ別の名前が付けられています。

Vim fuzzyfinder
Emacs fuzzy-find-in-project
TextMate ファイルへ移動 (ファジー)
Eclipse OpenResource (ファジーではない)
Eclipse GotoFile (ファジー)
Komodo ファイルへ移動(ファジーではない)
Netbeans ファイルへ移動 (ファジーではない)

jEdit、Geany、または Ultraedit にはこの機能がありますか?

Command-TでのTextmateのあいまい検索、VimのFuzzyFinder、またはEmacsのIdoのようなものを探しています。それは存在しますか？いいえの場合、どのようにそれを行うことを好みますか？

あいまい一致とは、レーベンシュタイン距離などによる類似の文字列を意味するのではなく、TextMate/Ido/Icicles で使用される方法です。間の文字、最適な適合を優先します。

Lucene のあいまい検索を使用したいと思います。これは、ある種のレーベンシュタインのようなアルゴリズムに基づいていると理解しています。かなり高いしきい値 (つまり、"new york~0.9") を使用する場合、最初に編集距離を計算してから、それが 0.9 に対応するものよりも小さいかどうかを確認するか、それが明らかになった場合にアルゴリズムを遮断しますか?ドキュメントがクエリと厳密に一致していませんか? レーベンシュタインアルゴリズムでそれが可能であることを理解しています。

事前定義された文字列のあいまい一致がないかすべてのエントリをチェックして、テキスト記事のストリームをフィルタリングする必要があります（スペルミスのある製品名を検索しています。語順が異なり、「：」や「、」などの余分な文字以外の文字が含まれている場合があります）。

この記事をスフィンクスインデックスに入れて検索すると素晴らしい結果が得られますが、残念ながら毎秒数百の記事を取得し、すべての記事を取得した後にインデックスを更新するのは遅すぎます（そのようなタスク用に設計されていないことを理解しています）。100kbまでの小さなテキストのメモリインデックスを組み込み、あいまい検索を実行できるライブラリが必要ですが、このようなものはありますか？

インデックスにa、b、cの3つのブールフィールドが含まれている場合...
「a = True、b = False、c = True」を検索すると、SOLRはすべてのエントリを返し、それらのスコアはどれだけ良いかを表す必要があります。クエリ全体が一致します。

例えば

それは可能ですか？

社内CRMの仕事をしています。同社の現在のフロントエンドでは、多くの重複が許可されています。エンドユーザーが「ウィリアム ジョンソン」ではなく「ビル ジョンソン」を検索したため、エンドユーザーが同じ人物を入力しないようにしています。そのため、ユーザーが新しい顧客に関する情報を入力すると、類似した名前 (あいまいな名前を含む) が検索され、データベースに既に存在するものと照合され、それらの意味があるかどうかが尋ねられます...そのようなデータベースまたは技術は存在しますか？

実際のタイプミスの統計はどこにありますか？

私は人々の入力テキストを内部オブジェクトに一致させようとしていますが、人々はスペルミスをする傾向があります。
2種類の間違いがあります：

1. typos-「Hello」の代わりに「Helllo」/「Saturday」の代わりに「Satudray」など。
2. Spelling-「シカゴ」の代わりに「シカゴ」

タイプミスにはダメラウ・レーベンシュタイン距離を使用 し、スペルにはダブルメタフォンを使用します（Pythonの実装はこことここにあります）。

ダメラウ・レーベンシュタイン（または単に）に焦点を当てたいと思いedit-distanceます。教科書の実装では、削除、挿入、置換、および転置の重みに常に「1」が使用されます。これは単純で優れたアルゴリズムを可能にしますが、「現実」/「現実世界の確率」とは一致しません。

例：

• 「Helllo」（「Hello」）の可能性は「Helzlo」よりも大きいと確信していますが、どちらも編集距離が1つ離れています。
• QWERTYキーボードでは、「Gello」は「Qello」より「Hello」に近いです。
• Unicodeの音訳：「ミュンヘン」と「ミュンヘン」の間の「実際の」距離はどれくらいですか？

削除、挿入、置換、および転置の「実世界」の重みはどのようにする必要がありますか？

Norvigの非常にクールなスペルコレクターでさえ、重み付けされていない編集距離を使用します。

ところで-重みは単純なフロートではなく関数である必要があると確信しています（上記の例による）...

アルゴリズムを調整できますが、これらの重みをどこで「学習」できますか？Googleスケールのデータにアクセスできません...

私はそれらを推測する必要がありますか？

編集-ユーザーの質問に答えようとしています：

• 上記の理由でタイプミスに直面すると、現在の重み付けされていないアルゴリズムが失敗することがよくあります。「ReturnonTursday」：すべての「実在の人物」は、木曜日が火曜日よりも可能性が高いことを簡単に判断できますが、どちらも1編集距離です。（はい、ログに記録してパフォーマンスを測定します）。
• 私はNLP旅行検索エンジンを開発しているので、辞書には最大25Kの宛先（100Kに成長すると予想される）、時間式〜200（予想される1K）、人の表現〜100（予想される300）、お金の式〜100（予想される500）が含まれています）、 "glue logic words"（ "from"、 "beautiful"、 "apartment"）〜2K（予想される10K）など...
• 編集距離の使用法は、上記の単語グループごとに異なります。私は「明白なときに自動修正」しようとします。たとえば、辞書内の他の1つの単語から1編集距離だけ離れています。他にも多くの手動で調整されたルールがあります。たとえば、長さが4を超える辞書の単語から2編集距離以内のダブルメタフォン修正などです。実際の入力から学習するにつれて、ルールのリストは増え続けます。
• 「しきい値の範囲内にある辞書エントリのペアはいくつですか？」：まあ、それは「ファンシーウェイトシステム」と実際の（将来の）入力に依存しますね。とにかく、私は広範な単体テストを行っているので、システムに加えるすべての変更は、システムを改善するだけです（もちろん、過去の入力に基づいています）。ほとんどのサブ6文字の単語は、別の辞書エントリから1編集距離離れた単語から1編集距離以内にあります。
• 今日、入力から同じ距離に2つの辞書エントリがある場合、ユーザーが何を意味するかをより正確に推測するためにさまざまな統計を適用しようとします（たとえば、フランスのパリはイランのパリよりも検索に表示される可能性が高くなります）。
• 間違った単語を選択するコストは、半ランダムな（しばしばばかげた）結果をエンドユーザーに返し、潜在的に顧客を失うことです。理解できない場合のコストはわずかに低くなります。ユーザーは言い換えを求められます。
• 複雑さのコストはそれだけの価値がありますか？はい、そうだと思います。人々がシステムに投げかけるタイプミスの量を信じて、それが理解することを期待することは信じられないでしょう、そして私は確かに適合率と再現率のブーストを使うことができました。