[공학]허프만 알고리즘을 이용한 압축(설명 자료)

소개글

source는 제 박스의 다른 자료에 있습니다.

목차

I. INTRODUCTION 2

II. Related Works 3

III. Presented Works 4

Problem Overview 5

A. Solution Overview 6

B. Solution Overview 9

C. Solution Overview 10

IV. Implementation 12

V. Results 14

IX. Conclusion 24

References

본문내용

Abstract —Summary

자료 압축의 가장 오래되고 훌륭한 형태중의 하나가 최소 중복코딩에 기반을 둔 알고리즘인 Huffman 코딩이다.
이 기법은 MIT에서 Robert Fano교수에 의해 개설되었던 정보이론 분야의 첫 번째 강의에서 수업 과제의 일부분으로서 David Huffman에 의해 개발되었다. 이 기법과 절차에 의해 생성된 코드를 ‘Huffman 코드’라고 부른다. 이러한 코드들은 prefix 코드이며, 또한 어떤 주어진 모델(set of probability)에 대해 최적이다.
최소 중복 코딩은 다른 기호들이 자료 집합에서 얼마나 자주 발생했는지 안다면, 자료가 공간을 덜 필요로 하도록 자료의 기호들을 표현할 수 있다는 것을 말한다.
이 기법은 데이터 내의 각 문자에 대한 발생빈도를 조사해 자주 나타나는 문자에는 보다 짧은 비트로 기호화를 하고, 잘 나타나지 않는 문자에는 더 긴 비트로 기호화함으로써, 전체 압축 후 기호화의 길이를 원래의 데이터의 길이보다 더 축소시킬 수 있는 통계적 특성을 이용한 압축기법이다.
결국 이 발상은 더 자주 발생하는 기호들을 더 적은 비트로 기호화하는 것이다. 기호들이 문서의 문자일 필요가 없다는 점이 중요하다. 기호는 임의의 크기의 자료가 될 수 있지만 보통 한 바이트를 사용한다.

JPEG
정지 영상 압축의 국제 표준 방식
Haffuman 압축 기법
압축하려는 정보내의 각 문자에 대한발생 빈도를 조사해 자주 나타나는 문제에는 짧은 기호를 할당하고, 잘 나타나지 않는 문자에는 긴 기호를 할당하는 방식
LZW 압축 기법
연속된 문자열을 특수한 코드로 변환하여 표를 만들고, 그 다음에 그 문자열이 나타나면 이 표의 코드로 해당문자열을 변환하여 압축하는 방식

참고 자료

[1] "second edition Introduction to Data Compressioin." Khalid Sayood University of nebraska-Lincoln MORGAN KAUFMANN PUBLISHERS
[2] “Algorithm with C” Kyle Loudon