터널 부호화

컴퓨터 과학 및 정보 이론에서, Tunstall 부호화는 무손실 데이터 압축에 사용되는 엔트로피 부호화의 한 형태이다.

역사

툰스톨 코딩은 조지아 공과대학에 재학 중이던 1967년에 브라이언 파커 툰스톨의 박사 논문의 주제였다.그 논문의 주제는 "소음 없는 압축 코드의 합성"이었다.

이 설계는 Lempel-Ziv의 선구자이다.

특성.

Huffman 및 Lempel-Ziv 부호화를 포함하는 가변 길이 코드와 달리 Tunstall 부호화는 소스 기호를 고정 비트 ^[2]수에 매핑하는 코드입니다.

Tunstall 코드와 Lempel-Ziv 코드는 모두 가변 길이 단어를 고정 길이 ^[3]코드로 나타냅니다.

일반적인 세트 부호화와는 달리, Tunstall 부호화는 가변 길이의 코드 워드를 사용하여 확률 소스를 해석합니다.

충분히 큰 사전의 경우 소스 문자당 비트 수는 소스의 엔트로피인 H$)\displaystyle$ H$(U$에 $임의$로 근접할 수 있습니다^[4].

알고리즘.

이 알고리즘에는 입력 $알파벳{\displaystyle \mathcal{}}$U(\$displaystyle\mathcal {U$와 각 단어 입력에 대한 확률 분포가 필요합니다.또한 계산하는 사전 $크기$의 상한인 임의의 상수$$C(\$style$ C$)$가 필요합니다.문제의 사전 $(\displaystyle$ D$)$는 확률 트리로 구성되며, 이 트리에서 각 가장자리는 입력 알파벳의 문자와 관련지어집니다.알고리즘은 다음과 같습니다.

 :${\displaystyle }$= ${\displaystyle U\mathcal{}}$ \$$$display$ \ $mathcal$$${ U $}$$,,,$ 。$D$<  \ $display D < C$> : U$\ display$ \ $mathcal$ {$U }$ } ${\displaystyle in\mathcal{}}$ in in 。 

예

이 문서는 Wikipedia의 품질 기준을 충족하기 위해 청소가 필요할 수 있습니다.구체적인 문제는 잘못된 확률입니다. 가능하면 이 문서를 개선해 주십시오. (2014년 8월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

예를 들어 문자열 "hello, world"를 부호화한다고 가정합니다.($어느{\displaystyle \mathcal{}}$ 정도 비현실적으로) 입력 알파벳$$U$(\displaystyle\mathcal {U$})에$$ 문자열 "hello, world" 문자(즉, 'h', 'e', 'l', '', 'w', 'o', 'r', 'd' 문자만 포함되어 있다고 가정합니다.따라서 입력 문자열의 통계적 외관을 바탕으로 각 문자의 확률을 계산할 수 있습니다.예를 들어 문자 L은 12자 문자열로3번 표시됩니다.$확률$은 $3 12$입니다$.$

트리는 U ${\displaystyle =}$ $({displaystyle {U}}$=$9)$의 ${\displaystyle 잎}$으로 시작합니다.따라서 각 단어는 알파벳 문자와 직접 관련지어집니다.따라서 취득한9개의 워드는${\displaystyle }$"${\displaystyle {log\mathrm{}}_{}}$ 2${\displaystyle "}$ (${\displaystyle 9)}$ ${\displaystyle =}$ ${\displaystyle$ \$lceil$ \$log _{2$}($9)\rceil = 4}$ 비트의$$ 고정 크기 출력으로 부호화할 수 있습니다.

그런 다음 확률이 가장 높은 잎($여기$서 ${\displaystyle {w\mathrm{}}_{}}$ ${\$1})을 가져와서 ${\displaystyle \mathrm{U}}$ 9$(\displaystyle$ {$U} = 9)$의 또 다른 트리로 변환합니다.우리는 그 휴가들의 확률을 재계산한다.예를 들어 두 글자 L의 시퀀스는 한 번 발생합니다.L 뒤에 세 개의 문자가 있다고 가정하면, 그 결과는 $1{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{3}{}}$ ${\displaystyle ÷}$ ${\displaystyle 3\frac{\mathrm{}}{}}$ ${\displaystyle \frac{12}{}}$ $=$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{12}{}}$ ${$ { $displaystyle { 1$ \$over$ 3$}\cdot${ 3 \$over$ 12 $}=$ {$$1$$\$over$ 12}

17개의 워드를 취득했습니다.이러한 워드는 각각${\displaystyle }$"${\displaystyle {log\mathrm{}}_{}}$ 2${\displaystyle "}$ ($=$ ${\displaystyle 5}$ ${\displaystyle \lceil$ \$log _{2}($17)\$rceil =$5}비트의$$ 고정 크기 출력으로 부호화할 수 있습니다.

다시 한 번 반복하면${\displaystyle }$단어 ${\displaystyle \mathrm{수}}$가 U - ${\displaystyle 1}$ 8개$(\displaystyle\mathcal {U}} -1=8개$$)$ 늘어날 수 있습니다.

제한 사항

터널 코딩은 해석 조작 전에 알고리즘이 알파벳의 각 문자에 대한 확률 분포를 알아야 합니다.이 문제는 Huffman 코딩과 공유됩니다.

고정 길이 블록 출력이 필요하기 때문에 사전 기반 설계가 유사하지만 가변 크기 블록 출력이 ^{[clarification needed]}있는 Lempel-Ziv보다 작습니다.

레퍼런스