산술 부호화는 주어진 메시지를 더 작은 비트 시퀀스로 압축하는 엔트로피 부호화 방법 중 하나
이 방법은 메시지 전체를 하나의 숫자로 표현하여, 기호의 빈도에 따라 효율적으로 데이터를 압축합니다.
- 기호의 확률
-
메시지를 구성하는 각 기호의 출현 확률을 계산한다.
-
이 확률은 기호의 빈도를 기반으로 하며, 기호가 자주 나타날수록 낮은 비트 수로 표현될 수 있다. 예를 들어, 문자열 "ABABAC"에서 각 기호의 확률은 다음과 같이 계산된다.
P(A) = 3/6 = 0.5
P(B) = 2/6 ≈ 0.333
P(C) = 1/6 ≈ 0.167
- 구간 할당
-
초기 구간 [0, 1) 내에서 각 기호의 확률에 비례하여 구간을 할당합니다.
-
앞서 계산한 확률을 바탕으로 구간을 할당하면 다음과 같다.
'A'는 [0, 0.5)
'B'는 [0.5, 0.833)
'C'는 [0.833, 1)
-
산술 부호화 과정
초기화
초기 구간을 [0, 1)로 설정함.
이는 전체 메시지를 표현할 수 있는 범위임.메시지 인코딩
- 메시지의 각 기호에 대해 다음 단계를 반복
- 현재 구간을 기호의 확률에 따라 세분화
- 현재 구간을 해당 기호의 하위 구간으로 업데이트
-
예제: "AB" 인코딩 과정
기호 'A', 'B', 'C'의 확률이 각각 0.5, 0.333, 0.167이라고 가정하고, 메시지 "AB"를 인코딩함.4.1 초기 구간 설정
- 초기 구간: [0, 1)
4.2 첫 번째 기호 'A' 처리
- 'A'의 구간은 [0, 0.5)
- 현재 구간을 [0, 0.5)로 업데이트
4.3 두 번째 기호 'B' 처리
'B'의 구간은 [0.5, 0.833) //
현재 구간 [0, 0.5) 내에서 'B'가 차지하는 비율을 계산:
하위 구간 [0.25, 0.4165)
계산 과정 : [0 + 0.5 x 0.5, 0 + 0.5 x 0.833) = [0.25, 0.4165)
최종 구간은 [0.25, 0.4165)임.
이 구간 내의 어떤 숫자 (예: 0.25)를 부호화된 값으로 사용함 -
복호화 과정
복호화는 부호화의 역과정으로, 부호화된 값을 사용하여 원래 메시지를 복원함
초기 구간을 [0, 1)로 설정하고, 부호화된 값을 포함하는 하위 구간을 찾음
하위 구간에 따라 기호를 결정하고, 현재 구간을 그 기호의 구간으로 업데이트.
이 과정을 반복하여 원래 메시지를 복원함.
예를 들어, 부호화된 값이 0.25라면:
초기 구간: [0, 1)
값 0.25가 포함된 첫 번째 하위 구간은 [0, 0.5) → 기호 'A'
구간을 [0, 0.5)로 업데이트
값 0.25가 포함된 두 번째 하위 구간은 [0.25, 0.4165) → 기호 'B'
복호화된 메시지는 "AB"임. -
장점과 단점
- 장점
- 높은 압축률: 기호의 출현 확률에 따라 최적화된 압축을 제공하여 효율적임
- 유연성: 고정된 코드 길이가 없기 때문에 다양한 데이터에 적용 가능함
- 실시간 압축: 스트림 데이터 압축에 적합하여 실시간으로 데이터를 압축할 수 있음 - 단점
- 복잡성: 구현이 상대적으로 복잡하며, 특히 부동소수점 연산의 정확도가 중요함.
- 성능 문제: 매우 긴 메시지에 대해 성능이 떨어질 수 있으며, 부동소수점 연산의 정밀도에 따라 오류가 발생할 수 있음.
- 결론
산술 부호화는 높은 압축률을 제공하는 강력한 데이터 압축 기법임. 기호의 확률에 따라 구간을 분할하여 메시지를 효율적으로 압축하는 이 방법은 무손실 압축을 위해 다양한 분야에서 사용됨. 구현의 복잡성에도 불구하고, 이미지 압축(JPEG), 비디오 압축(MPEG), 텍스트 압축 등 다양한 응용 분야에서 널리 활용됨.
