허프만 코딩 알고리즘의 문자 위치 확인

Question

문자열을 인코딩하기 위해 허프만 코딩 알고리즘을 읽습니다. 캐릭터의 빈도를 고려하여 나무를 만들 수 있습니다. 나는이로 만든 나무가 볼 수

a b d e f h i k n o r s t u v 
5 1 3 7 3 1 1 1 4 1 5 1 2 1 1 9 

*space has frequency 9 

: 여기

는 주파수 테이블입니다. 그러나 나무에 요소를 배치하는 법칙을 도출 할 수는 없습니다.

이 책에서는 빈도가 높은 모든 문자가 근근에 있어야한다고 말합니다. 그러나 두 개 이상의 문자가 동일한 빈도를 갖는 경우에는 루트의 다른면에 있어야합니다.

질문은 어떻게 위치를 결정합니까? 내 책 a IN

는 r는 011을 가지고 있으며, e 코드 100을 가지고, 코드 010 있습니다.

아무도 도와 줄 수 있습니까?

Answer 1

Wikipedia을 사용해 보셨습니까? 허프만 코딩에 대한 훌륭한 데모가 있습니다. 알고리즘은 충분히 간단합니다 : priority queue이 필요합니다.

알고리즘이 같은 정도이다

1. Create tree nodes with each character and their frequencies 
2. Put all the letters and their frequencies in a priority queue Q 
3. Do until Q contains only one element: 
    3a. Pick two lowest-frequency items a, b 
    3b. Create a tree node z with frequency(z) = frequency(a) + frequency(b) 
    3c. Add a and b as left and right children of z 
    3d. Put z in Q 
4. Pick up the only element from Q. This would be the root of the tree. 
5. Assign binary codes to each leaf node according to their root-to-leaf path. 

우선 순위 큐, 즉 가장 낮은 주파수를 가진 노드가 제 나와야하는 최소 우선 순위 대기열로 설계되어야한다. 동일 주파수 항목을 처리하려면 타이 브레이크 (tie-breaker)와 같은 다른 기준 (예 : 알파벳 순서)을 사용하십시오. 인코딩과 디코딩 모두에 대한 타이 브레이크 기준과 일치해야합니다.

Answer 2

일단 나무가 있으면 도로의 각 분기점에서 두 분기에 0과 1을 할당하는 방법은 임의로 선택할 수 있습니다. 따라서 할당을 정식으로 만드는 방법이 없으면 각 심볼에 비트를 할당하는 방법에 대한 "정답"이 없습니다. r은 011이어야합니다. r은 3 비트 값이 될 수 있습니다. (이 주파수 집합에 대해서는 길이가 3 비트 여야합니다.)

중요한 것은 디코더가 0과 1의 동일한 할당을 인코더로 얻는 것입니다. 직접 코드를 전송하거나 길이를 보내고 0과 1을 정식 방식으로 할당 할 수 있습니다. 예를 들어, zip, gzip, png 등에서 사용되는 압축 알고리즘은 각 심볼에 대한 비트 수만 보냅니다. 그런 다음 가장 작은 길이로 시작하여 해당 길이의 모든 기호에 0부터 시작하는 코드가 지정됩니다. 기호에는 표현 정수로 정렬 된 기호가 순서대로 코드가 지정됩니다. 예 : 문자의 ASCII 정렬 순서. 다음 길이의 경우 비트가 오른쪽에 추가되고 코드 카운팅이 계속됩니다. 이렇게하면 적절한 접두어 코드가 보장되고 왼쪽에서 오른쪽으로 디코딩됩니다. 이 경우에 따라서

, 코드 길이는 다음과 같습니다

2: _ 
3: a, e, r 
4: d, f, n 
5: b, h, t 
6: i, k, o, s, u, v 

그래서 우리는 (각 길이 내에서 알파벳 순서로 기호) 얻을 : 여기

_: 00 
a: 010 
e: 011 
r: 100 
d: 1010 
f: 1011 
n: 1100 
b: 11010 
h: 11011 
t: 11100 
i: 111010 
k: 111011 
o: 111100 
s: 111101 
u: 111110 
v: 111111 

비트 할당이 무엇 다릅니다 당신의 책에서 세 가지 기호 중 두 가지를 찾으십시오.완전히 다른 좋은 접두사 코드 선택의 예로서, 모든 비트를 반전시킬 수 있습니다. 그렇지 않으면 비트 열의 모든 하위 집합을 바꿀 수 있습니다. 예 : 첫 번째 열 전체를 뒤집을 수 있습니다. 각 길이의 기호 순서를 변경할 수 있습니다. 비트 순서를 반대로 바꿀 수 있습니다. 실제로, zip 등은 위에서 보인 비트들을 역순으로 저장하므로, 디코딩은 최하위 비트부터, 즉 오른쪽에서 왼쪽으로 수행됩니다.