허프만 인코딩 - 헤더 및 EOF

Question

현재 자바의 허프만 알고리즘을 기반으로하는 프로그램을 구현하고 있으며 인코딩 된 콘텐츠를 파일로 출력해야하는 단계에 있습니다. 디코딩에 필요한 헤더와 eof를 구현하는 방법에 대해 약간 혼란 스럽다. 내 머리글의 경우 현재 입력 파일과 빈도에서 발생하는 모든 고유 값을 가지고 있지만 일부 기사에서는 사람들이 0 또는 1을 사용하여 노드와 주파수를 나타냄을 보았습니다 (어느 정도는 의아해합니다). 기호가 무엇인지 말하지 않기 때문에).

또한 EOF를 이해하기 때문에 심볼처럼 인코딩하여 읽고 읽고 디코딩하므로 확실히 사용할 수없는 값을 사용할 수 있는지 확실하지 않습니다. 나는 1의 가중치가 필요하다는 것을 알고 있지만 파일에 실제로 있지는 않을지 확신 할 수는 없었다.

Answer 1

과제를 수행 할 때 한 번이 작업을 수행해야했으며 이는 우리가 사용한 접근 방식입니다.

헤더 인코딩은 주파수보다는 트리 구조를 인코딩하기 위해 0과 1을 사용하여 수행되었습니다. 나무를 따라 이동하는 것으로 표시된 "0", 우리가 잎 노드에 있었던 "1". 이로 인해 고유하게 인코딩 된 트리의 일종의 선주문 통과가 발생했습니다.

예를 들어, 같은 트리 (((AB) c) (DE))는 "0001 a 1 b 1 c 01 d 1 e는"A, B, C, D, E가있는 곳으로 인코딩 될 그들의 ASCII 양식.

/\ 
    /\ /\ 
/\ c d e 
a b 

우리가 읽을 수하는 방법을 필요로하는 마지막 두 바이트의 많은 지정 파일의 마지막 3 비트를 사용 EOF를 들어

여기에 그래픽 형태로 나무입니다. 우리가 마지막 바이트를 읽으면 (마지막 두 번째 바이트에서 작업 했으므로) 마지막 3 비트를 검사했습니다. 그들은 더 많은 비트를 읽은 다음 6을 인코딩했습니다. 따라서 110101xxxxxxx000은 "110101 (6 비트)을 읽고 나머지는 모두 버립니다 ". 1101011xxxxxx001은 "1101011 (7 비트)을 읽고 나머지는 버립니다"등을 의미합니다.

이렇게하면 EOF를 나타내는 특별한 값을 가질 필요가 없으며 파일을 읽을 수 있습니다. (우리가 실제로 일하고 있던 곳보다 1 바이트 앞당겨 읽을 필요가 있었지만).

(나는 당신의 기사를 읽을 수 없습니다, 그래서 우리의 생각은 당신의 접근 방식으로 작동하는지 내가 모르는 EOF를 들어.)

Answer 2

허프만 인코딩 문자의 어떤 순서에서 허프만 트리를 만드는 방법을 지정하고 그 다음 비트 시퀀스로 인코딩하는 방법을 설명합니다.

트리를 어떻게 인코딩해야하는지 또는 얼마나 많은 비트를 읽을 지 계산하는 방법은 지정하지 않습니다. 전체 바이트 만 파일에 저장할 수 있기 때문에 정확한 비트 수는 문제가됩니다. 따라서 어떤 비트를 끝내야할지 정확히 판단 할 방법이 필요합니다.

트리 인코딩에는 여러 가지 옵션이 있습니다. 그 중 하나는 각 문자의 수를 기록하고 디코더가 그로부터 트리를 재구성하도록하는 것입니다. 다른 옵션은 어떻게 든 트리를 직접 인코딩하는 것입니다. 예를 들어, 0-1 접근법 멍청이를 사용하는 것입니다 (그리고 내가 언급 한 기사를 가정합니다).

다음은 전혀 필요하지 않은 adaptive Huffman coding이지만 더 복잡합니다.

언제 끝낼 지 결정할 때 총 문자 수를 파일에 기록하고이를 사용하여 중지 할시기를 결정할 수 있습니다.또는 문자 수를 사용하여 트리를 인코딩 한 경우이 개수를 무료로 얻을 수 있습니다.

다른 옵션은 EOF 문자를 사용하는 것입니다. 이 문자는 허프만 트리에 있지만 정상적인 값은 인코딩하지 않습니다. 바이트를 인코딩한다고 가정하면 257 번째 값으로 상상할 수 있습니다. 은 EOF 토큰에 대해 0 바이트와 같은 일부 일반 값을 사용할 수 있지만 입력 파일에 실제로 나타나지 않아야합니다.