이 실험 소개
모든 ZIP 파일, PNG 이미지, MP3 트랙은 반복되는 부분을 제거하기 때문에 원시 데이터보다 크기가 작습니다. 자신의 메시지에 대표적인 무손실 압축 방식 두 가지를 적용해 보세요. 런 길이 부호화는 같은 기호가 연속되는 부분을 개수로 바꾸는 방식으로, 단순한 이미지에는 매우 효과적이지만 일반적인 텍스트에는 쓸모가 없습니다. 허프만 부호화는 자주 나타나는 기호에는 짧은 코드를, 드물게 나타나는 기호에는 긴 코드를 부여합니다. 트리를 단계적으로 만들어 가며, 1948년 클로드 섀넌이 발견한 이론적 한계에서 기호당 1비트 이내의 효율을 달성합니다.
학습 목표
- 무손실 압축과 손실 압축의 차이 설명하기
- 런 길이 부호화로 메시지를 인코딩하고 디코딩한 뒤, 어떤 경우에 효과적인지 말하기
- 빈도가 가장 낮은 두 기호를 반복해서 결합해 허프만 트리 만들기
- 트리에서 코드워드를 읽고 어떤 코드도 다른 코드의 시작 부분이 되지 않는 이유 설명하기
- 압축된 크기를 엔트로피 한계와 비교하고 압축률 계산하기
사용 방법
- 1Pixel 행을 선택하고 런 렝스를 선택하세요. 변환 전과 후에 이 행을 표현하는 데 몇 비트가 필요한가요? 왜 이렇게 효과적일까요?
- 2런 렝스를 선택한 상태에서 Hamlet으로 전환하세요. 메시지 크기가 커지는 이유는 무엇인가요?
- 3Mississippi를 선택하고 '트리 만들기'를 누르세요. 각 단계에서 어떤 두 트리가 결합되며, 그 이유는 무엇인가요?
- 4트리가 완성되면 가장 자주 나오는 문자와 가장 드물게 나오는 문자의 코드워드를 찾으세요. 비트 수를 세어 보세요.
- 5루트에서 트리를 따라가며 인코딩된 메시지의 처음 몇 비트를 직접 디코딩해 보세요.
- 6한 글자만 사용하는 메시지를 입력한 다음, 모든 글자가 서로 다른 메시지를 입력하세요. 두 경우 모두 허프먼 코드와 엔트로피 한계를 비교하세요.
모델
가정
- 원본 메시지에서는 ASCII와 마찬가지로 문자당 8비트를 사용합니다.
- 각 런 길이 쌍은 8비트 개수와 8비트 문자로 저장되므로, 길이가 255를 넘는 런은 분할됩니다.
- 허프만 부호의 크기에는 인코딩된 메시지만 포함됩니다. 실제 파일에는 부호표나 각 문자의 개수도 저장해야 하며, 이는 짧은 메시지에서 중요합니다.
- 가중치가 같은 트리가 두 개 있으면 먼저 만들어진 트리를 먼저 선택하고, 더 가벼운 트리가 0 가지가 됩니다. 동률을 처리하는 규칙이 다르면 전체 길이는 같아도 부호가 달라집니다.
수업에서 해 보기
- Q1런 길이 부호화를 사용해 BBBBBWWWBBBBBBBB를 인코딩하세요. 몇 바이트가 필요한가요?
- Q2개수가 A 5, B 2, R 2, C 1, D 1인 허프만 트리를 만들고 ABRACADABRA를 인코딩하는 데 필요한 총 비트 수를 구하세요.
- Q3허프만 부호가 접두 부호여야 하는 이유는 무엇인가요? A를 0, B를 01로 지정하면 어떤 문제가 생기나요?
- Q4텍스트에서 서로 다른 8개의 문자가 모두 같은 횟수만큼 사용됩니다. 이 텍스트의 엔트로피는 얼마이며, 허프만 부호로 압축할 수 있나요?
- Q5JPEG와 MP3는 허프만 부호보다 훨씬 더 많이 압축합니다. 이를 위해 무엇을 포기하나요?
자주 묻는 질문
오늘날 허프만 부호는 어디에 사용되나요?
일상에서 사용하는 다양한 형식에 적용됩니다. ZIP과 gzip(DEFLATE 방식), PNG 이미지, 손실 압축 단계 이후의 JPEG 이미지, MP3 오디오가 그 예입니다. 보통 다른 방식으로 반복을 숫자로 바꾼 다음에 수행되는 마지막 단계입니다.
모든 파일을 압축할 수 있나요?
아니요. 모든 파일을 더 작게 만드는 무손실 방식이 있다면, 그 결과를 계속해서 다시 압축할 수 있을 것입니다. 하지만 긴 파일보다 짧은 파일의 수가 더 적기 때문에 이는 불가능합니다. 무작위 데이터와 이미 압축된 파일은 대체로 더 작아지지 않습니다.
허프만 트리는 유일한가요?
항상 그렇지는 않습니다. 빈도수가 같으면 선택에 따라 서로 다른 트리와 코드워드가 만들어질 수 있지만, 같은 빈도수에 대해 만들어진 허프만 트리는 모두 총 비트 수가 같습니다.