問題タブ [fuzzy-search]

西ヨーロッパの言語でうまく機能するあいまい検索の実装を探しています。

どのアルゴリズムが最適に機能し、C＃の実装はどこにありますか？

アップデート

スウェーデン語に適応したSoundex：

• http://escuelle.blogspot.com/2008/03/swedish-soundex.html

NYSSISの実装：

• http://www.gamedev.net/community/forums/topic.asp?topic_id=497137
• http://dropby.com/PhonKey.cs

レーベンシュタイン：

• http://www.merriampark.com/ldcsharp.htm

印象的なJavaライブラリ：

• http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

しかし、西ヨーロッパの言語にどちらが適しているかはまだわかりません

Textmateの「ファイルに移動」あいまい検索は本当に素晴らしいです。

Wincentのvim用のCommand-Tプラグインも同様のことを行い、それも素晴らしいものです。

誰かがこれらがどのように機能するかを説明できますか？彼らが使用する方法の一般的な用語はありますか？

編集：私はそれらのツールが何をするかについてもう少し詳しく説明します

ツールを使用すると、入力時にオプション（この場合はファイルパス）のリストを絞り込むことができます。

たとえば、次のファイルがある場合：

リストを絞り込むに/app/models/people.rbは、次のいずれかを入力できます。

それは非常に柔軟性があり、私が使用しているアプリにこの「リストの絞り込み」がない場合、私は自分自身にこの「リストの絞り込み」が欠けていることに気付きます。必要に応じて自分のプラグインを実装できるように、もっと詳しく知りたいです。もっとよく説明できればいいのですが、それが私がここにいる理由です:)

実際の動作を確認するには、wincentのcommand-tのデモをご覧ください。

約800万行を含むインデックスを使用してFuzzyQueryを作成する必要があります。この種のクエリはかなり遅く、一致するたびに約20秒かかります。実際、あいまい検索を実行する前に、別のフィールドを使用して結果を約5000ヒットに絞り込むことができます。これが機能するためには、最初に「より狭い」フィールドで検索を行い、次にそれらの結果内であいまい検索を使用できる必要があります。

lucene FAQによると、私がしなければならないのはBooleanQueryだけです。ここでは、「より狭い」が必要です（lucene 3ではBooleanClause.Occur.MUST）。

今、私は2つの異なるアプローチを試しました。

a）次のような入力でクエリパーサーを使用します。 narrower:+narrowing_text fuzzy:fuzzy_text~0.9

b）TermQueryとFuzzyQueryを使用してBooleanQueryを構築する

どちらも機能しませんでした。ナローを使用しない場合とほぼ同じ時間になります。

また、ナローが機能している場合は時間が大幅に改善されることを確認するために、ナローに一致する5000アイテムのみのインデックスを再作成したところ、検索は非常に高速になりました。

不思議に思う人のために、私はピルセン3.0.2を使用しています。

私は現在、用語 Web サービスのあいまい検索の実装に取り​​組んでおり、現在の実装を改善する方法についての提案を探しています。共有するにはコードが多すぎますが、思慮深い提案を促すには説明で十分だと思います。読むのは大変だと思いますが、助けていただければ幸いです。

まず、用語は基本的に名前 (または用語) の数です。単語ごとに、スペースでトークンに分割し、各文字を反復処理してトライに追加します。ターミナル ノード (イチゴの文字 y に達したときなど) では、マスター ターム リストへのインデックスをリストに格納します。そのため、ターミナル ノードは複数のインデックスを持つことができます (イチゴのターミナル ノードは「イチゴ」と「イチゴ アレルギー」に一致するため)。

実際の検索に関しては、検索クエリもスペースごとにトークンに分割されます。検索アルゴリズムはトークンごとに実行されます。検索トークンの最初の文字は一致する必要があります (したがって、traw はいちごと一致しません)。その後、連続する各ノードの子を調べます。一致する文字を持つ子があれば、検索トークンの次の文字で検索を続けます。子が指定された文字と一致しない場合は、検索トークンの現在の文字を使用して子を調べます (したがって、それを進めません)。これはあいまいな部分なので、「stwb」は「strawberry」に一致します。

検索トークンの最後に到達すると、そのノードの残りのトライ構造を検索して、すべての潜在的な一致を取得します (マスター ターム リストへのインデックスはターミナル ノードにのみあるため)。これをロールアップと呼びます。BitSet に値を設定してインデックスを保存します。次に、単純に各検索トークンの結果から BitSet を取得します。次に、anded BitSet から最初の 1000 または 5000 のインデックスを取得し、それらが対応する実際の用語を見つけます。レーベンシュタインを使用して各用語をスコアリングし、スコアで並べ替えて最終結果を取得します。

これはかなりうまく機能し、かなり高速です。ツリーには 39 万を超えるノードと、110 万を超える実際の用語名があります。しかし、このままでは問題があります。

たとえば、「car cat」を検索すると、望ましくない場合でも Catheterization が返されます (検索クエリが 2 つの単語であるため、結果は少なくとも 2 つになるはずです)。これは簡単に確認できますが、2 つの単語であるため、カテーテル挿入手順のような状況には対処できません。理想的には、心臓カテーテル法のようなものと一致させたいと考えています.

これを修正する必要性に基づいて、いくつかの変更を考え出しました。1 つは、深さ/幅が混在する探索でトライを通過することです。基本的に、キャラクターが一致する限り、深さを優先します。一致しなかった子ノードは優先キューに追加されます。優先キューは、トライの検索中に計算できる編集距離によって順序付けられます (文字の一致がある場合、距離は同じままであり、そうでない場合は 1 増加するため)。これにより、各単語の編集距離が得られます。BitSet は使用しなくなりました。代わりに、Terminfo オブジェクトへのインデックスのマップです。このオブジェクトには、クエリ フレーズのインデックスと用語フレーズ、およびスコアが格納されます。検索が「car cat」で、一致する用語が「Catheterization procedure」の場合 用語フレーズ インデックスは、クエリ フレーズ インデックスと同様に 1 になります。「Cardiac Catheterization」の場合、語句インデックスはクエリ フレーズ インデックスと同様に 1,2 になります。ご覧のとおり、後で単語フレーズ インデックスとクエリ フレーズ インデックスの数を確認するのは非常に簡単です。それらが少なくとも検索語数と等しくない場合は、それらを破棄できます。

その後、単語の編集距離を合計し、単語句インデックスに一致する単語を単語から削除し、残りの文字を数えて真の編集距離を取得します。たとえば、「イチゴ アレルギー」という用語に一致し、検索クエリが「ストロー」であった場合、イチゴのスコアは 7 になります。その場合、用語フレーズ インデックスを使用して用語からイチゴを除外し、カウントするだけです。 「アレルギー」（スペースを除く）で 16 のスコアを取得します。

これにより、期待どおりの正確な結果が得られます。ただし、速度が遅すぎます。以前は 1 単語の検索で 25 ～ 40 ミリ秒を取得できましたが、今では 0.5 秒にもなる可能性があります。これは主に、TermInfo オブジェクトのインスタンス化、.add() 操作、.put() 操作の使用、および多数の一致を返さなければならないという事実によるものです。各検索を 1000 件の一致のみを返すように制限することはできますが、「car」の最初の 1000 件の結果が「cat」の最初の 1000 件の一致のいずれかに一致するという保証はありません (110 万以上の用語があることを思い出してください)。

cat のような単一のクエリ ワードの場合でも、多数の一致が必要です。これは、'cat' を検索すると、検索が car に一致し、その下のすべてのターミナル ノードがロールアップされるためです (これは非常に多くなります)。ただし、結果の数を制限すると、編集距離ではなく、クエリで始まる単語が強調されすぎてしまいます。したがって、カテーテル法などの単語は、コートなどの単語よりも含まれる可能性が高くなります。

では、基本的に、2 番目の実装で修正された問題をどのように処理できるかについて何か考えはありますか? 物事を明確にするために選択したコードを含めることができますが、巨大なコードの壁を投稿したくありませんでした.

私はかなりの期間これを自分で試し、ネットのいたるところを見てきましたが、Lucene.NET 2.9.2 を介して検索するファジー フレーズの例を見つけることができませんでした。( C# )

これを詳細に行う方法やサンプルコードを提供する方法をアドバイスできる人はいますか?

私が探しているのは、コストのかかる呼び出しになる可能性がある実際の数ではなく、行数の推定値を返すことです。あなたがグーグル検索で見るものと同様です（約1.000行の...）。

このためのすぐに使えるソリューションはありますか？そうでない場合、一般的なアプローチは何ですか？

SQLServer2008データベースにクエリを実行しています。

編集：明確にするために、結果の数は特定のユーザークエリに関連しています。たとえば、ユーザーが「John」を検索すると、結果は「Johnに一致する行が約1.280.000行あります」になります。

私はある種のこれを実装する必要があります:

C# で記述された関数スタブを次に示します。

しかし、 IsFuzzyMatch メソッドにロジックを実装する方法がわかりません。何か案は？おそらく、この目的のための既製のソリューションはありますか?

学校のプロジェクトの場合、目標は、クエリ文字列と Song オブジェクト内の歌詞文字列のあいまい一致を実行することです。全体的なデータ構造は、歌詞にその単語を含む曲のセットとペアになった一意の単語の TreeMap です。

クエリ文字列を含む曲の予備一致セットがあります。ここでひねりを加えたのは、各結果の曲に、マッチ セクションの文字数 (スペースを含む) に基づいてランクを割り当てる必要があることです。たとえば、「彼女はあなたを愛している」を検索すると、次の一致が返されます。

「... 彼女はあなたを愛している...」 ビートルズ、ランク= 13
"... 彼女はあなたを愛している..." ボニー・レイット、ランク= 18
"... 彼女は私を愛している、まああなた..." エルヴィスプレスリー、ランク=23

結果をソートするために使用しているのは次のとおりです。

結果セット内のすべての曲には特定の順序でクエリ ワードが含まれているため、すべてが結果の印刷出力に含まれるわけではありません。このアルゴリズムを使用して、クエリが特定の長さに一致しない場合にセットから曲を削除するトリガーを設定するにはどうすればよいですか?

編集 - Lucene はこれに対する解決策ですか? これはプロジェクトの灰色の領域であり、明日のクラスで取り上げます。彼は、このプロジェクトのデータ構造を選択することを許可していますが、文字列の一致に別の実装を使用することが成功するかどうかはわかりません。

Edit 2 @ belisarius- ここで編集距離がどのように適用されるかわかりません。レーベンシュタイン距離の最も一般的な適用では、長さ n の文字列 a と長さ m の文字列 b が必要であり、距離は a==b に必要な編集の数です。このプロジェクトでは、開始点と終了点が不明な、一致するキャラクターのランクのみが必要です。上記のコードにいくつかの変更を加えて、開始点と終了点を正確に見つけています。私が必要としているのは、歌詞が何らかの形で検索に適合しない場合に、セットから一致しないものを削除する方法です。

OCR で認識されたテキスト内の文字列を一致させる問題に遭遇し、間違った文字、欠落した文字、または余分な文字の任意の許容範囲がある可能性があることを考慮して、その位置を見つけました。結果は、一致する部分文字列の長さで、おそらく (必ずしもそうとは限りませんが) 最適な一致位置になるはずです。

例えば：

Levenstein アルゴリズムを適用しようとしましたが、部分文字列に対しては適切に機能せず、位置を返しません。

Delphi のアルゴリズムが優先されますが、任意の実装または疑似ロジックでもかまいません。

既存の質問の投稿をすべて調べていましたが、関連性の高いものを取得できませんでした。

個人の名、姓、住所 1、住所 2、国コード、生年月日の何百万ものレコードを含むファイルがあります。上記のファイルを使用して顧客のリストを毎日チェックしたいと思います (顧客リストも毎日更新され、ファイルも毎日更新されます）。

名と姓についてはあいまい一致 (lucene fuzzyquery/levenshtein 距離 90% 一致の可能性があります) を希望し、残りのフィールドの国と生年月日については完全一致が必要でした。

私はLuceneを初めて使用しますが、投稿の数を見ると、可能のようです。

私の質問は次のとおりです。

• 入力ファイルのインデックスはどのように作成すればよいですか? FN、LN、国、DOB の組み合わせでインデックスを作成し、そのインデックスを検索に使用する必要があります
• ここでLuceneのファジークエリを使用するにはどうすればよいですか?

同じことを実装できる他の方法はありますか？