問題タブ [radix-tree]

バイナリ基数ツリー (最長共通プレフィックス ツリー) を作成しています。データはリーフ ノードにのみ格納されます。ツリー階層には内部ノードがあり、各内部ノードには 2 つの子ノードがあります。子ノードは、リーフ ノードまたは内部ノードのいずれかです。リーフ ノードと内部ノードの両方が、親ノードへの参照を格納します。

リーフ ノードは配列に格納されます。内部ノードは別の配列に格納されます。ルート ノードは内部ノード配列の最初の要素です

ツリー構造が内部ノードの配列として満たされていると仮定すると、ツリーの内部ノードを選択すると、内部ノードの子ノードが内部ノードであるか葉ノードであるかをどのように知ることができますか? これを行うには、子ノードごとに 1 つのブール変数を格納して、リード ノードまたは内部ノードとしてマークすることを考えています。しかし、これは私には良い解決策ではないようです。

誰かがこれを行うためのより良い方法を提案できますか?

これは、実際に通常行われていることについての質問です。

エントリが 1 つの基数ツリーがあるとします (何らかの理由で、これをデモ用の単一のエントリと見なしてください)。

そして、2 番目のエントリを挿入します。

ルートからのエッジで終了したい

そしてそこから2つのエッジがあり、1つは

そして1つ

単純に、"te" と "sts are really..." の新しい文字列 (文字配列など) を作成できます。新しい単語「チーム」は短いものですが、これには多くの操作が必要です。

あるいは、「te」と「sts are really...」ラベルに、同じ元の文字列への参照と、開始/終了値を含めることができます。つまり、次のようになります。

と

このようにして、コピーを回避し、「チーム」の挿入時間は「チーム」の長さにのみ依存し、他の文字列の長さには依存しません。つまり、この場合は「テストは本当に...」です。

kしたがって、 inO(k)が挿入される文字列の長さを意味するのか、それともこれまでで最も長い文字列を意味するのかの問題です。

明らかに後者の実装はより難しく、実際には (エンドポイントの保存のため) より多くのメモリを使用する可能性がありますが、理論上の最悪の場合の時間は改善されているようです。

実際に一般的に行われていることを誰かが知っているかどうか疑問に思っていますか?

ありがとう

編集: 後者の実装に関する 1 つの問題は、削除によって発生すると思います。後で "telepathy" を挿入してから "tests are really hard..." を削除した場合、"te" エッジが残り、必要以上に長い文字列への参照が残ります。

ハフマン コードを使用してテキストを圧縮することを考えていますが、可変長(文字列) のシンボルを使用します。例 (アンダースコアをスペースとして使用):

頻度表を作成するにはどうすればよいですか? 重複する問題がいくつかあることは明らかです。シーケンス_THは とほぼ同じ頻度で表示されTHEますが、表では役に立ちません ( と の両方_にTHE短いハフマン コードがあります)。

そのようなアルゴリズムは存在しますか？特別な名前はありますか？頻度表を生成するためのトリックは何ですか? 入力をトークン化する必要がありますか? 文献/ウェブには何も見つかりませんでした。（これはすべて、基数ツリーについても考えさせます）。

私は反復プロセスを使用することを考えていました:

1. 長さが 1 ～ N のすべてのシンボルのハフマン ツリーを生成する
2. N>1 で特定のカウントしきい値を下回るすべてのシンボルをツリーから削除します
3. 2 番目のハフマン ツリーを再生成しますが、今回は前のハフマン ツリーで入力をトークン化します (おそらくルックアップに基数ツリーを使用します)。
4. 収束するまで（または数回）1まで繰り返します

_THしかし、これでオーバーラップ（ vs ）の問題をどのように防ぐことができるかわかりませんTHE。

物事をより簡単にすると同時により複雑にするために、複数の基本的なタグ形式にさらに拡張する「結合/簡潔なタグ」の概念を実装しようとしました。

この場合、タグはセミコロンで区切られた (1 つ以上の) 「サブタグ」で構成されます。

スラッシュは「サブタグ」の互換性を示します。したがって、インタープリターはそれらを次のように翻訳します。

使用されたコード (完全ではありませんが、動作します):

質問: このプロセスを元に戻すにはどうすればよいですか? 読みやすさのためにこれが必要です。

自分の変数を Linux ページ キャッシュに追加したいと考えています。ページ キャッシュは基数ツリーによって管理されます。

radix-tree-node に変数「X」を追加したいと考えています。ただし、radix_tree_root の 'X' を埋めると機能しません。

root という名前の基数ツリー ルートがあります。// struct radix_tree_root* root; root には、radix_tree_node のポインターである rnode があります。

失敗します。なぜうまくいかないのかわかりません。

開いているファイルのページ キャッシュ統計を取得する必要があります。file struct には address_space ポインター ( f_mapping ) があり、これはpage_treeと呼ばれる基数ツリーのルートを持ちます。そのツリーをたどって、開いているファイルのキャッシュされたすべてのページに関する情報を取得する必要があります。

radix_tree_for_each_chunk (チャンクを反復するため)、radix_tree_for_each_chunk_slot (1 つのチャンク内のスロットを反復するため) などの関数がいくつかあり、これらを使用して機能を実現できます。同じものの適切な使用法（引数）について確信が持てません。例が掲載されていると助かります。

構造体の定義に大きな問題があります。それらを定義するいくつかの異なる方法を試しましたが、エラーを取り除くことができないようです。

おそらく、コードには他にも多くの問題がありますが、コードを実行してそれらを見つけずに実際に修正することはできません。そのため、まずこれを解決する必要があります。

完全なコードは次のとおりです。

ここに私が得るエラーがあります:

基数ツリーの実装に問題があります。アイデアは、最初のノードを作成してから、いくつかの 2 進数を入力するというものです。2 進数は、左側のノード (0) または右側のノード (1) のどちらが作成されるかを決定します。2 進数の末尾に到達したら、ノードを「アクティブ」に設定します。

次に、ツリーを検索してアクティブなノードを見つけ、アクティブなノードに到達するためにどの方向に進む必要があるかを確認して、元の 2 進数を再度出力します。

完全なコードは次のとおりです。

出力は次のとおりです。

(そして無限に続く)

明らかに、insert()関数の再帰に問題がありますが、再帰を行うときに2進数文字列の最初の文字を削除することを考えると、それがどのように無限に実行できるかわかりません。