허프만 부호 알고리즘 설계 및 결과 보고서

소개

허프만 부호화 구현

목차

없음

본문내용

전산학과 정보 이론에서 허프만 부호화(Huffman coding)는 무손실 압축에 쓰이는 엔트로피 부호화의 일종으로, 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘이다. 1952년 당시 박사과정 학생이던 데이비드 허프만이 A Method for the Construction of Minimum-Redundancy Codes[1]란 제목의 논문으로 처음 발표했다.

허프만 부호화는 문자들의 빈도로부터 접두 부호(어떤 한 문자에 대한 부호가 다른 부호들의 접두어가 되지 않는 부호)를 만들어 내는 알고리즘으로, 적게 나오는 문자일수록 더 긴 부호를 쓰고 많이 나올수록 더 짧은 부호를 쓴다. 허프만 부호화는 주어진 빈도에 대해서 항상 최적의 접두 부호를 만들어 내며, 이 과정은 빈도가 정렬되어 있을 경우 O(n)만에 가능하다. 각 문자들의 빈도가 2의 거듭제곱 꼴이거나 모두 같을 경우 이 접두 부호는 간단한 이진 블록 부호와 동일하다.

해당 구현은 파일을 통해 입출력하는 것을 바탕으로 구현하였으며, 영문자를 기준으로 작성하였다. 영문자로 된 텍스트 파일을 입력받아 새로운 텍스트 파일에 부호화 테이블의 길이, 부호화 테이블, 부호화 된 문장 순으로 쓰게 하였다. 총 세 개의 구조체를 사용하였으며 단일 연결 리스트와 이진 트리를 응용하여 구성하였다. 함수는 크게 초기화 함수, 삽입 함수, 정렬 함수, 허프만 부호화 함수, 출력 함수 등이 있다. 특이 사항은 삽입 함수를 두 가지를 구성하였는데, 한 가지는 문자열을 하나 씩 순차적으로 입력받아 이를 리스트로 만드는 삽입함수이고, 또 한 가지는 허프만 부호화 진행과정에서 새로운 이진트리의 삽입을 진행하는 함수이다. 전자는 정렬을 고려하지 않아서 따로 정렬함수를 구현하였고 후자는 삽입 시에 정렬을 하도록 하여 별도의 정렬 함수를 구현하지 않았다. 전자를 구현할 때 사용한 정렬은 삽입 정렬이다.

참고자료

· 없음