规范化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_left是maximum_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）
• 内部哈希计数是所有特殊根节点的哈希计数之和
• 顶部哈希计数是所有其他（非特殊）根节点的哈希计数之和