비대칭 수 체계(rANS) 부호화 계산기

기호마다 빈도 f_s, 전체 빈도의 합 M, 그 기호 앞의 누적빈도 c_s를 정해 두고, x′ = ⌊x/f_s⌋·M + (x mod f_s) + c_s로 계산합니다. 빈도가 큰(자주 나오는) 기호일수록 ⌊x/f_s⌋가 작아 상태가 덜 불어나므로, 자주 나오는 기호는 싼 값에, 드문 기호는 비싼 값에 상태를 불리는 셈입니다.

인코딩은 기호를 s₁, s₂, ..., sₙ 순서로 상태 하나에 계속 밀어 넣습니다. 디코딩은 그 최종 상태에서 시작해 맨 나중에 넣은 sₙ부터 꺼내고 맨 마지막에 s₁이 나옵니다. 스택에 쌓았다가 뽑는 것과 같은 후입선출(LIFO) 구조이기 때문이며, 그래서 원래 순서로 복원하려면 디코딩된 목록을 다시 뒤집어야 합니다.

slot = x′ mod M을 구해, 그 값이 어느 기호의 누적빈도 구간 [c_s, c_s+f_s)에 들어가는지 찾으면 그것이 방금 넣은 기호입니다. 이전 상태는 x = f_s·⌊x′/M⌋ + slot − c_s로 되돌립니다. 인코딩 식을 정확히 거꾸로 푼 것입니다.

허프만은 기호마다 정수 개의 비트만 쓸 수 있어 확률이 정확히 2의 거듭제곱 분의 1이 아니면 손해를 봅니다. 산술부호화는 로그 비트(분수 비트)를 쓸 수 있어 그 손해가 없지만 구현이 복잡하고 느립니다. rANS는 산술부호화만큼 분수 비트를 쓰면서도 정수 연산 몇 번으로 끝나 훨씬 단순하고 빠릅니다 — Zstandard·LZFSE가 이것을 쓰는 이유입니다.

실전 구현은 상태가 너무 커지지 않도록 비트를 쏟아내며 상태를 좁히는 정규화(renormalization)를 겹쳐 씁니다. 이 계산기는 이해를 돕기 위해 정규화를 생략하고 상태가 임의 정밀도 정수(BigInt)로 자유롭게 자라도록 두어, 핵심 재귀식만 그대로 보여 줍니다.

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