私は現在、用語 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 番目の実装で修正された問題をどのように処理できるかについて何か考えはありますか? 物事を明確にするために選択したコードを含めることができますが、巨大なコードの壁を投稿したくありませんでした.