캐노니컬 허프만 코드

Canonical Huffman code

컴퓨터 과학 및 정보 이론에서 표준 허프만 코드는 매우 간결하게 기술할 수 있는 고유한 특성을 가진 허프만 코드의 특정 유형입니다.

데이터 압축기는 일반적으로 두 가지 방법 중 하나로 작동합니다.압축 해제기는 이전 컨텍스트에서 압축기가 사용한 코드북을 추론할 수 있거나 압축기가 압축 해제기에 코드북이 무엇인지 알려야 합니다.표준 Huffman 코드북은 특히 효율적으로 저장할 수 있기 때문에 대부분의 압축기는 "일반" Huffman 코드북을 생성한 후 사용하기 전에 표준 Huffman으로 변환합니다.

허프만 코드 등의 심볼 코드 스킴이 압축 해제되기 위해서는 소스 데이터를 압축하기 위해 사용되는 부호화 알고리즘과 동일한 모델이 복호화 알고리즘에 제공되어 부호화 데이터의 압축 해제에 사용할 수 있어야 한다.표준 Huffman 코딩에서 이 모델은 가변 길이 코드의 트리의 형태를 취하며, 가장 빈번한 기호가 구조의 상단에 위치하며 가장 적은 비트로 표시됩니다.

그러나 이 코드 트리는 코딩 방식의 구현에 두 가지 중요한 비효율성을 초래합니다.먼저 트리의 각 노드는 하위 노드에 대한 참조 또는 그것이 나타내는 기호를 저장해야 합니다.이는 메모리 사용 비용이 많이 들고 소스 데이터에 고유 기호의 비율이 높을 경우 코드 트리의 크기가 전체 인코딩 데이터의 상당량을 차지할 수 있습니다.둘째, 트리를 통과하는 것은 알고리즘이 부호화 데이터의 각 비트를 읽을 때 메모리 내의 구조를 랜덤으로 통과해야 하기 때문에 계산 비용이 많이 듭니다.

Canical Huffman 코드는 명확한 표준화된 형식으로 코드를 생성함으로써 이러한 두 가지 문제를 해결합니다. 주어진 길이의 모든 코드는 순차적으로 값을 할당합니다.즉, 압축을 해제하기 위해 코드 트리의 구조를 저장하는 대신 코드 길이만 필요하므로 인코딩된 데이터의 크기가 줄어듭니다.또, 코드가 순차적이기 때문에, 복호화 알고리즘을 극적으로 간략화할 수 있어 계산 효율이 높다.

알고리즘.

일반 Huffman 부호화 알고리즘은 알파벳의 모든 기호에 가변 길이 코드를 할당합니다.자주 사용되는 기호에는 더 짧은 코드가 할당됩니다.예를 들어 다음과 같은 비표준 코드북이 있다고 가정합니다.

A = 11 B = 0 C = 101 D = 100

여기서 문자 A는 2비트, B는 1비트, C와 D는 모두 3비트가 할당되어 있습니다.코드를 표준 Huffman 코드로 만들기 위해 코드를 다시 번호가 매겨집니다.비트길이는 동일하게 유지되며 코드북은 처음에는 코드워드 길이로 정렬되고 다음으로 알파벳 으로 정렬됩니다.

B = 0 A = 11 C = 101 D = 100

기존의 각 코드는 다음 알고리즘을 사용하여 같은 길이의 새로운 코드로 대체됩니다.

  • 목록의 첫 번째 기호에는 기호의 원래 코드워드와 길이가 같지만 모두 0인 코드워드가 할당됩니다.이것은 종종 단일 0('0')이 됩니다.
  • 이후의 각 기호에는 다음 이진수가 순서대로 할당되어 항상 다음 코드의 값이 높아지도록 합니다.
  • 더 긴 코드워드에 도달한 증가하면 새 코드워드의 길이가 이전 코드워드의 길이와 같아질 때까지 0을 추가합니다.이것은 좌회전이라고 생각할 수 있습니다.

이 세 가지 규칙을 따름으로써 생성되는 코드북의 정식 버전은 다음과 같습니다.

B = 0 A = 10 C = 110 D = 111

소수 2진수로서

표준 코드워드에 대한 또 다른 관점은 특정 시리즈의 이진 표현에서 기수점(이진 소수점)을 지나는 숫자라는 것입니다.구체적으로, 코드워드의 길이가 l1... l이라고n 가정합니다. 그러면 기호 i의 표준 코드워드는 이진 표현에서 기수 점을 지나치는 첫 번째i l 이진 숫자입니다.

크래프트의 부등식에 비추어 볼 때 이 관점은 특히 유용합니다. 이 부등식은 위의 합계가 항상 1보다 작거나 같을 것이라는 것입니다(길이 프리픽스 코드로부터 나오기 때문입니다).이는 위의 알고리즘에 1을 추가하는 것이 오버플로가 되지 않고 의도한 것보다 긴 코드워드가 작성됨을 나타냅니다.

코드북 인코딩

표준 Huffman 트리의 장점은 임의의 트리보다 적은 비트로 인코딩할 수 있다는 것입니다.

오리지널 Huffman 코드북을 보겠습니다.

A = 11 B = 0 C = 101 D = 100

이 허프만 트리를 부호화할 수 있는 방법은 여러 가지가 있습니다.예를 들어, 각 기호 다음에 비트 수와 코드를 쓸 있습니다.

('A', 2,11', ''B', 1,0', ''C', 3,101', ''D', 3,100')

알파벳 순으로 기호를 나열하기 때문에 기호 자체를 생략하고 비트 수코드 수만 나열할 수 있습니다.

(2,11), (1,0), (3,101), (3,100)

표준 버전에서는 기호가 알파벳 순서로 순차적으로 배열되어 있으며, 이후 코드가 이전 코드보다 항상 값이 높다는 것을 알고 있습니다.송신할 수 있는 부분은 각 기호의 비트 길이(비트 수)뿐입니다.표준 Huffman 트리는 항상 긴 비트 길이에 대해 더 높은 값을 가지며 동일한 비트 길이(C D)의 모든 기호에는 더 높은 코드 값이 있습니다.

A = 10 (코드값: 10진수 2개, 비트: 2) B = 0 (코드값: 0 소수, 비트: 1) C = 110 (코드값: 6 소수, 비트: 3) D = 111 (코드값: 7 소수, 비트: 3)

제약 조건의 3분의 2가 알려져 있으므로 각 기호의 비트 수만 전송하면 됩니다.

2, 1, 3, 3

표준 Huffman 알고리즘에 대한 지식이 있으면 비트 길이에서만 전체 테이블(심볼 및 코드 값)을 다시 만들 수 있습니다.사용되지 않는 심볼은 일반적으로 비트 길이가 0인 것으로 전송됩니다.

코드북을 표현하는 또 다른 효율적인 방법은 모든 기호를 비트 길이에 따라 오름차순으로 나열하고 각 비트 길이에 대한 기호 수를 기록하는 것입니다.상기의 예에서는, 부호화는 다음과 같이 됩니다.

(1,1,2), ('B', 'A', 'C', 'D')

즉, 첫 번째 기호 B는 길이 1이고, 그 다음 A는 길이 2이며, 나머지 기호 B는 길이 3입니다.기호는 비트 길이로 정렬되어 있기 때문에 효율적으로 코드북을 재구성할 수 있습니다.재구성을 기술하는 의사 코드가 다음 섹션에 도입된다.

이러한 유형의 부호화는 알파벳의 일부 기호만 압축하는 경우에 유용합니다.예를 들어 코드북에 C, O, D E가 각각 길이 2인 4글자만 포함되어 있다고 가정합니다.이전 방법을 사용하여 문자 O를 나타내려면 많은 0을 추가해야 합니다.

0, 0, 2, 2, 2, 0, ... , 2, ... 

어떤 글자를 썼는지 적어주세요.어느 쪽이든 설명이 다음보다 길어집니다.

(0,4), ('C', 'O', 'D', 'E')

JPEG 파일 교환 포맷은 이 인코딩 방법을 사용합니다. 왜냐하면 크기가 256인 8비트 알파벳 중 최대 162개의 기호만 코드북에 포함되기 때문입니다.

유사 코드

비트 길이로 정렬된 기호 목록을 지정하면 다음 의사 코드는 표준 Huffman 코드 북을 인쇄합니다.

코드 : = 0 이지만 더 많은 기호가 기호를 인쇄합니다. 코드 : = (코드 + 1) < (다음 기호의 비트 길이) - (현재 비트 길이)


알고리즘 계산 허프만 코드 입력됩니다: 메시지 앙상블(메시지, 확률) 세트).기본 D. 출력: 코드 앙상블(메시지, 코드) 세트).1-확률 감소에 따라 메시지 앙상블을 정렬합니다. 2-N은 메시지 앙상블의 기본(다른 메시지의 수)입니다.3- 정수 0  (\ 2D (-  0/ ( -) 등의  n style ( 합니다.선택한 메시지를 복합 메시지에 따라 변환한 후 다시 정렬합니다. 6 - 메시지가 여러 개 남아 있는 동안 8.7 - 가장 가능성이 낮은 D개의 메시지를 선택하고 각 메시지에 숫자 코드를 할당합니다.8 - 선택한 메시지를 가능성을 합한 복합 메시지로 대체하고 다시 정렬합니다. 9 - 각 메시지의 코드는 삽입된 집합의 코드 디짓의 연결로 지정됩니다. 

[1] [2]

레퍼런스

  1. ^ 이 알고리즘은 "A Method for the Construction of Minimum-Redundancy Codes" David A에서 설명되어 있습니다.허프먼, I.R.E. 의사록입니다
  2. ^ 기가바이트 관리: 단어 사전의 표준 허프만 코드를 구현한 책.