허프만 부호화

Huffman coding
"이것은 허프만 트리의 예입니다."라는 텍스트의 정확한 주파수에서 생성된 허프만 트리입니다.각 문자의 빈도와 코드는 다음과 같습니다.이 코드를 사용하여 문장을 인코딩하려면 8(또는 5)비트의 36자가 사용된 288(또는 180)비트가 아닌 135(또는 147)비트가 필요합니다.(이것은, 코드 트리 구조가 디코더에 인식되고 있기 때문에, 송신 정보의 일부로서 카운트 할 필요가 없는 것을 전제로 하고 있습니다).
문자 프라크 코드
공간 7 111
a 4 010
e 4 000
f 3 1101
h 2 1010
i 2 1000
m 2 0111
n 2 0010
s 2 1011
t 2 0110
l 1 11001
o 1 00110
p 1 10011
r 1 11000
u 1 00111
x 1 10010

컴퓨터 과학 및 정보 이론에서 허프만 코드무손실 데이터 압축에 일반적으로 사용되는 최적의 접두사 코드입니다.이러한 코드를 찾거나 사용하는 과정은 David A에 의해 개발된 알고리즘인 Huffman coding을 통해 진행됩니다. 허프먼은 MIT에서 박사과정을 밟으며 1952년 논문 '최소 용장성 코드 구축 방법'에 발표했다.[1]

Huffman 알고리즘의 출력은 소스 기호(파일 내의 문자 등)를 인코딩하기 위한 가변 길이 코드 테이블로 볼 수 있습니다.알고리즘은 소스 기호의 각 가능한 값에 대한 추정된 발생 확률 또는 빈도(무게)에서 이 표를 도출합니다.다른 엔트로피 부호화 방법과 마찬가지로, 일반적으로 보다 일반적인 심볼은 보다 적은 비트를 사용하여 표현된다.Huffman의 방법은 효율적으로 구현될 수 있으며, 이러한 가중치가 [2]정렬되면 입력 가중치 수에 선형인 코드를 시간 에 찾을 수 있다.그러나 기호를 별도로 인코딩하는 방법에서는 최적이지만, Huffman 부호화가 모든 압축 방법에서는 항상 최적이지는 않다. 더 나은 압축비가 필요할 경우 산술[3] 부호화 또는 비대칭 숫자 시스템으로[4] 대체된다.

역사

1951년, 데이비드 A. 허프만MIT 정보이론 급우들은 학기말 논문과 기말고사 중 하나를 선택할 수 있었다.교수님, 로버트 M. 파노, 가장 효율적인 바이너리 코드를 찾는 문제에 대한 학기 논문을 배정받았습니다.어떤 코드도 가장 효율적이라는 것을 증명할 수 없었던 허프만은 포기하고 기말고사 공부를 시작하려다 주파수 정렬 이진 트리를 사용하는 아이디어를 떠올렸고 이 방법이 가장 [5]효율적이라는 것을 재빨리 증명했다.

그렇게 함으로써, 허프만은 비슷한 코드를 개발하기 위해 클로드 섀넌과 함께 일했던 파노를 능가했다.Shannon-Fano 코딩의 하향식 접근 방식과는 달리 트리를 아래에서 위로 구축하면 최적성이 보장됩니다.

용어.

허프만 부호화는 각 심볼에 대한 표현을 선택하기 위해 특정 방법을 사용하여 프리픽스 코드('프리픽스 프리 코드'라고도 함)를 생성합니다.즉, 특정 심볼을 나타내는 비트 문자열은 다른 심볼을 나타내는 비트 문자열의 프리픽스가 아닙니다.허프만 부호화는 프리픽스 코드를 만드는 매우 광범위한 방법이어서 "허프만 코드"라는 용어는 허프만의 알고리즘에 의해 생성되지 않은 경우에도 "프리픽스 코드"의 동의어로 널리 사용된다.

문제의 정의

허프만 트리 구성

비공식적인 설명

정해진
기호 집합 및 가중치(일반적으로 확률에 비례함)입니다.
검색
예상되는 코드워드 길이가 최소인 프리픽스 프리 바이너리 코드(코드워드의 세트)입니다(따라서 루트로부터의 최소 가중 패스 길이를 가지는 트리).

형식화된 설명

입력.
A ( , , , ){ A = ( a {1 , 2} , \ , a _ { n}은 크기n { n의 기호 알파벳입니다.
W ( , 2, ...,w ) { W = ( _ {1} ,_ {2} , \ , w { }는 (일반적으로 확률에 비례하는) 기호 가중치의 튜플입니다. 즉, ) , 1 , 1 display ,.를 클릭합니다.

출력.
C (W ) ( , , ,n ) { \( W \ right ) = ( _ { , c _ 2 , \ , _ { } i 의 코드워드입니다

이에요.
( ( ) 길이 ( i){ L ( \( W \ ) = \ _ i=}{ }{ _ } \{ } \ left ( i }\ ) 의 길이 에 가중치를 부여합니다 L(Wright T( Tright에 대해 지정합니다.

우리는 5개의 문자와 주어진 가중치를 가진 코드에 대한 Huffman 코딩 결과의 예를 제공한다.모든 코드에 걸쳐 L을 최소화하는지 검증하지 않지만 L을 계산하여 주어진 가중치 세트의 섀넌 엔트로피 H와 비교한다. 결과는 거의 최적이다.

입력(A, W) 기호(ai) a b c d e
중량(wi) 0.10 0.15 0.30 0.16 0.29 = 1
출력 C 코드워드(ci) 010 011 11 00 10
코드워드 길이(비트)
(li)
3 3 2 2 2
가중 경로 길이에 대한 기여
(lwii)
0.30 0.45 0.60 0.32 0.58 L(C) = 2.25
최적성 확률 예산
(2li)
1/8 1/8 1/4 1/4 1/4 = 1.00
정보 내용(비트 단위)
(-log2i w)
3.32 2.74 1.74 2.64 1.79
엔트로피에 대한 기여
(-wi2 로그i w)
0.332 0.411 0.521 0.423 0.518 H(A) = 2.199

바이유니크한 코드의 경우, 즉 코드는 고유하게 디코딩할 수 있으며, 모든 심볼에 걸친 확률 버젯의 합계는 항상 1보다 작거나 같습니다.이 예에서는 합계가 1과 완전히 같기 때문에 코드는 완전한 코드라고 불립니다.그렇지 않은 경우, 코드를 완전하면서도 고유하게 만들기 위해 추가 기호(관련된 null 확률 포함)를 추가함으로써 항상 동등한 코드를 도출할 수 있습니다.

Shannon(1948)의해 정의된 바와 같이, null이 아닌 확률을 갖는i 각 기호 a의 정보 내용 h(비트 단위)는 다음과 같습니다.

엔트로피 H(비트 단위)는 0이 아닌 확률 w의 모든 기호i a에 걸쳐i 각 기호의 정보 내용에 대한 가중치 합입니다.

(주: 이 0인 심볼은 w→ 0 + 2) 0 { style _ { 00}이므로 단순성을 위해 확률이 0인 심볼은 위의 공식에서 제외할 수 있습니다.)

섀넌의 소스 코딩 정리의 결과로, 엔트로피는 이론적으로 연관된 가중치를 가진 주어진 알파벳에 가능한 가장 작은 코드워드 길이의 측정값이다.이 예에서 가중 평균 코드워드 길이는 기호당 2.25비트로 계산된 엔트로피(2.205비트)보다 약간 큽니다.따라서 이 코드는 다른 어떤 실행 가능한 코드도 더 나은 성능을 발휘하지 못한다는 점에서 최적일 뿐만 아니라 Shannon이 설정한 이론적 한계에 매우 가깝습니다.

일반적으로 Huffman 코드는 고유할 필요가 없습니다.따라서 특정 확률 분포에 대한 Huffman 코드 세트는 해당 확률 분포에 대한 L L 하는 코드의 서브셋이 비어 있지 않습니다.(단, 코드워드의 길이를 최소화하는 각 할당에는 그 길이를 가진 허프만 코드가 적어도1개 존재합니다).

기본 기술

압축

"A_DEAD_DAD_CED_A_B" 메시지를 인코딩하기 위한 Huffman 코딩 사용 시각화AD_BABE_A_BEADED_아바카_
BED」스텝 2~6에서는 빈도를 높여 문자를 정렬하고, 각 스텝의 빈도가 가장 낮은 2개를 조합하여 리스트에 재삽입하여 부분 트리를 구축한다.스텝 6의 마지막 트리는 스텝7의 사전을 생성하기 위해 트래버스 됩니다.스텝 8에서는 메시지를 부호화하기 위해 사용합니다.
소스는 4개의 다른 기호 1,, a, { )를 생성합니다.확률 4 ; 0. 0.; {4 0. ; 0. ; 0.05)는 왼쪽 트리에서 생성됩니다.두 기호의 합과 같은 확률을 갖는 등가 기호.이 과정은 하나의 기호만 있을 때까지 반복됩니다.그런 다음 트리를 오른쪽에서 왼쪽으로 거꾸로 읽을 수 있으며 서로 다른 비트를 서로 다른 분기에 할당할 수 있습니다.최종 Huffman 코드는 다음과 같습니다.
기호. 코드
a1 0
a2 10
a3 110
a4 111
4개의 기호로 구성된 신호를 표현하는 표준 방법은 2비트/심볼을 사용하는 것이지만 소스의 엔트로피는 1.74비트/심볼입니다.이 Huffman 코드를 사용하여 신호를 나타낼 경우 평균 길이는 1.85비트/심볼로 낮아집니다.기호의 확률은 2의 음의 거듭제곱과 다르기 때문에 이론적인 한계와는 거리가 멀기 때문입니다.

이 기술은 노드의 바이너리 트리를 생성하여 작동합니다.이러한 노드는 기호 에 따라 크기가 달라지는 일반 에 저장할 수 있습니다(n n 노드는 리프 노드 또는 내부 노드 중 하나입니다.처음에 모든 노드는 리프 노드이며 심볼 자체, 심볼의 무게(출현 빈도) 및 선택적으로 리프 노드에서 시작하는 코드를 읽기 쉽게 하는 부모 노드에 대한 링크를 포함한다.내부 노드에는 가중치, 2개의 자식 노드에 대한 링크 및 부모 노드에 대한 옵션 링크가 포함됩니다.일반적으로 비트 '0'은 왼쪽 아이를 따르고 비트 '1'은 오른쪽 아이를 따릅니다.완성된 트리에는 n개의 노드가 있습니다사용되지 않는 기호를 생략한 Huffman 트리는 최적의 코드 길이를 생성합니다.

프로세스는 리프 노드가 나타내는 기호의 확률을 포함하는 리프 노드에서 시작됩니다.그런 다음 이 프로세스는 가장 낮은 확률로 두 개의 노드를 가져와서 이 두 개의 노드를 자녀로 가진 새로운 내부 노드를 만듭니다.새 노드의 무게는 하위 노드의 무게 합계로 설정됩니다.그런 다음 프로세스를 새 내부 노드와 나머지 노드(즉, 두 리프 노드 제외)에 다시 적용하고, Huffman 트리의 루트인 노드가 하나만 남을 때까지 이 프로세스를 반복합니다.

가장 단순한 구축 알고리즘에서는 priority 큐를 사용합니다.이 큐에서는 확률이 가장 낮은 노드에 가장 높은 priority가 부여됩니다.

  1. 기호별로 리프 노드를 생성하여 priority 큐에 추가합니다.
  2. 큐에 노드가 여러 개 있는 경우:
    1. 큐에서 priority가 가장 높은 노드(최저 확률)를 2개 삭제합니다.
    2. 이들 2개의 노드를 자녀로서 2개의 노드의 확률 합계와 같은 확률로 새로운 내부 노드를 작성합니다.
    3. 큐에 새 노드를 추가합니다.
  3. 나머지 노드는 루트 노드이며 트리는 완성됩니다.

효율적인 priority 큐 데이터 구조는 삽입당 O(log n) 시간을 필요로 하며 n개의 리프가 있는 트리는 2n-1개의 노드를 가지므로 이 알고리즘은 O(n log n) 시간으로 동작합니다.여기서 n은 심볼 수입니다.

기호가 확률에 따라 정렬되면 두 의 큐를 사용하여 Huffman 트리를 만드는 선형 시간(O(n) 방법이 있습니다. 첫 번째 큐는 초기 가중치(관련된 리프 포인터와 함께)를 포함하며 결합된 가중치(트리에 대한 포인터와 함께)는 두 번째 큐의 뒤쪽에 배치됩니다.이렇게 하면 최소 가중치가 항상 다음 2개의 큐 중 하나의 전면에 유지됩니다.

  1. 기호 수만큼 잎부터 시작하세요.
  2. 모든 리프 노드를 첫 번째 큐에 큐잉합니다(확률적으로 가장 가능성이 낮은 항목이 큐의 선두에 오름차순 배치됩니다).
  3. 큐에 노드가 여러 개 있는 경우:
    1. 양쪽 큐의 전면을 조사하여 무게가 가장 작은2개의 노드를 큐에서 제외합니다.
    2. 방금 제거된 2개의 노드를 자녀(어느 노드든 자녀 노드일 수 있음)로 하고 가중치의 합계를 새 가중치로 하여 새 내부 노드를 만듭니다.
    3. 새 노드를 두 번째 큐의 후면에 큐잉합니다.
  4. 나머지 노드는 루트노드로 트리가 생성되었습니다.

Huffman 트리가 생성되면 다음과 같이 기호를 바이너리 코드에 매핑하는 사전을 생성하기 위해 트리를 통과합니다.

  1. 루트로 설정된 현재 노드부터 시작합니다.
  2. 노드가 리프 노드가 아닌 경우 왼쪽 아이에 가장자리를 0으로, 오른쪽 아이에 가장자리를 1로 라벨링합니다.왼쪽 아이와 오른쪽 아이 모두에서 이 과정을 반복합니다.

그런 다음 루트 노드에서 심볼까지의 경로를 따라 에지의 라벨을 연결하여 심볼의 최종 인코딩을 읽습니다.

대부분의 경우 알고리즘 선택에 있어서 시간 복잡도는 그다지 중요하지 않습니다.여기서 n은 알파벳의 기호 수이며, 보통 매우 작은 숫자(인코딩되는 메시지의 길이에 비해)이기 때문입니다.복잡도 분석은 n이 매우 커졌을 의 동작에 관한 것입니다.

일반적으로 코드워드 길이의 편차를 최소화하는 것이 좋습니다.예를 들어, 특히 트리가 불균형한 경우, 허프만 부호화 데이터를 수신하는 통신 버퍼는 특히 긴 심볼을 처리하기 위해 더 커야 할 수 있다.편차를 최소화하려면 첫 번째 큐에서 항목을 선택하여 큐 간의 연결을 끊기만 하면 됩니다.이 수정은 분산을 최소화하고 가장 긴 문자 코드의 길이를 최소화하면서 Huffman 코딩의 수학적 최적성을 유지합니다.

감압

일반적으로 압축 해제 프로세스는 프리픽스 코드의 스트림을 개별 바이트 값으로 변환하는 문제이며, 보통 입력 스트림에서 각 비트가 읽힐 때 노드별로 허프만 트리 노드를 통과함으로써(리프 노드에 도달하면 특정 바이트 값의 검색이 반드시 종료됩니다).그러나, 이 일이 일어나기 전에, 허프만 트리는 어떻게든 재건되어야 한다.문자 빈도가 상당히 예측 가능한 가장 단순한 경우, 트리는 사전 구성(및 각 압축 사이클에서 통계적으로 조정됨)될 수 있으며, 따라서 최소한 압축 효율의 일부 측정값을 희생시키면서 매번 재사용될 수 있습니다.그렇지 않으면 트리를 재구성하기 위한 정보를 먼저 전송해야 합니다.간단한 접근법은 각 문자의 주파수 카운트를 압축 스트림에 추가하는 것입니다.안타깝게도 이러한 경우 오버헤드는 몇 킬로바이트에 달할 수 있으므로 이 방법은 실용성이 거의 없습니다.표준 부호화를 사용하여 데이터를 압축하는 경우, 2B style B 2^{ 비트의 만으로 압축 모델을 정밀하게 재구성할 수 있습니다(여기서 B는 기호당 비트 수).다른 방법은 출력 스트림에 Huffman 트리를 하나씩 추가하는 것입니다.예를 들어 값 0이 부모 노드를 나타내고 1이 리프 노드를 나타낸다고 가정하면 트리 구축 루틴이 발견될 때마다 다음 8비트를 읽어 특정 리프 문자 값을 결정합니다.프로세스는 마지막 리프 노드에 도달할 때까지 반복적으로 계속됩니다.그 시점에서 Huffman 트리는 충실하게 재구성됩니다.이러한 방식을 사용하는 오버헤드는 약 2 ~320바이트(8비트 알파벳을 상정)입니다.다른 많은 기술들도 가능하다.어떤 경우에도 압축된 데이터는 사용되지 않는 "트레이킹 비트"를 포함할 수 있으므로 압축 해제기는 출력 생성을 중지할 시기를 결정할 수 있어야 합니다.이는 압축 모델과 함께 압축 해제된 데이터의 길이를 전송하거나 입력의 끝을 나타내는 특수 코드 기호를 정의함으로써 달성할 수 있습니다(단, 후자의 방법은 코드 길이의 최적성에 악영향을 미칠 수 있습니다).

주요 속성

사용되는 확률은 평균 경험을 기반으로 한 애플리케이션 도메인에 대한 일반 확률이거나 압축 중인 텍스트에서 발견된 실제 빈도가 될 수 있습니다.를 위해서는 주파수 테이블을 압축 텍스트와 함께 저장해야 합니다.이 목적을 위해 사용되는 다양한 기술에 대한 자세한 내용은 위의 압축 해제 섹션을 참조하십시오.

최적성

Huffman의 원래 알고리즘은 알려진 입력 확률 분포를 가진 기호별 부호화, 즉 그러한 데이터 스트림에서 관련 없는 기호를 별도로 부호화하는 데 최적이다.그러나 기호별 제한이 삭제되거나 확률 질량 함수를 알 수 없는 경우에는 최적이 아닙니다.또한 기호가 독립적이지 않고 동일한 분포를 보이는 경우 최적성을 위해 단일 코드가 충분하지 않을 수 있습니다.산술 코딩과 같은 다른 방법은 압축 기능이 더 좋은 경우가 많습니다.

앞서 언급한 두 방법 모두 보다 효율적인 부호화를 위해 임의의 수의 기호를 조합할 수 있고 일반적으로 실제 입력 통계에 적응할 수 있지만, 산술 부호화는 계산 또는 알고리즘의 복잡성을 크게 증가시키지 않고 그렇게 한다(단순한 버전은 허프만 부호화보다 느리고 복잡함).이러한 유연성은 입력 확률이 정확하게 알려져 있지 않거나 스트림 내에서 크게 다를 때 특히 유용합니다.그러나 Huffman 코딩은 일반적으로 더 빠르며 산술 코딩은 역사적으로 특허 문제에 대한 우려의 대상이었다.따라서 많은 기술은 역사적으로 Huffman 및 기타 프리픽스 부호화 기술을 위해 산술 부호화를 회피해 왔습니다.2010년 중반 현재, 허프만 코딩의 대안으로 가장 일반적으로 사용되는 기술은 초기 특허가 만료됨에 따라 공공 영역으로 넘어갔습니다.

균일한 확률 분포와 2의 거듭제곱인 멤버의 수에 대해 허프만 부호화는 예를 들어 ASCII 부호화와 같은 단순한 바이너리 블록 부호화와 동등하다.이는 이러한 입력으로는 압축이 불가능하다는 사실을 반영합니다. 즉, 데이터에 아무것도 하지 않는 것이 최선의 방법입니다.

허프만 부호화는 각 입력 기호가 쌍방향 확률을 갖는 알려진 독립적이고 동일한 분포 랜덤 변수인 경우에 모든 방법 중에서 최적이다.프리픽스 코드, 특히 Huffman 부호화는 작은 알파벳에서는 비효율적인 경향이 있으며, 여기서 종종 이러한 최적(다이아딕) 포인트 사이에 확률이 있습니다.가장 가능성이 높은 기호의 확률이 2 = 0.5를 훨씬−1 초과하여 비효율의 상한을 제한하지 않는 경우 허프만 부호화의 최악의 경우가 발생할 수 있습니다.

Huffman 코딩을 사용하면서도 이 특별한 비효율성을 회피하기 위한 두 가지 접근법이 있습니다.고정된 수의 기호를 함께 결합하면("차단") 압축이 증가하거나 감소하지 않는 경우가 많습니다.블록의 크기가 무한대에 가까워짐에 따라 이론적으로 Huffman 부호화는 엔트로피 한계, 즉 최적의 [6]압축에 근접한다.그러나 허프만 부호의 복잡도는 부호화 가능 수, 즉 블록 크기에서 기하급수적인 수의 선형이기 때문에 임의의 대규모 심볼 그룹을 차단하는 것은 실용적이지 않다.이를 통해 실제로 수행되는 차단의 양이 제한됩니다.

널리 사용되는 실용적인 대안은 런렝스 부호화입니다.이 기술은 엔트로피 부호화보다 한 단계 먼저 추가되며, 특히 반복된 기호의 카운트(실행)가 부호화됩니다.베르누이 프로세스의 단순한 경우, Golomb 코딩은 실행 길이를 코딩하기 위한 프리픽스 코드 중에서 최적이며, 이는 Huffman [7]코딩 기법을 통해 입증되었다.변경된 Huffman 부호화를 사용하는 팩스기에서도 같은 접근방식이 취해지고 있습니다.그러나 런타임 코딩은 다른 압축 기술만큼 많은 입력 유형에 적응할 수 없습니다.

바리에이션

허프만 부호화에는 많은 종류가 있으며,[8] 그 중 일부는 허프만과 같은 알고리즘을 사용하며, 다른 일부는 최적의 프리픽스 코드를 찾습니다(출력에 다른 제한을 가하는 등).후자의 경우 방법은 허프만과 같을 필요가 없으며, 실제로 다항식 시간이 될 필요도 없습니다.

n-ary Huffman 부호화

n-ary Huffman 알고리즘은 {0, 1, ..., n - 1) 알파벳을 사용하여 메시지를 인코딩하고 n-ary 트리를 만듭니다.이 접근방식은 Huffman이 원본 논문에서 고려했습니다.2진수( { n 코드와 동일한 알고리즘이 적용됩니다.단, n개의 가장 가능성이 낮은 기호는 단순히 2개의 가장 가능성이 낮은 기호가 아니라 함께 수집됩니다.n이 2보다 클 경우 모든 소스 워드가 허프만 부호화를 위한 n-ary 트리를 적절하게 형성할 수 있는 것은 아닙니다.이 경우, 0-확률 자리 표시자를 추가해야 합니다.이는 트리가 n 대 1의 청부업자를 형성해야 하기 때문입니다.바이너리 코딩의 경우 이는 2 대 1의 청부업자이며, 모든 크기의 집합이 이러한 청부업자를 형성할 수 있습니다.소스 워드의 수가 1 modulo n-1과 일치할 경우 소스 워드의 세트는 적절한 Huffman 트리를 형성합니다.

적응형 허프만 부호화

적응형 허프만 부호화라고 불리는 변형은 소스 기호 시퀀스의 최근 실제 주파수를 기반으로 동적으로 확률을 계산하고 업데이트된 확률 추정치에 일치하도록 부호화 트리 구조를 변경하는 것을 포함합니다.트리의 갱신 코스트에 의해서, 보다 유연성이 높고 압축성이 뛰어난 최적화된 적응형 산술 부호화보다 속도가 느려지기 때문에, 실제로는 거의 사용되지 않습니다.

허프만 템플릿 알고리즘

대부분의 경우, Huffman 코딩 구현에 사용되는 가중치는 수치 확률을 나타내지만, 위에 제시된 알고리즘은 이를 요구하지 않는다. 가중치가 가중치를 정렬하고 추가하는 방법을 의미하는 완전히 순서가 매겨진 교환 모노이드를 형성해야 한다.Huffman 템플릿알고리즘을 사용하면 모든 종류의 가중치(비용, 주파수, 가중치 쌍, 비수치 가중치)와 많은 조합 방법 중 하나를 사용할 수 있습니다(더하기뿐만 아니라).이러한 알고리즘은 회선 설계에 최초로 적용되는 [ + e g (c i )\ \_ { } \ [ w { } + \ { \ ( c { } \ 등의 최소화 문제를 해결할 수 있습니다.

길이 제한 허프만 부호화/최소 분산 허프만 부호화

길이 제한 허프만 부호화는 최소 가중 경로 길이를 달성하는 것이 목표이지만, 각 코드 워드의 길이가 주어진 상수보다 작아야 한다는 추가적인 제한이 있습니다.패키지 머지 알고리즘은 Huffman 알고리즘에 의해 사용되는 것과 매우 유사한 단순한 탐욕적 접근법으로 이 문제를 해결합니다.시간 복잡도는 OL O입니다.서 L L 코드 워드의 최대 길이입니다.기존의 Huffman 문제와는 달리 O O O logn O n시간 에 이 문제를 해결할 수 있는 알고리즘은 없습니다.

동일하지 않은 문자 비용으로 허프만 부호화

표준 Huffman 부호화 문제에서는 코드 워드가 구성된 세트 내의 각 심볼은 전송 비용이 동일하다고 가정합니다. 길이가 N자리인 코드 워드는 그 중 몇 자리수가 0인지, 몇 자리수가 1인지 등에 관계없이 항상 N의 비용이 발생합니다.이 전제 하에 작업할 경우 메시지의 총 비용을 최소화하는 것과 총 자리 수를 최소화하는 것은 동일합니다.

문자 코스트가 같지 않은 허프만 부호화는 이러한 가정 없이 일반화됩니다. 부호화 알파벳의 문자는 전송 매체의 특성에 따라 길이가 균일하지 않을 수 있습니다.예를 들어, Morse 코드의 부호화 알파벳은, 「닷」보다 「대시」의 송신에 시간이 걸리기 때문에, 송신 시간의 대시 코스트가 높아집니다.목표는 여전히 가중 평균 코드워드 길이를 최소화하는 것이지만 메시지에 사용되는 기호 수를 최소화하는 것만으로는 충분하지 않습니다.Golin에 의해 정수비용의 경우, Karp에 의해 해결되었지만, 기존의 Huffman 코딩과 같은 방식으로 또는 같은 효율로 이것을 해결할 수 있는 알고리즘은 없다.

최적의 알파벳 이진 트리(Hu-Tucker 부호화)

표준 Huffman 부호화 문제에서는 임의의 코드워드가 임의의 입력 심볼에 대응한다고 가정합니다.알파벳 버전에서는 입력과 출력의 알파벳 순서가 같아야 합니다.따라서 를 들어 A { , , c { A \\ { a ,, c \right \ } { , , 01 { H \, C \ right ) \ left { , 01 \ right \}는 할당할 수 없습니다. 또는 ( ) { , , { H \ ( , \ )= \ \ { 0 , ,\} 。이 문제는 T. C. HuAlan Tucker의 이름을 따서 Hu-Tucker 문제로도 알려져 있습니다.이 문제는 최적의 바이너리 알파벳 [9]문제에 대한 의 O logn O n 시간 솔루션을 제시하며 Hu-Tucker의 변형은 아닙니다.이후 방법인 가르시아-Adriano Garsia와 Michelle L.의 Wachs 알고리즘. Wachs(1977)는 단순한 논리를 사용하여 동일한 총 시간 범위 내에서 동일한 비교를 수행합니다.이러한 최적의 알파벳 바이너리 트리[10]바이너리 검색 트리로 사용됩니다.

표준 허프만 코드

알파벳 순서로 정렬된 입력에 대응하는 가중치가 숫자 순서대로 있는 경우, Huffman 코드는 최적의 알파벳 코드와 동일한 길이를 가지며, 이러한 길이를 계산함으로써 Hu-Tucker 부호화를 불필요하게 만들 수 있습니다.숫자(재순서화된) 입력에서 발생하는 코드는 때때로 표준 Huffman 코드라고 불리며 인코딩/복호화가 용이하기 때문에 실제로 사용되는 코드이기도 합니다.이 코드를 찾는 기술은 허프만 부호화처럼 최적이지만 섀넌-파노 부호화처럼 무게 확률에서는 알파벳이기 때문에 허프만-샤논-파노 부호화라고 불리기도 한다.이 예에 대응하는 Huffman-Shannon-Fano 코드는 { 01 \{11이며 이 코드워드 길이도 원래의 솔루션과 동일합니다., 표준 Huffman 코드에서는 { { 01, 이 됩니다

적용들

산술 부호화와 허프만 부호화는 모든 기호가 1/2k 형식의 확률을 가질 때 엔트로피를 달성하는 동등한 결과를 생성합니다.다른 상황에서는 산술 부호화가 Huffman 부호화보다 더 나은 압축을 제공할 수 있는데, 이는 직감적으로 "코드 워드"가 효과적으로 정수 비트 길이를 가질 수 있는 반면 Huffman 코드와 같은 프리픽스 코드의 코드 워드는 정수 비트 수 밖에 없기 때문입니다.따라서 길이 k의 코드 워드는 확률 1/2의k 심볼에만 최적으로 일치하고 다른 확률은 최적으로 표현되지 않는다.반면 산술 부호화의 코드 워드의 길이는 심볼의 실제 확률과 정확하게 일치하도록 할 수 있다.이 차이는 알파벳 크기가 [citation needed]작을 때 특히 두드러집니다.

그럼에도 불구하고 프레픽스코드는 단순성, 고속성 및 특허 적용 범위 부족으로 널리 사용되고 있습니다.이들은 종종 다른 압축방식에 대한 "백엔드"로 사용됩니다.감압(PKZ)IP의 알고리즘) 및 JPEG 및 MP3같은 멀티미디어 코덱은 프런트 엔드 모델과 양자화 후에 프리픽스 코드의 사용이 있습니다.대부분의 애플리케이션이 허프만의 알고리즘을 사용해 설계된 코드가 아닌, 미리 정의된 가변 길이 코드를 사용하고 있어도, 이러한 코덱은 종종 「허프만 코드」라고 불립니다.

레퍼런스

  1. ^ Huffman, D. (1952). "A Method for the Construction of Minimum-Redundancy Codes" (PDF). Proceedings of the IRE. 40 (9): 1098–1101. doi:10.1109/JRPROC.1952.273898.
  2. ^ Van Leeuwen, Jan (1976). "On the construction of Huffman trees" (PDF). ICALP: 382–410. Retrieved 2014-02-20.
  3. ^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (2014-04-09). Fundamentals of Multimedia. Springer Science & Business Media. ISBN 978-3-319-05290-8.
  4. ^ J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, Huffman 코딩의 정확한 대체로서 비대칭 숫자 시스템을 사용한다, Picture Coding Symposium, 2015.
  5. ^ Huffman, Ken (1991). "Profile: David A. Huffman: Encoding the "Neatness" of Ones and Zeroes". Scientific American: 54–58.
  6. ^ Gribov, Alexander (2017-04-10). "Optimal Compression of a Polyline with Segments and Arcs". arXiv:1604.07476 [cs.CG].
  7. ^ Gallager, R.G.; van Voorhis, D.C. (1975). "Optimal source codes for geometrically distributed integer alphabets". IEEE Transactions on Information Theory. 21 (2): 228–230. doi:10.1109/TIT.1975.1055357.
  8. ^ Abrahams, J. (1997-06-11). Written at Arlington, VA, USA. Division of Mathematics, Computer & Information Sciences, Office of Naval Research (ONR). "Code and Parse Trees for Lossless Source Encoding". Compression and Complexity of Sequences 1997 Proceedings. Salerno: IEEE: 145–171. CiteSeerX 10.1.1.589.4726. doi:10.1109/SEQUEN.1997.666911. ISBN 0-8186-8132-2. S2CID 124587565.
  9. ^ Hu, T. C.; Tucker, A. C. (1971). "Optimal Computer Search Trees and Variable-Length Alphabetical Codes". SIAM Journal on Applied Mathematics. 21 (4): 514. doi:10.1137/0121057. JSTOR 2099603.
  10. ^ 역사 및 참고 문헌 목록, 페이지 453-454를 참조하십시오Knuth, Donald E. (1998), "Algorithm G (Garsia–Wachs algorithm for optimum binary trees)", The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Addison–Wesley, pp. 451–453.

참고 문헌

외부 링크