허프만 트리를 저장하는 효율적인 방법
https://stackoverflow.com/questions/759707
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
Huffman 인코딩/디코딩 도구를 작성하고 있으며 출력 파일 내부에 저장하기 위해 생성 된 Huffman 트리를 저장하는 효율적인 방법을 찾고 있습니다.
현재 구현하는 두 가지 버전이 있습니다.
- 이것은 전체 파일을 문자별로 메모리 문자로 읽고 전체 문서의 주파수 테이블을 작성합니다. 이것은 트리를 한 번만 출력하면 필요하므로 입력 파일이 작은 경우 외에는 효율성이 크지 않습니다.
- 내가 사용하는 다른 방법은 크기가 약 64 킬로 바이트 인 데이터 덩어리를 읽고 그에 대한 주파수 분석을 실행하고 트리를 만들고 인코딩하는 것입니다. 그러나이 경우 모든 청크 전에 디코더가 트리를 다시 구축하고 인코딩 된 파일을 올바르게 디코딩 할 수 있도록 주파수 트리를 출력해야합니다. 가능한 한 많은 공간을 절약하고 싶기 때문에 효율성이 제자리에 들어간 곳입니다.
지금까지의 검색에서 나는 가능한 한 작은 공간에 나무를 저장하는 좋은 방법을 찾지 못했습니다. StackoverFlow 커뮤니티가 좋은 솔루션을 찾는 데 도움이되기를 바랍니다!
해결책
바이트 조직 스트림/파일 위에 약간 현명한 계층을 처리하기 위해 코드를 이미 구현해야하므로 여기에 제안이 있습니다.
실제 주파수를 저장하지 마십시오. 디코딩 할 필요가 없습니다. 그러나 실제 나무가 필요합니다.
루트에서 시작하여 각 노드에 대해 :
- Leaf-Node 인 경우 : 출력 1 비트 + N- 비트 문자/바이트
- 리프 노드가 아닌 경우 출력 0 비트. 그런 다음 두 하위 노드 (먼저 오른쪽으로 왼쪽)를 인코딩하여 같은 방식으로 인코딩합니다.
읽으려면 다음을 수행합니다.
- 비트를 읽으십시오. 1 인 경우 N-Bit 문자/바이트를 읽고 아이가없는 새 노드를 반환하십시오.
- 비트가 0 인 경우 왼쪽과 오른쪽 아동 노드를 동일한 방식으로 디코딩하고 그 어린이들과 함께 새로운 노드를 반환하지만 가치는 없습니다.
리프 노드는 기본적으로 자녀가없는 노드입니다.
이 접근법을 사용하면 글을 쓰기 전에 출력의 정확한 크기를 계산하여 이익이 노력을 정당화하기에 충분한 지 알아낼 수 있습니다. 이것은 각 문자의 빈도를 포함하는 키/값 쌍 사전이 있다고 가정합니다. 여기서 주파수는 실제 발생 수입니다.
계산을위한 의사 코드 :
Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))
트리 크기 계산은 리프 및 비 잎 노드를 고려하며 문자보다 인라인 노드가 하나 더 적습니다.
size_of_one_character는 비트의 수가 될 것이며,이 두 개는 트리 + 인코딩 된 데이터에 대한 나의 접근 방식이 차지하는 총 비트 수를 제공합니다.
경로 (c)는 트리의 트리의 문자로 비트 경로를 산출하는 함수/테이블입니다.
다음은 C#-Loking 의사 코드가 있습니다. 한 문자는 단순한 바이트라고 가정합니다.
void EncodeNode(Node node, BitWriter writer)
{
if (node.IsLeafNode)
{
writer.WriteBit(1);
writer.WriteByte(node.Value);
}
else
{
writer.WriteBit(0);
EncodeNode(node.LeftChild, writer);
EncodeNode(node.Right, writer);
}
}
다시 읽으려면 :
Node ReadNode(BitReader reader)
{
if (reader.ReadBit() == 1)
{
return new Node(reader.ReadByte(), null, null);
}
else
{
Node leftChild = ReadNode(reader);
Node rightChild = ReadNode(reader);
return new Node(0, leftChild, rightChild);
}
}
예제 (단순화, 속성 사용 등) 노드 구현 :
public class Node
{
public Byte Value;
public Node LeftChild;
public Node RightChild;
public Node(Byte value, Node leftChild, Node rightChild)
{
Value = value;
LeftChild = leftChild;
RightChild = rightChild;
}
public Boolean IsLeafNode
{
get
{
return LeftChild == null;
}
}
}
다음은 특정 예제의 샘플 출력입니다.
입력 : AAAAAABCCCCCCDDEEEEE
주파수 :
- A : 6
- B : 1
- C : 6
- D : 2
- E : 5
각 캐릭터는 8 비트에 불과하므로 나무의 크기는 10 * 5-1 = 49 비트입니다.
나무는 다음과 같이 보일 수 있습니다.
20
----------
| 8
| -------
12 | 3
----- | -----
A C E B D
6 6 5 1 2
따라서 각 문자에 대한 경로는 다음과 같습니다 (0은 왼쪽, 1은 오른쪽) : :
- A : 00
- B : 110
- C : 01
- D : 111
- E : 10
출력 크기를 계산하려면 다음과 같습니다.
- A : 6 발생 * 2 비트 = 12 비트
- B : 1 발생 * 3 비트 = 3 비트
- C : 6 발생 * 2 비트 = 12 비트
- D : 2 발생 * 3 비트 = 6 비트
- E : 5 발생 * 2 비트 = 10 비트
인코딩 바이트의 합계는 12+3+12+6+10 = 43 비트입니다.
트리에서 49 비트에 추가하면 출력은 92 비트 또는 12 바이트가됩니다. 원래 20자를 인코딩하지 않은 저장하는 데 필요한 20 * 8 바이트와 비교하면 8 바이트를 절약 할 수 있습니다.
처음 시작할 나무를 포함한 최종 출력은 다음과 같습니다. 스트림 (AE)의 각 문자는 8 비트로 인코딩되는 반면 0과 1은 단일 비트입니다. 스트림의 공간은 트리를 인코딩 된 데이터와 분리하는 것이며 최종 출력의 공간을 차지하지 않습니다.
001A1C01E01B1D 0000000000001100101010101011111111010101010
댓글에있는 구체적인 예는 AABCDEF를 얻을 수 있습니다.
입력 : AABCDEF
주파수 :
- A : 2
- B : 1
- C : 1
- D : 1
- E : 1
- F : 1
나무:
7
-------------
| 4
| ---------
3 2 2
----- ----- -----
A B C D E F
2 1 1 1 1 1
경로 :
- A : 00
- B : 01
- C : 100
- D : 101
- E : 110
- F : 111
트리 : 001A1B001C1D01E1F = 59 비트
데이터 : 000001100101110111 = 18 비트
합 : 59 + 18 = 77 비트 = 10 바이트
원본은 8 비트 = 56의 7 자 였으므로 작은 데이터가 너무 많습니다.
다른 팁
나무 세대를 충분히 제어 할 수 있다면 정식 나무를 만들 수 있습니다 (같은 방식으로 꺾다 예를 들어, 그렇습니다)는 기본적으로 나무를 만들 때 모호한 상황을 해결하기위한 규칙을 생성한다는 것을 의미합니다. 그런 다음 Deflate와 마찬가지로 실제로 저장해야 할 것은 각 문자에 대한 코드의 길이입니다.
즉, 위에서 언급 한 트리/코드 Lasse가 있다면 다음과 같습니다.
- A : 00
- B : 110
- C : 01
- D : 111
- E : 10
그런 다음 2, 3, 2, 3, 2로 저장할 수 있습니다.
그리고 그것은 항상 동일한 문자 세트 (ASCII)를 사용하고 있다고 가정 할 때 허프만 테이블을 재생하기에 충분한 정보입니다. (이는 문자를 건너 뛸 수 없다는 것을 의미합니다. 제로이라도 각각의 코드 길이를 나열해야합니다.)
비트 길이 (예 : 7 비트)를 제한하면 짧은 이진 문자열을 사용하여 각 숫자를 저장할 수 있습니다. 따라서 2,3,2,3,2는 010 011 010 011 010이됩니다.
당신이 원한다면 진짜 미친, 당신은 deflate가하는 일을하고,이 코드의 길이의 또 다른 허프만 테이블을 만들고, 코드 길이를 미리 저장할 수 있습니다. 특히 "0 N 회에 0 번 삽입"에 대한 추가 코드를 추가하여 물건을 더 단축시킵니다.
Huffman 코딩에 이미 익숙하다면 Deflate의 RFC는 나쁘지 않습니다. http://www.ietf.org/rfc/rfc1951.txt
가지는 0 잎입니다. 1은 1입니다. 먼저 "모양"을 얻기 위해 나무 깊이를 먼저 가로 지릅니다.
e.g. the shape for this tree
0 - 0 - 1 (A)
| \- 1 (E)
\
0 - 1 (C)
\- 0 - 1 (B)
\- 1 (D)
would be 001101011
동일한 깊이의 첫 번째 주문 aecbd의 캐릭터에 대한 비트를 따르십시오 (읽을 때 트리 모양에서 얼마나 많은 문자가 기대할 수 있는지 알 수 있습니다). 그런 다음 메시지 코드를 출력하십시오. 그런 다음 출력을 위해 문자로 나눌 수있는 일련의 비트가 있습니다.
당신이 그것을 청킹하는 경우, 다음 척을 위해 나무를 저장하는 것이 이전 청크의 나무를 재사용하는 것만 큼 효율적이며 이전 덩어리에서 나무를 재사용하는 지표만큼 "1"인 것만 큼 효율적이라는 것을 테스트 할 수 있습니다. .
트리는 일반적으로 바이트의 주파수 테이블에서 생성됩니다. 따라서 그 테이블을 보관하거나 주파수로 정렬 된 바이트 자체를 보관하고 나무를 즉석에 다시 만들어냅니다. 물론 이것은 더 큰 블록이 아닌 단일 바이트를 나타내는 나무를 만들고 있다고 가정합니다.
업데이트: j_random_hacker가 주석으로 지적한 바와 같이, 당신은 실제로 이것을 할 수 없습니다 : 당신은 주파수 값 자체가 필요합니다. 당신이 나무를 만들 때 그들은 결합되고 "거품"을 위쪽으로합니다. 이 페이지 주파수 테이블에서 트리가 제작되는 방식을 설명합니다. 보너스로서, 나무를 저장하는 방법을 언급 하여이 답변이 삭제되지 않도록 저장합니다.
허프만 트리 자체를 출력하는 가장 쉬운 방법은 뿌리에서 시작하여 왼쪽을 먼저 덤프 한 다음 오른쪽을 덤프하는 것입니다. 각 노드에 대해 0을 출력하면 각 리프마다 1을 출력 한 다음 값을 나타내는 N 비트를 출력합니다.
더 나은 접근
나무:
7
-------------
| 4
| ---------
3 2 2
----- ----- -----
A B C D E F
2 1 1 1 1 1 : frequencies
2 2 3 3 3 3 : tree depth (encoding bits)
이제이 테이블을 도출합니다.
depth number of codes
----- ---------------
2 2 [A B]
3 4 [C D E F]
동일한 바이너리 트리를 사용할 필요가 없으며 계산 된 트리 깊이를 유지하면서 인코딩 비트 수를 유지하십시오. 따라서 트리 깊이로 주문한 압축되지 않은 값 [ABCDEF]의 벡터를 유지하려면이 별도의 벡터 대신 상대 색인을 사용하십시오. 이제 각 깊이에 대해 정렬 된 비트 패턴을 재현합니다.
depth number of codes
----- ---------------
2 2 [00x 01x]
3 4 [100 101 110 111]
즉시 보는 것은 각 행에서 첫 번째 비트 패턴 만 중요하다는 것입니다. 다음 조회 테이블을 얻을 수 있습니다.
first pattern depth first index
------------- ----- -----------
000 2 0
100 3 2
이 LUT는 크기가 매우 작습니다 (Huffman 코드가 32 비트 길이 일 수 있더라도 32 행만 포함). 실제로 첫 번째 패턴은 항상 Null이므로 패턴의 이진 검색을 수행 할 때 완전히 무시할 수 있습니다. IT (여기서는 비트 깊이가 2 또는 3인지 확인하고 관련 데이터가 벡터에 저장되는 첫 번째 인덱스를 가져 오기 위해 1 패턴 만 비교해야합니다). 이 예에서는 최대 31 값의 검색 공간에서 입력 패턴의 빠른 이진 검색, 즉 최대 5 개의 정수 비교를 수행해야합니다. 이 31 개의 비교 루틴은 모든 루프를 피하고 정수 바이너리 룩업 트리를 찾을 때 상태를 관리 해야하는 31 코드로 최적화 될 수 있습니다. 이 테이블은 모두 작은 고정 길이에 맞습니다 (LUT는 32 비트를 넘지 않는 허프만 코드의 경우 최대 31 행이 필요하며 위의 2 개의 다른 열은 최대 32 행으로 채워집니다).
다시 말해 위의 LUT는 비트 깊이 값을 저장하기 위해 각각 32 비트 크기의 31 개 Ints, 32 바이트가 필요합니다. 그러나 깊이 열 (깊이 1의 첫 번째 행)을 암시하여이를 피할 수 있습니다.
first pattern (depth) first index
------------- ------- -----------
(000) (1) (0)
000 (2) 0
100 (3) 2
000 (4) 6
000 (5) 6
... ... ...
000 (32) 6
따라서 LUT에는 [000, 100, 000 (30Times)]이 포함되어 있습니다. 그것을 검색하려면 입력 비트 패턴이 두 패턴 사이에있는 위치를 찾아야합니다.이 LUT의 다음 위치에서 패턴보다 낮아야하지만 현재 위치의 패턴보다 여전히 높거나 동일해야합니다 (두 위치가 두 위치 인 경우. 동일한 패턴을 포함하면 현재 행이 일치하지 않으며 입력 패턴은 아래에 맞습니다). 그런 다음 나누고 정복하고 최대 5 개의 테스트를 사용합니다 (바이너리 검색에는 5 개의 내장 된 If/elo/else 중첩 레벨이 포함 된 단일 코드가 필요합니다. 32 개의 분기가 있고 분기에 도달 한 분기는 비트 깊이를 직접 나타냅니다. 저장해야합니다. 첫 번째 인덱스를 반환하기 위해 두 번째 테이블에 직접 색인화 된 단일 조회를 수행합니다. 디코딩 된 값의 벡터에서 최종 인덱스를 추가로 도출합니다).
조회 테이블 (첫 번째 열에서 검색)에서 위치를 얻으면 즉시 입력에서 가져올 비트 수와 시작 인덱스가 벡터로 향합니다. 얻은 비트 깊이는 첫 번째 인덱스를 잠술 후 기본 비트 마스킹을 통해 조정 된 인덱스 위치를 직접 도출하는 데 사용될 수 있습니다.
요약 : 링크 된 이진 트리를 저장하지 않으며, 31 패턴의 표에서 고정 된 위치에서 패턴을 비교하는 5 개의 중첩 IF를 비교하는 5 개의 중첩 IF를 필요로하는 루프와 디코딩 된 값의 벡터 (중첩 if/then/else 테스트의 첫 번째 분기에서 벡터에 대한 시작 오프셋은 항상 제로이며 가장 짧은 코드와 일치 할 때 가장 빈번한 분기입니다. 가장 빈번한 디코딩 값을위한 것입니다).
