적응형 허프만 부호화

Adaptive Huffman coding

Adaptive Huffman 코딩(다이나믹 허프만 코딩이라고도 함)은 허프만 코딩에 기반한 적응형 코딩 기술입니다.소스 배포에 대한 초기 지식이 없는 상태에서 심볼이 전송될 때 코드를 빌드할 수 있으므로 데이터의 [1]변화하는 조건에 대한 원패스 인코딩 및 적응이 가능합니다.

원패스 프로시저의 장점은 송신 에러에 대한 민감도가 높아지지만, 송신원을 실시간으로 부호화할 수 있다는 것입니다.단 한 번의 손실이 코드 전체를 파괴하기 때문입니다.

알고리즘

이 방법에는 여러 가지 구현이 있으며 가장 주목할 만한 것은 FGK(Faller-Gallager-Knuth)와 Vitter 알고리즘입니다.

FGK 알고리즘

이것은 Huffman 코딩에 기반한 온라인 코딩 기술입니다.발생 빈도에 대한 초기 지식이 없기 때문에 데이터가 전송될 때 Huffman's Tree를 동적으로 조정할 수 있습니다.FGK Huffman 트리에서는 0-node라고 하는 특수한 외부 노드를 사용하여 새로운 문자를 식별합니다.즉, 새로운 데이터가 발견될 때마다 0-노드에 대한 경로를 출력한 후 데이터를 출력합니다.과거 캐릭터의 경우 현재 Huffman's 트리의 데이터 경로를 출력하기만 하면 됩니다.가장 중요한 것은 필요에 따라 FGK Huffman 트리를 조정하고 마지막으로 관련 노드의 빈도를 업데이트해야 한다는 것입니다.데이텀의 빈도가 높아짐에 따라 허프만 나무의 형제 특성이 파괴될 수 있다.이러한 이유로 조정이 트리거됩니다.노드, 서브트리, 또는 그 양쪽을 연속적으로 스왑함으로써 실현됩니다.데이터 노드는 Huffman's 트리에서 동일한 주파수의 최상위 노드(또는 최상위 노드에 루트된 하위 트리)와 스왑됩니다.노드의 모든 상위 노드도 동일한 방식으로 처리해야 합니다.

FGK 알고리즘에는 노드 또는 서브트리 스왑에 관한 몇 가지 단점이 있기 때문에 Vitter는 이를 개선하기 위한 다른 알고리즘을 제안했습니다.

비터 알고리즘

몇 가지 중요한 용어 및 제약사항:

  • 암묵적 번호부여 : 단순히 노드에는 레벨별, 왼쪽에서 오른쪽으로 번호가 매겨지는 것을 의미합니다.즉, 하위 레벨의 노드에는 상위 레벨의 노드에 비해 암묵적 번호가 낮고, 같은 레벨의 노드에는 왼쪽에서 오른쪽으로 번호가 매겨집니다.
  • [불변성] : 무게w마다 무게w의 모든 리프가 무게w의 모든 내부 노드 앞에 있습니다.
  • 블록 : 무게와 유형이 동일한 노드(리프 노드 또는 내부 노드)가 블록을 형성합니다.
  • 리더 : 블록 내에서 번호가 가장 높은 노드.

블록은 가중치의 차수를 늘려 서로 연결됩니다.

리프 블록은 항상 같은 무게의 내부 블록 앞에 있기 때문에 불변성을 유지합니다.

NYT(Not Yet Transfered)는 특수 노드이며 '아직 전송되지 않은' 기호를 나타내는 데 사용됩니다.

Slide_And_Increment(리프 노드) 슬라이드가 시작됩니다.P는 리프 노드입니다.
Slide_And_Increment(리프 노드) 슬라이딩 순서 2.P는 리프 노드이기 때문에 동일한 무게의 다음 블록 노드 앞으로 슬라이딩됩니다.
Slide_And_Increment(리프 노드) 슬라이딩 순서 3.여기서는 현재 무게를 1씩 늘립니다.
Slide_And_Increment(리프 노드) 슬라이딩 순서 4.방법은 끝이 난다.P가 새로운 부모입니다.
Slide_And_Increment(내부 노드) 슬라이드가 시작됩니다.P는 내부 노드입니다.
Slide_And_Increment(내부 노드) 슬라이딩 순서 2.노드 P는 중량 wt+1의 Leave 노드 블록 앞에 슬라이드합니다.
Slide_And_Increment(내부 노드) 슬라이딩 순서 3.이제 무게를 9로 늘립니다.따라서 현재 노드가 내부 노드이기 때문에 불변성이 유지되며 가중치를 높인 것과 동일한 무게의 리프 노드 앞에서 발생해야 합니다.
Slide_And_Increment(내부 노드) 슬라이딩 순서 4.이제 'P'는 이전 부모(알고리즘에 따른 내부 노드의 경우)를 가리킵니다.
기호를 추가하는 알고리즘은 리프 노드(p가 NYT인 경우)를 포함하는 리프 노드에 대한 leaf_to_null p:= 포인터입니다. 이 경우, (p가 NYT인 경우) 두 아이를 추가하여 p를 확장합니다. 왼쪽 아이는 새로운 NYT가 되고 오른쪽 아이는 새로운 심볼 리프 노드 p:= 새 리프 노드 leaf_to_node의 부모입니다.d of p의 경우 p를 블록의 선두와 스왑합니다(새로운 p가 NYT와 형제일 경우). leaf_to_increment : = p : = p의 부모(p null NULL)는 Slide_And_Increment(p null NULL)를 실행한 후 Slide_And_Increment(leaf_To_Increment!= NULL)를 실행합니다.
Slide_And_Increment(p)는 p의 p 이전_p := 부모(p는 내부 노드)인 경우 트리에서 wt + 1 가중치 p의 리프 노드보다 1p 증가:= previous_p 그렇지 않으면 트리에서 p의 내부 노드보다 1 가중치 증가p : = p의 새 부모.

인코더와 디코더는 최대 수를 가진 루트노드만으로 시작합니다.처음에는 초기 NYT 노드입니다.

NYT 기호를 전송할 때는 NYT 노드에 대한 코드를 전송하고 일반 코드를 전송해야 합니다.

트리에 이미 있는 모든 기호에 대해 리프 노드의 코드만 전송하면 됩니다.

예

Adaptive Huffman Vitter.jpg

abb를 인코딩하면 01100001 001100010 11이 됩니다.

순서 1:

빈 나무부터 시작합니다.

"a"의 경우 바이너리 코드를 전송합니다.

순서 2:

NYT는 254와 255의 2개의 자노드를 생성합니다.둘 다 웨이트0 입니다root의 무게를 255로 늘립니다.노드 255와 관련된 "a"의 코드는 1입니다.

"b" 전송 0(NYT 노드의 경우)의 경우 바이너리 코드입니다.

순서 3:

NYT는 2개의 자노드를 생성합니다.2개의 자노드는 NYT의 경우 252개, 리프 노드의 경우 253개입니다.둘 다 가중치가0 입니다253, 254 및 루트의 무게를 늘립니다.무게의 모든 잎 w가 무게 w의 모든 내부 노드 앞에 있는(암묵적인 번호부여에서) Vitter의 불변성을 유지하려면 노드 254로 시작하는 분기를 노드 255로 교환해야 합니다(번호순서는 교환하지 않음)."b"의 코드는 11입니다.

두 번째 "b"의 경우 11을 송신합니다.

설명을 쉽게 하기 위해 이 단계는 비터의 [2]알고리즘을 정확히 따르지는 않지만 효과는 동일합니다.

순서 4:

리프 노드 253으로 이동합니다.무게가 1인 블록이 두 개 있습니다.노드 253 및 254는 하나의 블록(리프로 구성), 노드 255는 다른 블록(내부 노드로 구성)입니다.노드 253의 경우 블록 내에서 가장 큰 수는 254이므로 노드 253과 254의 가중치와 기호를 교환합니다.노드 254와 노드 255에서 시작하는 브랜치는 SlideAndIncrement 조건을[2] 충족하므로 스왑해야 합니다.마지막으로 노드 255와 256의 무게를 증가시킵니다.

"b"의 미래 코드는 1이고 "a"의 미래 코드는 01입니다.이것은 그 빈도를 반영하고 있습니다.

레퍼런스

  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.
  2. ^ a b "Adaptive Huffman Coding". Cs.duke.edu. Retrieved 2012-02-26.
  • 비터의 원본 논문: J. S. 비터, "Design and Analysis of Dynamic Huffman Codes", 저널 오브 더 ACM, 34(4), 1987년 10월, 페이지 825-845.
  • J. S. 비터, "ALGorithm 673 Dynamic Huffman Coding", ACM Transactions on Mathemical Software, 15(2), 1989년 6월, 페이지 158-167.ACM 의 수집 알고리즘에도 표시됩니다.
  • Donald E. Knuth, "Dynamic Huffman Coding", 알고리즘 저널, 6(2), 1985, 페이지 163–180.

외부 링크