一様分布のランダム可変長コード番号

Question

仮想Bツリーを解析し、ハフマン符号化に似たアイテムに到達したときにデータを取り出すことができるときに可変長符号化されたデータがあるとします。未知数の項目があります（最善のケースでは上限がわかります）。一様分布の数値を生成するアルゴリズムはありますか？問題は、コインベースのアルゴリズムでは、この場合、たとえば101に符号化された数字があり、10010101に符号化された数字がある場合に、不均一な結果が得られることです。後者は、前者とほとんど同じです。

更新：言い換えれば、すべての要素が任意のビット数で（そして情報理論に基づいて）アドレス指定できるとき、私は最大N要素のセットを持っています他の要素は同じプレフィックスでエンコードすることができます）。だから私はちょっと左から右に行くとB-Treeに似ていて、ある時点でデータ項目に行きます。このテクニックで扱われる一連の乱数を取得したいと思いますが、それらの分布は一様でなければなりません（右の例をランダムに選択してもうまくいかない理由は上記101,10100101です）

ありがとう

最大

Answer 1

私は3つの基本的な方法が考えられますが、そのうちの1つは頻繁なレギュレーションがあり、もう1つは余分な情報を保持することです。私は、これらのことのどちらかを行うことはやむを得ないことだと思います。私は余分な情報から始めるつもりです

各ノードには、子孫の数を表す数字countを格納します。すべてのノードで、左の子ノードの数と左の子ノードの数を比較するかどうかを指定するには、そのノードに1からcountまでの数値が必要です。ここでは、アルゴリズムです：

n := random integer between 1 and root.count 
node := route 
while node.count != 1 
    if n <= node.left.count 
      node = node.left 
    else 
      node = node.right 
      n = n - node.left.count 

ので、基本的に、我々はすべてのノードで左から右への順序を課すと、左からn番目のいずれかを選択しています。これはかなり速く、O（ツリーの深さ）を持つだけです。これは、すべてのノードラベルを含むベクトルを構築するようなことをせずにできる最高の可能性があります。これは、カウントを修正する必要があるため、ツリーの変更にO（ツリーの深さ）のオーバーヘッドを追加します。あなたが他の方法を行っていてツリーを一度も変更することはないが、ランダムなノードをたくさん選択する場合は、弾丸を少し打ち、すべてのノードラベルをベクターに入れてください。そうすることで、O（N）の初期セットアップ時間後にO（1）でランダムなものを選択できます。

ただし、ストレージスペースを使い切っていない場合は、たくさんの規制があります。まず、ツリーの深さ（私はBとラベル付けする）を見つけます（必要ならばN-1を使うことができますが、それは非常に緩やかな境界です）。走る）。次に、可能なノードラベルをランダムに生成します。 2 ^（B + 1）-1の可能性がある。たとえば、文字列 "0011"と "11"は完全に異なる文字列なので、2^Bだけではありません。結果として、0とBの間の可能なすべてのバイナリ文字列を数える必要があります。明らかに、長さiの2^i文字列があります。したがって、長さがi以下の文字列の場合、合計（i = 0〜B）{2^i} = 2 ^（B + 1）-1となります。したがって、0と2 ^（B + 1）-2の間の数字を選択し、対応するノードラベルを見つけることができます。もちろん、数字からノードラベルへのマッピングは簡単ではないので、ここで説明します。

通常の方法で選択した数値をビット列に変換します。次に、左から読み取ると、最初の数字が0の場合、ノードラベルは残りの文字列（おそらく空の文字列です。これは有効ではありませんが、有効なノードラベルです）。最初の数字が1の場合は、それを投げ捨て、このプロセスを繰り返します。従って、B = 4であれば、ノードラベル「0001」は番号「00001」から来る。ノードラベル "001"は、数字 "10001"から来る。ノードラベル "01"は、番号 "11001"から来る。ノードラベル「1」は、番号「11101」から来る。ノードラベル ""は番号 "11110"から来ます。このスキームで有効な解釈がない2 ^（B + 1）-1（この場合は "11111"）という数字は含まれていませんでした。私は長さ0からBのすべての文字列がこのスキームの下で表現できることを自分自身に証明するために、読者に練習として残しておきます。それを証明しようとするより、私はそれがうまくいくと主張します。

これでノードラベルが作成されました。次のステップは、そのラベルがツリーを横断することによって存在するかどうかを確認することです。もしそうなら、私たちは完了です。そうでない場合は、新しい番号を選択してやり直してください（それは調整部分です）。法律上のノードラベルのごく一部しか使用されないので、多くのことを規制する必要がありますが、これは公正を歪ませず、時間を増やすだけです。

function num_to_binary_list(n,digits) = 
    if digits == 0 return() 
    if n mod 2 == 0 return 0 :: num_to_digits(n/2,digits-1) 
    else return 1 :: num_to_digits((n-1)/2,digits-1) 

function binary_list_to_node_label_list(l) = 
    if l.head() == 0 return l.tail() 
    else return binary_list_to_node_label_list(l.tail()) 

function check_node_label_list_against_tree(str,node) = 
    if node == null return false,null 
    if str.isEmpty() 
    if node.isLeaf() return true,node 
    else return false,null 
    if str.head() == 0 return check_node_label_list_against_tree(str.tail(),node.left) 
    else check_node_label_list_against_tree(str.tail,node.right) 

function generate_random_node tree b = 
    found := false 
    while (not found) 
    x := random(0,2**(b+1)-2) // We're assuming that this random selects inclusively 
    node_label := binary_list_to_node_label(num_to_binary_list(x,b+1)) 
    found,node := check_node_label_list_against_tree(node_label,tree) 
    return node 

このタイミング解析は、当然のことながら、かなり恐ろしいです：

はここで4つの機能で、このプロセスの擬似コードバージョンです。基本的に、whileループは（2 ^（B + 1）-1）/ N回の平均を実行します。だから、最悪の場合、それはひどいO（（2^N）/ N）です。最良の場合、Bはlog（N）のオーダーになるので、おおよそO（1）となりますが、それは木がかなりバランスが取れていることが必要です。それでも、余分なスペースを必要としない場合は、この方法で行います。

私は本当にあなたがいくつかの情報を保存せずにこの最後の方法よりも優れているとは思いません。あなたが行くにつれて木を横切ることができるように魅力的に聞こえますが、構造に関する追加の情報を保存することなく、あなたはそれを行うことができません。分岐する決定を下すたびに、左側にノードが1つだけあり、右側に100万のノードがあるか、左側に100万のノードがあり、右側に1つのノードがある可能性があります。それらはどちらも可能であり、どちらが当てはまるかわからないので、両者の間でランダムな決定をする方法はありません。明らかに50-50は機能せず、他の選択肢も同様に問題になるだろう。

余分なスペースを必要としない場合、2番目の方法は機能しますが、遅くなる可能性があります。余分なスペースを追加しても構わない場合は、最初の方法が機能し、高速になります。先ほどお話したように、ツリーを変更しないでランダムなノードをたくさん選んだら、弾丸をたたき、ツリーをたどり、すべての葉ノードを自己成長アレイに貼り付けますまたはベクトルを選択してから選択します。