허프만트리압축 메모

빈도 역순으로 정렬하는 힙에 삽입된 노드들이 차례로 2개씩 쌍으로 인출되서, 한 부모를 모시는 하위 트리로 2개로 변화하게 된다. 그리고 새로 생긴 부모 트리는 자식들의 빈도를 합산한 빈도값을 지니게 된체로 다시 힙으로 들어간다. 이 방식을 통해서 잦은 값은 상위 레벨에, 드문 값은 점점 트리 하위 레벨로 가게 된다. 결과적으로 그래서 잦은 값은 적은 비트로 표현하고, 드믄 값은 그보다 많은 비트로 표현하겠다는 것 같은데, 출현값들의 테이블의 인덱스를 압축코드로 쓰면서 경제적인 가변길이 인덱스를 지원한다고 말하는게 더 맛이 나는 것 같기도 하다.

이책을 읽으며 -

간단히 순서를 정리하자면, 우선 [데이터][빈도] 이렇게 구성되는 빈도표를 구성하고 간 항목을 빈도값을 역순으로 비교하는 힙에 넣는다. 그런 후에 2개씩 빼서 허프만 트리 만들기 알고리즘을 실행하고, 완성된 허프만 트리에서 실제 [데이터][허프만속성] 모양으로 변환표를 구성해서 압축할때 이표를 참조해서 간단히 허프만 코드로 변환한다. 압축 해제할때 허프만 트리가 필요하니, 트리는 배열 형태로 변환 후 허프만코드 파일에 같이 저장한다.