본문으로 건너뛰기

정식 셀 직렬화

셀 가중치​

가중치는 셀 트리의 각 셀의 특성이며 다음과 같이 정의됩니다:

  • 셀이 트리의 리프 노드인 경우: 가중치 = 1
  • 일반 셀(리프가 아닌)의 경우 가중치는 합계: 셀 가중치 = 자식 가중치 + 1
  • 셀이 특수 셀인 경우 가중치는 0으로 설정

아래 알고리즘은 가중치 균형 트리를 만들기 위해 각 셀에 가중치를 할당하는 방법과 시기를 설명합니다.

가중치 재정렬 알고리즘​

각 셀은 가중치 균형 트리이며 reorder_cells() 메서드는 누적 자식 가중치를 기반으로 가중치를 재할당합니다. 순회 순서는 루트 -> 자식입니다. 캐시 선형성을 유지하기 위해 아마도 너비 우선 탐색을 사용합니다. 또한 해시 크기 재계산을 트리거하고 bag(루트)과 각 트리를 재인덱싱하며, 빈 참조에 대한 새 인덱스를 설정합니다. 재인덱싱은 깊이 우선이지만, 백서에서 이 인덱싱 순서가 선호된다고 명시하고 있어 이 순서에 의존하는 무언가가 있을 것 같습니다.

원본 노드의 셀 bag 직렬화를 따르려면:

  • 먼저, 셀의 가중치가 설정되지 않은 경우(노드는 셀 가져오기에서 이를 수행) 각 셀의 가중치를 1 + sum_child_weight로 설정합니다. 여기서 sum_child_weight는 자식 노드 가중치의 합입니다. 리프가 가중치 1을 갖도록 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입니다. 코드에서는 카운터 변수를 먼저 maximum_possible_weight - 1로 초기화한 다음 counter -= valid_ref_weight로 감소시키는 방식으로 구현할 수 있습니다. 본질적으로 남은 가중치를 이 노드들 사이에 재분배(균형)합니다.

  • 루트를 다시 순회하면서 각 루트에 대해:

    • 참조의 새로운 가중치 합이 maximum_possible_weight보다 작은지 확인하고, 새로운 합이 이전 루트 셀의 가중치보다 작아졌는지 확인한 후 가중치를 새로운 합으로 제한합니다. (new_sum < root_cell_weight이면 root_cell_weight를 new_sum과 같게 설정)
    • 새로운 합이 루트의 가중치보다 큰 경우, 가중치가 0인 특수 노드여야 하므로 그렇게 설정합니다. (여기서 노드의 해시 수만큼 내부 해시 수 증가)

  • 루트를 다시 순회하면서 각 루트에 대해: 특수 노드가 아닌 경우(가중치 > 0), 노드의 해시 수만큼 상단 해시 수를 증가시킵니다.

  • 트리를 재귀적으로 재인덱싱:

    • 먼저 모든 루트 셀을 사전 방문합니다. 이전에 사전 방문이나 방문하지 않은 경우, 재귀적으로 모든 참조를 특수 노드에 대해 확인합니다. 특수 노드를 찾으면 다른 노드보다 먼저 사전 방문하고 방문해야 합니다. 즉, 특수 노드의 자식이 목록에서 가장 먼저 오게 됩니다(가장 낮은 인덱스를 가짐). 그런 다음 다른 노드의 자식을 추가합니다(가장 깊은 -> 가장 높은 순서). 루트는 목록의 맨 끝에 옵니다(가장 큰 인덱스를 가짐). 결과적으로 노드가 깊을수록 더 낮은 인덱스를 갖는 정렬된 목록을 얻습니다.

maximum_possible_weight는 상수 64입니다.

주의사항​

  • 특수 셀은 가중치가 없습니다(0)

  • 가져올 때 가중치가 8비트에 맞는지 확인(가중치 <= 255)

  • 내부 해시 수는 모든 특수 루트 노드의 해시 수의 합계

  • 상단 해시 수는 다른 모든(특수하지 않은) 루트 노드의 해시 수의 합계