데이터 압축 알고리즘 컴퓨터과학부 2003440134 조 산 컴퓨터과학부 2003920017 김형주
Contents 압축 알고리즘의 기초 Run – Length Algorithm Lempel – Ziv Algorithm Huffman Algorithm Demo
압축알고리즘의 기초 압축 알고리즘의 기본 아이디어는 반복적 패턴의 발 견과 그것의 부호화. 무손실 압축 알고리즘 RLE, LZ, Huffman… 손실 압축 알고리즘 MPEG, JPEG …
Run-Length Algorithm(1) 반복 길이 부호화(RLE, Run-Length encoding) 데이터에서 같은 값이 연속적으로 나타날 때, 그 개 수와 반복되는 값만으로 표현.
Run-Length Algorithm(2) <탈출문자, 반복문자, 개수>로 표현. 원래 문자열: ABAAAAABCBDDDDDDDABC 압축 문자열: AB*A5BCB*D7ABC ‘*’ 를 ESCAPE 문자로 사용 ESCAPE 문자는 출현빈도수가 가장 적은 문자로 선택.
Run-Length Algorithm(3) 알고리즘이 매우 단순함. 이미지 파일이나 exe파일처럼 똑같은 문자가 반복되 는 경우 매우 좋은 압축률. 똑같은 문자가 이어져 있지 않은 경우에는 압축률이 매우 떨어짐.
Lempel-Ziv Algorithm(1) 실제 상용에서 가장 많이 사용되는 매우 우수한 알고 리즘. LZ77, LZSS, LZ78, LZW 등 많은 변형이 존재.
Lempel-Ziv Algorithm(2) <탈출문자, 상대위치, 길이> 로 표현. 원래 문자열: ABCDEFGHIJKBCDEFJKLDM 압축 문자열: ABCDEFGHIJK<10,5>JKLDM 현재 패턴이 가까운 거리에 존재한다면, 그것에 대한 상대적 위치와 패턴의 길이를 기록. Sliding Window, Look Ahead Buffer를 이용. 실제로는 이 원리를 응용하여 구현. 정적 사전법(Static Dictionary) 동적 사전법(Dynamic Dictionary)
Lempel-Ziv Algorithm(3) 동적 사전법(Dynamic Dictionary)을 이용한 구현의 응용
Huffman Algorithm(1) 1952년 당시 박사과정 학생이던 David Huffman이 고안해낸 알고리즘. 데이터문자의 등장 빈도에 따라서 다른 길이의 부호 를 사용하는 알고리즘. MPEG 포맷의 형태에 쓰임. 우리가 자주 이용하는 ALZIP 또한 Huffman 방식으 로 한번 압축 후, Lempel 알고리즘으로 한번 더 압축 하는 방식.
Huffman Algorithm(2) Huffman Tree를 구축하여 문자를 부호화. 대상 문자열: CDDCACBCBCCCBBCDA 1. 각 문자열별로 빈도수를 체크하고 정렬. 2. 가장 낮은 두 그룹을 묶어서 하나의 그룹을 만들고 정렬.
Huffman Algorithm(3) 대상 문자열: CDDCACBCBCCCBBCDA 3. 가장 낮은 두 그룹을 묶어서 하나의 그룹을 만들고 정렬. 4. 가장 낮은 두 그룹을 묶어서 하나의 그룹을 만듬.(완성)
Huffman Algorithm(4) 대상 문자열: CDDCACBCBCCCBBCDA 5. 가장 윗 트리에서 부터 빈도수가 큰 트리에 0을, 작은 트리에 1을 부여. 압축 문자열: 1000000100110110111101011000001 17Byte -> 31bit (8Byte)
Q&A