相互投稿:簡潔なデータ構造アルゴリズムの概要が必要
私はSuccinct Data Structuresについて知っていたので、その分野の最新の開発の概要を知りたいと思っています。
私はグーグルで検索し、頭の上からのリクエストでグーグルの結果の一番上に表示される多くの記事を読みました. ここで何か重要なことを見逃したのではないかと今でも思っています。
私が特に興味を持っているトピックは次のとおりです。
親、左/右の子、サブツリー内の要素数を取得する効率的な操作によるバイナリ ツリーの簡潔なエンコード。
ここでの主な質問は次のとおりです。私が知っているすべてのアプローチは、ツリーノードが息の順序で列挙されていることを前提としています (この分野のパイオニア作品のように、Jacobson、G. J (1988)。 Succinct static data structure ) 。私の仕事に適しているようです。深さ優先レイアウトで指定された巨大なバイナリ ツリーを処理し、深さ優先ノード インデックスは他のノード プロパティのキーであるため、ツリー レイアウトを変更するとコストがかかり、それを最小限に抑えたいと考えています。したがって、BFツリーレイアウト以外の作品への参照を取得することに関心があります。
外部メモリ内の大きな可変長項目配列。配列は不変です。アイテムを追加/削除/編集する必要はありません。唯一の要件は、O(1) 要素のアクセス時間と、可能な限り低いオーバーヘッドであり、単純なオフセットとサイズのアプローチよりも優れています。これは、私のタスクの典型的なデータについて収集した統計です。
アイテムの典型的な数 - 数億から数千ミリまで。
項目の約 30% の長さは 1ビット以下です。
40% ～ 60% の項目の長さが 8 ビット未満です。
長さが 32 ～ 255 ビットのアイテムは数パーセントのみです (255 ビットが限界です)。
アイテムの長さの平均は ~4 ビット +/- 1 ビットです。
アイテムの長さの他の分布は理論的には可能ですが、実際に興味深いケースはすべて、上記に近い統計を持っています。
複雑な記事へのリンク、あいまいなチュートリアル、多かれ少なかれ文書化された C/C++ ライブラリ、- 同様のタスクで役に立ったもの、または知識に基づいた推測でそのように見えるものはすべて、そのようなものすべてに感謝します。
更新:質問1に追加するのを忘れました:私が扱っているバイナリツリーは不変です。それらを変更する必要はありません。必要なのは、常にノードから子または親に移動するさまざまな方法でそれらをトラバースすることだけです。そのため、そのような操作の平均コストは O(1) でした。
また、典型的なツリーには数百万のノードがあり、RAM に完全に格納するべきではありません。
更新 2誰かが興味を持っている場合にのみ。https://cstheory.stackexchange.com/a/11265/9276にいくつかの良いリンクがあります。