조회 테이블이있는 호프만 코드

Question

인터넷에서 기사를 읽었으며 루트에서 트래버스하여 자연스럽게 디코딩하는 방법을 알고 있지만 조회 테이블을 사용하여 더 빨리 처리하려고합니다.

독서 후에, 나는 아직도 점을 얻을 수 없다.

예는 :

 
input:"abcdaabaaabaaa" 
code data 
0  a 
10  b 
110 c 
111 d 

기사로 인해 가변 길이로, 그것은 최대 코드 길이의 문자열의 비트를 복용하여 길이를 결정하고 인덱스로 사용할 수 있다고 말한다.

 
output:"010110111001000010000" 
Index Index(binary) Code Bits required 
0  000    a  1 
1  001    a  1 
2  010    a  1 
3  011    a  1 
4  100    b  2 
5  101    b  2 
6  110    c  3 
7  111    d  3 

내 질문은 :

가

1. 무엇 그것이 due to variable length, it determine the length by taking a bit of string of max code length을 의미합니까? 길이를 결정하는 방법?

2. 어떻게 조회 테이블을 생성하고 사용하는가? 뒤에있는 알고리즘은 무엇입니까?

Answer 1

예를 들어, 최대 코드 길이는 3 비트입니다. 따라서 스트림 (010)에서 처음 3 비트를 가져 와서 테이블을 인덱싱하는 데 사용합니다. 이 코드는 'a'와 bits = 1을 제공합니다. 입력 스트림에서 1 비트를 소비하고 코드를 출력하고 계속 수행합니다. 두 번째로 돌아 가면 '(b)'와 2 비트 등으로 색인하는 (101)을 얻을 수 있습니다.

테이블을 만들려면 1 < < max_code_length만큼 큰 테이블을 만들고, 허프 먼 코드로 색인을 해독하고 있습니다. 당신의 예제를 보면 '0'으로 시작하는 모든 인덱스는 a이고, '10'으로 시작하는 인덱스는 b 등입니다.