0

仮想 B ツリーを解析し、アイテムに到達すると停止するデータを取得できるときに、可変長エンコーディングで提示されたデータがあるとします (ハフマン エンコーディングと同様)。アイテムの数は不明です (最高の場合、上限のみがわかっています)。一様に分布した数値を生成するアルゴリズムはありますか? 問題は、この場合、コインベースのアルゴリズムが不均一な結果をもたらすことです。たとえば、101 としてエンコードされた数値があり、10010101 としてエンコードされた数値がある場合、後者は前者と比較してほとんど表示されません。

更新: 言い換えると、すべての要素を任意のビット数でアドレス指定できる場合 (および情報理論に従って、1 つが 101 でエンコードされている場合、他の要素は同じプレフィックスでエンコードされます)。したがって、ビットに応じて左または右に移動し、ある時点でデータ項目に到達すると、B-Tree に似ています。この手法で対処される一連の乱数を取得したいのですが、それらの分布は均一である必要があります (左右のランダムな選択がうまくいかない理由の例は、上記の数字 101 と 10010101 です)。

ありがとう

マックス

4

1 に答える 1

1

3 つの基本的な方法が考えられます。1 つは頻繁に再推測する方法で、もう 1 つは余分な情報を保持する方法です。どちらか一方を行うことはやむを得ないと思います。追加情報から始めます。

count各ノードには、その子孫の数を表す数値を格納します。すべてのノードについてcount、左の子のカウントと比較して左または右に移動するかどうかを判断するために、1 からそのノードまでの数値が必要です。アルゴリズムは次のとおりです。

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 以下の文字列の場合、sum(i=0 to 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 までのすべての文字列がこのスキームで表現できることを証明するために、読者の演習として残します。それを証明しようとするのではなく、それが機能すると断言します。

これで、ノード ラベルができました。次のステップは、ツリーをたどってそのラベルが存在するかどうかを確認することです。もしそうなら、私たちは終わりです。そうでない場合は、新しい番号を選択して最初からやり直します (これが再推測の部分です)。有効なノード ラベルのごく一部しか使用されないため、多くの再推測が必要になる可能性がありますが、これによって公平性が損なわれることはなく、時間が増えるだけです。

4 つの関数でこのプロセスの疑似コード バージョンを次に示します。

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

もちろん、これのタイミング分析は非常に恐ろしいものです。基本的に、while ループは平均で (2^(B+1)-1)/N 回実行されます。ですから、最悪の場合、O((2^N)/N) はひどいです。最良の場合、B は log(N) のオーダーになるため、おおよそ O(1) になりますが、それにはツリーがかなりバランスが取れている必要があり、そうでない場合もあります。それでも、余分なスペースが本当に必要ない場合は、このメソッドがそれを行います。

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

したがって、余分なスペースが必要ない場合は、2 番目の方法が機能しますが、遅くなります。余分なスペースを追加してもかまわない場合は、最初の方法が機能し、高速です。そして、前に述べたように、ツリーを変更するつもりがなく、ランダムなノードをたくさん選択する場合は、気を抜いてツリーをたどり、すべてのリーフ ノードを自己成長配列に貼り付けてください。またはベクトルを選択し、そこから選択します。

于 2011-01-28T02:15:12.007 に答える