최적의 이진 트리 알고리즘 코딩의 적용

데이터 통신에서 전송된 텍스트를 바이너리 문자 0, 1 으로 구성된 바이너리 문자열로 변환해야 하는 경우가 많습니다. 이를 인코딩이라고 합니다. 예를 들어 전송할 메시지가 a, b, c, d 의 네 문자만 포함하는 ABACCDA 라고 가정합니다. 이 네 문자가 표 7.3(A) 에 표시된 대로 인코딩되면 메시지 코드는 00001000/klook 입니다 메시지를 전송할 때 항상 전송 시간이 짧을수록 좋습니다. 이를 위해서는 메시지 코드가 짧을수록 좋습니다. 분명히, 이 인코딩 체계에서 생성된 메시지 코드는 충분히 짧지 않다. 표 7.3(b) 는 또 다른 코딩 체계를 보여줍니다. 이 코드를 사용하여 위 메시지를 인코딩하여 만든 코드는 00010010101100, 길이입니다 이 인코딩 체계에서 네 문자의 인코딩은 두 자리, 즉 동일 길이 인코딩입니다. 인코딩할 때 문자의 빈도를 고려하여 빈도가 높은 문자를 가능한 한 짧게 인코딩하고 빈도가 낮은 문자를 약간 길게 인코딩하여 길이가 같지 않은 코드를 구성하는 경우 메시지의 코드가 더 짧을 수 있습니다. 예를 들어 문자 a, b, c, d 가 표 7.3(C) 과 같이 인코딩되면 위 메시지의 코드는 011010/kloc-입니다

표 a, 표 b, 표 c, 표 d (아래 그림 아래 순서로 정렬): 문자 인코딩 a000b010c100d1/kloc- 인코딩 a0b110c10d111문자 인코딩 A0

호프만 트리는 메시지의 전체 인코딩 길이를 최소화하는 인코딩 체계를 구축하는 데 사용할 수 있습니다. 인코딩할 문자 세트는 {d 1, D2, ..., dn}, 메시지에 나타나는 시간 또는 주파수 세트는 {w 1, w2, ..., wn} 입니다 오른쪽 분기는 1 을 나타냅니다. 루트 노드에서 각 리프 노드까지의 경로 분기에 의해 형성된 0 과 1 의 시퀀스는 해당 노드의 해당 문자 인코딩입니다. 이를 호프만 인코딩이라고 합니다.

호프만 코딩 트리에서 트리의 가중 경로 길이는 각 문자의 코드 길이와 발생 횟수의 곱, 즉 메시지의 전체 코드 길이를 합한 것을 의미하므로 호프만 트리가 구성한 코드는 길이가 같지 않은 코드입니다. 메시지의 전체 코드 길이를 가장 짧게 만들 수 있습니다.

길이가 같지 않은 코드를 설정할 때 디코딩의 고유성을 보장하기 위해 한 문자의 코드를 다른 문자 코드의 접두사가 아닌 것으로 만들어야 합니다. 예를 들어 표 7.3(d) 의 인코딩 체계에서 문자 a 의 코드 0 1 은 문자 b 의 코드 0 10 의 접두어 부분이므로 코드 문자열 010/kloc 입니다 따라서 이러한 인코딩은 디코딩의 고유성을 보장하지 않습니다.

그러나 호프만 트리를 인코딩에 사용하면 위의 모호성 문제가 발생하지 않습니다. 호프만 트리에서 각 문자 노드는 루트 노드에서 다른 문자 노드로의 경로에 있을 수 없는 리프 노드이기 때문에 한 문자의 호프만 인코딩은 다른 문자의 호프만 인코딩 접두사가 될 수 없으므로 디코딩의 모호성을 보장합니다.

다음은 호프만 코딩을 구현하는 알고리즘에 대해 설명합니다. 호프만 코딩을 구현하는 알고리즘은 두 부분으로 나눌 수 있습니다.

(1) 호프만 나무 건설;

(2) 호프만 나무 잎 노드의 코드를 찾으십시오.

본질적으로 호프만 코드를 찾는 것은 설정된 호프만 트리에서 리프 노드부터 노드의 상위 체인 도메인을 따라 루트 노드로 거슬러 올라가는 것을 의미하며, 각 역추적 단계마다 호프만 트리의 한 분기를 거쳐 호프만 코드 값을 얻습니다. 문자의 호프만 코드는 루트 노드에서 해당 리프 노드까지의 경로에 있는 분기로 구성된 0, 1 시퀀스이므로 먼저 가져옵니다. 각 문자의 호프만 인코딩 정보를 저장하기 위해 구조 배열 HuffCode 를 설정할 수 있습니다. 배열 요소의 구조는 다음과 같습니다. bit start, 여기서 구성 비트는 문자의 호프만 인코딩을 저장하는 1 차원 배열이고, start 는 배열 비트에서 인코딩이 시작되는 위치를 나타냅니다. 따라서 I 문자의 경우 호프만 코드는 Huffcode [I] 의 구성 요소에 저장됩니다. 허프 코드 [I]. Bit 의 시작부터 n 까지.

호프만 인코더 세그먼트 찾기

Constmaxleaf =128; {리프 노드의 최대 수 정의}

MaxNode = 255{ 최대 노드 수 정의}

Maxbit =10; {호프만 코딩의 최대 길이 정의}

유형 HCodeType = 레코드

비트: 배열 [0 .. 정수의 최대 비트]

Start: 정수;

끝;

......

HaffmanCode{ 프로그램 {호프만 코드 생성}

Var huff node: array [0 ... hcodetype 의 MaxNode];

HuffCode: 배열 [0..HcodeType 의 MaxLeaf]

Cd: h 코드 유형;

I, j, c, p: 정수;

시작

허프만테리 (huff node); {호프만 나무 구축}

I:=0 ~ n- 1 만들기 {각 리프 노드에 대한 호프만 코드 찾기}

시작

Cd.start: = n-1; C: = I;

허프드. 부모;

P<& gt0 do {리프 노드에서 루트까지}

만약 허핑턴 [P] 이라면. L child = c then cd.bit [cd.start]: = 0

Elsecd.bit [cd.start]: =1;

Dec (cd.start); C: = p;

허프드. 부모;

끝;

For j: = cd.start1ton-1do {각 리프 노드에 대한 호프만 코드와 코드의 시작 위치 저장}

시작

허프 코드 [I]. 비트 [j]: = cd.bit [j];

허프 코드 [I]. Start = cd.start

끝;

I:=0 ~ n- 1 만들기 {각 리프 노드에 대한 호프만 코드 출력}

시작

For j: = huff code [I]. 시작 1 끝 n- 1 쓰기 작업 (huffcode [I]). 비트 [j]:10);

Writeln

끝;

끝;