0

三分探索木 (TST) を使用して自動提案を実装しようとしていますが、TST はプレフィックス検索を探しているときに便利です。部分文字列の一致に対しても自動提案を実装するにはどうすればよいですか? 使用できる他のデータ構造はありますか?

部分文字列の一致の例 : autoSuggest を使用して UML を検索しようとすると、文字列 "Beginners Guide for UML" も一致するはずです。

4

1 に答える 1

1

これは私の頭の上からのものであり、適切で証明されたデータ構造/アルゴリズムではありません:

  1. すべての正当な文字から N 個の記号へのマッピングを選択します (簡単にするために: 大文字と小文字を区別しないラテン文字および同様の非ラテン文字の 26 記号 + 非文字の 1 = 合計 27 記号)。

  2. 辞書から、最大分岐係数が N (つまり、非常に高い) の浅いツリーを作成します。リーフ ノードには、ルートからそのリーフにつながるシンボル コンボを含むすべての単語への参照が含まれます (中間ノードには、リーフ ノードの深さよりも短い単語への参照が含まれる場合があります。または、その短い単語を単に無視することもできます)。

  3. ツリーの深さは可変で、おそらく 1..4 の範囲で、各リーフ ノードにはほぼ同じ数の単語が含まれます (もちろん、同じ単語が多くのリーフの下にリストされます。ツリーの深さの場合、葉 MAT、ATC、TCH の下の MATCH のように)たまたま3）。

  4. ユーザーが文字を入力するときは、比較的小さな単語のセットが残るまで、ツリーに従って進みます。次に、ツリーのリーフに到達し、ユーザーが一致するテキストをさらに入力した後、残りの単語に対して線形フィルタリングを実行します。必要に応じて、実際には文字の一致ではない記号の一致を除外しますがäöO、ユーザーao0が などを入力したときにも一致させるとよい場合があります。

  5. 文字をマップするシンボルの数を最適化して、ツリーの分岐係数を適切にします。葉ごとの単語数を最適化して、ツリーの葉に到達した後に線形にフィルタリングする単語が多すぎずに適切なメモリ使用量が得られるようにします。

もちろん、 Aho–CorasickやRabin–Karpのように、大きなテキスト (一致させたいすべてのフレーズ/単語) から文字列 (ユーザーが入力したもの) を見つけるための実際の調査済みアルゴリズムがあり、おそらく調査する価値があります。

于 2013-04-02T11:37:04.613 に答える