데이터 압축 알고리즘 컴퓨터과학부 2003440134 조 산 컴퓨터과학부 2003920017 김형주.

Presentation on theme: "데이터 압축 알고리즘 컴퓨터과학부 2003440134 조 산 컴퓨터과학부 2003920017 김형주."— Presentation transcript:

1 데이터 압축 알고리즘 컴퓨터과학부 조 산 컴퓨터과학부 김형주

2 Contents 압축 알고리즘의 기초 Run – Length Algorithm Lempel – Ziv Algorithm
Huffman Algorithm Demo

3 압축알고리즘의 기초 압축 알고리즘의 기본 아이디어는 반복적 패턴의 발 견과 그것의 부호화. 무손실 압축 알고리즘
RLE, LZ, Huffman… 손실 압축 알고리즘 MPEG, JPEG …

4 Run-Length Algorithm(1)
반복 길이 부호화(RLE, Run-Length encoding) 데이터에서 같은 값이 연속적으로 나타날 때, 그 개 수와 반복되는 값만으로 표현.

5 Run-Length Algorithm(2)
<탈출문자, 반복문자, 개수>로 표현. 원래 문자열: ABAAAAABCBDDDDDDDABC 압축 문자열: AB*A5BCB*D7ABC ‘*’ 를 ESCAPE 문자로 사용 ESCAPE 문자는 출현빈도수가 가장 적은 문자로 선택.

6 Run-Length Algorithm(3)
알고리즘이 매우 단순함. 이미지 파일이나 exe파일처럼 똑같은 문자가 반복되 는 경우 매우 좋은 압축률. 똑같은 문자가 이어져 있지 않은 경우에는 압축률이 매우 떨어짐.

7 Lempel-Ziv Algorithm(1)
실제 상용에서 가장 많이 사용되는 매우 우수한 알고 리즘. LZ77, LZSS, LZ78, LZW 등 많은 변형이 존재.

8 Lempel-Ziv Algorithm(2)
<탈출문자, 상대위치, 길이> 로 표현. 원래 문자열: ABCDEFGHIJKBCDEFJKLDM 압축 문자열: ABCDEFGHIJK<10,5>JKLDM 현재 패턴이 가까운 거리에 존재한다면, 그것에 대한 상대적 위치와 패턴의 길이를 기록. Sliding Window, Look Ahead Buffer를 이용. 실제로는 이 원리를 응용하여 구현. 정적 사전법(Static Dictionary) 동적 사전법(Dynamic Dictionary)

9 Lempel-Ziv Algorithm(3)
동적 사전법(Dynamic Dictionary)을 이용한 구현의 응용

10 Huffman Algorithm(1) 1952년 당시 박사과정 학생이던 David Huffman이 고안해낸 알고리즘.
데이터문자의 등장 빈도에 따라서 다른 길이의 부호 를 사용하는 알고리즘. MPEG 포맷의 형태에 쓰임. 우리가 자주 이용하는 ALZIP 또한 Huffman 방식으 로 한번 압축 후, Lempel 알고리즘으로 한번 더 압축 하는 방식.

11 Huffman Algorithm(2) Huffman Tree를 구축하여 문자를 부호화.
대상 문자열: CDDCACBCBCCCBBCDA 1. 각 문자열별로 빈도수를 체크하고 정렬. 2. 가장 낮은 두 그룹을 묶어서 하나의 그룹을 만들고 정렬.

12 Huffman Algorithm(3) 대상 문자열: CDDCACBCBCCCBBCDA
3. 가장 낮은 두 그룹을 묶어서 하나의 그룹을 만들고 정렬. 4. 가장 낮은 두 그룹을 묶어서 하나의 그룹을 만듬.(완성)

13 Huffman Algorithm(4) 대상 문자열: CDDCACBCBCCCBBCDA
5. 가장 윗 트리에서 부터 빈도수가 큰 트리에 0을, 작은 트리에 1을 부여. 압축 문자열: 17Byte -> 31bit (8Byte)

14 Q&A