엔트로피

엔트로피 부호화(entropy encoding)는 메시지에서 '낭비되는' 정보, 즉 불필요한 정보를 제거하여 무손실 압축을 달성하는 데이터 부호화 방법이다. 다시 말해, 엔트로피 부호화는 메시지를 정확히 표현하는 데 애초에 필요하지 않았던 정보를 제거한다. 엔트로피가 높다는 것은 낭비되는 정보가 많은 메시지라는 뜻이다. ASCII로 부호화된 영어 텍스트는 엔트로피가 매우 높은 메시지의 예이다. JPEG 이미지나 ZIP 아카이브처럼 이미 압축된 메시지는 엔트로피가 매우 낮아 추가적인 엔트로피 부호화의 이점을 거의 얻지 못한다.

ASCII로 부호화된 영어 텍스트의 엔트로피가 높은 이유는 모든 문자가 똑같이 8비트로 부호화되기 때문이다. 영어 텍스트에서 E, L, N, R, S, T 같은 문자는 다른 대부분의 문자보다 훨씬 자주 등장한다는 사실이 알려져 있다. 만약 이 문자들만 4비트로 부호화할 방법이 있다면, 새로운 부호화는 더 작아지고 원래 정보를 모두 담으면서 엔트로피는 더 낮아질 것이다. 그러나 ASCII가 고정 길이 비트를 쓰는 데에는 이유가 있다. 각 글자를 표현하는 비트 수가 항상 고정되어 있어 다루기 쉽기 때문이다. 그렇다면 위 문자들에 4비트를 쓰는 부호화 방식은 4비트 부호와 8비트 부호를 어떻게 구별할 수 있을까? 이 문제는 '접두사가 없는 가변 길이(prefix-free variable-length)' 부호화로 해결된다.

이러한 부호화에서는 각 글자를 임의의 비트 수로 표현할 수 있고, 메시지에 등장하지 않는 글자는 아예 부호화하지 않는다. 다만 정보를 복원할 수 있으려면, 어떤 글자를 나타내는 비트 패턴이 다른 부호의 접두사가 되어서는 안 된다. 이 제약 덕분에 부호화된 비트열을 한 비트씩 읽어 나가다가 어떤 글자를 나타내는 비트 묶음을 만나는 순간 그 글자를 곧바로 복호화할 수 있다. 접두사 제약이 없다면 이러한 복호화는 불가능하다.

텍스트 AAAAABCD를 생각해 보자. ASCII로는 64비트가 필요하다. 대신 A를 00, B를 01, C를 10, D를 11로 부호화하면 16비트로 표현할 수 있으며, 결과 비트열은 0000000000011011이 된다. 그러나 이것은 여전히 글자당 2비트를 쓰는 고정 길이 부호화이다. A가 더 자주 등장하므로 더 적은 비트로 부호화하면 더 좋아질 수 있다. 접두사 없는 부호화를 유지하려면 다른 비트 패턴 일부는 2비트보다 길어져야 한다. 최적 부호화의 한 예는 A를 0, B를 10, C를 110, D를 111로 부호화하는 것이다. (B, C, D의 부호는 서로 자유롭게 바꿔도 최종 크기가 늘지 않으므로, 이것이 유일한 최적 부호화는 아니다.) 이 부호화를 쓰면 메시지는 단 13비트인 0000010110111로 부호화되어 약 4.9 대 1의 압축률을 얻는다. 즉 최종 부호화의 각 비트는 원래 부호화의 4.9비트만큼의 정보를 담는다.

두 번째 예로 텍스트 THE CAT IN THE HAT을 생각해 보자. 여기서는 문자 T와 공백이 가장 자주 등장하므로 최적 부호화에서 가장 짧은 비트 패턴을 갖는다. 반면 C, I, N은 한 번씩만 등장하므로 가장 긴 부호를 갖는다. 최적 부호화, 즉 가장 적은 비트로 텍스트를 부호화하는 접두사 없는 가변 길이 비트 패턴 집합은 여러 가지가 있다. 그중 하나는 공백을 00, A를 100, C를 1110, E를 1111, H를 110, I를 1010, N을 1011, T를 01로 부호화하는 것이다. 이 최적 부호화는 8비트 ASCII로 필요한 144비트에 비해 단 51비트만 필요하며, 약 2.8 대 1의 압축률을 얻는다.

입력은 한 줄에 하나씩 놓인 여러 개의 텍스트 문자열로 이루어진다. 각 문자열은 대문자 영숫자와 밑줄(_)로만 이루어지며, 밑줄은 공백을 대신한다. 입력의 끝은 텍스트 문자열이 END라는 단어만으로 이루어진 줄로 표시된다. 이 줄은 처리하지 않는다.

각 입력 텍스트 문자열마다 세 값을 공백 하나로 구분하여 한 줄에 출력한다: 8비트 ASCII 부호화의 비트 길이, 최적 접두사 없는 가변 길이 부호화의 비트 길이, 그리고 소수점 첫째 자리까지 반올림한 압축률. 압축률은 (ASCII 비트 길이) ÷ (최적 부호화 비트 길이)이며, 소수점 아래 한 자리로 정확히 반올림한다.