산술 부호화 구간 계산기
문자별 확률과 짧은 메시지를 넣으면 [0,1) 구간이 글자마다 어떻게 좁아지는지 단계별로 보이고, 최종 구간 안의 이진소수와 필요한 비트 수를 냅니다. 같은 확률표로 만든 허프만 부호와 나란히 놓아 정수 비트의 한계를 어떻게 넘는지 확인할 수 있습니다.
40글자까지. 한 글자마다 구간이 어떻게 좁아지는지 표로 나옵니다.
«기호:가중치»를 한 줄에 하나씩. 가중치는 1 이상의 정수여야 유리수로 정확히 셈할 수 있습니다.
메시지 전체를 담는 데 드는 비트
6비트
구간 폭이 0.03874205이므로 정보량이 4.69비트이고, 여기에 ⌈·⌉+1을 씌운 값입니다. 같은 확률표로 허프만 부호를 쓰면 10비트가 듭니다.
부호 — 구간 안의 이진소수
0.011
= 0.375이고 최종 구간 [0.34867844, 0.38742049) 안에 듭니다. 이 3비트만 보내면 받는 쪽은 같은 확률표로 구간을 되짚어 원문을 복원합니다.
확률 모델
| 기호 | 확률 | 맡은 칸 | 정보량 | 허프만 |
|---|---|---|---|---|
| a | 9/10 | 0 ~ 0.9 | 0.152b | 1b |
| b | 1/10 | 0.9 ~ 1 | 3.322b | 1b |
「정보량」과 「허프만」 열의 차이가 이 도구의 요점입니다. 정보량 −log₂(p)는 소수인데 허프만은 반드시 정수 비트를 써야 해서 늘 위로 올려 붙입니다. 확률이 모두 2의 거듭제곱이면 두 열이 딱 맞고, 그때만 허프만이 최적입니다. 엔트로피는 0.469비트/기호입니다.
구간이 좁아지는 과정
| 글자 | 좁혀진 구간 | 폭 | 쌓인 비트 |
|---|---|---|---|
| 1. a | [0, 0.9) | 0.9 | 0.15 |
| 2. a | [0, 0.81) | 0.81 | 0.3 |
| 3. a | [0, 0.729) | 0.729 | 0.46 |
| 4. a | [0, 0.6561) | 0.6561 | 0.61 |
| 5. a | [0, 0.59049) | 0.59049 | 0.76 |
| 6. a | [0, 0.531441) | 0.531441 | 0.91 |
| 7. a | [0, 0.4782969) | 0.4782969 | 1.06 |
| 8. a | [0, 0.43046721) | 0.43046721 | 1.22 |
| 9. a | [0, 0.387420489) | 0.387420489 | 1.37 |
| 10. b | [0.34867844, 0.387420489) | 0.038742049 | 4.69 |
글자를 하나 읽을 때마다 지금 구간을 확률대로 잘라 그 글자 몫만 남깁니다. 폭은 확률을 계속 곱한 값이므로 구간 폭이 곧 그 메시지가 나올 확률이고, 「쌓인 비트」는 log₂(1/폭)입니다. 흔한 글자를 읽으면 조금만 늘고 드문 글자를 읽으면 많이 느는 것을 보면 −log₂(p)가 왜 정보량인지가 보입니다.
사용 방법
- 1부호화할 메시지를 넣습니다. 40글자까지 다룹니다.
- 2확률 모델을 「기호:가중치」 꼴로 적거나, 메시지에서 세도록 고릅니다.
- 3「구간이 좁아지는 과정」 표에서 글자마다 폭이 확률만큼 곱해지는 것을 봅니다.
- 4「확률 모델」 표에서 정보량과 허프만 부호 길이 열을 견줍니다.
- 5최종 구간 안의 이진소수가 부호이며, 그것을 도로 읽어 원문이 나오는지 확인합니다.
자주 묻는 질문
[0, 1)에서 시작해 글자를 하나 읽을 때마다 지금 구간을 확률대로 잘라 그 글자 몫만 남깁니다. 글자 c의 확률이 p, 그 앞 글자들의 확률 합이 F라면 새 시작은 「시작 + 폭 × F」, 새 폭은 「폭 × p」입니다. 메시지가 끝나면 남은 구간 안의 아무 수나 하나 고른 것이 부호이고, 구간 폭이 곧 그 메시지가 나올 확률입니다.
⌈log₂(1/구간폭)⌉ + 1비트입니다. 폭은 확률을 계속 곱한 값이라 −log₂(확률)이 그대로 정보량이 되고, 그 구간을 가리키는 데 드는 자릿수가 이 값입니다. 그래서 산술 부호화는 엔트로피 한계에 1~2비트 차이로 붙습니다. 메시지가 길수록 이 1~2비트가 전체에서 차지하는 몫이 작아져 한계에 더 가까워집니다.
허프만은 글자마다 부호를 하나씩 배정하므로 길이가 반드시 정수 비트입니다. 확률 0.9인 글자의 정보량은 0.152비트인데 허프만은 1비트를 써서 여섯 배를 씁니다. 산술 부호화는 글자마다 부호를 주는 대신 메시지 전체를 구간 하나로 나타내므로 「0.152비트어치만 자르는」 것이 그대로 됩니다. 확률이 모두 2의 거듭제곱일 때만 두 방식이 같아지고, 그때가 허프만이 최적인 유일한 경우입니다.
구간 폭이 글자마다 확률만큼 곱해져 지수로 줄기 때문입니다. 배정밀도 실수는 유효자리가 53비트뿐이라 엔트로피가 2비트/글자면 27글자쯤에서 구간의 시작과 끝이 같은 수로 뭉개집니다. 그때부터 답이 틀리는데 예외도 나지 않아 알아채기 어렵습니다. 이 계산기는 확률을 정수 가중치 c/T로 받아 BigInt 유리수로 셈하며, 글자 n개를 읽은 뒤 분모가 정확히 T^n이라 오차가 없습니다.
아닙니다. 자릿수 재조정(renormalization)을 써서 구간의 앞자리가 확정될 때마다 그 비트를 내보내고 남은 구간을 두 배로 폅니다. 그래야 32비트 정수만으로 몇 기가바이트짜리 파일도 부호화할 수 있습니다. 이 계산기는 원리를 보이는 것이 목적이라 분모가 커지도록 두었고, 재조정은 다루지 않습니다.
부호와 함께 보내거나, 양쪽이 같은 규칙으로 확률을 갱신해야 합니다. 확률표를 함께 보내면 그 몫이 짧은 메시지에서는 본문보다 클 수도 있습니다. 실제 압축기는 지금까지 읽은 글자로 확률을 계속 고쳐 나가는 적응형 모델을 써서 표를 아예 보내지 않는 쪽을 택하는 경우가 많습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 구간은 BigInt 유리수로 정확히 셈합니다. 글자 n개를 읽은 뒤 분모가 정확히 T^n(T는 가중치 총합)이라 시작과 폭을 그 위의 정수로만 들고 있으면 오차가 생기지 않습니다. 가중치를 정수로만 받는 것이 이 때문입니다.
- 검증은 무작위 메시지 500벌(모델 4종 × 길이 1~20)을 부호화한 뒤 도로 읽어 원문과 같은지 대조해 했습니다. 왕복이 맞는다는 것은 구간 계산과 이진소수 선택이 모두 맞다는 뜻입니다.
- 손으로 셈한 값과도 맞췄습니다. a:1 b:1 모델의 「ab」가 [1/4, 1/2)이고 부호가 0.01인 것, a:3 b:1 모델의 「aaaa」가 [0, 81/256)이고 정보량이 8 − log₂81비트인 것을 고정해 두었습니다.
- 「구간에 드는 가장 짧은 이진소수」는 자릿수를 하나씩 늘려 가며 찾은 진짜 최솟값입니다. 한 자리 짧게는 구간 안에 드는 이진소수가 없다는 것까지 테스트로 확인했습니다. 구간이 0을 품으면 소수점 아래가 한 자리도 필요 없어 0비트가 나오는데, 실제 부호기는 메시지 끝을 알리는 몫이 따로 있어 이렇게까지 줄지 않습니다.
- 허프만 부호 길이는 같은 확률표로 만든 허프만 트리에서 가져옵니다. 확률이 모두 2의 거듭제곱이면 산술 부호화의 정보량과 정확히 같아지는 것, 한쪽으로 크게 쏠리면 크게 벌어지는 것을 함께 고정했습니다.
- 배정밀도 실수로 같은 계산을 나란히 돌려 구간이 뭉개지는 글자 번호를 함께 보입니다. 균등한 네 기호로는 27글자 언저리에서 뭉개집니다. 다만 구간이 0에 붙어 있으면(첫 기호만 이어지면) 시작이 0이라 뭉개지지 않습니다.
- 메시지는 40글자, 기호는 20종까지 다룹니다. 글자마다 구간을 그려 보이는 것이 목적이라 그보다 길면 표가 읽히지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.