algorithm - 具有均匀分布的随机可变长度编码数字

Question

假设当我可以检索解析某个虚拟b树的数据并在到达项时停止（类似于huffman编码）时，我将数据呈现为可变长度编码。项目数未知（在最佳情况下，只有上限已知）。是否有生成均匀分布数的算法？问题是，在这种情况下，基于硬币的算法会给出不一致的结果，例如，如果有一个编码为101的数字，而有一个编码为10010101的数字，后者与前者相比将很少出现。
更新：换句话说，当每个元素都可以用任意数量的比特来处理（并且根据信息理论来处理）时，我有一组最大的n个元素（但可能更少），因此，如果一个元素被编码101，那么没有其他元素可以用相同的前缀编码。所以当我向左或向右看的时候，它更像是b-树，在某个时刻，我得到了数据项。我想用这种技术得到一个随机数序列，但是它们的分布应该是均匀的（选择随机的左-右不起作用的例子在上面，数字101和10010101）
谢谢
马克斯

Answer 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（1）中的O（n）初始设置时间之后随机选择一个。
但是，如果你不想占用任何存储空间，这里有一个非常有规律的选择。首先找到树的深度的一个界限（我将标记为b）（如果需要，我们可以使用n-1，但显然，这是一个非常松散的界限。找到的界限越紧，算法运行的速度就越快）接下来，我们将以随机但均匀的方式生成一个可能的节点标签。有2^（b+1）-1种可能性。这不仅仅是2^b，因为例如，字符串“0011”和“11”是完全不同的字符串。因此，我们需要计算所有可能的长度在0和B之间的二进制字符串。显然，我们有长度为I的2^I字符串。因此，对于长度为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

当然，这方面的时间分析相当可怕。基本上，while循环将平均运行（2^（b+1）-1）/n次。所以，在最坏的情况下，是o（（2^n）/n），这很糟糕。在最好的情况下，B的顺序是log（N），所以它大致是O（1），但这要求树是相当平衡的，而它可能不是不过，如果你真的不需要额外的空间，这个方法可以做到。
我真的不认为不存储一些信息就可以做得比上一种方法更好。这听起来很吸引人，因为你可以遍历树，做随机的决定，但没有存储额外的信息，结构，你只是不能做到这一点。每次做出分支决策时，您可以只在左侧有一个节点，在右侧有一百万个节点，也可以在左侧有一百万个节点，在右侧只有一个节点因为这两者都是可能的，你不知道是哪一种情况，根本没有办法在双方之间做出一个甚至是随机的决定显然50-50不起作用，任何其他选择都会有类似的问题。
所以，如果你不需要额外的空间，第二种方法会起作用，但要慢。如果您不介意添加一些额外的空间，第一种方法将工作并快速。而且，正如我前面所说，如果你不打算改变树，你会选择很多随机节点，然后咬紧牙关，只需遍历树，将所有叶节点粘贴在一个自生长数组或向量中，然后从中选择。