3

Web サイトの自動提案機能に使用しているトライ (サフィックス ツリー) があります。

ここで、最も人気のある (最もウェイトの高い) テキストを、ウェイトの低いテキストの上に表示したいと考えています。候補が加重順に表示されるようにトライを変更するにはどうすればよいですか。

それとも、メモリ内の重みでソートする必要がありますか?

4

1 に答える 1

3

count各ノードにorプロパティを追加weightし、単語を使用してトライを構築するときにそれを更新できます。各文字の初期重みは です0が、文字が単語の終端文字である場合、初期重みは になり1ます。単語を追加し続けると、終端文字の重みを調整できます。

したがって、たとえば、次のようにすることができます。

t:0
|  
o:1
|
w:3---e:0
|  \    \
n:2 a:0  l:4
     \
      r:0
       \
        d:2

文字列to(1 回表示)、tow(3 回表示)、towel(4 回表示)、town(2 回表示)、およびtoward(2 回表示) の場合。

次に、プレフィックスがあればtow、、、、、などのゼロ以外の加重文字列を見ることtow:3がtowel:4できtown:2ますtoward:2。

その後、重みに基づいて並べ替えることができます。

この実装を実際に試したことはありません。これは単なるアイデアです。

于 2013-07-09T17:48:56.740 に答える