정수 숫자에 대한 이진 인코딩 구성표의 이름

Question

나는 한 번 wikipedia에서 발견 $ k \ in (2 ^ {n-1}, 2 ^ n) $ 균일하게 분산 된 정수를 균일하게 $ \ log_2n $ 평균 비트 / 기호, 가변 길이 코드를 간단하게 사용합니다.기본적으로 일부 기호와 $ \ log_2n - 1 $ 에 대해 $ \ log_2n $ 을 사용했습니다.

불행히도 모든 Googling은 모두 실패했습니다.나는 "가변 길이 바이너리"와 비슷한 것을 회상하지만, 다른 짐승 인 VLQ는 계속 끝나고 있습니다.나는 당신의 기억을 내 것보다 낫다는 것을 알고 있기 때문에, 당신은 나를 도울 수 있습니까?

Answer 1

기술 아이디어는 Yuval Filmus 답변으로 완벽하게 설명됩니다.약간 다르더라도, 잘린 바이너리 인코딩 가 잘 렸습니다.나는 특허 "를 언급 한 것 외에도 그대로 원래 소스를 찾을 수 없었습니다.,이 책 또는이 Google API

Answer 2

$ k= 2 ^ {n-1} + t $ , 여기서 $ 0 \ Leq T <2 ^ {n-1} $ . $ z \ {0, \ ldots, k-1 \} $ :

을 인코딩하려면 다음을 사용하십시오.

• $ z <2 ^ {n-1} -t $ 인 경우 $ z $ 자체 $ (n-1) $ -bit 인코딩.
• 그렇지 않으면 $ z= 2 ^ {n-1} -t + 2 \ Δ + epsilon $ , 여기서 $ \ delta \ \ {0, \ ldots, t-1 \} $ 및 $ \ epsilon \ in \ {0,1 \} $ . $ (n-1) $ $ z $ 을 인코딩합니다. 수학 컨테이너 "> $ 2 ^ {n-1} -t + \ Δ $ 뒤에 $ \ epsilon $

다음은 예제입니다. $ k= 11= 2 ^ 3 + 3 $ 을 보자. 인코딩은 다음과 같습니다.

• $ 0 \ 000 $
• $ 1 \ 001 $ .
• $ 2 \ 010 $
• $ 3 \ 011 $
• $ 4 \ 100 $
• $ 5 \ $ 1010 $
• $ 6 \ $ \ $
• $ 7 \ 1100 $
• $ 8 \ 1101 $
• $ 9 \ 1110 $
• $ 10 \ 1111 $