跳到主要内容

规范化cell序列化

cell权重

Weight是定义每个cell在cell树中的特征,具体如下:

  • 如果cell是cell树中的叶节点:weight = 1
  • 对于普通cell(非叶子),权重是一个总和:cell weight = children weight + 1
  • 如果cell是特殊的,其权重设为零。

以下算法解释了我们如何以及何时为每个cell分配权重以创建一个权重平衡的树。

权重重排序算法

每个cell都是权重平衡树,reorder_cells() 方法 基于累积子权重重新分配权重。遍历顺序是根 -> 子节点。这是一种广度优先搜索,可能用于保持缓存线性。它还触发哈希大小的重新计算,并对包(根)和每个树进行重新索引,为空引用设置新索引。尽管重新索引是深度优先的,可能存在某些依赖于此索引顺序的内容,正如白皮书所述,这是首选的。

要遵循原始节点的cell序列化,您应该:

  • 首先,如果cell的权重尚未设置(节点在cell导入时这样做),我们将每个cell的权重设置为1 + sum_child_weight,其中sum_child_weight是其子节点权重的总和。我们添加1以使叶子具有1的权重。

  • 遍历所有根,对于每个根cell:

    • 检查它的每个引用是否有一个权重小于maximum_possible_weight - 1 + ref_index除以根cell引用的数量,以便它们均匀地共享父权重,我们做(+ index)以确保如果语言在除法中向0取整,我们总是得到一个数学上四舍五入的数字(例如对于5 / 3,c++会返回1,但我们在这里希望2)

    • 如果一些引用违反了该规则,我们将它们添加到列表中(或更有效地创建一个位掩码,就像原始节点所做的那样),然后再次遍历这些引用,并将它们的权重限制为weight_left / invalid_ref_count,其中weight_leftmaximum_possible_weight - 1 - sum_of_valid_refs_weights。在代码中,它可以实现为减少一个计数器变量,该变量首先初始化为maximum_possible_weight - 1,然后当counter -= valid_ref_weight时递减。因此,我们基本上在这些节点之间重新分配剩余权重(平衡它们)

  • 再次遍历根,对于每个根:

    • 确保其引用的新权重总和小于maximum_possible_weight,检查新总和是否小于先前根cell的权重,并将其权重限制为新总和。(如果new_sum < root_cell_weight,则将root_cell_weight设置为等于new_sum
    • 如果新总和高于根的权重,则它应该是一个特殊节点,其权重为0,设置它。(这里通过节点的哈希计数增加内部哈希计数)
  • 再次遍历根,对于每个根: 如果它不是特殊节点(如果其权重> 0),则通过节点的哈希计数将顶部哈希计数增加。

  • 递归地重新索引树:

    • 首先,我们预访问所有根cell。如果我们之前没有预访问或访问过此节点,请递归检查其所有引用以查找特殊节点。如果我们找到一个特殊节点,我们必须在其他节点之前预访问和访问它,这意味着特殊节点的子节点将首先出现在列表中(它们的索引将是最低的)。然后我们添加其他节点的子节点(顺序最深 -> 最高)。根在列表的最后(它们有最大的索引)。因此,最终我们得到一个排序的列表,其中节点越深,其索引就越低。

maximum_possible_weight是常数64

注释

  • 特殊cell没有权重(它是0)

  • 确保导入时的权重适合8位(weight <= 255)

  • 内部哈希计数是所有特殊根节点的哈希计数之和

  • 顶部哈希计数是所有其他(非特殊)根节点的哈希计数之和