범용 코드(데이터 압축)

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : "범용코드" 데이터 압축– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2011년 11월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

데이터 압축에서, 정수를 위한 범용 코드는 정수의 실제 확률 분포가 단조로운 한 (즉, 모든 양의 i에 대한 p(i) p p(i + 1) 코드 워드의 예상 길이 안에 있는 한, 정수의 진정한 확률 분포가 무엇이든 간에 2진수 코드워드에 매핑하는 접두사 코드이다.해당 확률 분포에 대한 최적 코드가 할당했을 기대 길이의 상수 요인.유니버설 코드는 실제 길이와 최적 기대 길이의 비율이 엔트로피가 무한대에 가까워짐에 따라 바운드에 더해 1에 가까워지는 코드의 정보 엔트로피 함수에 의해 바운딩되면 점근적으로 최적이다.

일반적으로 정수용 프리픽스코드의 대부분은 큰 정수에 긴 코드워드를 할당합니다.이러한 코드를 사용하여 가능성이 낮은 메시지세트를 정렬하고 원하는 메시지의 인덱스를 송신하는 것만으로 가능한 메시지세트에서 도출된 메시지를 효율적으로 전달할 수 있습니다.범용 코드는 일반적으로 정확하게 알려진 확률 분포에는 사용되지 않으며, 실제로 사용되는 분포에 최적인 범용 코드는 알려져 있지 않습니다.

범용 코드를 범용 소스 코드와 혼동해서는 안 된다.이 코드에서는 데이터 압축 방법이 고정 프리픽스 코드일 필요는 없으며 실제 길이와 최적 예상 길이 사이의 비율이 1에 근접해야 한다.단, 점근적으로 최적의 유니버설코드는 유니버설소스 코딩의 방법으로 점점 더 큰 블록을 사용함으로써 등분포된 독립된 소스에 사용할 수 있습니다.

범용 및 비범용 코드

다음은 정수의 범용 코드입니다.아스타리스크(*)는 사전순으로 3차적으로 재작성할 수 있는 코드를 나타내고, 이중 단검(")은 점근적으로 최적의 코드를 나타냅니다.

• Elias 감마 부호화 *
• Elias 델타 부호화 * ‡
• Elias 오메가 코드 *^{[further explanation needed]} ‡
• Exp-Golomb 부호화 *. Elias 감마 부호화가 특수한 경우입니다.(H.264/MPEG-4 AVC에서 사용)
• 피보나치 부호화
• Levenshtein 부호화 * ,, 원래의 범용 부호화 기법 [1]
• 특수 비트 패턴(2비트 이상)을 사용하여 코드의 끝을 마크하는 바이트 코딩. 예를 들어 정수가 보다 자연스러운 베이스 16이 아닌 베이스 15에서 숫자를 나타내는 니블 시퀀스로 인코딩된 경우, 가장 높은 니블 값(즉, 바이너리에서는 4개의 1의 시퀀스)을 사용하여 적분의 끝을 나타낼 수 있습니다.음.정말.
• 가변길이수량

다음은 비범용입니다.

• Elias 코드에서 사용되는 단항 부호화
• 쌀 코딩: FLAC 오디오코덱에서 사용되며 특수한 경우로서 단항 코딩이 있습니다.
• Golomb 코딩 - 라이스 코딩 및 단항 코딩이 특수한 경우입니다.

가우스-쿠즈민 분포 또는 제타 분포를 모수 s=2로 코드화하는 데 사용되는 경우 예상되는 코드워드 길이가 무한하다는 것을 알아냄으로써 이들의 비범용성(nonuniversity) 비범용성을 관찰할 수 있다.예를 들어, 제타 분포에서 단항 부호화를 사용하면 예상 길이가 다음과 같습니다.

${\displaystyle E(l)=frac {6}{\pi ^{2}}\sum _{l=1}^{\infty}{\frac {1}{l}=\infty .,}$

한편, Gauss-Kuzmin 분포에 범용 Elias 감마 코딩을 사용하면 엔트로피(약 3.43 비트)[2]에 가까운 예상 코드워드 길이(약 3.51 비트)가 된다.

실용적 압축과의 관계

허프만 부호화 및 산술 부호화(사용 가능한 경우)는 적어도 범용 코드보다 우수하고 종종 더 나은 압축을 제공합니다.

단, 유니버설코드는 Huffman 부호화를 사용할 수 없는 경우(예를 들어 각 메시지의 정확한 확률을 모르고 확률의 순위만 알고 있는 경우)에 도움이 됩니다.

유니버설 코드는 허프만 코드가 불편할 때도 유용합니다.예를 들어, 송신기가 메시지의 확률을 알고 있지만 수신자가 아닌 경우, Huffman 부호화는 그러한 확률을 수신자에게 송신하는 오버헤드를 필요로 한다.범용 코드를 사용하면 오버헤드가 발생하지 않습니다.

각 범용 부호는 서로 자기계발적(self-contracting) 이진 코드와 마찬가지로 P(i)=2에^−l(i) 의해 주어진 자체 "확률 분포"를 가진다. 여기서 l(i)는 ith 코드 워드의 길이이고 P(i)는 대응하는 심볼의 확률이다.If the actual message probabilities are Q(i) and Kullback–Leibler divergence ${\displaystyle D_{\text{KL}}(Q\ P)}$ is minimized by the code with l(i), then the optimal Huffman code for that set of messages will be equivalent to that code.마찬가지로 코드가 최적에 얼마나 가까운지도 이 차이를 통해 측정할 수 있습니다.유니버설 코드는 Huffman 코드보다 부호화 및 복호화가 간단하고 빠르기 때문에(즉, 산술 부호화보다 간단하고 빠르기 때문에) ${\displaystyle {\text{DKL}}_{}}$ ${\displaystyle {}_{}Qp}$P$$) { $displaystyle D_{\text{$KL$}}$ ($Q\P)}$ 이$$ $충분히{\displaystyle {}_{}}$ 작은 경우에는 유니버설코드가 바람직합니다.[3]

모든 기하 분포(정수의 지수 분포)에 대해 Golomb 코드가 최적입니다.유니버설 코드의 경우 암묵적 분포는${\displaystyle }$대략 1/${\displaystyle {n\mathrm{}}^{}}$ 2$(\$1/$n^{2})$와 $같은{\displaystyle \mathrm{}}$ 멱함수 법칙입니다(더 정확히는 Zipf 분포).피보나치 코드의 경우 암묵적인 분포는 $약{\displaystyle \mathrm{}}$1/$(\$1/$n^{q$입니다.

${\displaystyle q=1/\log _{2}(varphi)\displayq 1.44,}$

여기서$\delta {\displaystyle }$(\$displaystyle \varphi)$는 황금 비율입니다.3진법 콤마 코드(즉, 기호당 2비트로 표시됨)의 경우 암묵적 분포는 q ${\displaystyle =1}$ + ${\displaystyle {log\mathrm{}}_{}}$ 3 ${\displaystyle (}$ ($4$ /${\displaystyle 3\mathrm{}}$)$$ 1.$26 {$ $displaystyle$q$$= 1 + $log$_ {$3$ ($4$ / 3) \ $log _$ { 3$\}$ )의 멱함수 법칙입니다.이러한 분포는 각각의 최적 분포에 가깝습니다.

외부 링크

• 데이터 압축, Debra A.르워와 다니엘 S.Hirschberg(캘리포니아 대학교 어바인)
• David McKay의 정보 이론, 추론 및 학습 알고리즘에는 Ellias 코드에 대한 소개를 포함한 정수 코드에 대한 장이 있습니다.
• Кодирование целых чисел has mostly English-language papers on universal and other integer codes.