엘리아스 감마·델타 부호 계산기

값의 이진수 길이 − 1만큼 0을 앞에 붙이고 이어서 이진수를 그대로 적습니다. 5는 이진수가 101(3비트)이므로 0을 두 개 붙여 00101이 됩니다. 읽을 때는 1이 나올 때까지 0을 세고 그 개수만큼 더 읽으면 한 수가 끝납니다.

감마의 앞부분(0을 늘어놓는 부분)을 다시 감마로 적어 줄인 것입니다. 값의 비트 수를 감마로 쓴 뒤, 값의 이진수에서 맨 앞 1을 뗀 나머지를 붙입니다. 맨 앞 1을 떼도 되는 이유는 비트 수를 이미 알기 때문입니다.

31까지는 감마가 같거나 짧고, 32부터 델타가 앞섭니다. 값이 커질수록 차이가 벌어져 10억(30비트)이라면 감마 59비트, 델타 38비트입니다. 다룰 값이 대부분 작다면 감마가, 크다면 델타가 유리합니다.

부호가 스스로 길이를 알려 주기 때문입니다. 감마라면 앞의 0 개수가 곧 「뒤로 몇 비트를 더 읽어야 하는가」이므로, 여러 수를 그냥 이어 붙여도 읽는 쪽이 정확히 나눌 수 있습니다. 이런 성질을 접두 부호(prefix-free)라고 합니다.

매개변수가 없기 때문입니다. 골롬–라이스 부호는 값이 대략 어느 크기인지 알아야 k를 정할 수 있지만, 엘리아스 부호는 분포를 몰라도 그냥 쓸 수 있고 어떤 분포에서도 최적의 상수배 안에 듭니다. 대신 분포를 잘 아는 경우에는 골롬–라이스가 더 짧습니다.

0은 이진수가 「0」 한 자리라 「맨 앞 비트가 1」이라는 전제가 무너지기 때문입니다. 두 부호 모두 1 이상만 다루므로, 0부터 쓰려면 n + 1을 부호화하고 읽을 때 1을 빼는 것이 관행입니다.

검색 엔진의 역색인처럼 1 이상인 정수를 줄줄이 적는 자리에 쓰입니다. 문서 번호를 그대로 적는 대신 앞 번호와의 차이(gap)를 적으면 값이 작아지는데, 작은 값이 짧게 적히는 이 부호와 잘 맞습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.