Каноническая сериализация ячеек

warning

Эта страница переведена сообществом на русский язык, но нуждается в улучшениях. Если вы хотите принять участие в переводе свяжитесь с @alexgton.

Вес ячейки

Weight это характеристика каждой ячейки в дереве ячеек, которая определяется следующим образом:

• Если ячейка является конечным узлом в дереве ячее: weight = 1;
• Для обычных ячеек (не листьев) вес — это сумма: cell weight = children weight + 1;
• Если ячейка является special, ее вес устанавливается равным нулю.

Приведенный ниже алгоритм объясняет, как и когда мы назначаем веса каждой ячейке для создания сбалансированного по весу дерева.

Алгоритм переупорядочивания весов

Каждая ячейка является сбалансированным по весу деревом, и метод reorder_cells() переназначает веса на основе совокупного веса потомков. Порядок обхода — roots -> children. Это поиск в ширину, вероятно, используемый для сохранения линейности кэша. Он также запускает пересчет размера хэшей и переиндексирует bag (roots) и каждое дерево, устанавливает новые индексы для пустых ссылок. Переиндексация выполняется в глубину, хотя, возможно, есть что-то, что зависит от этого порядка индексации, поскольку в техническом описании указано, что это предпочтительнее.

Чтобы следовать сериализации bag of cells исходного узла, вам следует:

• Во-первых, если веса ячеек не установлены (узел делает это при импорте ячеек), мы устанавливаем вес для каждой ячейки на 1 + sum_child_weight, где sum_child_weight — это сумма весов его дочерних узлов. Добавляем один, чтобы листья имели вес 1.

• Повторяем все корни для каждой корневой ячейки:

  • Проверьте, имеет ли каждая из его ссылок вес меньше, чем maximum_possible_weight - 1 + ref_index, разделенный на количество ссылок в корневой ячейке, чтобы они равномерно распределяли родительский вес, мы делаем (+ index), чтобы убедиться, что если язык при делении принимает значение 0, мы всегда получаем математически округленное число (например, для 5 / 3, c++ вернул бы значение 1, но здесь нам нужно значение 2)

  • Если какие-то ссылки нарушают это правило, мы добавляем их в список (или, что более эффективно, создаем битовую маску, как это делает исходный узел), а затем снова выполняем итерацию по ним и фиксируем их вес до weight_left / invalid_ref_count, где weight_left - это maximum_possible_weight - 1 - sum_of_valid_refs_weights. В коде это может быть реализовано как уменьшение переменной counter, которая сначала инициализируется значением maximum_possible_weight - 1, а затем уменьшается как counter -= valid_ref_weight. Таким образом, по сути, мы перераспределяем оставшийся вес между этими узлами (балансируем их)

• Снова перебираем корни для каждого корня:

  • Убедитесь, что новая сумма весов его ссылки меньше, чем maximum_possible_weight, проверьте, стала ли новая сумма меньше веса предыдущей корневой ячейки, и сопоставьте ее вес с новой суммой. (если new_sum < root_cell_weight, установите root_cell_weight равным new_sum)
  • Если новая сумма больше веса корня, то это должен быть особый узел, который имеет вес 0, установим его. (Увеличьте здесь количество внутренних хэшей на количество хэшей узла)

• Снова перебираем корни для каждого корня: Если это не особый узел (если его weight > 0), увеличим количество верхних хэшей на количество хэшей узла.

• Рекурсивно переиндексируем дерево:

  • Сначала мы просматриваем все корневые ячейки. Если мы не просматривали или не посещали этот узел раньше, рекурсивно проверьте все его ссылки на наличие специальных узлов. Если мы находим специальный узел, мы должны просмотреть его раньше других, это означает, что дочерние узлы этого специального узла будут первыми в списке (их индексы будут самыми низкими). Затем мы добавляем дочерние узлы других узлов (в порядке наибольшей глубины -> наибольшей высоты). Корни находятся в самом конце списка (у них самые большие индексы). Таким образом, в итоге мы получаем отсортированный список, где чем глубже находится узел, тем меньший у него индекс.

maximum_possible_weight это константа 64

Обозначения

• Специальная ячейка не имеет веса (это 0)

• Убедитесь, что вес при импорте укладывается в 8 бит (weight <= 255)

• Внутреннее количество хэшей — это сумма количества хэшей всех специальных корневых узлов

• Верхнее количество хэшей — это сумма количества хэшей всех остальных (не специальных) корневых узлов