問題タブ [radix-tree]

各単語に次の単語と共通する文字が少なくとも 2 つある場合、文字列は2-consistentと呼ばれます。

例えば

「Atom another era」 [ atomhas aand tin common with anotherand anotherhas eand ain common with era(答えは一意ではありません)。

まず、質問で一定時間内に 2 つの単語と回答を受け取るデータ構造が必要です。 "Do these words have at least 2 letters in common?"

ここで、単語の文字列が与えられた場合、最長の 2 つの一貫性のnある部分文字列を見つける必要があります。

使用するデータ構造がわかりません。radix treeかと思ったprefix treeのですが、答えが見つかりませんでした。手伝って頂けますか？

以下は、基数ツリーに IP プレフィックスを格納し、IP がプレフィックスに属している場合は、IP と ASN をディクショナリに関連付ける Python のコード スニペットです。

特定のプレフィックスのさまざまな ASN をすべて見つけたいと考えています。詳細を以下に示します。

例:valは、いくつかの反復で protobuf から次の値を取得します。

を印刷するとseen_list：

明らかvalに入っていseen_listます。しかし、if val not in seen_list:常に真であり、何度もval追加されます。seen_list条件が常に true を返す理由がわかりません。に格納されているオブジェクトの種類が原因seen_listですか?

試行を使用して辞書を作成する必要があります。アルファベットの文字数が 26 から 120 に増加するため、リーフ ノードの数は指数関数的に増加します。ルックアップ、挿入、および削除の時間が指数関数的に増加しないようにするには、どのような最適化を使用できますか?

編集 質問をより明確にします。詳細が不足していて申し訳ありません。基数ツリーのようなマルチウェイ トライを使用し、それにいくつかの変更を加えています。私の質問は、ワード サイズが (確実に) 26 から 120 に増加することがわかっている場合、ツリーの深さが増加するということです。キーを 64 ビット以上に増やすことで深さの増加を減らすことは可能ですか (レジスタは最大 64 ビットをゴールドにすることができます)?

私が理解しているように (こちらからも)、これらの DS のメモリの複雑さは、Trie > Radix > Patricia のように並べることができます。しかし、時間の複雑さはどうでしょうか? ほぼ同じだと思います。

私の問題に言及すると、事前に構築された辞書から多くのプレフィックス検索クエリを実行したいと考えています。メモリは私にとって大きな問題ではありません。最速のDSを使いたい。

HAT-trie は私に最適ですが、実装するには複雑すぎます。上記の DS の代わりに三分探索木を使用する必要がありますか?

どうもありがとう！

Golang の練習用に作成した基数ツリーの実装のベンチマークを試みています。

しかし、「どのようにベンチマークすればよいですか?」という問題に遭遇しました。以下のコードでは、2 つのケースを示しています。または、LookUp 関数のベンチマークを実行するさまざまな方法を示しています。

• ケース 1: ツリー上に存在する 1 つのバイト スライスを使用すると、すべての子ノードなどを介してルックアップが成功します。

• ケース 2: func を使用して、ツリー内の既存のデータからそのランダムなスライスを生成します。これは、ルックアップも成功することを意味します...

かかる時間はツリーの深さに依存することはわかっています... ケース 2 は実際の実装に近いと思いますか?

質問: ベンチマークするのに、どちらのケースがより効率的または有用ですか?

基準：

結果 ケース 1:

結果ケース 2:

一致しない場合の結果:

「基数ツリー」の全会一致の定義を見つけることは困難ですが、最も受け入れられている基数ツリーの定義は、圧縮されたプレフィックス ツリーであることを示しています。私が理解するのに苦労しているのは、この場合の「基数」という用語の意味です。圧縮されたプレフィックス ツリーがそのように命名され (つまり、基数ツリー)、圧縮されていないプレフィックス ツリーが基数ツリーと呼ばれないのはなぜですか?

トライで特定のプレフィックスを検索することは O(M) で行われることを知っています。ここで、M はトライに挿入される任意の単語の最大長です。

しかし、特定のプレフィックスで始まるすべての要素を取得する時間の複雑さはどのくらいでしょうか?

私は可能な答えについて考えました：

O(M+n) ここで、n はプレフィックスで始まる単語の数です。アイデア: プレフィックスの検索は O(M) にあります。次に、指定されたプレフィックスで始まるすべての単語を含むサブトリーがあり、それをトラバースするだけです。問題 (おそらく): プレフィックス ツリーに単語より多くのノードがあります。しかし、私がそれらを見る必要がないように、何らかの形の効率的な保存があるのではないでしょうか?