호프만 텍스트 압축 트리 트래버스 알고리즘

Question

텍스트 압축 알고리즘을 리버스 엔지니어링하려고하는데 약 한 달 동안 이미 한 곳에서 고생했습니다. 일반적으로 here's C의 디코더 코드는 완벽하게 작동하지만 압축 방식이 어떻게 작동하는지 아직 이해할 수 없습니다. 문제는 GetNextChararacter 함수입니다.

이 반복 비트 스트림 형식을 이해할 수 없습니다. 이상한 방법으로 직렬화 된 바이너리 허프 먼 트리처럼 보입니다. 이터 레이션 비트 스트림은 재귀 트리와 유사하며, 현재 노드가 모든 노드를 통과 할 때 알고리즘 검색을 수행하여 리프 수를 출력합니다. 그 후 소스 비트 스트림은 iterationBitStream의 일부 비트를 건너 뜁니다. 현재 위치의 iterBit이 설정되면 반복 스트림의 나머지 부분을 가로 지르고 결과를 이전 오프셋에 더합니다. 그리고 계속 반복 될 때까지 리프에 도달 할 때까지 계속됩니다. 도달 한 리프의 총 수는 디코딩 문자의 문자 목록에서의 오프셋입니다.

나무가 처음에는 총량을 저장하는 데 사용된다는 것을 처음 알았습니다. 압축은이 계획과 복잡하게 보입니다. 동시에, 나는 코드가 아주 기본적인 것을하지만, 알고리즘에 대한 나의 이해는 잘못된 것이라고 생각한다. 다른 알고리즘이 더 논리적으로 설명되어 있는지 아니면 간단히 다른 곳에서 설명했는지 누군가가 알 수 있습니까?

Answer 1

모두에게 감사드립니다. 일단 나무를 만들고 손으로 그것에서 기어 들어가려고하면 나는 그것을 이해했습니다. 일반적으로 반복 비트 스트림은 이진 트리이며 일련 번호는 in pre-order traversal입니다. 어셈블러 코드에서 트리 탐색을 인식하는 것이 어려워 보입니다. 원본 스트림은 해당 트리의 일반 경로입니다. 전체 압축 스키마는 각 문자에 대해 개별 트리가있는 호프만입니다. 텍스트의 다음 문자는 선행 문자의 트리를 기반으로 디코딩됩니다.