Rice 코딩 | 적응형 정수 압축

>> 기능

[적응형]

조정 가능한 파라미터

다양한 데이터 분포에 맞게 k 값을 조정해 압축 효율을 최적화합니다.

[효율적]

기하분포 데이터

기하·지수 분포를 따르는 데이터에 최적화되어 있습니다.

[단순]

고속 코딩

단순한 나눗셈과 나머지 연산으로 높은 성능을 제공합니다.

>> 기술 정보

Rice 코딩 동작 방식:

Rice 코딩에서는 각 정수 n을 2^k로 나누어 몫 q와 나머지 r을 구합니다. 몫은 유니어리(1을 q번 나열하고 0으로 종료)로 인코딩하고, 나머지는 k비트 이진수로 표현합니다. 이렇게 하면 k 파라미터를 통해 데이터 분포에 맞게 조정되는 가변 길이 코드가 만들어집니다.

Rice 코딩 예제 (k=2):

k=2, M=2^2=4

0 → q=0, r=0 → 0|00 → 000
1 → q=0, r=1 → 0|01 → 001
2 → q=0, r=2 → 0|10 → 010
3 → q=0, r=3 → 0|11 → 011
4 → q=1, r=0 → 10|00 → 1000
5 → q=1, r=1 → 10|01 → 1001
6 → q=1, r=2 → 10|10 → 1010
7 → q=1, r=3 → 10|11 → 1011
8 → q=2, r=0 → 110|00 → 11000

k가 클수록: 유니어리 비트는 줄고 이진 비트는 늘어남
k가 작을수록: 유니어리 비트는 늘고 이진 비트는 줄어듦

Rice 코딩을 사용하는 이유:

▸데이터 분포에 적응
▸구현이 간단함
▸빠른 인코딩/디코딩
▸센서 데이터에 적합
▸작은 정수에 대해 효율적

>> 자주 묻는 질문

Rice 코딩이란 무엇인가요?

Rice 코딩은 기하분포에 특히 효율적인 가변 길이 엔트로피 코딩 방식입니다. 나누는 값 M을 2의 거듭제곱(M = 2^k)으로 제한한 Golomb 코딩의 특수한 형태로, 비트 시프트 연산을 사용해 더 빠르게 구현할 수 있습니다.

k 파라미터는 어떻게 선택하나요?

최적의 k 값은 데이터 분포에 따라 달라집니다. 평균이 μ인 데이터의 경우 대략적으로 k ≈ log₂(μ × ln(2))로 근사할 수 있습니다. 작은 k(0–2)는 아주 작은 값에 적합하고, 큰 k(4–8)는 더 큰 값을 가지는 데이터에 적합합니다. 분석 기능을 사용해 데이터에 가장 잘 맞는 k를 찾아보세요.

Rice 코딩과 Golomb 코딩의 차이는 무엇인가요?

Rice 코딩은 M = 2^k 제약을 가지는 Golomb 코딩의 부분 집합입니다. 이 제약 덕분에 Rice 코딩은 (나눗셈 대신) 비트 시프트를 사용해 더 빠르게 동작하지만, 압축 효율이 약간 떨어질 수 있습니다. Golomb 코딩은 더 나은 압축을 위해 임의의 M 값을 선택할 수 있지만, Rice는 속도를 위해 약간의 효율을 희생합니다.

Rice 코딩은 어디에 사용되나요?

Rice 코딩은 무손실 오디오 압축(FLAC, ALAC), 이미지 압축(JPEG-LS), 그리고 기하분포를 따르는 센서 데이터 등에서 널리 사용됩니다. 특히, 확률이 지수적으로 감소하는 작은 비음수 정수에 대해 매우 효과적입니다.

// 계산 예시

n	q	r	k=2
0	0	00	000
1	0	01	001
2	0	10	010
3	0	11	011
4	1	00	1000
5	1	01	1001
6	1	10	1010
7	1	11	1011
8	2	00	11000

// 코드 예제

Rice code with parameter k  (Golomb code with M = 2^k)
  q = n >> k            quotient, written as q ones followed by a zero
  r = n & (2^k - 1)     remainder, written as k plain bits
  code = unary(q) + r

k = 2, n = 9  ->  q = 2, r = 01  ->  110 01
Decode: count the leading 1s (q), skip the 0, read k bits (r), n = (q << k) | r
Choose k about log2(mean value): small values -> small k

>> 더 많은 질문

Q: Rice 코드와 Golomb 코드의 차이는?

A: Rice 코드는 Golomb 코드에서 매개변수 M이 2의 거듭제곱(M = 2^k)인 특수한 경우입니다. 나눗셈 대신 비트 시프트와 마스크를 써서 매우 빠릅니다.

Q: 매개변수 k는 어떻게 고르나요?

A: k는 값 평균의 log2 정도로 합니다. 너무 작으면 단항 부분이 길어지고, 너무 크면 나머지에 비트를 낭비합니다. FLAC 같은 코덱은 블록마다 k를 고릅니다.

Q: Rice 코드는 어디에 적합한가요?

A: 작은 값이 훨씬 자주 나오는 기하 분포의 음이 아닌 정수에 적합합니다. 무손실 오디오(FLAC)와 이미지(JPEG-LS)의 예측 잔차가 대표적입니다.

> rice | adaptive | compress <