Huffman_Coding_Program

허프만 코딩을 이용한 압축 프로그램 개발 Repository입니다.

개요

허프만 코딩(Huffman coding)은 자료 압축의 가장 오래되고 기초적인 방법 중의 하나이며 최소 중복 코딩(minimum redundancy coding)에 기반한 알고리즘을 사용한다. 최소 중복 코딩은 문자들이 자료 집합에서 얼마나 자주 발생하는지를 안다면 발생되는 문자들의 비율에 따라 자주 반복되는 문자들을 더 적은 비트로 부호화 하는 방법이다. 일반적인 경우 한 문자를 표현하기 위해 한 개의 바이트(ASCII 코드)를 사용하나 허프만 코드는 문자 발생 비율에 따라 다른 크기의 비트 로 표현한다.

문제

임의의 텍스트 파일이 주어지면 허프만 코딩 방법을 이용하여 자료를 압축하며 압축된 파일을 해제하는 프로그램을 작성한다. 다수의 텍스트 파일에서 실험을 하여 각각의 압축률과 평균적인 압축률을 계산해 본다.

제한요소 및 요구사항

허프만 코드로 압축한 파일은 이진 파일로 저장한다.
허프만 코드로 압축한 파일은 허프만 테이블과 허프만 부호화코드를 포함한다.
50,000자, 100,000자, 500,000자 이상의 텍스트 파일을 직접 준비한다.
여러 가지 텍스트 파일에 대해 압축을 수행하여 파일별 및 평균적인 통계정보(압축률, 문자당 평균 비트 수, 압축 및 복원 시간 등)를 계산한다.

확장 기능

GUI 방식으로 구현한다.
ASCII 문자 이외의 문자(한글, 유니코드 등)에 대해서도 동작하도록 한다.

개발

목표 설정

여러 가지 문자 길이를 가진 텍스트 파일을 입력받았을 때, 해당 텍스트 파일을 정상적으로 압축 및 압축해제를 하여 시스템 내에 저장할 수 있도록 하는 프로그램을 구현하는 것이 목표이며 그 과정에서의 상세한 결과를 사용자가 직접 볼 수 있도록 개발한다.

개발 환경

H/W
- CPU : 11𝑡ℎ Gen Intel® Core™ i5-1135G7 @ 2.40GHz(8cpus) ~ 2.4GHz
- RAM : 16GB
- GPU : Internal – Intel® Iris® Xe Graphics, External – NVIDIA GeForce MX450
S/W
- OS : WINDOW 10
- Develop Tool: Eclipse IDE - Java
- Version : JDK 16

자료구조

Node(이진트리)

자료형	변수명	내용
char	ch	하나의 문자를 담기 위한 변수
int	freq	해당 문자의 빈도수를 저장하기 위한 변수
Node	left	허프만 트리를 구성하기 위한 왼쪽 노드
Node	right	허프만 트리를 구성하기 위한 오른쪽 노드

PriorityQueue(우선순위 큐)

자료형	변수명	내용
Priority	queue	각 노드에 대한 정보를 우선순위 큐에 저장하기 위한 변수

HashMap(해시 맵)

<허프만 트리를 생성하기 위한 해시 맵>

자료형	변수 형태	내용
Character	Node.ch	노드에 담겨있는 각 문자들을 해시 맵에 저장하기 위한 변수
Integer	Node.freq	노드에 담겨있는 해당 문자의 빈도수를 해시 맵에 저장하기 위한 변수

<허프만 트리를 생성하기 위한 해시 맵>

자료형	변수 형태	내용
Character	Node.ch	노드에 담겨있는 각 문자들을 해시 맵에 저장하기 위한 변수
String	String	각 문자에 해당되는 허프만 코드를 저장하는 변수

※ 우선순위 큐(PriorityQueue), 해시 맵(HashMap)은 자바에서 기본적으로 제공하는 구현 클래스를 사용하였음.

Min-su-Jeong/Huffman_Coding_Program