0

假设当我可以检索解析某些虚拟 b-tree 的数据并在到达项目时停止（类似于 Huffman 编码）时，我有数据以可变长度编码呈现。项目数量未知（在最好的情况下，只有上限是已知的）。是否有生成均匀分布数字的算法？问题是在这种情况下，基于硬币的算法会给出不一致的结果，例如，如果有一个编码为 101 的数字和一个编码为 10010101 的数字，与前者相比，后者将很少出现。

更新：换句话说，当每个元素都可以用任意数量的位寻址时，我有一组最大 N 个元素（但可能更少）（并且根据信息理论，所以如果一个被编码为 101 则没有其他元素可以是用相同的前缀编码）。因此，当我根据一点向左或向右移动时，它更像是 B-Tree，有时我会到达数据项。我想得到一个用这种技术解决的随机数序列，但它们的分布应该是均匀的（上面的例子为什么随机选择左右不起作用，数字 101 和 10010101）

谢谢

最大限度

4

1 回答 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 种可能性。这不仅仅是 2^B，因为例如字符串“0011”和“11”是完全不同的字符串。因此，我们需要计算所有可能的长度在 0 到 B 之间的二进制字符串。显然，我们有 2^i 个长度为 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 的每个字符串都可以在这个方案下表示。我不会试图证明它，而是断言它会起作用。

所以现在我们有一个节点标签。下一步是通过遍历树来查看该标签是否存在。如果是这样，我们就完成了。如果不是，则选择一个新号码并重新开始（这是猜测部分）。可能需要进行很多猜测，因为只有一小部分合法节点标签会被使用，但这不会影响公平性，只会增加时间。

这是此过程的四个函数的伪代码版本：

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 不起作用，任何其他选择都会有类似的问题。

所以，如果你不想要额外的空间，第二种方法会起作用，但会很慢。如果您不介意添加一些额外的空间，第一种方法将起作用并且速度很快。而且，正如我之前所说，如果您不打算更改树并且您将选择大量随机节点，那么硬着头皮遍历树并将所有叶节点粘贴在一个自增长的数组中或向量，然后从中挑选。

于 2011-01-28T02:15:12.007 回答