산술 부호화
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
산술 부호화는 기호의 확률에 따라 구간을 분할하여 데이터를 압축하는 무손실 압축 방법이다. 동작 원리는 기호의 빈도에 따라 구간 [0, 1)을 나누고, 각 기호에 해당하는 구간을 선택하여 반복적으로 분할하는 것이다. 산술 부호화는 허프만 부호화보다 압축 효율이 높지만, 연산량이 많고, 메시지 길이에 대한 정보가 필요하다. 적응 산술 부호화는 데이터 처리 중 빈도 테이블을 변경하여 압축 효율을 높인다. 과거에는 특허 문제로 사용에 제약이 있었지만, 특허 만료로 인해 JPEG XL, JPEG 2000 등에서 사용되고 있다. 산술 부호화는 구현 방식에 따라 여러 종류가 있으며, 압축률과 성능은 데이터 유형에 따라 달라진다. 긴 메시지의 경우, 산술 부호화는 엔트로피에 의해 주어진 비트 수에 가깝게 압축하며, 점근적 등분할 성질(AEP)을 따른다.
더 읽어볼만한 페이지
- 무손실 압축 알고리즘 - VP9
VP9는 구글이 개발한 오픈 소스 비디오 코덱으로, VP8보다 압축 효율을 높이고 HEVC보다 나은 성능을 목표로 개발되었으며, WebM 형식으로 사용되고 주요 웹 브라우저와 넷플릭스, 유튜브 등에서 지원했으나 AV1의 등장으로 개발이 중단되었다. - 무손실 압축 알고리즘 - FLAC
FLAC은 조시 콜슨이 개발한 무손실 오디오 코덱으로, 원본 음질을 유지하면서 파일 크기를 줄이기 위해 오디오 데이터를 압축하며, 4~32비트 샘플 크기, 최대 8 채널을 지원하고, 미국 국립 문서 기록 관리청에서 디지털 오디오에 선호되는 형식으로 지정되었다.
| 산술 부호화 | |
|---|---|
| 산술 부호화 | |
 | |
| 개요 | |
| 유형 | 엔트로피 부호화 |
| 다른 이름 | 산술 부호 |
| 특징 | |
| 개발자 | 요리스 룬던, 글렌 G. 랭던 주니어, 조르마 리사넨 |
| 최초 출시 | 1976년 |
2. 동작 원리
산술 부호화는 데이터의 확률 분포에 따라 데이터를 다른 길이의 부호로 표현한다. 예를 들어, 데이터 A, B, C가 각각 0.5, 0.3, 0.2의 확률로 나타날 때, 산술 부호화는 이들을 반개구간 [0, 0.5), [0.5, 0.8), [0.8, 1)에 할당한다. 만약 AA, AB, AC와 같이 데이터가 연속으로 나타나는 경우에는 해당 구간을 다시 나누어 [0, 0.25), [0.25, 0.4), [0.4, 0.5)에 할당하는 과정을 반복한다. 이와 같이 부호화하려는 데이터 시퀀스에 해당하는 반개구간을 구하고, 해당 구간 내의 값을 선택하여 부호화한다.[1]
모든 데이터의 출현 확률을 미리 알아야 하는 것은 아니며, 이를 모르더라도 부호화할 수 있는 '''적응 산술 부호'''도 알려져 있다.[1]
산술 부호화는 데이터 압축에 적합하며, JPEG 2000에 Q-coder의 개량형인 MQ-coder로 채택되었다.[1]
2. 1. 메시지 모형
산술 부호화를 실행하기 위해서는 먼저 데이터의 모형을 결정해야 한다. 모형이란 메시지의 기호들이 어떤 패턴을 갖고 있을 것인지를 예측하는 것으로, 이 모델이 실제 메시지를 더 정확하게 예측할수록 압축률은 더 높아진다.[1]예를 들어, 다음과 같이 메시지에 출현하는 기호들의 고정된 통계적 모형을 가정할 수 있다.
위와 같은 간단한 네 개의 기호 집합 외에도 더 복잡한 모형 또한 얼마든지 다룰 수 있다. 예를 들어 '''고차 모형'''은 이전까지 나온 기호들의 역사에 따라 다음 기호가 나타날 확률을 달리 계산할 수도 있다. 만약 영어 텍스트를 압축하려고 한다면 "Q"나 "q" 기호 다음에는 "u"가 나타날 확률이 훨씬 높을 것이라고 예측할 수 있을 것이다. 혹은 적응적인 모형을 생각할 수도 있는데, 이 경우에는 부호화 알고리즘이 기호를 하나씩 압축할 때마다 지금까지 나온 기호의 분포에 따라 모델을 조금씩 바꿔가면서 압축한다. 부호화 알고리즘이 어떤 모형을 취하든 복호화 알고리즘이 동일한 모형을 취한다면 메시지를 원래 그대로 복원할 수 있다.[1]
일반적으로 산술 부호화는 주어진 기호 집합과 확률에 대해 거의 최적의 출력을 생성할 수 있다. (최적 값은 확률 ''P''의 각 기호에 대해 −log2''P'' 비트이다. 정보원 부호화 정리 참조).[2] 산술 부호화를 사용하는 압축 알고리즘은 데이터의 모델을 결정하는 것부터 시작하며, 기본적으로 메시지 기호에서 어떤 패턴이 발견될지 예측하는 것이다. 이 예측이 더 정확할수록 출력은 최적에 더 가까워진다.[2]
'''예시''': 특정 모니터링 기기의 출력을 시간 경과에 따라 설명하기 위한 간단한 정적 모델[2]
- 기호 NEUTRAL이 나타날 확률 60%[2]
- 기호 POSITIVE가 나타날 확률 20%[2]
- 기호 NEGATIVE가 나타날 확률 10%[2]
- 기호 END-OF-DATA가 나타날 확률 10% (이 기호가 있다는 것은 스트림이 '내부적으로 종료'됨을 의미하며, 이는 데이터 압축에서 매우 일반적이다. 이 기호가 데이터 스트림에 나타나면 디코더는 전체 스트림이 디코딩되었음을 알게 된다.)[2]
모델은 이 예제에 대해 선택된 간단한 4개의 기호 집합 외에 다른 알파벳도 처리할 수 있다. 더 정교한 모델도 가능한데, ''고차'' 모델링은 이전 기호(즉, ''컨텍스트'')를 기반으로 기호의 현재 확률에 대한 추정치를 변경한다. 예를 들어 영어 텍스트 모델에서 "u"의 백분율 확률은 "Q" 또는 "q"가 뒤따를 때 훨씬 더 높다. 모델은 심지어 스트림에 실제로 포함된 내용에 따라 데이터에 대한 예측을 지속적으로 변경하는 적응형일 수도 있다. 디코더는 인코더와 동일한 모델을 가져야 한다.[2]
2. 2. 부호화 단계
부호화 단계는 다음 세 가지 정보를 바탕으로 실행된다.
- 부호화할 다음 기호
- 현재의 '''구간''' (0에서 1 사이의 임의의 두 실수 사이)
- 각 단계에서 다음에 올 수 있는 기호들의 확률 (고정 확률, 고차 모형, 적응적 모형 등)
먼저 현재 구간을 다음에 올 수 있는 기호들에 해당하는 더 작은 구간으로 나눈다. 이때 각 기호에 해당하는 구간의 크기는 기호가 나타날 확률에 비례한다. 그리고 이 구간들 가운데 메시지에 실제로 나타나는 기호에 해당하는 구간을 골라 다음 단계를 진행한다.
예를 들어, 네 개의 기호를 사용하는 모형에서 [0, 1) 구간을 다음과 같이 나눌 수 있다. (이 예제에서는 십진법을 사용하지만, 실제 구현에서는 효율을 위해 이진법을 사용한다.)
| 기호 | 확률 | 구간 |
|---|---|---|
| 가 | 60% | [0, 0.6) |
| 나 | 20% | [0.6, 0.8) |
| 다 | 10% | [0.8, 0.9) |
| 메시지 끝 | 10% | [0.9, 1) |
만약 "가다(메시지 끝)" 메시지를 부호화한다면 다음과 같이 진행된다.
1. 첫 번째 기호가 "가"이므로 [0, 0.6) 구간을 선택한다.
2. 새로운 구간 [0, 0.6)을 다시 다음과 같이 나눈다.
| 기호 | 확률 | 구간 | 설명 |
|---|---|---|---|
| 가 | 60% | [0, 0.36) | [0, 0.6)의 0%~60% |
| 나 | 20% | [0.36, 0.48) | [0, 0.6)의 60%~80% |
| 다 | 10% | [0.48, 0.54) | [0, 0.6)의 80%~90% |
| 메시지 끝 | 10% | [0.54, 0.6) | [0, 0.6)의 90%~100% |
3. 다음 기호가 "다"이므로 [0.48, 0.54) 구간을 선택한다.
4. 다시 이 구간을 작게 나누면 다음과 같다.
| 기호 | 확률 | 구간 |
|---|---|---|
| 가 | 60% | [0.48, 0.516) |
| 나 | 20% | [0.516, 0.528) |
| 다 | 10% | [0.528, 0.534) |
| 메시지 끝 | 10% | [0.534, 0.54) |
5. "메시지 끝"에 해당하는 구간은 [0.534, 0.54)이고, 이 구간 안에 포함되는 실수 0.537이 있으므로 전체 메시지는 0.537로 부호화된다.
| 설명 | |
|---|---|
| 1. | 문자 빈도를 찾는다. |
| 2. | 구간 [0, 1)을 빈도 비율로 분할한다. |
| 3–5. | 메시지의 각 문자에 대해 해당 구간을 반복적으로 분할한다. |
| 6. | 최종 구간의 모든 값을 선택하여 메시지를 나타낸다. |
| 2*–6*. | 메시지가 "KIWI"인 경우의 분할 및 값이다. |
요약하면, 인코딩 과정은 다음 세 가지 데이터를 기반으로 한다.[1]
- 인코딩해야 할 다음 기호
- 현재 구간 ([0, 1]에서 시작하여 변경됨)
- 각 단계에서 가능한 기호에 할당되는 확률 (고차 또는 적응형 모델에서는 확률이 매 단계 동일하지 않을 수 있음)
인코더는 현재 구간을 하위 구간으로 나누고, 각 하위 구간은 해당 기호의 확률에 비례하는 크기를 가진다. 다음에 인코딩될 기호에 해당하는 구간이 다음 단계에서 사용된다.[1]
모든 기호가 인코딩된 후, 결과 구간은 해당 기호 시퀀스를 명확하게 식별한다. 동일한 최종 구간과 모델을 사용하면 원래 기호 시퀀스를 복원할 수 있다. 최종 구간 전체를 전송할 필요는 없으며, 해당 구간 내의 하나의 값만 전송해도 충분하다. 특히, 해당 값으로 시작하는 모든 값이 최종 구간에 속하도록 충분한 자릿수의 값만 전송하면 접두사 코드가 보장된다.[1]
예를 들어, A, B, C가 각각 0.5, 0.3, 0.2의 확률로 나타날 때, [0, 0.5), [0.5, 0.8), [0.8, 1) 구간에 할당한다. AA, AB, AC는 [0, 0.25), [0.25, 0.4), [0.4, 0.5) 구간에 할당한다. 이 과정을 반복하여 부호화하려는 데이터 시퀀스에 해당하는 구간을 구하고, 해당 구간 내의 값으로 부호화한다.[1]
출현 확률을 모르더라도 부호화할 수 있는 '''적응 산술 부호'''도 알려져 있다.[1]
이 부호화는 데이터 압축에 적합하며, JPEG 2000에도 채택되었다.[1]
2. 3. 메시지 복호화
이렇게 부호화된 실수와 메시지 모형을 함께 전송하면 복호화 알고리즘은 이 과정을 동일하게 진행하여 메시지를 복원한다."가다" 메시지를 예로 들어 복호화 과정을 설명하면 다음과 같다.
- 부호화된 실수 .537은 첫 번째 구간 가운데 [0, 0.6) 사이에 포함되므로 첫 번째 기호는 "가"가 된다.
- 위와 동일하게 [0, 0.6)을 나누면 .537은 다시 이 구간 가운데 [0.48, 0.54) 사이에 포함되므로 두 번째 기호는 "다"가 된다.
- [0.48, 0.54)를 다시 더 작은 구간으로 나누면 .537은 [0.534, 0.54) 사이에 포함된다. 따라서 세 번째 기호는 "메시지 끝"이 된다.
- "메시지 끝"을 복호화하였으므로 복호화 알고리즘은 더 이상 복호화를 진행하지 않아야 함을 알고 종료된다. 만약 "메시지 끝"을 나타내는 기호가 없다면 복호화 알고리즘은 복호화를 무한히 반복할 것이다.
4개 기호 모델로 인코딩된 메시지를 복호화하는 과정을 좀 더 자세히 살펴보자. 메시지는 0.538로 인코딩되어 있다 (명확성을 위해 이진법 대신 십진법을 사용하며, 메시지를 복호화하는 데 필요한 만큼의 숫자만 있다고 가정한다).[1]
1. 인코더가 사용한 것과 동일한 간격인 [0, 1)에서 시작하여, 동일한 모델을 사용하는 네 개의 하위 간격으로 나눈다. 0.538은 NEUTRAL의 하위 간격인 [0, 0.6)에 속하므로, 첫 번째 기호는 NEUTRAL이다.[1]
2. 간격 [0, 0.6)을 다시 하위 간격으로 나눈다.
- NEUTRAL의 간격은 [0, 0.36) ( [0, 0.6)의 60%)
- POSITIVE의 간격은 [0.36, 0.48) ( [0, 0.6)의 20%)
- NEGATIVE의 간격은 [0.48, 0.54) ( [0, 0.6)의 10%)
- END-OF-DATA의 간격은 [0.54, 0.6) ( [0, 0.6)의 10%)
0.538은 [0.48, 0.54)에 속하므로, 두 번째 기호는 NEGATIVE이다.[1]
3. 현재 간격을 다시 하위 간격으로 나눈다.
- NEUTRAL의 간격은 [0.48, 0.516)
- POSITIVE의 간격은 [0.516, 0.528)
- NEGATIVE의 간격은 [0.528, 0.534)
- END-OF-DATA의 간격은 [0.534, 0.540)
0.538은 END-OF-DATA 기호의 간격에 속하므로, 이것이 다음 기호이다. 내부 종료 기호이므로 복호화가 완료된다. 스트림이 내부적으로 종료되지 않으면, 스트림이 중지되는 위치를 나타내는 다른 방법이 필요하다. 그렇지 않으면 복호화 과정이 영원히 계속되어, 실제로 인코딩된 것보다 더 많은 기호를 분수에서 잘못 읽을 수 있다.[1]
2. 4. 동일 확률
가장 단순한 경우, 각 기호가 나타날 확률은 동일하다. 예를 들어 A, B, C 세 기호가 있고 각 기호가 나타날 확률이 모두 같다고 가정해 보자. 기호를 하나씩 부호화하려면 기호당 2비트가 필요한데, 이는 낭비적이다. 비트 변동 중 하나는 절대 사용되지 않는다. 즉, 기호 A, B, C는 각각 00, 01, 10으로 부호화할 수 있으며, 11은 사용되지 않는다.더 효율적인 해결책은 이 세 기호의 시퀀스를 각 숫자가 기호를 나타내는 3진수 기반의 유리수로 나타내는 것이다. 예를 들어 "ABBCAB" 시퀀스는 산술 부호화에서 구간 [0, 1)의 값으로 0.0112013이 될 수 있다. 다음 단계는 이 3진수를 이를 복구할 수 있을 만큼 충분한 정밀도를 가진 고정 소수점 이진수로 부호화하는 것이다. 예를 들어 0.00101100012는 10비트만 사용한다. 단순 블록 부호화와 비교하면 2비트가 절약된다. 임의의 정밀도 숫자의 밑을 변환하는 효율적인 인플레이스 알고리즘이 있기 때문에 긴 시퀀스에도 적용할 수 있다.
값을 디코딩하려면 원래 문자열의 길이가 6임을 알고, 다시 3진법으로 변환하고 6자리로 반올림하여 문자열을 복구할 수 있다.
2. 5. 정밀도 및 재정규화
실제 구현에서는 무한 정밀도 대신 유한 정밀도를 사용한다. 예를 들어, 모델에서 구간을 3등분하고 8비트 정밀도로 근사화하면 다음과 같이 표현할 수 있다.| 기호 | 확률 | 8비트 정밀도로 축소된 구간 | 범위 | |
|---|---|---|---|---|
| (분수로 표현) | (이진법) | (이진법) | ||
| A | 1/3 | [0.00000000, 0.01010101) | 00000000 – 01010100 | |
| B | 1/3 | [0.01010101, 0.10101011) | 01010101 – 10101010 | |
| C | 1/3 | [0.10101011, 1.00000000) | 10101011 – 11111111 |
''재정규화''는 유한 정밀도로 인해 발생하는 문제를 방지하기 위한 과정이다. 범위 내의 모든 값이 특정 시작 숫자를 공유하는 지점까지 범위가 축소될 때마다 해당 숫자는 출력으로 전송된다. 컴퓨터가 처리할 수 있는 정밀도의 숫자만큼 처리하고 있으므로, 기존 숫자는 왼쪽으로 이동하고 오른쪽에 새로운 숫자가 추가되어 범위를 가능한 한 넓게 확장한다.
| 기호 | 확률 | 범위 | 출력으로 전송할 수 있는 숫자 | 재정규화 후 범위 |
|---|---|---|---|
| A | 1/3 | 0 | |
| B | 1/3 | | | |
| C | 1/3 | 1 |
산술 부호화는 압축 대상 부호의 개수가 많을수록 정보 엔트로피에 근접하는 높은 압축률을 보인다. 하지만 각 부호를 압축할 때마다 구간을 계산해야 하므로 허프만 부호화보다 연산량이 크다.[1]
산술 부호화가 다른 유사한 데이터 압축 방법보다 갖는 한 가지 장점은 적응의 편리함이다. 적응은 데이터를 처리하는 동안 빈도(또는 확률) 테이블을 변경하는 것이다. 복호화 시의 빈도 테이블이 부호화 시와 동일한 방식으로, 동일한 단계로 교체되는 한, 복호화된 데이터는 원본 데이터와 일치한다. 동기화는 일반적으로 부호화 및 복호화 과정에서 발생하는 심볼들의 조합을 기반으로 한다.
허프만 부호화는 각 기호에 대해 고정 길이 코드를 할당하는 반면, 산술 부호화는 전체 메시지를 하나의 실수로 표현한다. 산술 부호화는 독립적이고 동일하게 분포된(IID) 문자열을 압축할 때 엔트로피에 더 가깝게 접근할 수 있다.[1] 허프만 부호화는 기호 확률이 2의 거듭제곱이 아닐 때 비효율적일 수 있지만, 산술 부호화는 이러한 경우에도 효율적이다.[1] 단순한 이진 문자열의 경우 허프만 코딩은 압축이 불가능할 수 있지만, 산술 부호화는 압축이 가능하다.[1]
3. 압축 효율
또한 "메시지 끝"을 나타내는 별도의 기호를 사용하거나, 몇 개의 기호가 들어있는지에 대한 부가적인 정보가 필요하다. 따라서 짧은 메시지의 경우에는 오히려 허프만 부호화보다 효율이 떨어질 수 있다. 예를 들어, 앞의 예제를 허프만 부호화로 압축하면 "메시지 끝" 기호가 필요 없어 3비트만 소모된다.[1]
확률 모델이 실제 데이터와 다르면 압축 효율이 저하될 수 있다. 예를 들어, 예측 확률과 실제 빈도가 다른 경우, 산술 부호화는 입력 메시지보다 더 큰 출력 메시지를 생성할 수 있다.[1]
4. 적응 산술 부호화
예를 들어, 데이터 A, B, C가 각각 0.5, 0.3, 0.2의 확률로 나타날 때, 각각 반개구간 [0, 0.5), [0.5, 0.8), [0.8, 1)에 할당한다. 다음으로 AA, AB, AC에 대해서는 반개구간 [0, 0.25), [0.25, 0.4), [0.4, 0.5)에 할당한다. 이 과정을 반복하여 부호화하려는 데이터의 시퀀스에 해당하는 반개구간을 구한다. 그리고 해당 반개구간 내의 값으로 부호화한다.
부호화 원리상 모든 데이터의 출현 확률을 미리 알아야 하지만, 출현 확률을 몰라도 부호화할 수 있는 '''적응 산술 부호'''도 알려져 있다.
이 부호화는 데이터 압축에 적합하며, JPEG 2000에도 다른 알고리즘으로 구현된 Q-coder의 개량형인 MQ-coder로 채택되었다.
5. 다른 압축 방법과의 비교
예를 들어, 이진 문자열 ({0, 1})이 {0.95, 0.05}의 확률을 가질 때, 허프만 인코딩은 각 값에 1비트를 할당하여 입력과 동일한 길이의 코드를 생성한다. 반면 산술 부호화는 비트를 잘 압축하여 최적 압축률에 근접한다.[1]
허프만 코딩의 비효율성을 해결하기 위해 기호를 연결하는("블로킹") 방식을 사용할 수 있다. 예를 들어, 인코딩하기 전에 세 개의 기호 시퀀스를 그룹화하면 새로운 "슈퍼 기호"가 생성되며, 빈도는 다음과 같다.[1]슈퍼 기호 빈도 000 85.7% 001, 010, 100 각각 4.5% 011, 101, 110 각각 0.24% 111 0.0125%
이 그룹화에서 허프만 코딩은 세 개의 기호당 평균 1.3비트, 즉 기호당 0.433비트를 사용하여 압축률을 높일 수 있다. 그러나 임의로 큰 시퀀스를 허용하면 산술 부호화와 마찬가지로 엔트로피에 임의로 가까워지지만, 그렇게 하려면 엄청난 코드가 필요하므로 산술 부호화만큼 실용적이지 않다.[1]
5. 1. 허프만 부호화
허프만 부호화는 각 기호에 대해 고정 길이 코드를 할당하는 반면, 산술 부호화는 전체 메시지를 하나의 실수로 표현한다. 산술 부호화는 독립적이고 동일하게 분포된(IID) 문자열을 압축할 때 엔트로피에 더 가깝게 접근할 수 있다.[1] 허프만 부호화는 기호 확률이 2의 거듭제곱이 아닐 때 비효율적일 수 있지만, 산술 부호화는 이러한 경우에도 효율적이다.[1] 단순한 이진 문자열의 경우 허프만 코딩은 압축이 불가능할 수 있지만, 산술 부호화는 압축이 가능하다.[1]
예를 들어, 이진 문자열 ({0, 1})이 {0.95, 0.05}의 확률을 가질 때, 허프만 인코딩은 각 값에 1비트를 할당하여 입력과 동일한 길이의 코드를 생성한다. 반면 산술 부호화는 비트를 잘 압축하여 최적 압축률에 근접한다.[1]
허프만 코딩의 비효율성을 해결하기 위해 기호를 연결하는("블로킹") 방식을 사용할 수 있다. 예를 들어, 인코딩하기 전에 세 개의 기호 시퀀스를 그룹화하면 다음과 같은 빈도를 가진 새로운 "슈퍼 기호"가 생성된다.[1]
이 그룹화에서 허프만 코딩은 세 개의 기호당 평균 1.3비트, 즉 기호당 0.433비트를 사용하여 압축률을 높일 수 있다. 그러나 임의로 큰 시퀀스를 허용하면 산술 부호화와 마찬가지로 엔트로피에 임의로 가까워지지만, 그렇게 하려면 엄청난 코드가 필요하므로 산술 부호화만큼 실용적이지 않다.[1]
6. 특허 문제
과거 산술 부호화는 특허 문제로 인해 자유로운 사용에 제약이 있었다. 역사적으로 산술 부호화의 다양한 기술들은 미국 특허로 보호되었으나, 특허가 만료되면서 여러 방법들이 공개 도메인으로 풀려났다.[3] bzip2영어와 같은 일부 압축 소프트웨어는 특허 문제로 인해 산술 부호화 대신 허프만 부호화를 사용하기도 했다.[4]
JPEG 이미지 형식에서도 특허 문제로 인해 허프만 부호화가 주로 사용되었으나,[4] JPEG의 산술 부호화 관련 특허[5]는 JPEG 표준의 연식(1990년경 설계 완료)[6]으로 인해 만료되었다.[7] JPEG XL, PackJPG, Brunsli, Lepton 등은 산술 부호화(또는 JPEG XL의 경우 비대칭 숫자 시스템)를 사용하여 허프만 부호화된 파일보다 더 높은 압축률을 제공한다.
JPEG 이미지 압축 형식의 산술 부호화 알고리즘은 다음의 만료된 특허들을 기반으로 한다.[7]
| 출원일 | 등록일 | 발명자 (회사) | 특허 번호 및 제목 |
|---|---|---|---|
| 1986년 2월 4일 | 1987년 3월 24일 | Kotapullam M. A. Mohiuddin|코타풀람 M. A. 모히딘영어, Jorma J. Rissanen|요르마 요한네스 리사넨영어 (IBM) | – 곱셈 없는 다중 알파벳 산술 코드 |
| 1988년 11월 18일 | 1990년 2월 27일 | Glenn George Langdon|글렌 조지 랭던영어, Joan L. Mitchell|조앤 L. 미첼영어, William B. Pennebaker|윌리엄 B. 페네베이커영어, Jorma J. Rissanen|요르마 요한네스 리사넨영어 (IBM) | – 산술 부호화 인코더 및 디코더 시스템 |
| 1988년 7월 20일 | 1990년 6월 19일 | William B. Pennebaker|윌리엄 B. 페네베이커영어, Joan L. Mitchell|조앤 L. 미첼영어 (IBM) | – 산술 코더를 위한 확률 적응 |
| 1989년 1월 21일 | 1990년 8월 10일 | 키무라 토시히로|기무라 도시히로일본어, 키노 시게노리|기노 시게노리일본어, 오노 후미타카|오노 후미타카일본어, 요시다 마사유키|요시다 마사유키일본어 (미쓰비시 전기) | [https://patents.google.com/patent/JPH02202267A/en JP 특허 1021672] – 코딩 시스템 |
| 1990년 2월 26일 | 1991년 11월 5일 | 오노 후미타카|오노 후미타카일본어, 키무라 토모히로|기무라 도모히로일본어, 요시다 마사유키|요시다 마사유키일본어, 키노 시게노리|기노 시게노리일본어 (미쓰비시) | [https://patents.google.com/patent/JPH0834434B2/en JP 특허 2-46275] – 코딩 장치 및 코딩 방법 |
산술 부호화와 관련된 다른 특허(대부분 만료됨)는 다음과 같다.[8]
| 출원일 | 등록일 | 발명자 (회사) | 특허 번호 및 제목 |
|---|---|---|---|
| 1977년 3월 4일 | 1978년 10월 24일 | Glenn George Langdon|글렌 조지 랭던영어, Jorma J. Rissanen|요르마 요한네스 리사넨영어 (IBM) | – 산술 문자열 코딩 방법 및 수단 |
| 1979년 11월 28일 | 1981년 8월 25일 | Glenn George Langdon|글렌 조지 랭던영어, Jorma J. Rissanen|요르마 요한네스 리사넨영어 (IBM) | – 연산 횟수를 줄인 산술 코딩 방법 및 수단 |
| 1981년 3월 30일 | 1984년 8월 21일 | Glenn George Langdon|글렌 조지 랭던영어, Jorma J. Rissanen|요르마 요한네스 리사넨영어 (IBM) | – 동시 값 업데이트를 사용하는 고속 산술 압축 코딩 |
| 1986년 9월 15일 | 1990년 1월 2일 | Joan L. Mitchell|조앤 L. 미첼영어, William B. Pennebaker|윌리엄 B. 페네베이커영어 (IBM) | – 선택적으로 사용되는 다양한 산술 코딩 인코더 및 디코더를 사용한 산술 코딩 데이터 압축/해제 |
| 1987년 5월 13일 | 1988년 11월 18일 | 시마다 미치오|시마다 미치오일본어 (NEC) | [https://patents.google.com/patent/JPS63281524A/en JP 특허 11782787] – 데이터 압축 산술 인코딩 장치 |
| 1987년 6월 18일 | 1988년 12월 22일 | 마츠모토 슈이치|마쓰모토 슈이치일본어, 사이토 마사히로|사이토 마사히로일본어 (KDDI) | [https://patents.google.com/patent/JPS63314918A/en JP 특허 15015487] – 산술 코딩에서 캐리 전파를 방지하는 시스템 |
| 1988년 5월 3일 | 1990년 6월 12일 | William B. Pennebaker|윌리엄 B. 페네베이커영어, Joan L. Mitchell|조앤 L. 미첼영어 (IBM) | – 산술 코더를 위한 확률 적응 |
| 1989년 6월 19일 | 1991년 1월 29일 | Dan S. Chevion|댄 S. 체비온영어, Ehud D. Karnin|에후드 D. 카르닌영어, Eugeniusz Walach|유제니우스 바라흐영어 (IBM) | – 간소화된 확률 서브 인터벌 추정을 사용한 산술 인코딩을 사용한 데이터 문자열 압축 |
| 1990년 1월 5일 | 1992년 3월 24일 | William B. Pennebaker|윌리엄 B. 페네베이커영어, Joan L. Mitchell|조앤 L. 미첼영어 (IBM) | – 산술 코더를 위한 확률 적응 |
| 1992년 8월 17일 | 1993년 12월 21일 | James D. Allen|제임스 D. 앨런영어 (리코) | – 엔트로피 코딩 방법 및 장치 |
디랙 코덱은 산술 부호화를 사용하며 특허 출원 중이 아니다.[9] 산술 부호화 특허는 다른 관할 구역에도 존재할 수 있다. 전 세계 소프트웨어의 특허성에 대한 논의는 소프트웨어 특허를 참조한다.
데이터 압축 분야에서 특허 문제는 끊이지 않았으며, GIF 이미지 파일 포맷의 압축 알고리즘인 LZW 부호의 특허료 지불 명령(2004년 만료) 등이 그 예시이다. 산술 부호화 역시 특허 문제로 인해 "빠져나갈 구멍이 없을 정도로 특허가 획득되어 있다"는 평가를 받으며, bzip에서는 공개를 포기하고 허프만 부호화로 대체되거나, Range Coder와 같은 "특허에 저촉되지 않는 산술 부호화"가 보급되기도 했다.
7. 종류
산술 부호화에는 구현 알고리즘에 따라 여러 종류가 존재한다. 모든 프로그래밍 구현은 서로 다른 압축률과 성능을 보인다. 압축률은 약간의 차이만 보이지만 (일반적으로 1% 미만),[10] 코드 실행 시간은 최대 10배까지 차이가 날 수 있다. 공개적으로 사용 가능한 인코더 목록에서 올바른 인코더를 선택하는 것은 간단한 작업이 아닌데, 성능과 압축률이 데이터 유형, 특히 알파벳 크기(다른 기호의 수)에도 영향을 받기 때문이다. 두 개의 특정 인코더 중 하나는 작은 알파벳에서 더 나은 성능을 보일 수 있으며, 다른 하나는 큰 알파벳에서 더 나은 성능을 보일 수 있다. 대부분의 인코더는 알파벳 크기에 제한이 있으며, 그중 많은 인코더가 정확히 두 개의 기호(0과 1)로 구성된 알파벳에 특화되어 있다.
- L-R형 산술 부호화
- Q-코더
- MQ-코더
- 존스 부호 - 범위 코더의 원형이 되었다.
- i.i.d 산술 부호화
8. 점근적 등분할 성질(Asymptotic Equipartition Property, AEP)
만약 소스(source)가 에르고딕하다면, 점근적 등분할 성질(AEP)을 가진다. AEP에 따라, 충분히 긴 심볼 스트림 이후, (0, 1)의 구간은 거의 동일한 크기의 구간으로 분할된다. 높은 확률로, 심볼 스트림은 nH(X)(1 + O(ε)) 길이의 이진 문자열로 산술 부호화될 수 있다. (H(X): 소스의 엔트로피)[1]
참조
[1]
서적
Fundamentals of Multimedia
https://books.google[...]
Springer Science & Business Media
2014-04-09
[2]
논문
The use of asymmetric numeral systems as an accurate replacement for Huffman coding
https://ieeexplore.i[...]
Picture Coding Symposium
2015
[3]
학위논문
Source coding algorithms for fast data compression
Stanford Univ
1976-05
[4]
웹사이트
What is JPEG?
http://www.faqs.org/[...]
[5]
웹사이트
Recommendation T.81 (1992) Corrigendum 1 (01/04)
http://www.itu.int/r[...]
International Telecommunication Union
2004-11-09
[6]
서적
JPEG Still Image Data Compression Standard
Kluwer Academic Press
[7]
웹사이트
T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES
https://www.w3.org/G[...]
CCITT
1992-09
[8]
웹사이트
Frequently Asked Questions
http://www.faqs.org/[...]
[9]
웹사이트
Dirac video codec 1.0 released [LWN.net]
https://lwn.net/Arti[...]
[10]
인용
Arithmetic coding for data compression
http://home.tiscali.[...]
[11]
서적
情報理論
昭晃堂
[12]
웹사이트
情報圧縮と特許
http://www.entis.jp/[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com