균일 한 분포를 갖는 무작위 가변 길이 인코딩 된 숫자

Question

일부 가상 b-tree를 구문 분석하고 해당 항목에 도달 할 때 데이터 (허프만 인코딩과 유사)를 검색 할 수있는 데이터가 가변 길이 인코딩으로 있다고 가정합니다. 알 수없는 항목이 있습니다 (최상의 경우는 상한 만 알 수 있음). 균일하게 분산 된 숫자를 생성하는 알고리즘이 있습니까? 문제는 코인 기반 알고리즘이이 경우에 비 균일 결과를 제공한다는 것입니다. 예를 들어, 101로 인코딩 된 숫자가 있고 10010101로 인코딩 된 숫자가있는 경우, 후자는 이전과 비교할 때 매우 드물게 나타납니다.

업데이트 : 즉, 모든 요소를 ​​임의의 비트 수로 주소 지정할 수있는 최대 N 개의 요소 집합을 가지고 있습니다 (정보 이론에 따르면 101 개로 인코딩 된 경우 다른 요소는 동일한 접두사로 인코딩 될 수 있음). 그래서 조금씩 왼쪽이나 오른쪽으로 가면 순간적으로 B-Tree와 비슷하게되고 데이터 항목을 보게됩니다. 이 기술로 처리되는 난수 시퀀스를 얻으려고합니다. 그러나 이들의 분포는 균일해야합니다 (예 : 임의로 좌우 선택을 선택하지 않으면 숫자 101과 10010101)

감사합니다.

최대

Answer 1

나는 세 가지 기본 방법 중 하나가 자주 규제가 포함되며 그 중 하나에는 추가 정보가 포함됩니다. 나는이 중 하나 또는 다른 것을하는 것이 피할 수 없다고 생각합니다. 추가 정보 하나부터 시작하겠습니다 :

각 노드에는 자손의 수를 나타내는 count 숫자를 저장하십시오. 모든 노드에 대해 왼쪽과 오른쪽으로 이동할지 여부를 왼쪽 노드의 자식 수와 비교하여 알려면 해당 노드에 대해 1에서 count 사이의 숫자가 필요합니다. 여기 알고리즘입니다 :

n := random integer between 1 and root.count 
node := route 
while node.count != 1 
    if n <= node.left.count 
      node = node.left 
    else 
      node = node.right 
      n = n - node.left.count 

그래서, 기본적으로, 우리는 모든 노드에서 왼쪽에서 오른쪽 순서를 부과하고 왼쪽에서 n 번째 하나를 선택하고 있습니다. 이것은 상당히 빠르며 오직 O (tree of depth) 만 가지고 있습니다. 모든 노드 레이블을 포함하는 벡터를 만드는 것과 같은 일을하지 않고도 할 수있는 최선의 방법입니다. 또한 수를 정정해야하기 때문에 트리의 변경 사항에 O (트리의 깊이) 오버 헤드를 추가합니다. 다른 방법으로 나무를 전혀 바꾸지 않고 랜덤 노드를 많이 선택하려는 경우에는 글 머리 기호를 비트하고 모든 노드 레이블을 벡터에 넣으십시오. 그렇게하면 O (N) 초기 설정 시간 후에 O (1)에서 임의의 것을 선택할 수 있습니다.

그러나 저장 공간을 모두 사용하지 않으려는 경우에는 다음과 같이 많은 규제가 필요합니다. 먼저 트리의 깊이에 대한 경계 (B로 표시)를 찾아야합니다 (필요한 경우 N-1을 사용할 수 있지만 분명히 매우 느슨한 경계입니다.) 찾을 수있는 경계가 좁을수록 알고리즘이 빠릅니다 실행). 다음으로 무작위로 가능한 노드 레이블을 생성하겠습니다. 2^(B + 1) -1 개의 가능성이 있습니다. 예를 들어, 문자열 "0011"과 "11"은 완전히 다른 문자열이므로 2^B가 아닙니다. 결과적으로, 우리는 0과 B 사이의 모든 가능한 길이의 이진 문자열을 계산해야합니다. 분명히 우리는 길이가 2 i 인 문자열을 가지고 있습니다. 따라서 길이가 i 이하인 문자열의 경우 sum (i = 0 ~ B) {2^i} = 2^(B + 1) -1이됩니다. 따라서 0과 2^(B + 1) -2 사이의 숫자를 선택한 다음 해당 노드 레이블을 찾을 수 있습니다. 물론 숫자에서 노드 레이블로의 매핑은 간단하지 않으므로 여기에서 설명하겠습니다.

우리는 선택한 숫자를 일반적인 방식으로 비트 열로 변환합니다. 그런 다음 왼쪽에서부터 읽으면 첫 번째 숫자가 0이면 노드 레이블은 오른쪽에있는 나머지 문자열입니다 (사용하지 않을 가능성이있는 유효한 노드 레이블 일 수있는 빈 문자열 일 수도 있음). 첫 번째 숫자가 1이면 우리는 그것을 버리고이 과정을 반복합니다. 따라서, B = 4이면, 노드 레이블 "0001"은 "00001"의 번호에서 나옵니다.노드 레이블 "001"은 "10001"의 번호에서옵니다. 노드 레이블 "01"은 번호 "11001"에서 나옵니다. 노드 레이블 "1"은 숫자 "11101"에서옵니다. 그리고 노드 레이블 ""은 "11110"의 번호에서옵니다. 이 스킴에서는 유효한 해석이없는 2^(B + 1) -1 (이 경우 "11111") 숫자는 포함하지 않았습니다. 나는 독자들에게 길이 0에서 B까지의 모든 스트링이이 스킴 하에서 표현 될 수 있음을 증명하기위한 운동으로 남겨 둘 것이다. 그것을 증명하려고 노력하기보다는, 나는 그것이 작동 할 것이라고 단언 할 것입니다.

이제 노드 레이블이 생겼습니다. 다음 단계는 해당 레이블이 트리를 통과하여 존재하는지 확인하는 것입니다. 그렇다면 우리는 끝났어. 그렇지 않은 경우 새 번호를 선택하고 다시 시작하십시오 (즉, 조정 부분). 합법적 인 노드 레이블의 작은 부분 만 사용되기 때문에 엄청나게 규제해야 할 것 같지만 공정성을 왜곡시키지 않고 시간을 늘리십시오.

function num_to_binary_list(n,digits) = 
    if digits == 0 return() 
    if n mod 2 == 0 return 0 :: num_to_digits(n/2,digits-1) 
    else return 1 :: num_to_digits((n-1)/2,digits-1) 

function binary_list_to_node_label_list(l) = 
    if l.head() == 0 return l.tail() 
    else return binary_list_to_node_label_list(l.tail()) 

function check_node_label_list_against_tree(str,node) = 
    if node == null return false,null 
    if str.isEmpty() 
    if node.isLeaf() return true,node 
    else return false,null 
    if str.head() == 0 return check_node_label_list_against_tree(str.tail(),node.left) 
    else check_node_label_list_against_tree(str.tail,node.right) 

function generate_random_node tree b = 
    found := false 
    while (not found) 
    x := random(0,2**(b+1)-2) // We're assuming that this random selects inclusively 
    node_label := binary_list_to_node_label(num_to_binary_list(x,b+1)) 
    found,node := check_node_label_list_against_tree(node_label,tree) 
    return node 

이의 타이밍 분석은 물론, 꽤 끔찍한입니다 :

는 다음 네 가지 기능이 과정의 의사 코드 버전입니다. 기본적으로 while 루프는 평균 (2^(B + 1) -1)/N 번 실행됩니다. 그래서, 최악의 경우, 그것은 끔찍한 O ((2^N)/N)입니다. 가장 좋은 경우, B는 log (N)의 차수가 될 것이므로 대략 O (1)가 될 것입니다.하지만 그럴 경우 나무가 균형을 이루지 않아야합니다. 그래도 공간을 추가하지 않으려면이 방법을 사용합니다.

저는 정보를 저장하지 않고이 마지막 방법보다 더 잘 할 수 있다고 생각하지 않습니다. 나무를 횡단하여 무작위로 결정을 내리는 것이 매력적이지만 구조에 대한 추가 정보를 저장하지 않으면 그 일을 할 수 없을 것입니다. 분기 결정을 내릴 때마다 왼쪽에는 하나의 노드가 있고 오른쪽에는 백만 개의 노드가 있거나 왼쪽에는 백만 개의 노드가 있고 오른쪽에는 하나의 노드가있을 수 있습니다. 그 둘 모두 가능하고 어떤 경우인지 모르기 때문에 양측간에 무작위로 의사 결정을 내릴 수있는 방법이 없습니다. 분명히 50-50은 효과가 없으며 다른 선택은 비슷한 문제가 될 것입니다.

따라서 공간을 추가하지 않으려면 두 번째 방법이 효과적 일 수 있지만 느려질 수 있습니다. 약간의 여유 공간을 추가하는 데 신경 쓰지 않는다면 첫 번째 방법이 효과적 일 것입니다. 앞에서 말했듯이, 만약 당신이 나무를 바꾸지 않고 많은 무작위 노드를 선택한다면, 총알을 물고 나무를 가로 지르며 모든 잎 노드를 자기 성장 어레이에 붙이십시오 또는 벡터를 선택하고 그 다음부터 선택하십시오.