본문으로 건너뛰기

표준 셀 직렬화

셀 무게​

'무게'는 트리 오브 셀에서 각 셀의 특성으로 다음과 같이 정의됩니다:

  • 셀이 셀 트리의 탈퇴 노드인 경우: weight = 1;
  • 일반 세포(잎이 아닌)의 경우 무게는 '세포 무게 = 어린이 무게 + 1'의 합계입니다;
  • 셀이 special인 경우 가중치는 0으로 설정됩니다.

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

가중치 재주문 알고리즘​

각 셀은 가중치가 균형 잡힌 트리이며 reorder_cells() 메서드 는 누적 자식 가중치를 기준으로 가중치를 재할당합니다. 탐색 순서는 루트 -> 자식입니다. 이는 캐시 선형성을 유지하기 위해 아마도 사용되는 폭 우선 검색입니다. 또한 해시 크기 재계산을 트리거하고 가방(루트)과 각 트리를 재색인하고 빈 참조에 대해 새 인덱스를 설정합니다. 재색인 작업은 깊이 우선이지만, 백서에 따르면 이 색인 순서가 선호된다고 명시되어 있으므로 아마도 이 색인 순서에 따라 달라지는 것이 있을 것입니다.

원래 노드의 셀 직렬화 백을 따르려면 다음과 같이 해야 합니다:

  • 먼저 셀의 가중치가 설정되지 않은 경우(노드가 셀 가져오기 시 이 작업을 수행) 각 셀의 가중치를 1 + sum_child_weight로 설정합니다. 여기서 sum_child_weight는 하위 노드의 가중치를 합한 값입니다. 잎의 가중치가 1이 되도록 1을 추가합니다.

  • 각 루트 셀에 대해 모든 루트를 반복합니다:

    • 각 참조의 가중치를 루트 셀의 참조 수로 나눈 '최대가능가중치-1 + 참조_인덱스'보다 작은지 확인하여 부모 가중치를 균일하게 공유하도록 하고, 언어가 나누기 시 0으로 캐스팅하는 경우 항상 수학적으로 반올림된 숫자가 나오도록 (+ 인덱스) 합니다(5 / 3의 경우 c++는 1을 반환하지만 여기서는 2를 원합니다).

    • 일부 참조가 이 규칙을 위반하는 경우, 해당 참조를 목록에 추가(또는 원래 노드처럼 비트마스크를 생성하는 것이 더 효율적)한 다음 다시 반복하여 가중치를 weight_left / invalid_ref_count로 클램프(여기서 weight_left는 최대_가능_weight - 1 - sum_of_valid_refs_weights입니다)하면 됩니다. 코드에서는 카운터 변수의 감소로 구현할 수 있는데, 이 변수는 먼저 maximum_possible_weight - 1로 초기화된 다음 counter -= valid_ref_weight로 감소됩니다. 따라서 기본적으로 다음 노드 간에 남은 가중치를 재분배(균형 조정)합니다.

  • 각 루트에 대해 루트를 다시 반복합니다:

    • 참조 가중치의 새 합이 최대 가능한 가중치보다 작은지 확인하고, 새 합이 이전 루트 셀의 가중치보다 작아졌는지 확인한 후 가중치를 새 합으로 고정합니다. (new_sum < root_cell_weight이면 root_cell_weight를 new_sum과 동일하게 설정합니다.)
    • 새로운 합이 루트의 가중치보다 높으면 가중치가 0인 특수 노드가 되어야 하며, 이를 설정합니다. (여기서 내부 해시 카운트는 노드의 해시 카운트만큼 증가합니다).

  • 각 루트에 대해 루트를 다시 반복합니다: 특수 노드가 아닌 경우(가중치가 0보다 큰 경우), 노드의 해시 수만큼 상위 해시 수를 증가시킵니다.

  • 재귀적으로 트리를 다시 색인화합니다:

    • 먼저 모든 루트 셀을 사전 방문합니다. 이전에 이 노드를 미리 방문하거나 방문한 적이 없는 경우, 특수 노드가 있는지 모든 참조를 재귀적으로 확인합니다. 특수 노드를 발견하면 다른 노드보다 먼저 방문해야 하는데, 이는 특수 노드의 자식이 목록에서 가장 먼저 오게 된다는 것을 의미합니다(인덱스가 가장 낮은 노드가 됩니다). 그런 다음 다른 노드의 자식들을 추가합니다(가장 깊은 순서-> 가장 높은 순서). 루트는 목록의 맨 끝에 오게 됩니다(가장 큰 인덱스를 가집니다). 따라서 결국 더 깊은 노드일수록 인덱스가 낮은 정렬된 목록을 얻게 됩니다.

최대가능무게`는 상수 64입니다.

다음을 나타냅니다.​

  • 특수 셀에는 가중치가 없습니다(0입니다).

  • 가져오기 시 무게가 8비트에 맞는지 확인합니다(무게 <= 255).

  • 내부 해시 카운트는 모든 특수 루트 노드의 해시 카운트를 합한 값입니다.

  • 최상위 해시 카운트는 다른 모든 (특별하지 않은) 루트 노드의 해시 카운트를 합한 값입니다.