허프만 코딩 - 두 글자의 주파수가 같으면 다른 코드 워드 생성이 가능합니다.

Question

내 압축기는 빈도 테이블을 사용하여 허프만 트리를 만든 다음 인코딩을 실행하고 빈도 테이블과 인코딩을 파일에 저장합니다.

압축 해제 기는 파일에서 빈도 테이블을 읽고 허프 먼 트리를 재구성 한 다음 파일에 저장된 인코딩을 디코딩합니다.

문제는 두 주파수가 같을 때 압축기와 압축 해제 기가 서로 다른 코드 워드를 생성하는 두 개의 서로 다른 허프만 트리를 생성하고 서로 다르므로 해독이 유효하더라도 문제가 있다는 것입니다.

이 문제를 해결하려면 어떻게해야합니까?

감사합니다.

참고 : 자바로 작성했습니다.

Answer 1

압축 해제 기가 파일에서 빈도 테이블을 읽지 않는 것으로 가정하고 허프 먼 트리를 재구성 한 다음 파일에 저장된 인코딩을 디코딩합니다. 압축기는 "스택"- 000 "흐름"--- 000이라는 단어 인 코드 테이블을 저장해야합니다. 그러면 압축 해제 기는 코드에 대한 단어를 얻기 위해 인 코드 테이블을 읽습니다.

Answer 2

Canonical Huffman codes : http://en.wikipedia.org/wiki/Canonical_Huffman_code을 확인해야합니다.

먼저 문제를 해결합니다. 둘째, 코드 테이블 또는 보통 (더 나쁜) 빈도 테이블 대신 코드 크기 차이 만 전송할 수 있습니다. 허프만 트리를 만드는 동안 심볼을 정렬하는 경우 안정적인 정렬 알고리즘을 사용해야합니다.

자바 구현 예는 여기있다 :