C언어를 이용한 Huffman coding

소개글

리눅스 상의 C 언어를 이용하여 텍스트 문서를 Huffman coding을 수행합니다. 소스코드와 결과 영상이 포함되어 있습니다.

목차

1.실습 목적
2.실습 방법
3.실습한 내용
4.결과 영상 및 분석
5.과제 수행 시 발생한 문제점 및 해결 방법

본문내용

1. 실습 목적

1.1. Huffman coding
- 리눅스 상의 C 언어를 이용하여 텍스트 문서를 Huffman coding을 수행한다.

1.2. 압축률 및 평균 코드워드 길이 얻기
- Huffman coding으로 부호화된 결과의 압축률 및 평균 코드워드 길이를 구한다.

2. 실습 방법

2.1. Huffman Encoding 수행 순서
2.1.1. Step #1
- 구조체로 노드를 지정해준 뒤 널 값으로 초기화를 시켜준다.
- 모든 문자들의 아스키 코드 값을 가진 배열을 만든다.
- 모든 문자들이 각기 사용된 빈도수를 위의 배열에 저장한다.
- 노드는 각 문자들의 빈도수를 구조체 내의 변수에 저장하여 비교 수단으로 사용한다.

2.1.2 Step #2
- 가장 적게 사용되는 문자가 들어있는 노드를 먼저 실행시킨다
- 매 실행시마다 가장 낮은 빈도로 사용된 2개의 문자가 들어있는 노드 2개의 합을 상위 연결된 새로 만든 노드에 저장하고 active = 1 -> 0으로 바꾼다.

2.1.3 Step #3
- Step #2 의 과정을 단 하나의 노드가 남을 때까지 반복한다.
- 비교시에 2 노드 중 큰 값에 1, 작은 값에 0을 넣어 각 노드안의 문자별로 저장시킨다.

2.2. 압축률 및 평균코드워드 계산
Compression Ratio = Original Data Size / Compressed Data Size
- 원래의 크기에 압축시킨 크기를 나눠 그 비율을 구한다. 그 값이 1보다 클 경우에 효율적인 압축이 되었다고 볼 수 있다.
Average Length of Codeword = ∑Bit지정된 모든 문자의 Bit길이 * 빈도확률
- 빈도확률은 각 워드별 빈도수를 총 워드수로 나눈 값이다.

참고 자료

없음