산술 부호화

산술 부호화(AC)는 무손실 데이터 압축에 사용되는 엔트로피 부호화의 한 형태입니다.일반적으로 문자열은 ASCII 코드와 같이 문자당 고정 비트 수를 사용하여 표시됩니다.문자열이 산술 부호화로 변환되면 자주 사용되는 문자는 더 적은 비트로 저장되고 빈도가 높지 않은 문자는 더 많은 비트로 저장되므로 총 사용되는 비트가 줄어듭니다.산술 부호화는 입력을 컴포넌트 기호로 분리하여 각각을 코드로 대체하는 것이 아니라 전체 메시지를 단일 번호, 즉 임의의 정밀도 q로 부호화한다는 점에서 Huffman 부호화와 같은 다른 형태의 엔트로피 부호화와는 다르다.여기서 0.0µq < 1.0이다.현재 정보를 2개의 ^[1]숫자로 정의된 범위로 나타냅니다.비대칭 숫자 시스템이라고 불리는 최근의 엔트로피 코드 패밀리는 ^[2]현재 정보를 나타내는 단일 자연수로 직접 작동하기 때문에 더 빠른 구현을 가능하게 합니다.

세 기호 "A", "B" 및 "C"의 고정 확률 분포를 가정한 산술 부호화 예제입니다. "A"의 확률은 50%, "B"의 확률은 33%, "C"의 확률은 17%입니다.또한 각 단계에서 재귀 깊이를 알고 있다고 가정합니다.1단계에서는 구간 [0.5, 0.83) 내에 있는 "B"를 코드화합니다.이진수 "0.10x"는 완전히 [0.5, 0.83] 안에 있는 간격을 나타내는 최단 코드입니다."x"는 임의의 비트시퀀스를 의미합니다.두 가지 극단적인 경우가 있습니다. 가장 작은 x는 표시된 간격의 왼쪽을 나타내는 0을 나타냅니다.그러면 구간의 왼쪽이 dec(0.10) = 0.5가 됩니다.다른 극단에서 x는 상한 dec(0.11) = 0.75인 유한 수열을 나타냅니다.따라서 "0.10x"는 [0.5, 0.83) 내부에 있는 구간[0.5, 0.75)을 나타냅니다.모든 구간이 "0"으로 시작되므로 "0" 부분은 생략할 수 있습니다. "x" 부분은 무시해도 됩니다. 어떤 비트 시퀀스를 나타내든 간에 [0.5, 0.75] 안에 그대로 있기 때문입니다.

구현 상세 및 예시

산술 부호화를 사용한 메시지 "WIKI" 인코딩

1.	문자의 빈도가 검출되었습니다.
2.	간격 [0, 1)은 주파수 비율로 분할됩니다.
3–5.	대응하는 간격은 메시지 내의 각 문자에 대해 반복적으로 분할됩니다.
6.	마지막 간격의 값은 메시지를 나타내는 값으로 선택됩니다.
2–6.	대신 메시지가 "KIWI"인 경우의 파티션과 값.

동그라미로 표시된 위의 예에서는 빨간색 인코딩 "WIKI" 및 "KIWI"의 값이 SVG 이미지에서 일정 간격으로 점멸하여 강조 표시하고 통계 정보를 표시합니다.

등가 확률

가장 간단한 경우, 각 기호가 발생할 확률은 동일합니다.예를 들어, 각각 발생할 가능성이 동일한 세 가지 기호(A, B 및 C)의 집합을 고려합니다.단순한 블록 부호화에서는 심볼당 2비트가 필요합니다.이것은 낭비입니다.비트 종류 중 하나는 사용되지 않습니다.즉, 기호 A, B 및 C는 각각 00, 01 및 10으로 인코딩되며 11은 사용되지 않습니다.

보다 효율적인 해법은 각 자릿수가 기호를 나타내는 기저 3에서 이들 세 기호의 시퀀스를 유리수로 표현하는 것입니다.예를 들어 시퀀스 "ABBCAB"는 [0, 1] 간격의 값으로 산술 부호화에서 0.011201이₃ 될 수 있습니다.다음 절차에서는 0.0010110010₂ 등 복구에 충분한 정밀도의 고정점 이진수를 사용하여 이 3진수를 부호화합니다.이것은 10비트입니다.네이브 블록 부호화와 비교하여2비트가 절약됩니다.이것은, 임의의 정밀한 숫자의 베이스를 변환하기 위한 효율적인 임플레이스 알고리즘이 있기 때문에, 긴 시퀀스에 대해서 실현 가능합니다.

값을 디코딩하려면 원래 문자열의 길이가 6인 것을 알고 있으면 기본 3으로 변환하여 6자리로 반올림하고 문자열을 복구하기만 하면 됩니다.

모델 정의

일반적으로 산술 코더는 주어진 기호 및 확률 집합에 대해 거의 최적의 출력을 생성할 수 있습니다.(최적의 값은 확률 P의 각 기호에 대한 -logP₂ 비트입니다. 소스 코딩 정리를 참조하십시오.)산술 부호화를 사용하는 압축 알고리즘은 기본적으로 메시지 기호에서 어떤 패턴이 발견될지 예측하는 데이터 모델을 결정하는 것으로 시작합니다.이 예측이 정확할수록 출력은 최적에 가까워집니다.

예: 특정 모니터링 기기의 시간 경과에 따른 출력을 설명하기 위한 간단한 정적 모델은 다음과 같습니다.

기호의 60% 확률 중립
기호의 20% 확률 양성
10% 확률로 기호가 음수
END-OF-DATA 기호의 확률이 10%입니다(이 기호의 존재는 데이터 압축에서 흔히 볼 수 있듯이 스트림이 '내부 종료'됨을 의미합니다. 이 기호가 데이터 스트림에 나타나면 디코더에서 전체 스트림이 디코딩되었음을 알 수 있습니다).

모델에서는 이 예에서 선택한 단순한 4심볼 세트 이외의 알파벳도 처리할 수 있습니다.보다 정교한 모델도 가능하다: 고차 모델링은 앞에 오는 기호(문맥)를 기반으로 기호의 현재 확률에 대한 추정을 변경하기 때문에, 예를 들어 영어 텍스트의 모델에서 "Q" 또는 "q"를 따를 때 "u"의 백분율 확률이 훨씬 높아질 수 있다.모델은 적응성이 뛰어나 스트림에 실제로 포함된 내용을 기반으로 데이터에 대한 예측을 지속적으로 변경할 수도 있습니다.디코더는 인코더와 같은 모델이어야 합니다.

인코딩 및 디코딩: 개요

일반적으로 마지막을 제외하고 부호화 프로세스의 각 단계는 동일합니다.인코더에는 기본적으로 고려해야 할 데이터가3개밖에 없습니다

부호화할 필요가 있는 다음 기호
현재 간격(부호화 프로세스의 시작 시 간격은 [0,1]로 설정되지만 변경됨)
모형이 이 단계에서 가능한 다양한 기호 각각에 할당하는 확률(앞에서 언급한 바와 같이 고차 또는 적응 모형은 이러한 확률이 각 단계에서 반드시 동일하지는 않음을 의미합니다.)

인코더는 현재 인터벌을 서브인터벌로 나눕니다.각각은 현재 컨텍스트에서 해당 심볼의 확률에 비례하는 현재 인터벌의 일부를 나타냅니다.부호화할 실제 심볼에 대응하는 간격은 다음 단계에서 사용되는 간격이 됩니다.

예: 위의 4심볼 모델의 경우:

중립의 간격은 [0, 0.6]입니다.
POSITION의 간격은 [0.6, 0.8]가 됩니다.
Negative의 간격은 [0.8, 0.9]가 됩니다.
END-OF-DATA 간격은 [0.9, 1)]가 됩니다.

모든 기호가 부호화되면 그 결과 간격은 그것을 생성한 기호의 시퀀스를 명확하게 식별합니다.사용 중인 최종 간격과 모델이 동일한 사용자는 인코더에 입력된 심볼시퀀스를 재구성하여 최종 간격을 얻을 수 있습니다.

다만, 최종 간격을 송신할 필요는 없습니다.단, 그 간격 내에 있는 1개의 부분만을 송신할 필요가 있습니다.특히, 그 자리수로 시작하는 모든 분수가 마지막 간격에 들어갈 수 있도록 충분한 자릿수(근거에 관계없이)만 전송하면 됩니다.이것에 의해, 결과 코드가 프리픽스 코드가 되는 것이 보증됩니다.

부호화 및 디코딩: 예

예제 모델에서 0.538(둥근 점)의 디코딩을 보여주는 다이어그램입니다.영역은 기호 주파수에 비례하는 하위 영역으로 분할된 다음 점을 포함하는 하위 영역은 동일한 방식으로 순차적으로 세분됩니다.

지정된 4개의 심볼모델로 인코딩된 메시지를 디코딩하는 프로세스를 검토합니다.메시지는 분율 0.538로 부호화됩니다(명확성을 위해 바이너리가 아닌 10진수를 사용합니다.또, 메시지의 디코딩에 필요한 자리수 밖에 없는 것을 전제로 하고 있습니다).

프로세스는 인코더가 사용하는 것과 같은 인터벌[0,1]부터 시작하여 같은 모델을 사용하여 인코더가 가져야 하는4개의 서브인터벌로 나뉩니다.분율 0.538은 NEUTRAL의 서브인터벌 [0, 0.6]에 속합니다.이것은 인코더가 판독한 첫 번째 기호가 NEUTRAL이어야 함을 나타냅니다.따라서 이것이 메시지의 첫 번째 기호가 됩니다.

다음으로 간격 [0, 0.6]을 하위 간격으로 나눕니다.

중립의 간격은 [0, 0.36]으로 [0, 0.6]의 60%가 됩니다.
POSITION의 간격은 [0.36, 0.48]으로 [0, 0.6]의 20%가 됩니다.
음의 간격은 [0.48, 0.54], [0, 0.6]의 10%가 됩니다.
END-OF-DATA에 대한 간격은 [0, 0.6]의 10%인 [0.54, 0.6]이 됩니다.

0.538은 [0.48, 0.54] 간격 내에 있으므로 메시지의 두 번째 기호는 Negative여야 합니다.

다시 현재 간격을 하위 간격으로 나눕니다.

중립 간격은 [0.48, 0.516]가 됩니다.
POSITION의 간격은 [0.516, 0.528]가 됩니다.
음의 간격은 [0.528, 0.534)]가 됩니다.
END-OF-DATA 간격은 [0.534, 0.540]이 됩니다.

이제 0.538은 END-OF-DATA 기호의 간격 내에 있으므로 이 기호가 다음 기호여야 합니다.내부 종단 기호이기도 하므로 복호화가 완료되었음을 의미합니다.스트림이 내부적으로 종료되지 않은 경우 스트림의 정지 위치를 나타내는 다른 방법이 필요합니다.그렇지 않으면, 디코딩 과정이 영원히 계속될 수 있으며, 실수로 분수에 실제로 인코딩된 것보다 더 많은 기호를 읽을 수 있습니다.

비효율의 원인

앞의 예에서 0.538 메시지는 0.534, 0.535, 0.536, 0.537 또는 0.539로 등가하게 짧은 분수로 부호화될 수 있습니다.이는 이진법 대신 십진법을 사용하면 비효율성이 발생했음을 나타냅니다.이는 정확합니다. $3*\log _{2}(10)\approx 9.966$ 자리수의 10 진수의 $3*\log _{2}(10)\approx 9.966$ 내용은 3 $3*\log _{2}(10)\approx 9.966$ $3*\log _{2}(10)\approx 9.966$ 2 $3*\log _{2}(10)\approx 9.966$ ( $3*\log _{2}(10)\approx 9.966$ ) $3*\log _{2}(10)\approx 9.966$ 9 $3*\log _{2}(10)\approx 9.966$ 9 $3*\log _{2}(10)\approx 9.966$ { $displaystyle 3$ * \ $log$ _ {2 $}$ ( $10$ ) \ $999.$ 966 $3*\log _{2}(10)\approx 9.966$ $)$ 비트입니다.같은 메시지는 8비트의 비용으로 이진수 부분 0.10001010(0.5390625에 상당)으로 부호화될 수 있습니다.(마지막 0은 이진수로 지정해야 합니다.그렇지 않으면 압축 스트림크기 등의 외부 정보가 없으면 메시지가 애매해집니다).

이 8비트 출력은 메시지의 정보 내용 또는 엔트로피보다 큽니다.

\sum - \log _{2} (p_{i})=-\log _{2} (0.6)-\log _{2} (0.1)-\log _{2} (0.1)=7.381gctext {bits}}

단, 바이너리 부호화에서는 정수 비트를 사용해야 합니다.따라서 이 메시지의 인코더는 적어도8비트를 사용하기 때문에 엔트로피 콘텐츠보다 8.4% 큰 메시지가 생성됩니다.최대 1비트의 비효율성으로 인해 메시지사이즈가 커짐에 따라 오버헤드가 상대적으로 줄어듭니다.

더욱이, 주장된 기호 확률은 [0.6, 0.2, 0.1, 0.1]이었지만, 이 예에서 실제 주파수는 [0.33, 0.33, 0.33)입니다.이러한 주파수로 간격이 재조정되면 메시지의 엔트로피는 4.755비트이며, 동일한 NEUTRAL Negative END-OF-DATA 메시지는 간격[0, 1/3, 2/9); [5/27, 6/27] 및 이진 간격 [0.001011011, 00010001]로 인코딩될 수 있습니다.이는 산술 부호화 등의 통계 부호화 방법이 특히 확률 모델이 꺼진 경우 입력 메시지보다 큰 출력 메시지를 생성하는 방법을 보여주는 예이기도 합니다.

적응 산술 부호화

다른 유사한 데이터 압축 방법보다 산술 부호화의 한 가지 장점은 적응의 편리성이다.적응은 데이터를 처리하는 동안 빈도(또는 확률) 표를 변경하는 것입니다.디코딩된 데이터는 디코딩의 주파수 테이블을 인코딩과 동일한 방법으로 동일한 단계로 교체하는 한 원래 데이터와 일치합니다.동기화는 보통 부호화 및 디코딩 프로세스 중에 발생하는 기호의 조합을 기반으로 합니다.

정밀도 및 재규격화

위의 산술 부호화 설명은 약간의 단순화를 포함하고 있다.특히, 부호화가 최초로 무한정밀을 사용해 구간의 끝점을 나타내는 분수를 모두 계산해, 부호화의 마지막에 그 분수를 최종 형태로 변환한 것처럼 기술한다.대부분의 산술 부호화기는 무한 정밀도를 시뮬레이션하는 대신 디코더가 일치시킬 수 있는 고정 정밀도 한계로 동작하며 계산된 분수를 가장 가까운 등가물로 반올림합니다.예를 들어, 모델에서 구간 [ $0,1)$ 을 3등분해야 하며, 이는 8비트 정밀도로 근사한 경우 어떻게 작동하는지 보여 줍니다.이제 정밀도가 알려졌으므로 사용할 수 있는 이진 범위도 알 수 있습니다.

기호.	확률	간격이 8비트 정밀도로 감소		범위
기호.	(단위로 표시)	(분수로)	(2진수)	(2진수)
A	1/3	$[0, 85/256)$	[0.00000000, 0.01010101)	00000000 – 01010100
B	1/3	$[85/256, 171/256)$	[0.01010101, 0.10101011)	01010101 – 10101010
C	1/3	$[171/256, 1)$	[0.10101011, 1.00000000)	10101011 – 11111111

재규격화라고 하는 프로세스는 부호화할 수 있는 심볼의 총수에 대한 유한한 정밀도가 제한되는 것을 방지합니다.범위의 모든 값이 특정 시작 자릿수를 공유하는 지점까지 범위가 축소될 때마다 해당 자릿수가 출력으로 전송됩니다.컴퓨터가 처리할 수 있는 정밀도가 아무리 높더라도 현재 처리되는 정밀도는 이보다 낮기 때문에 기존 숫자는 왼쪽으로 이동하고 오른쪽에는 범위를 최대한 넓히기 위해 새로운 숫자가 추가됩니다.이 결과는 앞의 예에서 세 가지 경우 중 두 가지 경우에 발생합니다.

기호.	확률	범위	출력에 송신할 수 있는 자리수	정규화 후 범위
A	1/3	00000000 – 01010100	0	00000000 – 10101001
B	1/3	01010101 – 10101010	없음.	01010101 – 10101010
C	1/3	10101011 – 111111	1	01010110 – 111111

기수의 일반화 변화로서의 산술 부호화

기호가 동일한 확률을 갖는 경우 산술 부호화는 단순한 기저값 변경 또는 기수를 통해 구현될 수 있음을 기억하십시오.일반적으로 산술(및 범위) 부호화는 기수의 일반화 변화로 해석될 수 있다.예를 들어, 다음과 같은 기호 시퀀스를 볼 수 있습니다.

\displaystyle \mathrm {DABDDB} }

포함된 기호가 순서 집합을 형성하고 순서 집합의 각 기호는 순차 정수 A = 0, B = 1, C = 2, D = 3 등을 나타낸다고 가정하는 특정 기저값의 수치입니다.그 결과 다음과 같은 주파수와 누적 주파수가 발생합니다.

기호.	발생 빈도	누적 빈도
A	1	0
B	2	1
D	3	3

항목의 누적 빈도는 항목 앞에 있는 모든 빈도의 합입니다.즉, 누적 주파수는 실행 중인 총 주파수입니다.

위치 숫자 체계에서 기수 또는 밑수는 숫자를 표현하기 위해 사용되는 여러 가지 다른 기호와 수치적으로 동일합니다.예를 들어 10진법에서 기호 수는 10, 즉 0, 1, 2, 3, 4, 5, 6, 7, 8, 9입니다.기수는 추정된 승수의 유한 정수를 다항식으로 표현하기 위해 사용됩니다.예를 들어, 숫자 457은 실제로는 4²×10 + 5×10 + 7⁰×10¹ 이며, 여기서 베이스 10은 추정되지만 명시적으로 나타나지는 않습니다.

6은 문자열 길이이기 때문에 처음에는 DABDDB를 6진수로 변환합니다.문자열은 먼저 숫자 문자열 301331에 매핑되며, 그 다음 다항식으로 정수에 매핑됩니다.

6^{5}\times 3+6^{4}}\times 0+6^{3}\times 1+6^{2}\x 3+6^{1}\times 3+6^{0}\times 1=23671

결과 23671의 길이는 15비트로 이론적인 한계(메시지 엔트로피)에 매우 가깝지 않습니다.이것은 약 9비트입니다.

정보이론에 의해 부과된 이론적 한계에 가까운 길이로 메시지를 인코딩하려면 기수를 바꾸는 고전적인 공식을 약간 일반화해야 합니다.하한과 상한 L과 U를 계산하고 그 중에서 숫자를 선택합니다.L의 계산을 위해 위의 식에서 각 항에 이전에 발생한 모든 기호의 빈도를 곱한다.

디스플레이 스타일L={}&(6^{5}\times 3)+{}\&3\times (6^{4}\times 0)+{}\&(3\times 1)\times (6^{3}\times 1)+{}\&(3\times 1\times 2)\times (6^{2}\times 3\tes 3\times 1)+{\times 1\times 1\times 1\times 1\times 1\times }&times

이 다항식과 위의 다항식의 차이점은 각 항에 이전에 발생한 모든 기호의 빈도를 곱한 것입니다.보다 일반적으로 L은 다음과 같이 계산될 수 있다.

L=\sum _{i=1}^{n^{n-i}C_{i}{\prod _{k=1}^{i-1}f_{k}}

$\scriptstyle C_{i}$ 서 $(\displaystyle$ \ $scriptstyle C_{i$ })는 $\scriptstyle C_{i}$ 누적 빈도, $(\$ })는 $\scriptstyle f_{k}$ 발생 빈도입니다.색인은 메시지에서 기호의 위치를 나타냅니다.모든 $\scriptstyle f_{k}$ $(\displaystyle$ \ $scriptstyle f_{$ k $\scriptstyle f_{k}$ })가 1인 특수한 경우, 이것은 기저 변경 공식입니다.

상한 U는 L + 모든 주파수의 곱이 됩니다. 이 경우 U = L + (3 × 1 × 2 × 3 × 2) = 25002 + 108 = 25110입니다.일반적으로 U는 다음과 같이 표시됩니다.

U=L+\prod _{k=1}^{n}f_{k

이제 인터벌 [L, U]에서 임의의 숫자를 선택하여 메시지를 나타낼 수 있습니다.하나의 편리한 선택은 결과를 251×10으로² 표현함으로써 압축을 달성할 수 있기 때문에 가능한 한 긴 트레일이 0인 값인 25100입니다.메시지 길이가 별도로 저장될 경우 0이 잘려 251이 될 수도 있습니다.메시지가 길수록 0의 흔적이 길어지는 경향이 있습니다.

정수 25100을 디코딩하려면 아래 표와 같이 다항식 계산을 반전할 수 있습니다.각 단계에서 전류 기호가 식별되고, 그 결과에서 대응하는 항이 감산된다.

나머지	신분증	식별 기호	보정잔량
25100	25100 / 6⁵ = 3	D	(25100 - 6⁵ × 3) / 3 = 590
590	590 / 6⁴ = 0	A	(590 - 6⁴ × 0) / 1 = 590
590	590 / 6³ = 2	B	(590 - 6³ × 1) / 2 = 187
187	187 / 6² = 5	D	(162² - 6 × 3) / 3 = 26
26	26 / 6¹ = 4	D	(26¹ - 6 × 3) / 3 = 2
2	2 / 6⁰ = 2	B	—

복호화 중에는 6의 해당 거듭제곱으로 나눈 후 층을 차지합니다.그런 다음 결과가 누적 간격과 비교되고 조회 테이블에서 적절한 기호가 선택됩니다.기호가 식별되면 결과가 보정됩니다.이 프로세스는 메시지의 기존 길이 동안 또는 나머지 결과가 양일 때 계속됩니다.기존의 기저 변경과 비교되는 유일한 차이점은 각 기호와 관련된 값의 범위가 있을 수 있다는 것입니다.이 예에서는 A는 항상 0, B는 1 또는 2, D는 3, 4, 5 중 하나입니다.이는 주파수에 따라 결정되는 간격과 정확히 일치합니다.모든 구간이 1일 때 전형적인 기저값 변경의 특별한 경우가 있습니다.

압축 메시지의 이론적 한계

하한 L은 n을 넘지ⁿ 않습니다.여기서 n은 메시지의 크기이므로 로그 2 $\log _{2}(n^{n})\;=\;n\log _{2}(n)$ ( n $\log _{2}(n^{n})\;=\;n\log _{2}(n)$ ) $=$ $\log _{2}(n^{n})\;=\;n\log _{2}(n)$ 2 $\log _{2}(n^{n})\;=\;n\log _{2}(n)$ ( $\log _{2}(n^{n})\;=\;n\log _{2}(n)$ $displaystyle \log$ _ ${2}$ ( $n^{n$ } \ ; n $\log _{2$ } ( $n$ ) } 비트로 $\log _{2}(n^{n})\;=\;n\log _{2}(n)$ $\log _{2}(n^{n})\;=\;n\log _{2}(n)$ 수 있습니다.상한 U를 계산하고 0의 가장 긴 트레일이 있는 간격 [L, U]에서 숫자를 선택하여 메시지를 줄인 후 $\log _{2}\left({\scriptstyle \prod _{k=1}^{n}}f_{k}\right)$ 2 $2$ ( $\log _{2}\left({\scriptstyle \prod _{k=1}^{n}}f_{k}\right)$ k $\log _{2}\left({\scriptstyle \prod _{k=1}^{n}}f_{k}\right)$ $1$ n $\log _{2}\left({\scriptstyle \prod _{k=1}^{n}}f_{k}\right)$ ) { $display$ style $_ {2}$ \ display style \ $left$ \ $script$ style \ $script$ style \ $light$ _ { k = $1 }^{nf_k})$ 로 $\log _{2}\left({\scriptstyle \prod _{k=1}^{n}}f_{k}\right)$ 이 길이를 줄일 수 있다고 가정할 수 있습니다.제품의 각 주파수는 이 주파수의 값과 정확히 같은 횟수로 발생하므로 제품의 계산에 알파벳 A의 크기를 사용할 수 있습니다.

\displaystyle _{k=1}^{n}f_{k}=\display_{k=1}^{A}f_{k}^f_{k}}

메시지 내의 예상 비트 수에 대한 로그를 적용하면₂ 최종 메시지(메시지 길이 및 주파수 테이블에 대한 로그 오버헤드는 카운트되지 않음)는 엔트로피에 의해 지정된 비트 수와 일치합니다.이 값은 긴 메시지의 경우 최적에 매우 가깝습니다.

-\left[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\right]*n

다른 압축 방식과의 연결

허프만 부호화

산술 부호화는 한 번에 하나의 데이터를 압축하지 않기 때문에 IID 문자열을 압축할 때 임의로 엔트로피에 가까워질 수 있습니다.반대로, (문자열로의) 허프만 부호화의 확장은 알파벳 기호의 모든 확률이 2의 거듭제곱이 되지 않는 한 엔트로피에 도달하지 않는다.이 경우 허프만 부호화와 산술 부호화 모두 엔트로피를 달성한다.

순수하게 Huffman 부호화 바이너리 스트링의 경우 엔트로피가 낮더라도 압축이 불가능합니다(예: {0, 1) 확률 {0.95, 0.05}).허프만 부호화는 각 값에 1비트를 할당하여 입력과 같은 길이의 코드를 생성합니다.반면, 산술 부호화는 비트를 잘 압축하여 최적의 압축비에 접근한다.

\ displaystyle 1 - 0 . 95 \ log _ { 2 （ 0 . 95 ) + 0 . 05 \ log _ { 2 （ 0 . 0 5 ）\ ]약 71.4%}

허프만 부호화의 부최적성에 대처하는 한 가지 간단한 방법은 기호("블록")를 연결하여 각 새로운 기호가 원래의 알파벳에서 원래의 기호(이 경우 비트)의 시퀀스를 나타내는 새로운 알파벳을 형성하는 것입니다.위의 예에서는 부호화 전에 3개의 심볼로 시퀀스를 그룹화하면 다음 주파수의 새로운 "슈퍼 심볼"이 생성됩니다.

000: 85.7%
001, , : 각 4.5%
011, , : 각 0.24%
111: 0.0125%

이 그룹에서 Huffman 코딩은 3개의 기호당 평균 1.3비트, 즉 기호당 0.433비트를 나타냅니다.이것에 비해, 원래의 부호화에서는 $56.7\%$ 7 $%(\style 56$ .7 $\%)$ 의 $56.7\%$ 압축률을 나타내고 있습니다.임의의 큰 시퀀스를 산술 부호화처럼 임의로 엔트로피에 가깝게 할 수 있지만, 그러기 위해서는 거대한 코드가 필요하기 때문에 이 목적을 위한 산술 부호화만큼 실용적이지 않습니다.

다른 방법으로는 Huffman 기반의 Golomb-Rice 코드를 사용하여 실행 길이를 인코딩하는 방법이 있습니다.이러한 접근법에 의해 산술 부호화 또는 허프만 부호화보다 간단하고 빠른 부호화/복호화가 가능해집니다.{0.95, 0.05} 예에서 나머지 4비트의 Golomb-Rice $코드$ 는 71 $.1%$ 의 $71.1\%$ 을 달성하며, 이는 3비트 블록을 사용하는 것보다 훨씬 더 최적에 가깝습니다 $71.1\%$ 단, Golomb-Rice 코드는 이 예시와 같은 Bernouli 입력에만 적용되므로 모든 경우에 블로킹을 대체하는 것은 아닙니다.

이력 및 특허

산술 부호화를 위한 기본 알고리즘은 Jorma J. Rissanen, IBM Research 및 Richard C에 의해 독립적으로 개발되었습니다.스탠포드 대학의 박사과정 학생인 Pasco; 둘 다 1976년 5월에 출판되었다.Pasco는 Rissanen의 기사의 출판 전 초안과 그들의 ^[3]작품 간의 관계에 대한 코멘트를 인용했다.

한 계열 알고리즘은 Rissanen에 의해 독립적으로 개발되었다[1976].덧셈과 지수를 통해 얻은 포인터를 사용하여 코드 요소를 어큐뮬레이터의 가장 중요한 끝으로 이동합니다.이제 이 세 가지 선택지의 대안을 비교하여 어큐뮬레이터보다 코드 요소를 전환하고 어큐뮬레이터의 최하위 엔드에 코드 요소를 추가하는 것이 더 낫다는 것을 확인합니다.

IBM은 발표된 지 1년도 채 되지 않아 Rissanen의 작품에 대한 미국 특허를 출원했다.Pasco의 작품은 특허를 받지 않았다.

산술 부호화에 관한 다양한 특정 기술은 역사적으로 미국 특허에 의해 다루어져 왔지만, 특허가 만료됨에 따라 여러 가지 알려진 방법이 그 후 일반에 보급되었다.특허에 포함되는 기술은 일부 공식 국제 표준에서 규정된 산술 부호화 알고리즘을 구현하기 위해 필수적일 수 있다.이러한 경우, 이러한 특허는 일반적으로 (적어도 표준위원회 정책의 문제로서) "합리적이고 차별적이지 않은" (RAND) 라이선스 조건에 따라 라이선스할 수 있다.일부 잘 알려진 경우(기한이 만료된 IBM 특허와 관련된 경우 포함)에는 이러한 라이센스가 무료로 제공되었고, 다른 경우에는 라이센스 비용이 요구되었습니다.RAND 조건에 따른 라이선스의 이용은, 이 테크놀로지를 사용하고 싶다고 하는 모든 사람을 만족시키는 것은 아닙니다.이것은, 독자 사양의 상용 소프트웨어 제품을 준비하고 있는 기업에게는 「합리적인」 것처럼 보이는 것이, 무료 소프트웨어나 오픈 소스 프로젝트에는 그다지 타당하지 않은 것처럼 보일 수 있기 때문입니다.

적어도 하나의 중요한 압축 소프트웨어 프로그램인 bzip2는 당시 인식된 특허 상황 때문에 허프만 부호화를 위해 산술 부호화의 사용을 의도적으로 중단했다.또한, 이것은 허프만과 부호화 산술 부호화를 위한 옵션이 있는 JPEG파일 형식의 인코더 및 디코더는 오직 일반적으로;그 결과 비록 JPEG의 산술 코딩 patents[5]이 사용에서 거의 모든 제이 페그 이미지 파일들 오늘 허프만 encoding[4]사용하는 것은 당초 특허에 대한 우려 때문에는 허프만 부호화 방식 선택 지지한다. expirJPEG 표준의 연령으로 인해 편집되었습니다(^[6]JPEG 표준의 설계는 1990년에 대략 완료됨).JPEG XL과 PackJPG, Brunsli, Lepton 등의 아카이브 서버는 Huffman 인코딩 파일을 산술 부호화(또는 JPEG XL의 경우 비대칭 숫자 시스템)로 무손실 변환하여 최대 25%의 크기를 절약할 수 있습니다.

JPEG 이미지 압축 포맷의 산술 부호화 알고리즘은 다음과 같은 인용 특허를 기반으로 합니다(유효 ^[7]기간이 지났습니다).

미국 특허 4,652,856 – (IBM) 1986년 2월 4일 출원, 1987년 3월 24일 부여 - 코타푸람 M. A. 모히우딘, 조르마 요한넨 리사넨 – 곱셈 없는 다중 알파벳 산술 코드
미국 특허 4,905,297 – (IBM) 1988년 11월 18일 출원, 1990년 2월 27일 - Glen George Langdon, Joan L.미첼, 윌리엄 BPennebaker, Jorma Johannen Rissanen – 산술 부호화 인코더 및 디코더 시스템
미국 특허 4,935,882 – (IBM) 1988년 7월 20일 출원, 1990년 6월 19일 부여 - 윌리엄 B.페네베이커, 조앤 L.Mitchell – 산술 코더를 위한 확률 적응
JP특허 1021672 – (미쓰비시) 1989년 1월 21일 출원, 1990년 8월 10일 허가– 키무라 도시히로, 키노 시게노리, 오노 후미타카, 요시다 마사유키 - 코딩 시스템
JP특허 2-46275 – (미쓰비시) 1990년 2월 26일 출원, 1991년 11월 5일 허가– 오노 후미타카, 기무라 도모히로, 요시다 마사유키, 키노 시게노리 - 부호화 장치 및 부호화 방법

산술 코딩과 관련된 기타 특허(대부분 유효기간이 만료됨)는 다음과 같습니다.

미국 특허 4,122,440 – (IBM) 1977년 3월 4일 출원, 1978년 10월 24일 부여 – Glen George Langdon, Jorma Johannen Rissanen – 산술 문자열 부호화 방법 및 방법
미국 특허 4,286,256 – (IBM) 1979년 11월 28일 출원– Glen George Langdon, Jorma Johannen Rissanen – 감소된 연산수를 이용한 산술 부호화 방법 및 방법
미국 특허 4,467,317 – (IBM) 1981년 3월 30일 출원, 1984년 8월 21일 부여 – Glen George Langdon, Jorma Johannen Rissanen – 동시 값 업데이트를 사용한 고속 산술 압축 부호화
미국 특허 4,891,643 – (IBM) 1986년 9월 15일 출원, 1990년 1월 2일 부여 - Joan L.미첼, 윌리엄 BPennebaker – 선택적으로 사용되는 다양한 산술 부호화 인코더 및 디코더에 의한 산술 부호화 데이터 압축/해제
JP 특허 11782787 – (NEC) 1987년 5월 13일 출원, 1988년 11월 18일 부여 - 시마다 미치오 – 데이터 압축 산술 부호화 장치
JP특허 15015487 – (KDDI) 1987년 6월 18일 출원, 1988년 12월 22일 부여 - 마쓰모토 슈이치, 사이토 마사히로 - 산술 부호화에서의 전파 방지를 위한 시스템
미국 특허 4,933,883 – (IBM) 1988년 5월 3일 출원, 1990년 6월 12일 부여 - 윌리엄 B.페네베이커, 조앤 L.Mitchell – 산술 코더를 위한 확률 적응
미국 특허 4,989,000 – (IBM) 1989년 6월 19일 출원, 1991년 1월 29일 부여– Dan S.쉐비온, 에후드 DKarnin, Eugeniusz Walach – 산술 부호화를 사용한 데이터 문자열 압축 및 확률 하위 구간 추정
미국 특허 5,099,440 – (IBM) 1990년 1월 5일 출원, 1992년 3월 24일 부여 - 윌리엄 B.페네베이커, 조앤 L.Mitchell – 산술 코더를 위한 확률 적응
미국 특허 5,272,478 – (Ricoh) 1992년 8월 17일 출원, 1993년 12월 21일 부여 - 제임스 D.Allen – 엔트로피 부호화 방법 및 장치

주의: 이 목록은 전체 목록이 아닙니다.기타 미국 ^[8]특허 목록은 다음 링크를 참조하십시오.Dirac 코덱은 산술 부호화를 사용하며 특허 ^[9]출원 중이 아닙니다.

산술 부호화에 관한 특허는 다른 국가에서도 존재할 수 있습니다.전 세계 소프트웨어의 특허성에 대해서는 소프트웨어 특허를 참조해 주십시오.

벤치마크 및 기타 기술적 특징

산술 부호화의 각 프로그램 실장은 압축비와 퍼포먼스가 다릅니다.압축률은 약간(보통 1%^[10] 미만)에 불과하지만 코드 실행 시간은 10배 정도 차이가 날 수 있습니다.퍼포먼스와 압축비는 데이터 유형, 특히 알파벳 크기(다른 기호의 수)에 따라 달라지기 때문에 공개적으로 사용 가능한 인코더 목록에서 적절한 인코더를 선택하는 것은 간단한 작업이 아닙니다.2개의 특정 인코더 중 하나는 작은 알파벳에 대해 더 나은 성능을 나타내고 다른 하나는 큰 알파벳에 대해 더 나은 성능을 나타낼 수 있습니다.대부분의 인코더는 알파벳 크기에 제한이 있으며 많은 인코더는 정확히 두 개의 기호(0과 1)를 가진 알파벳 전용입니다.

「」를 참조해 주세요.

메모들

^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 April 2014). Fundamentals of Multimedia. Springer Science & Business Media. ISBN 978-3-319-05290-8.
^ J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, Huffman 코딩의 정확한 대체로서 비대칭 숫자 시스템을 사용한다, Picture Coding Symposium, 2015.
^ Pasco, Richard Clark (May 1976). Source coding algorithms for fast data compression (PhD). Stanford Univ. CiteSeerX 10.1.1.121.3377.
^ "What is JPEG?". comp.compression Frequently Asked Questions (part 1/3).
^ "Recommendation T.81 (1992) Corrigendum 1 (01/04)". Recommendation T.81 (1992). International Telecommunication Union. 9 November 2004. Retrieved 3 February 2011.
^ Pennebaker, W. B.; Mitchell, J. L. (1992). JPEG Still Image Data Compression Standard. Kluwer Academic Press. ISBN 0442012721.
^ "T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES" (PDF). CCITT. September 1992. Retrieved 12 July 2019.
^ "Frequently Asked Questions". comp.compression.
^ "Dirac video codec 1.0 released".
^ 예를 들어 Howard & Vitter(1994)는 실수 범위, 그 범위에 대한 정수 근사치 및 이진수 준산수 부호화라고 불리는 훨씬 더 제한된 유형의 근사치에 기초한 산술 부호화 버전을 논의한다.이들은 실수 버전과 정수 버전 간의 차이가 무시할 수 있다고 명시하고, 준산술 방법에 대한 압축 손실을 임의로 작게 만들 수 있음을 증명하며, 근사치 중 하나에 의해 발생한 압축 손실을 0.06% 미만으로 제한한다.를 참조해 주세요.

레퍼런스

MacKay, David J.C. (September 2003). "Chapter 6: Stream Codes". Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1. Archived from the original (PDF/PostScript/DjVu/LaTeX) on 22 December 2007. Retrieved 30 December 2007.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 22.6. Arithmetic Coding". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
Rissanen, Jorma (May 1976). "Generalized Kraft Inequality and Arithmetic Coding". IBM Journal of Research and Development. 20 (3): 198–203. doi:10.1147/rd.203.0198. Retrieved 21 September 2007.
Rissanen, J.J.; Langdon G.G., Jr (March 1979). "Arithmetic coding" (PDF). IBM Journal of Research and Development. 23 (2): 149–162. doi:10.1147/rd.232.0149. Archived from the original (PDF) on 28 September 2007. Retrieved 22 September 2007.
Witten, Ian H.; Neal, Radford M.; Cleary, John G. (June 1987). "Arithmetic Coding for Data Compression" (PDF). Communications of the ACM. 30 (6): 520–540. doi:10.1145/214762.214771. S2CID 3343393. Archived (PDF) from the original on 28 September 2007. Retrieved 21 September 2007.

로디오노프 아나톨리, 볼코프 세르게이(2010) "p-adic 산술 부호화" 현대 수학 제508권, 2010 현대 수학
Rodionov Anatoly, Volkov Sergey (2007) "p-adic 산술 부호화", https://arxiv.org/abs//0704.0834v1

외부 링크

이 문서에는 NIST 문서의 퍼블릭 도메인 자료가 포함되어 있습니다.
산술 부호화의 간단한 예제를 사용한 뉴스 그룹의 투고(정수만).
산술 부호화에 관한 PlanetMath 기사
범위 인코더의 해부 이 문서에서는 범위 및 산술 부호화에 대해 설명합니다.또한 성능 비교와 함께 3개의 다른 산술 인코더에 대한 코드 샘플도 포함되어 있습니다.
산술 부호화 입문60페이지.
Eric Bodden, Malte Clasen 및 Joachim Kneis:산술 부호화가 공개되었습니다.테크니컬 리포트 2007-5, 맥길 대학교 세이블 리서치 그룹.
산술 부호화 + 통계 모델링 = Mark Nelson의 데이터 압축.
Mark Nelson의 산술 부호화에 의한 데이터 압축(2014)
James K에 의한 범위 코딩 및 rANS의 신속한 구현.본필드

[LiDrew2014-1] Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 April 2014). Fundamentals of Multimedia. Springer Science & Business Media. ISBN 978-3-319-05290-8.

[PCS2015-2] J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, Huffman 코딩의 정확한 대체로서 비대칭 숫자 시스템을 사용한다, Picture Coding Symposium, 2015.

[3] Pasco, Richard Clark (May 1976). Source coding algorithms for fast data compression (PhD). Stanford Univ. CiteSeerX 10.1.1.121.3377.

[4] "What is JPEG?". comp.compression Frequently Asked Questions (part 1/3).

[5] "Recommendation T.81 (1992) Corrigendum 1 (01/04)". Recommendation T.81 (1992). International Telecommunication Union. 9 November 2004. Retrieved 3 February 2011.

[6] Pennebaker, W. B.; Mitchell, J. L. (1992). JPEG Still Image Data Compression Standard. Kluwer Academic Press. ISBN 0442012721.

[t81-7] "T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES" (PDF). CCITT. September 1992. Retrieved 12 July 2019.

[8] "Frequently Asked Questions". comp.compression.

[9] "Dirac video codec 1.0 released".

[10] 예를 들어 Howard & Vitter(1994)는 실수 범위, 그 범위에 대한 정수 근사치 및 이진수 준산수 부호화라고 불리는 훨씬 더 제한된 유형의 근사치에 기초한 산술 부호화 버전을 논의한다.이들은 실수 버전과 정수 버전 간의 차이가 무시할 수 있다고 명시하고, 준산술 방법에 대한 압축 손실을 임의로 작게 만들 수 있음을 증명하며, 근사치 중 하나에 의해 발생한 압축 손실을 0.06% 미만으로 제한한다.를 참조해 주세요.

[1]

[2]

[3]

[6]

[7]

[8]

[9]

[10]

Search

산술 부호화

네임스페이스

더

목차