bibomial heap (이항힙)으로 구현한 허프만 코드 인코더, 디코더 리포트

소개글

이항힙으로 구현한 허프만코드 인코더, 디코더 리포트입니다.
수도코드와 프로그램 동작순서와 알고리즘을 포함한 내용이 일반적인 리포트
양식에 의해 완벽히 정리되어 있습니다.

목차

1. 프로젝트 개론
1.1 프로젝트 주제
1.2 프로젝트 목표
1.3 기초 이론

2. 프로그램 전체구조 및 진행순서
2.1 파일의 용도
2.2 Class Information
2.3 프로그램 진행도

3. 프로젝트 세부구조와 분석
3.2 int Max_B_Heap::Delete()
3.3 Node * Max_B_Heap::JoinMaxTrees(Node * a, Node * b)
3.4 void FileIO::Write_Table(char c, int Num_Of_Del_Nodes)
3.5 void FileIO::Write_Code()
< Decoder >
3.6 void FileIO::Load_Code()

4. 자체 수행평가 및 고찰
4.1 수행평가
4.2 고찰

본문내용

1. 프로젝트 개론
1.1 프로젝트 주제
- 이항 힙 (Binomial Heap)을 이용한 허프만 (Huffman) 코딩

1.2 프로젝트 목표
- 알파벳과 문자를 표현하는데 아스키코드(Ascii code) 값이 쓰이는데 빈도수가 높은 경우는 더 짧은 코드로 대체하는 허프만 코드(Huffman code)를 사용하면 항상 7비트가 사용되는 아스키코드 보다 더 짧게 글을 압축할 수 있다. 또한 이항 힙(Binomial Heap)을 사용하면 각 문자의 빈도수 계산과 허프만 코드 부여를 정확하게 할 수 있다. 이번 과제에서는 이항 힙을 이용한 데이터 구조로 글을 허프만 코드로 인코딩 하고 다시 디코딩 하여 원래대로 복구 시키는 작업을 목표로 한다.

1.3 기초 이론
- Circular Linked List (원형 연결 리스트)
: 마지막 노드가 처음 노드를 다시 가리키는 Linked List 구조. 현재 노드가 가리키는 것이 처음 노드인지를 판별하여 중복 없이 한 바퀴만 탐색 가능하다.

- Bionomial Heap (이항 힙)
: 2에 n승 개의 노드를 가지는 트리의 집합이라 할 수 있으며, 같은 수의 자식을 가지는 트리는 허용되지 않는다. 그래서 같은 수의 자식을 가진 트리들끼리는 바로 Join해줘야 하며 같은 트리의 같은 레벨 자식들끼리는 Circular Linked List로 연결되어 있어야 한다. 모든 트리는 root가 빠져나 child들이 분리되더라도 각 child를 root로 하는 이항 힙 구조가 되어야 한다. 앞서 배웠던 Heap들에 비해 좀더 유동적인 구조를 취하고 있으면서도 일정한 구조를 유지하는 Heap이다. 이번 프로젝트에서는 parent가 첫 번째 child만 가리키고 있는 구조를 채택하였고 최상위의 root끼리 연결된 Circular Linked List에서 Max포인터가 우선순위 가장 큰 값을 가리키고 있는 최대 이항힙 구조로 구현하였다.

참고 자료

없음