브레슨햄 알고리즘의 기본은 '오차항'의 누적입니다. 즉, 컴퓨터 화면은 색깔이 칠해진 정사각형의 거대한 2차원 배열이라고 보면 됩니다. 이때, 직선(혹은 다른 도형)을 그린다는 행위는 실수로 구성된 연속 좌표계를 불연속좌표계로 '근사'하는 과정입니다. 따라서 하나의 점을 찍으면 직선의 원래 좌표와 화면에 찍힌 불연속 좌표 사이에 오차가 존재하게 마련이며, 직선(혹은 다른 도형)을 그려 가면서 이 오차를 최대로 작게 하는 점을 선택하는 것이 브레슨햄 알고리즘의 핵심 개념입니다.
브레슨햄 알고리즘으로 직선을 그리는 과정은,
1) 직선을 나타내는 두개의 점 p1, p2을 좌표순서로 정렬합니다. 이때, 직선의 기울기가 1보다 작으면 x축 방향으로 정렬하고, 1 보다 크면 y축 방향으로 정렬합니다. (단, 여기서는 x축방향으로 정렬한다고 가정하겠습니다)
2) 정렬된 점 중 첫번째 점부터 시작합니다.
3) 현재 위치에 점을 찍습니다.
4) 다음위치를 세팅합니다. 이때 x축 방향으로 현재 픽셀의 위치를 1증가시킵니다.
5) 다음위치의 오차값을 계산합니다. 이때 오차항은 p1,p2사이의 y좌표의 차이를 더합니다.
6) 오차항을 비교하여 이 오차분이 1개 픽셀보다 더 큰지를 검사합니다. 검사는 현재까지의 오차항과 p1,p2사이의 x좌표의 사이를 비교하여 오차항이 x좌표의 차이보다 크면 y축 방향으로 좌표를 1증가시킵니다.
7) 마지막 좌표를 찍을때까지 3)~6)과정을 반복합니다.
사각형을 그리는 과정은 브렌슨햄 알고리듬으로 직선4개를 그리는 과정을 반복하면 됩니다.
x^2 + y^2 = r^2으로 표현되는 원을 그리는 과정은 다음과 같습니다.
1) 원의 상단 정점으로부터 시작합니다. 이때, 시계방향으로 4분원을 그리고 이 4분원을 4번 반복하여 그리는 방법을 취하면 됩니다.
2) 현재 좌표에 점을 찍습니다.
3) x축방향으로 좌표를 1증가합니다.
4) 이제 y좌표를 결정합니다. y좌표는 y, 또는 y-1 둘중의 하나로 결정됩니다. 이때,
x^2 + (y-1)^2 < x^2 + y^2 < r^2 이 성립하면 y로 다음 좌표가 결정이 되며,
r^2 < x^2 + (y-1)^2 < x^2 + y^2 이 성립하면 y-1로 좌표가 결정됩니다.
그외의경우는 둘중 어떤 점을 선택해도 오차를 무시할 수 있습니다.
5) x==y가 될때까지 2)~4)의 과정을 반복합니다.
6) 원의 우측 정점으로부터 시작합니다.
7) 현재 좌표에 점을 하나 찍습니다.
8) y축방향으로 좌표를 1증가합니다.
9) 이제 x좌표를 결정합니다. x좌표는 x, 또는 x-1 둘 중의 하나로 결정됩니다. 이때,
(x-1)^2 + y^2 < x^2 + y^2 < r^2 이 성립하면 x가 다음 좌표가 되며,
r^2 < (x-1)^2 + y^2 < x^2 + y^2 이 성립하면 x-1이 다음 좌표가 됩니다.
그외의 경우는 둘 중 어떤 점을 선택해도 무방합니다.
10) x==y가 될때까지 7)~9)의 과정을 반복합니다.
타원을 그리는 알고리즘은 원의 경우와 유사하며, 방정식을 교체하고 축의 방향을 뒤집는 지점만 계산하여 적용하면 됩니다.
(Hamming Code)는 오류 검출후 오류 정정까지 가능한 것입니다.
해밍 코드는 R. W. Hamming에 의해 고안된 것이며, 데이터 비트에 따른 패리티 비트는
다음 수식에 의해 구해집니다.
2(p승) >= m + P + 1 (m은 데이터 비트값)
즉, 해밍코드에의해 구성된 코드가 16비트로 주어졌을 경우 2(p승)=16 이 되므로
p 값은 4가 되고 식에 의해서 16 >= m+ 4 + 1 이므로 m = 11 이 됩니다..
즉 데이터 비트값 : 11비트, 패리티 비트 : 5(4+1계산)비트 가 되는거겠죠?
이젠 본격적으로 해밍코드의 신기한 오류 검출방식을 보도록 하죠..
해밍코드는 정해진 위치의 패리티를 검색한후 오류체크를 하게되고 잘못된 위치를 찾아내게
됩니다.. 그럼.. 아래의 C1, C2, C4 를 가지고 5의 해밍코드를 우선 구해보겠습니다.
* C1 : 행 1, 3, 5, 7 짝수 패리티 체크
* C2 : 행 2, 3, 6, 7 짝수 패리티 체크
* C4 : 행 4, 5, 6, 7 짝수 패리티 체크
위의 C1, C2, C4 행의 각 셀에 들어있는 수를 비교하여 1의 개수를 짝수로 만들어 줘야
합니다... 10진수 5의 해밍코드를 구해봅시다. 10진수 5는 이진수로 0101 입니다
그럼.. 아래 그림처럼.. 8 4 2 1 위치에 순서대로 0 1 0 1 이 들어가겠죠?
|
C1 |
C2 |
8 |
C4 |
4 |
2 |
1 |
|
0 |
1 |
0 |
1 |
우선 C1을 비교해보면.. C1은 1,3,5,7 을 비교하라고 했죠? 그럼.. C1,8,4,1 자리의 값들을
비교해보면.. C1은 값이 없고 8,4,1자리의 값이 0,1,1 이기때문에 1의 개수가 짝수가 되려면
C1값에는 0이 들어가면 되겠죠?
다음으로 C2는 2,3,6,7을 비교하라고 했으니 C2,8,2,1자리의 값들을 비교해 보면
C2는 빈값 8,2,1 자리 값들이 0,0,1 이므로 1의 개수가 짝수가 되려면 C2값이 1이 되야
합니다.. C4역시 다음과 같이 하면...
|
C1 |
C2 |
8 |
C4 |
4 |
2 |
1 |
|
0 |
1 |
0 |
0 |
1 |
0 |
1 |
위와같은 5의 해밍코드를 얻을 수 있습니다..
여기까지 알았으면 이젠 해밍코드가 어떤식으로 오류를 검출해서 변경하는지 알아야 겠죠?
만일... 5라는 데이터 값에 잘못된 값이 들어갔을 경우..
▶ 제대로된 해밍코드
|
C1 |
C2 |
8 |
C4 |
4 |
2 |
1 |
|
0 |
1 |
0 |
0 |
1 |
0 |
1 |
▶ 잘못된 해밍코드
|
C1 |
C2 |
8 |
C4 |
4 |
2 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
값을 보면.. 4라는 위치의 값이 1이 되야 하는데 아래 그림에서보면
0이 들어갔죠??
그럼.. 잘못된 이 해밍코드를 봅시다. 위에서 비교한것 처럼 C1,C2,C4의
자리를 비교해 보죠
C1 : 1,3,5,7 자리값 비교해 보면 1의 개수가 1개 입니다. 짝수가 아니므로 오류값 C1=1
C2 : 2,3,6,7 자리값 비교해 보면 1의 개수가 2개 입니다. 짝수이므로 이상없음 C2=0
C4 : 4,5,6,7 자리값 비교해 보면 1의 개수가 1개 입니다. 짝수가 아니므로 오류값 C4=1
즉, C1=1, C2=0, C4=1 이라는 오류값이 나왔죠? 그럼 이것을 C4 / C2 / C1 순서로 나열해
보시면 1 / 0 / 1 이라고 나오죠? 그럼 이진수 101을 10진수로 고치면? 5라는 수가
나옵니다.. 아래 그림처럼 4라는 위치가 앞에서 부터 5번째 칸이죠??
즉, 5번째 자리의 값이 잘못되었다는 오류를 찾아내게 됩니다.
▶ 제대로된 해밍코드
|
C1 |
C2 |
8 |
C4 |
4 |
2 |
1 |
|
0 |
1 |
0 |
0 |
1 |
0 |
1 |
▶ 잘못된 해밍코드
|
C1 |
C2 |
8 |
C4 |
4 |
2 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
컴퓨터는 0과 1이라는 수만인식하기 때문에 0의 값이 잘못되었다고 인식하게되면
0의 값을 1이라고 자동으로 변환하게 됩니다.. 그럼.. 제대로된 해밍코드가 스스로 수정이
되겠죠??
이쯤에서 Tip을 하나 알려드리겠습니다..
이 부분은 설명이 된부분을 아직 제가 못봐서 대부분이 잘 모르고 있지 않을까 싶어서
제가 혼자서 알게된 방법이라서 혹시나 틀린부분이 있더라도 이해해 주시고 쪽지 날려주세요
왜? 아래와 같이 꼭~ 저런 자리를 체크해야하는가?
* C1 : 행 1, 3, 5, 7 짝수 패리티 체크
* C2 : 행 2, 3, 6, 7 짝수 패리티 체크
* C4 : 행 4, 5, 6, 7 짝수 패리티 체크
쉽게 설명하죠.. C 뒤에 붙어있는 숫자들은.. 2(0승)=1, 2(1승)=2, 2(2승)=4
입니다. 그럼.. 여러분이 1,2,4 라는 카드를 각각 몇장씩 들고있다고 생각해 보세요..
그리고 나서 자기 자신의 카드와 합치지 않고 서로 다른 카드와 합쳤을때 만들어지는 수를
만들어 봅시다..
1이라는 숫자를 맞들수 있는것은 단지 1카드 한장밖에 없습니다.. 또한 2라는 숫자를
만들수 있는 카드는 2라는 카드 1장 밖에 없습니다.. 그럼 우선 아래와 같이 써주세요..
* C1 카드자리 : 1
* C2 카드자리 : 2
* C4 카드자리 :
그럼.. 이번엔 3을 만들려면 1이란 카드와 2란 카드가 필요하겠죠? 그럼 1카드 자리와
2카드 자리에 3이라는 값을 써주세요.. 그리고 4를 만들수 있는 카드는 4카드 밖에 없습니다
그럼 다음과 같이 되겠죠?
* C1 카드자리 : 1, 3
* C2 카드자리 : 2, 3
* C4 카드자리 : 4
위와 같이 계속 해보면.. 5는 1과 4카드 자리에 위치하게 되고 6은 2와4 카드자리에 위치,
7은 1,2,4 모든 카드자리에 들어가게 되어서 비로소 아래와 같이 완성이 된다.
* C1 : 행 1, 3, 5, 7 짝수 패리티 체크
* C2 : 행 2, 3, 6, 7 짝수 패리티 체크
* C4 : 행 4, 5, 6, 7 짝수 패리티 체크
이것은.. 그냥.. 혼자서 끄적대다가 규칙적인게 발견이 되어서 이해하기 쉽기에 제가 기술
한것이고.. 좀 더 정확히 알아 봅시다...
|
10진수 |
2진수 | ||
|
c4 |
c2 |
c1 | |
|
1 |
0 |
0 |
1 |
|
2 |
0 |
1 |
0 |
|
3 |
0 |
1 |
1 |
|
4 |
1 |
0 |
0 |
|
5 |
1 |
0 |
1 |
|
6 |
1 |
1 |
0 |
|
7 |
1 |
1 |
1 |
위의 표를 보시면 왼쪽의 10진수를 우측에 해당되는 2진수로 변형시켜 놓았습니다..
아까 위에서 오류가 없는 부분은 0 오류가 있는 부분은 1 이었다는걸 기억해 보십시오
그럼 바로 위에 있는 표를 보듯이 C1은 1이라는 값들이 1,3,5,7 이란 위치에만 1이있고
C2는 2,3,6,7 이란 위치에 C4는 4,5,6,7이란 위치에만 1이있다는것을 한눈에 확인할 수
있다.
< 목 차 >
1 Prologue 3
2 Introduction 4
3 Run-Length 6
3.1 Run-Length 압축 알고리즘 6
3.2 Run-Length 압축 복원 알고리즘 10
3.3 Run-Length 압축 알고리즘 전체 구현 11
4 Lempel-Ziv 19
4.1 Lempel-Ziv 압축 알고리즘 19
4.2 Lempel-Ziv 압축 복원 알고리즘 26
4.3 Sliding Window를 이용한 Lempel-Ziv 알고리즘의 구현 27
5 Variable Length 39
6 Huffman Tree 43
6.1 Huffman 압축 알고리즘 51
6.2 Huffman 압축 복원 알고리즘 56
6.3 Huffman 압축 알고리즘 구현 60
7 JPEG (Joint Photographic Experts Group) 72
7.1 JPEG이란 72
7.2 다른 기술과의 비교 72
7.3 압축 방법 73
7.4 Baseline 압축 알고리즘 75
7.5 JPEG의 실제 압축 / 복원 과정 76
7.6 확장 JPEG 79
8 MPEG (Moving Picture Expert Group) 80
8.1 MPEG의 개념 80
8.2 MPEG의 표준 81
8.2.1 MPEG 1 81
8.2.2 MPEG 2 82
8.2.3 MPEG 4 83
8.3 MPEG의 기본적인 압축 원리 84
8.3.1 시간,공간의 중복성 제거 84
8.3.2 I,P,B영상 86
9 Conclusion 87
< 그 림 목 차 >
<그림 3‑1> Run-Length 압축 알고리즘 10
<그림 3‑2> 압축 파일 헤더 구조 12
<그림 4‑1> 슬라이딩 윈도우와 해시테이블 22
<그림 5‑1> 8비트에서 7비트로 줄이는 압축 알고리즘 39
<그림 5‑2> 문자 코드의 재구성 40
<그림 5‑3> <그림 5‑2>코드의 기수 나무 41
<그림 5‑4> 문자 코드의 재구성 41
<그림 6‑1> 빈도수 계산 44
<그림 6‑2> 허프만 나무 구성과정 48
<그림 6‑3> 허프만 나무에서 얻어진 코드 51
<그림 6‑4> code[]와 len[]의 저장 55
<그림 7‑1> JPEG Encoding / Decoding 단계 76
<그림 7‑2> RGB의 YIQ 변환식 77
1 Prologue
지금 생각하면 우스운 일이지만 몇 년 전만 하더라도 28800bps의 모뎀을 굉장히 빠른 통신 장비로 알고 있었다. 그러다가 56600bps의 모뎀이 발표되었을 때는 전화선의 한계를 뛰어 넘은 대단한 물건이라고 다들 놀라와 했다. 내 경우에도 56600bps 모뎀을 구입해서 처음 사용하던 날 감격의 눈물을 흘렸을 정도였으니..
전화로 통신을 하던 그 당시 사람들의 생각은 다들 비슷했을 것이다. 어떻게 하면 같은 내용의 자료를 더 짧은 시간에 전송할 수 있을까. 통신속도가 점차 빨라지면서(처음에 사용하던 2400bps에 비하면 거의 20배 이상의 속도 향상이었다.) 이런 고민은 줄어들 것이라 생각했지만, 그런 고민은 오히려 더 커져 만 갔다. 속도가 빨라지는 것보다 사람들이 주고받는 자료의 전송 량이 더 크게 증가한 것이다. 이럴 수록 더 강조되던 것이 바로 [압축] 이었다.
파일 압축이라고 하면 winzip, alzip 등을 생각할 것이다. 이런 종류의 프로그램들은 임의의 파일을 원래의 크기보다 작은 크기로 압축시켰다가 필요할 때 다시 원래대로 한치의 오차도 없이 복구 시켜 준다.
하지만 압축이란 것이 모두 앞에서 언급한 프로그램들처럼 원본을 그대로 복원해줄 수 있는 것이 아니다. 때에 따라서는 원본으로의 복원이 불가능한 압축 방법들이 유용하게 사용될 상황도 존재한다.
전자의 경우를 ‘비손실 압축’, 후자의 경우를 ‘손실 압축’ 이라고 하는데, 이 자료에서는 모든 압축의 근간이 되는 간단한 압축 알고리즘들을 살펴볼 것이고 뒤에 손실 압축의 대표적인 MPEG에 대해서 다룰 것이다.
이제 우리는 압축의 세계로 들어간다.
2 Introduction
우리가 보통 살펴보는 알고리즘들은 대부분이 시간을 절약하기 위한 목적을 가지고 개발된 것 들이다. 하지만, 우리가 지금부터 살펴볼 알고리즘들은 공간을 절약하기 위한 목적을 가진 알고리즘이다.
압축알고리즘이 처음으로 대두되기 시작한 것은 컴퓨터 통신 때문이었다. 컴퓨터 통신에서는 시간이 곧바로 돈으로 연결된다(적어도 model을 사용하던 시절에는 그랬다). 예를 들어 1MByte의 파일을 다운로드 받으려면 28,800bps 모뎀을 사용하면 약 6분, 56,600bps 모뎀을 사용하더라도 약 3분 이상의 시간이 소요됐었다. 하지만 이 파일을 전송 전에 미리 1/2로만 압축할 수 있다면 전송시간 역시 1/2로 줄어들 것이다. 즉, 통신 비용 역시 1/2로 줄어든다는 것이다.
압축 알고리즘은 크게 두 부류로 나뉜다. 비손실 압축(Non-lossy Compression)과 손실 압축(Lossy Compression)이 그것인데 말 그대로 비손실 압축은 압축했다가 다시 복원할 때 원래대로 파일이 복구된다는 뜻이고, 손실 압축은 복원할 때 100% 원래대로 복구되지 않는다는 뜻이다.
일반적으로 PC사용자들이 사용하는 압축프로그램들은 모두 비손실 압축을 지원한 프로그램들이다. 그렇다면 손실 압축은 어떤 경우에 사용하는 것일까?
확장자가 exe나 com으로 끝나는 실행파일이나, 기타 한 바이트만 바뀌더라도 프로그램 실행에 지장을 주는 파일들은 반드시 비손실 압축을 해야 한다. 그러나 그림 파일이나 동화상처럼 눈으로 보는 것에 지나지 않는 파일의 경우 약간의 손실이 있어도 무방하다.
일반적으로 손실 압축이 비손실 압축에 비해서 압축률이 훨씬 좋기 때문에 손실 압축도 또한 큰 중요성을 가지고 있다. 요즘 화제가 되고 있는 JPEG(정지 화상 압축 기술, Joint Photographic Expert Group), MPEG(동화상 압축 기술, Moving Picture Expert Group) 등도 대표적인 손실 압축법으로 주목 받고 있는 것들이다.
압축 알고리즘은 그 중요성으로 인해 오랫동안 연구되어 왔고, 많은 알고리즘이 있다. 가장 대표적인 압축 알고리즘은 Run-Length 압축법으로 동일한 바이트가 연속해 있을 경우 이를 그 바이트와 몇 번 반복되는지 수치를 기록하는 방법이다. 그러나 Run-Length 압축법은 간단함에 대한 대가로 압축률이 그다지 좋지 않아서 다른 방법들이 연구되어 왔다.
그래서 실제로 구현되는 압축 방법은 이 절에서 소개하는 Huffman 압축법과 Lempel-Ziv 압축법이다. 가변길이 압축법은 한 바이트가 8비트라는 고정 관념을 깨고, 각각을 다른 비트로 압축하는 방법이고, 그 중에서도 Huffman 압축법은 빈도가 높은 바이트는 적은 비트수로, 빈도가 낮은 바이트는 많은 비트수로 그 표현을 재정의하여 파일을 압축한다.
반면에 Lempel-Ziv법은 그 변종이 여러 개 있지만 가장 효율적인 동적 사전(Dynamic Dictionary)을 이용한 방법을 주로 사용한다. 동적 사전법은 파일에서 출현하는 단어(Word)들을 2진 나무(Binary Tree)나 해시를 이용한 검색 구조에 삽입하여 동적 사전을 구성한 다음, 이어서 읽어진 단어가 동적 사전에 수록되어 있으면 그에 대한 포인터를 그 내용으로 대체하는 방법으로 압축을 행한다. 주로 사용하는 ZIP 등도 Huffman 압축법이나 Lempel-Ziv 압축법 중 하나를 사용하거나 또는 둘 다 사용하거나, 혹은 그 응용을 사용한다.
3 Run-Length
3.1 Run-Length Encoding
Run-Length 압축법은 동일한 문자가 이어서 반복되는 경우 그것을 문자와 개수의 쌍으로 치환하는 방법이다. 예를 들어 다음의 문자열은 Run-Length 압축법으로 쉽게 압축될 수 있다.
원래 문자열 : ABAAAAABCBDDDDDDDABC
압축 문자열 : ABA5BCBD7ABC
개념적으로는 위와 같이 간단하지만 개수로 사용된 5나 7이라는 문자가 개수의 의미인지 아니면 그냥 문자인지를 판별하는 방법이 없다. 만일 압축할 파일이 알파벳 문자만을 사용한다면 위와 같은 압축이 그대로 사용 가능할 것이다. 그러나 일반적으로 0부터 255까지의 모든 문자가 사용된 파일을 압축한다면 단순한 위의 방법으로는 압축이 불가능하다.
그래서 탈출 문자(Escape Code)라는 것을 사용한다. 문자가 반복되는 모양을 압축할 때 <탈출 문자, 반복 문자, 개수>와 같이 표현한다. 예를 들어 탈출 문자를 ‘*’라고 한다면 위의 문자열은 다음처럼 압축 될 수 있다.
원래 문자열 : ABAAAAABCBDDDDDDDABC
압축 문자열 : AB*A5BCB*D7ABC
탈출 문자에서 탈출의 의미는 보통의 경우에서 벗어남을 말한다. 즉 탈출 문자 ‘*’가 나오기 전에는 단순한 문자열이지만 이 탈출 문자가 나오면 그 다음의 반복 문자와 그 다음의 개수를 읽어 들여서 반복 문자를 개수만큼 늘여 해석하면 된다.
또 한가지 남은 문제가 있다. 그것은 탈출 문자가 탈출의 의미로 해석되는 것이 아니라 문자로서 해석되어야 할 경우도 있다는 점이다. 이것은 마치 printf() 함수의 서식 문자열에서 ‘%’와 유사하다. %d나 %f는 그 문자를 의미하는 것이 아니라 정수나 실수형으로 대치될 부분이라는 표시이다. 즉 %가 탈출의 의미를 가지고 있다는 뜻이다. 그러나 정작 ‘%’라는 문자를 출력하기 위해서는 어떻게 해야 하는가?
C에서는 ‘%’를 출력하기 위해서 ‘%%’를 사용한다. 마찬가지로 Run-Length 압축법에서도 탈출 문자 ‘*’를 문자로 해석하기 위해서 ‘**’를 사용하면 될 것이다.
그렇다면 ‘*’ 문자가 계속해서 반복되는 경우는 어떻게 해야 하는가? 이 문제는 상당히 복잡하다. 만일 ‘*****’와 같은 문자열의 일부분이 있다면 ‘**5’와 같이 압축할 수 있는가? 아니면 ‘***5’와 같이 압축하는가? 둘 다 문제가 있다. 전자의 경우 ‘*5’와 같이 해석할 수 있으며, 후자의 경우는 ‘*’문자와 5 다음의 문자가 있다면 이를 개수로 해석해서 5를 반복하는 것으로 해석할 수 있다.
이렇게 탈출 문자가 반복되는 경우 그것을 <탈출 문자 반복 문자 개수>의 표현으로 나타내면 모호하게 되므로 탈출 문자자의 경우는 아무리 반복 횟수가 많더라도 단순하게 <탈출 문자, 탈출 문자>와 같이 압축한다(실제로는 더 길어지지만).
원래 문자열 : ABCAAAAABCDEBBBBBFG*****ABC
압축 문자열 : ABC*A5BCDE*B5FB**********ABC
이러한 이유로 탈출 문자 ‘*’는 가장 출현 빈도수가 적은 문자를 택해야 한다. 왜냐하면 탈출 문자가 문자로 해석되는 경우에는 그 길이가 두 배로 늘어나기 때문이다. 이 출현 빈도수라는 것이 사실 모호하기 짝이 없지만 일단은 영어의 알파벳이나 기호, 탭 문자(0x09), 라인 피드(0x0A), 캐리지 리턴(0x0D) 그리고 널문자(0x00)와 같은 코드들은 매우 많이 사용되기 때문에 피해야 한다. 따라서, 압축하는 파일에 따라 탈출 문자를 적절히 조정해 주면 압축 효율을 높일 수 있을 것이다.
그렇다면 과연 몇 개의 문자가 반복되었을 때 <탈출 문자, 반복 문자, 개수>로 치환할 것인가 하는 문제를 결정하자. ‘AA’처럼 두 문자가 반복되었다면 ‘*A2’로 하는 것은 두 바이트가 3바이트로 늘어나게 되므로 치환하지 말아야 할 것이다. 그렇다면 ‘AAA’와 같이 세 문자가 반복된다면 ‘*A3’으로 하는 것은 똑같이 세 바이트가 소요되므로 치환을 하든 하지 않든 변화가 없다. 따라서 같은 문자가 최소 3번 이상 반복되는 경우에만 치환을 하도록 한다.
그리고 개수를 나타내는 것 또한 1Byte를 사용하기 때문에 반복되는 문자의 개수는 255 이상이 될 수 없다. 만약 255개를 넘어버린다면 254에서 한번 잘라주고, 그 다음은 문자가 처음 나온 것으로 생각하면 된다.
위와 같은 방법으로 구현된 Run-Length 알고리즘은 다음과 같다.
<Run-Length 압축 알고리즘(FILE *src)
{
char code[10]; /* 버퍼 */
cur = getc(src); /* 입력 파일에서 한 바이트 읽음 */
code_len = length = 0;
while(!feof(src))
{
if (length == 0) /* code[]에 아무 내용이 없으면 */
{
if (cur != ESCAPE)
{
code[code_len++] = cur;
length++;
}
else /* 탈출 문자이면 <탈출문자 탈출문자>로 대체 */
{
code[code_len++] = ESCAPE;
code[code_len++] = ESCAPE;
flush(code); /* 출력 파일에 써넣음 */
length = code_len = 0;
}
cur = getc(src);
}
else if (length == 1) /* 반복 횟수가 1 이었으면 */
{
if (cur != code[0]) /* 읽은 문자가 버퍼의 문자와 다르면 */
{
flush(code); /* 버퍼의 내용을 출력 */
length = code_len = 0;
}
else /* 읽은 문자가 버퍼의 문자와 같으면 */
{
length++;
code[code_len++] = cur; /* 'A' -> 'AA' */
cur = getc(src);
}
}
else if (length == 2) /* 반복 횟수가 2 이면 */
{
if (cur != code[1]) /* 읽은 문자가 버퍼의 문자와 다를 경우 */
{
flush(code); /* 버퍼의 내용을 출력 */
length = code_len = 0;
}
else /* 읽은 문자가 버퍼의 문자와 같으면 */
{
length++;
code_len = 0;
code[code_len++] = ESCAPE; /* 'AA' -> '*A3' */
code[code_len++] = cur;
code[code_len++] = length;
cur = getc(src); /* 다음 문자를 읽음 */
}
}
else if (length > 2) /* 반복 횟수가 3 이상이면 */
{
if (cur != code[1] || length > 254)
{ /* 읽은 문자 != 버퍼의 문자 or 반복 횟수 > 255 */
flush(code); /* 버퍼의 내용 출력 */
length = code_len = 0;
}
else /* 읽은 문자가 버퍼의 문자와 같으면 */
{
code[code_len-1]++; /* 반복 횟수만 증가 */
length++;
cur = getc(src); /* 다음 문자를 읽음 */
}
}
}
flush(code); /* 버퍼의 내용을 출력 */
}
<그림 3‑1> Run-Length 압축 알고리즘
3.2 Run-Length Decoding
압축을 하고 나면 다시 복원을 하는 알고리즘도 있어야 할 것이다. Run-Length 압축법의 복원은 상당히 단순하다. 파일을 읽으면서 탈출 문자가 없으면 그대로 두면 되고, 탈출 문자를 만난다면, 다음 글자를 하나 더 읽어봐서 다시 탈출 문자가 나오면 탈출 문자를 그대로 기록하고, 숫자가 나오면 탈출 문자 전의 문자를 그 숫자만큼 반복해서 적으면 된다.
위와 같은 방법으로 구현된 Run-Length 압축 복원 알고리즘은 다음과 같다.
<Run-Length 압축 풀기 알고리즘(FILE *src)>
{
int cur;
FILE *dst;
int j;
int length;
dst = fopen(출력파일);
cur = getc(src);
while (!feof(src))
{
if (cur != ESCAPE) /* 탈출 문자가 아니면 */
putc(cur, dst);
else /* 탈출 문자이면 */
{
cur = getc(src);
if (cur == ESCAPE) /* 그 다음 문자도 탈출 문자이면 */
putc(ESCAPE, dst);
else /* 길이만큼 반복 */
{
length = getc(src);
for (j = 0; j < length; j++)
putc(cur, dst);
}
}
cur = getc(src);
}
fclose(dst);
}
3.3 Run-Length 압축 알고리즘 전체 구현
실제로 압축된 파일의 복원을 위해서는 몇 가지 추가적인 정보가 필요하다. 그것은 복원하려는 파일이 과연 Run-Length 압축 알고리즘에 의한 것인지를 판별하는 식별 코드와 복원할 파일의 원래 이름이다. 이 두 정보는 압축할 때 압축 파일의 선두(헤더)에 기록되어 있어야 한다.
Run-Length 압축 알고리즘의 식별 코드는 편의상 0x11과 0x22로 했고, 이어서 원래 파일의 이름이 나오고, 끝을 나타내는 NULL문자가 이어진다. 다음은 이 헤더의 구조를 나타낸 그림이다.
<그림 3‑2> 압축 파일 헤더 구조
이상으로 Run-Length 압축 알고리즘에 대한 설명을 마친다. Run-Length 알고리즘은 알고리즘이 단순할 뿐만 아니라 이미지 파일이나 exe 파일처럼 똑같은 문자가 반복되는 경우 매우 좋은 압축률을 보여준다. 그러나 똑같은 문자가 이어져 있지 않은 경우에는 압축률이 매우 떨어지는 단점이 있다.
위와 같은 방법으로 구현된 전체 Run-Length 알고리즘은 다음과 같다.
/* */
/* RUNLEN.C : Compression by Run-Length Encoding */
/* */
#include <stdio.h>
#include <string.h>
#include <dir.h>
#include <time.h>
#include <stdlib.h>
/* 탈출 문자 */
#define ESCAPE 0xB4
/* Run-Length 압축법에 의한 것임을 나타내는 식별 코드 */
#define IDENT1 0x11
#define IDENT2 0x22
/* srcname[]에서 파일 이름만 뽑아내어서 그것의 확장자를 rle로 바꿈 */
void make_dstname(char dstname[], char srcname[])
{
char temp[256];
fnsplit(srcname, temp, temp, dstname, temp);
strcat(dstname, ".rle");
}
/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
long file_length(char filename[])
{
FILE *fp;
long l;
if ((fp = fopen(filename, "rb")) == NULL)
return 0L;
fseek(fp, 0, SEEK_END);
l = ftell(fp);
fclose(fp);
return l;
}
/* code[] 배열의 내용을 출력함 */
void flush(char code[], int len, FILE *fp)
{
int i;
for (i = 0; i < len; i++)
putc(code[i], fp);
}
/* Run-Length 압축 함수 */
void run_length_comp(FILE *src, char *srcname)
{
int cur;
int code_len;
int length;
unsigned char code[10];
char dstname[13];
FILE *dst;
make_dstname(dstname, srcname);
if ((dst = fopen(dstname, "wb")) == NULL) /* 출력 파일 오픈 */
{
printf("\n Error : Can't create file.");
fcloseall();
exit(1);
}
/* 압축 파일의 헤더 작성 */
putc(IDENT1, dst); /* 출력 파일에 식별자 삽입 */
putc(IDENT2, dst);
fputs(srcname, dst); /* 출력 파일에 파일 이름 삽입 */
putc(NULL, dst); /* NULL 문자 삽입 */
cur = getc(src);
code_len = length = 0;
while (!feof(src))
{
if (length == 0)
{
if (cur != ESCAPE)
{
code[code_len++] = cur;
length++;
}
else
{
code[code_len++] = ESCAPE;
code[code_len++] = ESCAPE;
flush(code, code_len, dst);
length = code_len = 0;
}
cur = getc(src);
}
else if (length == 1)
{
if (cur != code[0])
{
flush(code, code_len, dst);
length = code_len = 0;
}
else
{
length++;
code[code_len++] = cur;
cur = getc(src);
}
}
else if (length == 2)
{
if (cur != code[1])
{
flush(code, code_len, dst);
length = code_len = 0;
}
else
{
length++;
code_len = 0;
code[code_len++] = ESCAPE;
code[code_len++] = cur;
code[code_len++] = length;
cur = getc(src);
}
}
else if (length > 2)
{
if (cur != code[1] || length > 254)
{
flush(code, code_len, dst);
length = code_len = 0;
}
else
{
code[code_len-1]++;
length++;
cur = getc(src);
}
}
}
flush(code, code_len, dst);
fclose(dst);
}
/* Run-Length 압축을 복원 */
void run_length_decomp(FILE *src)
{
int cur;
char srcname[13];
FILE *dst;
int i = 0, j;
int length;
cur = getc(src);
if (cur != IDENT1 || getc(src) != IDENT2) /* Run-Length 압축 파일이 맞는지 확인 */
{
printf("\n Error : That file is not Run-Length Encoding file");
fcloseall();
exit(1);
}
while ((cur = getc(src)) != NULL) /* 헤더에서 파일 이름을 얻음 */
srcname[i++] = cur;
srcname[i] = NULL;
if ((dst = fopen(srcname, "wb")) == NULL)
{
printf("\n Error : Disk full? ");
fcloseall();
exit(1);
}
cur = getc(src);
while (!feof(src))
{
if (cur != ESCAPE)
putc(cur, dst);
else
{
cur = getc(src);
if (cur == ESCAPE)
putc(ESCAPE, dst);
else
{
length = getc(src);
for (j = 0; j < length; j++)
putc(cur, dst);
}
}
cur = getc(src);
}
fclose(dst);
}
void main(int argc, char *argv[])
{
FILE *src;
long s, d;
char dstname[13];
clock_t tstart, tend;
/* 사용법 출력 */
if (argc < 3)
{
printf("\n Usage : RUNLEN <a or x> <filename>");
exit(1);
}
tstart = clock(); /* 시작 시각 기록 */
s = file_length(argv[2]); /* 원래 파일의 크기를 구함 */
if ((src = fopen(argv[2], "rb")) == NULL)
{
printf("\n Error : That file does not exist.");
exit(1);
}
if (strcmp(argv[1], "a") == 0) /* 압축 */
{
run_length_comp(src, argv[2]);
make_dstname(dstname, argv[2]);
d = file_length(dstname); /* 압축 파일의 크기를 구함 */
printf("\nFile compressed to %d%%", (int)((double)d/s*100.));
}
else if (strcmp(argv[1], "x") == 0) /* 압축의 해제 */
{
run_length_decomp(src);
printf("\nFile decompressed & created.");
}
fclose(src);
tend = clock(); /* 종료 시각 기록 */
printf("\nTime elapsed %d ticks", tend - tstart); /* 수행 시간 출력 : 단위 tick */
}
3.4 실행 결과
filetype Run-Length
random-bin 100.59
random-txt 100.24
wave 98.20
pdf 99.03
text(big) 85.04
text(small) 98.71
sql 96.78
Run-Length 알고리즘의 특성 때문에 Random 파일에 대해서는 오히려 파일 크기가 증가하는 결과가 나타났다. 다른 경우에는 조금씩 압축이 되었으며, 크기가 큰 텍스트 파일에 대해서는 상당히 많은 압축이 되었다. 이것은 텍스트 파일에 들어있는 연속된 Space나 Enter 등을 압축 한 것으로 해석된다. SQL 역시 Space가 많아서 압축이 되었을 것이라 생각한다.
4 Lempel-Ziv
4.1 Lempel-Ziv Encoding
Run-Length 압축 알고리즘도 실제로 많이 사용되지만, 이 절에서 소개하는 Lempel-Ziv 알고리즘 또한 실제에서 가장 많이 사용되는 매우 우수한 압축 알고리즘이다.
Run-Length 알고리즘은 똑같은 문자가 반복되는 경우 그것을 <탈출 문자, 반복 문자, 반복 횟수>로 치환하는 방법이었다. 이와 유사하게 Lempel-Ziv 압축법은 현재의 패턴이 가까운 거리에 존재한다면 그것에 대한 상재적 위치와 그 패턴의 길이를 구해서 <탈출 문자, 상대 위치, 길이>로 패턴을 대치하는 방법이다.
원래 문자열 : ABCDEFGHIJKBCDEFJKLDM
압축 문자열 : ABCDEFGHIJK<10,5>JKLDM
위의 그림을 보면, 원래 문자열에서 ‘BCDEF’라는 패턴이 뒤에 다시 반복된다. 이 때 뒤의 패턴을 <10,5>와 같이 10문자 앞에서 5문자를 취하라는 코드를 삽입함으로써 압축할 수 있고, 그 반대로 복원 할 수도 있다.
이렇게 떨어진 두 패턴뿐만 아니라 서로 겹쳐있는 패턴에 대해서도 이런 표현이 가능하다.
원래 문자열 : CDEFABABABABABAJKL
압축 문자열 : CDEFAB<2,9>JKL
원래 문자열 : CDEFAAAAAAAJKL
압축 문자열 : CDEFA<1,7>JKL
두 번째 예를 보면 Lempel-Ziv 압축법은 Run-Length 압축법과 마찬가지로 동일한 문자의 반복에 대해서도 Run-Length 압축법과 비슷한 압축률을 보임을 알 수 있다. 게다가 첫 번째와 같이 동일한 패턴이 반복되는 경우 Run-Length로는 압축하기 곤란하지만 Lempel-Ziv 압축법에서는 간단하게 압축된다.
이렇게 간단한 원리는 Lempel-Ziv 압축법은 그 실제 구현에서 여러 가지 다양한 방법이 있다. 가장 대표적인 방법은 정적 사전(Static Dictionary)법과 동적 사전(Dynamic Dictionary)법이다.
정적 사전법은 출현될 것으로 예상되는 패턴에 대한 정적 테이블을 미리 만들어 두었다가 그 패턴이 나올 경우 정적 테이블에 대한 참조를 하도록 하여 압축하는 방법이다.
이 방법은 압축하고자 하는 파일의 내용이 예상 가능한 경우에 매우 좋은 방법이다. 예를 들어 C의 소스 파일만을 압축하고자 할 경우 C의 예약어와 출현 빈도가 높은 식별자(Identifier)에 대해 테이블을 미리 만들어 둔다면 매우 높은 효율과 빠른 속도의 압축을 할 수 있을 것이다. 그러나 임의의 파일을 압축하고자 할 때에는 그 효율을 장담하지 못한다.
동적 사전법은 파일을 읽어들이는 과정에서 패턴에 대한 사전을 만든다. 즉 동적 사전법에서 패턴에 대한 참조는 이미 그전에 파일 내에서 출현한 패턴에 한한다. 동적 사전법은 파일을 읽어들이면서 사전을 구성해야 하는 부담이 생기기 때문에 속도가 느리다는 단점이 있으나, 임의의 파일에 대해 압축률이 좋은 경우가 많다.
우리는 정적 사전법은 동적 사전법과 별로 다를 것이 없으므로 동적 사전법만 다루기로 한다.
동적 사전법을 실제로 구현하는데 있어 가장 중요한 자료 구조는 Sliding Window이다. Sliding Window는 전체 파일의 일부분을 FIFO(First In First Out) 구조의 메모리에 유지하고 있는 것을 의미한다. 그리고 이 Sliding Window는 파일에서 문자를 읽을 때마다 파일 내에서의 상대 위치가 끝 쪽으로 전진하게 된다.
그리고 Sliding Window는 윈도우 내의 어떤 부분에 원하는 패턴이 있는지 찾아낼 수 있는 검색 구조까지 갖추고 있어야 한다.
Sliding Window의 FIFO 구조 때문에 가장 적절하게 사용될 수 있는 구조는 원형 큐(Circular Queue)이다. 그리고 Sliding Window의 검색 구조는 주로 해쉬(Hash)나 2진 나무(Binary Tree)를 사용한다.
일반적으로 FIFO 구조(Sliding Window)의 크기는 압축률에 상당한 영향을 미치며, 검색 구조는 압축 속도에 큰 영향을 미친다. 즉 Sliding Window가 크면 동적 사전이 그만큼 더 방대하게 구성되어서 패턴을 찾아낼 확률이 크게 되고, 검색 구조가 효율적일수록 패턴을 빨리 찾아내기 때문이다.
이 자료에서 작성할 Lempel-Ziv 압축법은 원형 큐와 한 문자에 대한 해시(연결법)로 패턴을 찾아낸다.
설명을 위해 다음 그림을 보자
<그림 4‑1> Sliding Window와 해시테이블
<그림 4‑1> (가) 그림은 큐 queue[]의 모양을 보여준다. 큐에는 압축할 파일에서 문자를 하나씩 읽어서 저장해 놓는다. front는 큐의 get() 명령 시 빠져나올 원소의 위치이고, rear는 큐의 put() 명령 시 새 원소가 들어갈 위치를 의미한다. 그리고 cp는 찾고자 하는 패턴이고, sp는 cp위치에 있는 패턴과 일치하는 앞쪽의 패턴 위치를 저장하고 있다. 그리고 length는 일치한 패턴의 길이를 의미하고 (가) 그림에서는 5가 된다.
(나) 그림은 해시 테이블 jump_table[]의 모습이다. jump_table[]은 큐에 있는 문자가 어느 위치에 있는지 바로 찾을 수 있도록 큐에서의 위치들을 연결 리스트로 구성하고 있다. 예를 들어 ‘G’라는 문자를 큐 내에서 찾으려면 선형 검색처럼 처음부터 끝까지 검색해야 하는 것이 아니라, jump_table[‘G’]로서 연결 리스트의 시작 위치를 찾은 다음 연결 리스트를 타고 가면 14의 위치와 9의 위치에 ‘G’라는 문자가 있음을 알 수 있다.
참고로 Lempel-Ziv 압축법에서는 패턴을 <탈출문자 상대위치 패턴길이>로 나타내는데 이 자료에서는 상대 위치와 패턴 길이 모두 1바이트를 사용한다. 즉 상대 위치는 앞으로 255만큼, 패턴의 길이도 255만큼이 가능하다는 이야기다. 패턴을 찾는 장소가 바로 큐이기 때문에 큐의 길이도 255보다 큰 것은 아무 의미가 없다. 이렇게 상대 위치와 패턴의 길이를 몇 비트로 나타낼 것인가에 따라 큐의 크기를 정해 준다.
Sliding Window에서 가장 핵심적인 부분은 원하는 패턴을 찾아내는 함수이다. 이 부분은 다음의 qmatch() 함수에 구현되어 있다. 이 qmatch() 함수는 Lempel-Ziv 압축법에서 압축 시에 가장 많이 호출되고 가장 많이 시간이 소요되는 부분이므로 충분히 최적화되어 있어야 한다.
int qmatch(int length)
{
int i;
jump *t, *p;
int cp, sp;
cp = qx(rear - length); // cp의 설정
p = jump_table + queue[cp];
t = p->next;
while (t != NULL)
{
sp = t->index; // sp의 설정, 해시 테이블에서 바로 읽어온다
for (i = 1; i < length && queue[qx(sp+i)] == queue[qx(cp+i)]; i++);
if (i == length) return sp;
// 패턴을 찾았으면 sp를 되돌림
t = t->next; // 패턴 검색에 실패했으면 다음 위치로 이동
}
return FAIL; // 패턴이 큐 내에 없음
}
qmatch() 함수는 결국 cp와 length로 주어지는 패턴을 큐 내에서 찾아서 그 위치 sp를 되돌려주는 기능을 한다.
<Sliding Window를 이용한 LZ 압축 알고리즘(FILE *src, char *srcname)>
{
FILE *dst = 출력파일;
jump_table[] 초기화;
init_queue();
put(getc(src));
length = 0;
while (!feof(src))
{
if (queue_full())
{
if (sp == front) /* 현재 추정된 패턴이 큐에서 벗어나려 하면 */
{ /* 현재까지의 정보로 출력 파일에 쓴다 */
if (length > 3) /* 패턴의 길이가 4 이상이면 압축 */
encode(sp, cp, length, dst);
else /* 아니면 그냥 씀 */
for (i = 0; i < length; i++)
{
put_jump(queue[qx(cp+i)], qx(cp+i));
/* 다음을 위해 jump_table[]에 문자들의 */
/* 위치를 기록 */
putc1(queue[qx(cp+i)], dst);
}
length = 0;
}
del_jump(queue[front], front);
/* 큐에서 빠져 나온 문자는 jump_table[]에서 제거 */
get(); /* 큐에서 문자 하나를 뺀다 */
}
if (length == 0)
{
cp = qx(rear-1); /* cp의 설정, 가장 최근에 들어온 문자 */
sp = qmatch(length+1); /* 패턴을 찾아 sp에 줌, 길이는 1 */
if (sp == FAIL) /* 패턴 검색에 실패했으면 */
{
putc1(queue[cp], dst); /* 출력 파일에 기록 */
put_jump(queue[cp], cp);
}
else
length++;
put(getc(src)); /* 다음 문자를 입력 파일에서 읽어 큐에 집어넣음 */
}
else if (length > 0) /* 패턴의 길이가 1 이상이면 */
{
if (queue[qx(cp+length)] != queue[qx(sp+length)])
j = qmatch(length+1); /* 새로 들어온 문자까지 포함해서 */
/* 패턴의 위치를 다시 검색 */
else j = sp;
if (j == FAIL || length > SIZE - 3)
{ /* 실패했으면 현재까지의 정보로 압축을 함 */
if (length > 3)
{
encode(sp, cp, length, dst);
length = 0;
}
else
{
for (i = 0; i < length; i++)
{
put_jump(queue[qx(cp+i)], qx(cp+i));
putc1(queue[qx(cp+i)], dst);
}
length = 0;
}
}
else /* 패턴 검색에 성공했으면 */
{
sp = j;
length++; /* 길이를 1증가 */
put(getc(src)); /* 큐에 새 문자를 집어넣음 */
}
}
}
/* 큐에 남아있는 문자들을 모두 출력
if (length > 3) encode(sp, cp, length, dst);
else
for (i = 0; i < length; i++)
putc1(queue[qx(cp+i)], dst);
delete_all_jump(); /* jump_table[] 소거 */
fclose(dst);
}
이 알고리즘을 자세히 살펴보면 알겠지만 그 기본적인 틀은 Run-Length 압축법과 유사함을 알 수 있을 것이다. length 변수가 상태를 표시하고 있음이 특히 그렇다.
그리고 주의할 점은 jump_table[]에 위치를 기록하는 시점이다. 쉽게 생각하면 큐에 입력할 때 집어넣은 것으로 착각할 수 있기 때문이다. jump_tablel[]에 문자의 위치를 집어넣는 정확한 시점은 파일에 그 문자를 출력할 때이다.
그리고 큐 내에 일치하는 패턴이 두 개 이상 있을 때 어느 것이 우선적으로 선택되어야 하는가 하는 문제 또한 중요하다. 이 때 적절한 기준은 cp 쪽에 가까운 패턴을 취하는 것이다. 이렇게 하는 이유는 패턴이 cp에서 멀 경우 패턴의 다음 문자들까지도 일치할 수 있으나 sp의 앞부분이 큐에서 벗어나는 경우가 있기 때문에 압축을 중단해야 하는 경우가 생기기 때문이다.
이러한 점은 put_jump() 함수에서 자연스럽게 구현된다. put_jump() 함수는 항상 최근에 들어온 그 문자의 위치를 가장 앞에 두기 때문에 jump_table[]에서 검색할 때 퇴근에 들어온 문자의 위치가 선택된다.
마지막으로 Run-Length 압축법과 마찬가지로 Lempel-Ziv 압축법에서도 압축 정보의 표시를 위해 탈출 문자(Escape Character)를 사용한다. 그런데 이 탈출 문자가 문자 자체의 의미로 사용될 때 Run-Length에서는 <ESCAPE ESCAPE>쌍을 사용했지만, Lempel_Ziv 법은 <ESCAPE 0x00>쌍을 사용한다.
왜냐하면 탈출 문자가 사용되는 두 가지 용도는 문자 자체를 의미하는 것과 <탈출문자 상대위치 패턴길이> 정보의 시작을 표시하기 위함이다. 그런데 <상대위치>는 항상 0보다 큰 값이어야 하기 때문에(0이면 자기 자신을 의미한다) 압축 정보에서 <ESCAPE 0x00>쌍이 나타날 경우는 없다. 그러므로 충분히 압축 정보와 문자 자체의 의미를 구분할 수 있다.
4.2 Lempel-Ziv Decoding
그렇다면 앞 절의 알고리즘으로 압축된 파일을 원래대로 복원하는 알고리즘을 생각해보자. 복원 알고리즘은 매우 간단하다.
복원 알고리즘의 개요는 입력 파일에서 문자를 차례대로 읽어 큐에 저장하는 것이다. 어느 정도 큐에 넣다 보면 큐가 차게 되는데 이 때 큐에서 빠져 나오는 문자들을 출력 파일에 쓰면 된다. 큐에 집어넣을 때 압축 정보가 들어올 때는 그 의미를 해석하여 다시 원 상태로 만든 다음에 큐에 한꺼번에 집어넣으면 아무 문제가 없다. 이런 알고리즘을 구현하기 위한 가장 핵심적인 함수는 put_byte() 함수이다. put_byte()함수는 매우 짧은 함수인데 인자로 주어진 문자를 큐에 집어넣되 큐가 꽉 차 있으면 출력 파일로 출력하는 기능을 한다. 이렇게 put_byte() 함수가 만들어지면 복원 알고리즘 또한 매우 간단하다.
<Sliding Window를 이용한 LZ압축 복원 알고리즘 (FILE *src)>
{
FILE *dst = 출력 파일;
init_queue();
c = getc(src);
while (!feof(src))
{
if (c == ESCAPE) /* 읽은 문자가 탈출 문자이면 */
{
if ((c = getc(src)) == 0) /* 그 다음이 0x00이면 탈출문자 자체 */
put_byte(ESCAPE, dst);
else /* 아니면 <탈출 문자 상대위치 패턴길이> 임 */
{
length = getc(src);
sp = qx(rear - c);
for (i = 0; i < length; i++) put_byte(queue[qx(sp+i)], dst);
/* 정보에 의해서 압축된 정보를 복원함 */
}
}
else /* 일반 문자의 경우 */
put_byte(c, dst);
c = getc(src);
}
while (!queue_empty()) putc(get(), dst);
/* 큐에 남아 있는 문자들을 모두 출력 */
fclose(dst);
}
4.3 Sliding Window를 이용한 Lempel-Ziv 알고리즘의 구현
이제 까지 설명한 것을 실제로 구현한 소스이다.
/* */
/* LZWIN.C : Lempel-Ziv compression using Sliding Window */
/* */
#include <stdio.h>
#include <dir.h>
#include <string.h>
#include <alloc.h>
#include <time.h>
#include <stdlib.h>
#define SIZE 255
int queue[SIZE];
int front, rear;
/* 해시 테이블의 구조 */
typedef struct _jump
{
int index;
struct _jump *next;
} jump;
jump jump_table[256];
/* 탈출 문자 */
#define ESCAPE 0xB4
/* Lempel-Ziv 압축법에 의한 것임을 나타내는 식별 코드 */
#define IDENT1 0x33
#define IDENT2 0x44
#define FAIL 0xff
/* 큐를 초기화 */
void init_queue(void)
{
front = rear = 0;
}
/* 큐가 꽉 찼으면 1을 되돌림 */
int queue_full(void)
{
return (rear + 1) % SIZE == front;
}
/* 큐가 비었으면 1을 되돌림 */
int queue_empty(void)
{
return front == rear;
}
/* 큐에 문자를 집어 넣음 */
int put(int k)
{
queue[rear] = k;
rear = ++rear % SIZE;
return k;
}
/* 큐에서 문자를 꺼냄 */
int get(void)
{
int i;
i = queue[front];
queue[front] = 0;
front = ++front % SIZE;
return i;
}
/* k를 큐의 첨자로 변환, 범위에서 벗어나는 것을 범위 내로 조정 */
int qx(int k)
{
return (k + SIZE) % SIZE;
}
/* srcname[]에서 파일 이름만 뽑아내어서 그것의 확장자를 lzw로 바꿈 */
void make_dstname(char dstname[], char srcname[])
{
char temp[256];
fnsplit(srcname, temp, temp, dstname, temp);
strcat(dstname, ".lzw");
}
/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
long file_length(char filename[])
{
FILE *fp;
long l;
if ((fp = fopen(filename, "rb")) == NULL)
return 0L;
fseek(fp, 0, SEEK_END);
l = ftell(fp);
fclose(fp);
return l;
}
/* jump_table[]의 모든 노드를 제거 */
void delete_all_jump(void)
{
int i;
jump *j, *d;
for (i = 0; i < 256; i++)
{
j = jump_table[i].next;
while (j != NULL)
{
d = j;
j = j->next;
free(d);
}
jump_table[i].next = NULL;
}
}
/* jump_table[]에 새로운 문자의 위치를 삽입 */
void put_jump(int c, int ptr)
{
jump *j;
if ((j = (jump*)malloc(sizeof(jump))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
j->next = jump_table[c].next; /* 선두에 삽입 */
jump_table[c].next = j;
j->index = ptr;
}
/* ptr 위치를 가지는 노드를 삭제 */
void del_jump(int c, int ptr)
{
jump *j, *p;
p = jump_table + c;
j = p->next;
while (j && j->index != ptr) /* 노드 검색 */
{
p = j;
j = j->next;
}
p->next = j->next;
free(j);
}
/* cp와 length로 주어진 패턴을 해시법으로 찾아서 되돌림 */
int qmatch(int length)
{
int i;
jump *t, *p;
int cp, sp;
cp = qx(rear - length); /* cp의 위치를 얻음 */
p = jump_table + queue[cp];
t = p->next;
while (t != NULL)
{
sp = t->index;
/* 첫 문자는 비교할 필요 없음. -> i =1; */
for (i = 1; i < length && queue[qx(sp+i)] == queue[qx(cp+i)]; i++);
if (i == length) return sp; /* 패턴을 찾았음 */
t = t->next;
}
return FAIL;
}
/* 문자 c를 출력 파일에 씀 */
int putc1(int c, FILE *dst)
{
if (c == ESCAPE) /* 탈출 문자이면 <탈출문자 0x00>쌍으로 치환 */
{
putc(ESCAPE, dst);
putc(0x00, dst);
}
else
putc(c, dst);
return c;
}
/* 패턴을 압축해서 출력 파일에 씀 */
void encode(int sp, int cp, int length, FILE *dst)
{
int i;
for (i = 0; i < length; i++) /* jump_table[]에 패턴의 문자들을 기록 */
put_jump(queue[qx(cp+i)], qx(cp+i));
putc(ESCAPE, dst); /* 탈출 문자 */
putc(qx(cp-sp), dst); /* 상대 위치 */
putc(length, dst); /* 패턴 길이 */
}
/* Sliding Window를 이용한 LZ 압축 함수 */
void lzwin_comp(FILE *src, char *srcname)
{
int length;
char dstname[13];
FILE *dst;
int sp, cp;
int i, j;
int written;
make_dstname(dstname, srcname); /* 출력 파일 이름을 만듬 */
if ((dst = fopen(dstname, "wb")) == NULL)
{
printf("\n Error : Can't create file.");
fcloseall();
exit(1);
}
/* 압축 파일의 헤더 작성 */
putc(IDENT1, dst); /* 출력 파일에 식별자 삽입 */
putc(IDENT2, dst);
fputs(srcname, dst); /* 출력 파일에 파일 이름 삽입 */
putc(NULL, dst); /* NULL 문자 삽입 */
for (i = 0; i < 256; i++) /* jump_table[] 초기화 */
jump_table[i].next = NULL;
rewind(src);
init_queue();
put(getc(src));
length = 0;
while (!feof(src))
{
if (queue_full()) /* 큐가 꽉 찼으면 */
{
if (sp == front) /* sp의 패턴이 넘어가려고 하면 현재의 정보로 출력 파일에 씀*/
{
if (length > 3)
encode(sp, cp, length, dst);
else
for (i = 0; i < length; i++)
{
put_jump(queue[qx(cp+i)], qx(cp+i));
putc1(queue[qx(cp+i)], dst);
}
length = 0;
}
/* 큐에서 빠져나가는 문자의 위치를 jump_table[]에서 삭제 */
del_jump(queue[front], front);
get(); /* 큐에서 한 문자 삭제 */
}
if (length == 0)
{
cp = qx(rear-1);
sp = qmatch(length+1);
if (sp == FAIL)
{
putc1(queue[cp], dst);
put_jump(queue[cp], cp);
}
else
length++;
put(getc(src));
}
else if (length > 0)
{
if (queue[qx(cp+length)] != queue[qx(sp+length)])
j = qmatch(length+1);
else j = sp;
if (j == FAIL || length > SIZE - 3)
{
if (length > 3)
{
encode(sp, cp, length, dst);
length = 0;
}
else
{
for (i = 0; i < length; i++)
{
put_jump(queue[qx(cp+i)], qx(cp+i));
putc1(queue[qx(cp+i)], dst);
}
length = 0;
}
}
else
{
sp = j;
length++;
put(getc(src));
}
}
}
/* 큐에 남은 문자 출력 */
if (length > 3)
encode(sp, cp, length, dst);
else
for (i = 0; i < length; i++)
putc1(queue[qx(cp+i)], dst);
delete_all_jump();
fclose(dst);
}
/* 큐에 문자를 넣고, 만일 꽉 찼다면 큐에서 빠져나온 문자를 출력 */
void put_byte(int c, FILE *dst)
{
if (queue_full()) putc(get(), dst);
put(c);
}
/* Sliding Window를 이용한 LZ 압축법의 복원 함수 */
void lzwin_decomp(FILE *src)
{
int c;
char srcname[13];
FILE *dst;
int length;
int i = 0, j;
int sp;
rewind(src);
c = getc(src);
if (c != IDENT1 || getc(src) != IDENT2) /* 헤더 확인 */
{
printf("\n Error : That file is not Lempel-Ziv Encoding file");
fcloseall();
exit(1);
}
while ((c = getc(src)) != NULL) /* 파일 이름을 얻음 */
srcname[i++] = c;
srcname[i] = NULL;
if ((dst = fopen(srcname, "wb")) == NULL)
{
printf("\n Error : Disk full? ");
fcloseall();
exit(1);
}
init_queue();
c = getc(src);
while (!feof(src))
{
if (c == ESCAPE) /* 탈출 문자이면 */
{
if ((c = getc(src)) == 0) /* <탈출 문자 0x00> 이면 */
put_byte(ESCAPE, dst);
else /* <탈출문자 상대위치 패턴길이> 이면 */
{
length = getc(src);
sp = qx(rear - c);
for (i = 0; i < length; i++)
put_byte(queue[qx(sp+i)], dst);
}
}
else /* 일반적인 문자의 경우 */
put_byte(c, dst);
c = getc(src);
}
while (!queue_empty()) /* 큐에 남아 있는 모든 문자를 출력 */
putc(get(), dst);
fclose(dst);
}
void main(int argc, char *argv[])
{
FILE *src;
long s, d;
char dstname[13];
clock_t tstart, tend;
/* 사용법 출력 */
if (argc < 3)
{
printf("\n Usage : LZWIN <a or x> <filename>");
exit(1);
}
tstart = clock(); /* 시작 시간 기록 */
s = file_length(argv[2]); /* 원래 파일의 크기를 구함 */
if ((src = fopen(argv[2], "rb")) == NULL)
{
printf("\n Error : That file does not exist.");
exit(1);
}
if (strcmp(argv[1], "a") == 0) /* 압축 */
{
lzwin_comp(src, argv[2]);
make_dstname(dstname, argv[2]);
d = file_length(dstname); /* 압축 파일의 크기를 구함 */
printf("\nFile compressed to %d%%.", (int)((double)d/s*100.));
}
else if (strcmp(argv[1], "x") == 0) /* 압축의 해제 */
{
lzwin_decomp(src);
printf("\nFile decompressed & created.");
}
fclose(src);
tend = clock(); /* 종료 시간 기록 */
printf("\nTime elapsed %d ticks", tend - tstart); /* 수행 시간 출력 : 단위 tick */
}
이 프로그램을 실행시켜 보면 우선 속도가 매우 느리다는 점에 실망할 수도 있다. 그러나 압축률은 상용 프로그램에는 못 미치지만 상당히 좋음을 알 수 있을 것이다. 일반적으로 <상대위치>의 비트 수를 늘리면 압축률은 좋아진다. 대신 패턴 검색 시간이 길어지는 단점이 있다.
<상대위치>와 <패턴길이>를 모두 8비트로 표현했지만, 이 둘을 적절히 조절하면 실행 시간을 빨리 하거나 압축률을 좋게 하는 변화를 줄 수 있다. 하지만 이럴 경우 비트 조작이 필요하므로 코딩 시 주의해야 한다.
4.4 실행 결과
filetype Lempel-Zip
random-bin 100.59
random-txt 100.24
wave 92.34
pdf 83.54
text(big) 66.64
text(small) 89.69
sql 55.18
Run-Length의 경우와 마찬가지로 Random File에 대해서는 압축을 하지 못했다. 하지만 그 외의 경우는 Run-Length에 비해 상당히 높은 압축률을 보여주고 있다. 이는 조금 떨어진 곳이라도 같은 패턴이 있으면 압축을 할 수 있기 때문에 가능한 결과라 생각한다.
5 Variable Length
영문 텍스트 파일의 경우 사용되는 문자는 영어 대.소문자와 기호, 공백 문자 등 100여 개 안팎이다. 그래서 원래 ASCII 코드는 7비트(128가지의 상태를 표현)로 설계되었으며 나머지 한 비트는 패리티 비트(Parity Bit)로 통신상에서 오류를 검출하는 데 사용하도록 되어 있었다.
통신 에뮬레이터의 환경설정에서 ‘데이터 비트 8’, ‘패리티 None’ 이라고 설정하는 것은 이러한 ASCII코드의 에러 검출 기능을 무시하고 8비트를 모두 사용하겠다는 뜻이다. 이러한 설정 기능은 원래 영어권에서 텍스트에 기반을 둔 통신 환경에서 8비트를 모두 사용할 필요가 없었기 때문에 만들어진 선택 사항이다.
그렇다면 패리티를 무시하고 7비트만으로 영문자를 표기하되, 남은 한 비트를 다음 문자를 위해 사용한다면 고정적으로 1/8의 압축률을 가지는 압축 방법이 될 것이다. 이를 ‘8비트에서 7비트로 줄이는 압축 알고리즘(Eight to Seven Encoding)’ 이라고 한다.
<그림 5‑1> 8비트에서 7비트로 줄이는 압축 알고리즘
위의 논의는 자연적으로 다음과 같은 생각을 유도한다. 즉 압축하고자 하는 파일이 단지 일부분의 문자 집합만을 사용한다면 이를 표현하기 위해 8비트 전부를 사용할 필요가 없다는 것이다. 예를 들어 ‘ABCDEFABBCDEBDD’라는 문자열을 압축한다고 하자. 이 문자열은 단 6 문자를 사용한다. 그렇다면 사용되는 각 문자에 대해서 다음과 같이 다시 비트를 재구성해보자.
<그림 5‑2> 문자 코드의 재구성
그렇다면 앞의 문자열은 다음과 같이 다시 쓸 수 있으며 결과적으로 압축된다.
원래 문자열 : ABCDEFABBCDEBDD
압축 비트열 : 0 1 00 01 10 11 0 1 1 00 01 10 1 01 01
하지만, 이렇게 표현을 하면 압축 비트열은 각 문자 코드마다 구분자(Delimiter)가 필요하게 된다. 만약 구분자가 없이 각 코드를 붙여 쓴다면 그 해석이 모호해져서 압축 알고리즘으로는 쓸모 없게 된다. 예를 들어 압축 비트열의 앞부분인 네 코드를 붙여 쓴다면 ‘010001’이 되는데 이는 ‘ABCD’로도 해석할 수 있지만 ‘DCD’로도 해석할 수 있고 ‘ABAAAB’로도 해석할 수 있다는 뜻이다.
그렇다면 이 모호함을 해결하는 방법은 없을까? 문제 해결의 열쇠는 문자 코드들을 기수 나무(Radix Tree)로 구성해 보는 데서 얻어진다.
<그림 5‑3> <그림 5‑2>코드의 기수 나무
기수 나무는 뿌리 노드에서 원하는 노드를 찾아가는 과정에서 비트가 0이면 왼쪽 자식으로, 1이면 오른쪽 자식으로 가는 탐색 구조를 가지고 있다. 이 그림에서 보면 각 문자들은 외부 노드와 내부 노드 모두에 존재한다. 이러한 구조에서는 구분자가 반드시 필요하게 된다.
그렇다면 이들을 기수 나무로 구성하지 않고 기수 트라이(Radix Trie)로 구성한다면 어떨까? 기수 트라이는 각 정보 노드들이 모두 외부 노드인 나무 구조를 의미한다. 이렇게 구성된다면 정보 노드를 찾아가는 과정에서 다른 정보 노드를 만나는 경우가 없어져서 구분자 없이도 비트들을 구성할 수 있다.
예를 들어 다음의 그림과 같이 기수 트라이를 만들고 코드를 재구성해 보도록 하자.
<그림 5‑4> 문자 코드의 재구성
<그림 5‑4>의 코드 표는 <그림 5‑2>에 비해서 코드의 길이가 길어졌지만 구분자가 필요 없다는 장점이 있다. 이 <그림 5‑4>를 이용하여 문제의 문자열을 압축하면 다음처럼 된다.
원래 문자열 : ABCDEFABBCDEBDD
압축 비트열 : 01001011101110111101001001011101110100110110
이렇게 어떤 파일에서 사용되는 문자 집합이 전체 집합의 극히 일부분이라면 상당한 압축률로 압축할 수 있음을 보았을 것이다. 이와 같이 문자 코드를 재구성하여 고정된 비트 길이의 코드가 아닌 가변 길이의 코드를 사용하여 압축하는 방법을 가변 길이 압축법(Variable Length Encoding)이라고 한다.
가변 길이 압축법에서 유의할 점은 압축 파일 내에 각 문자에 대해서 어떤 코드로 압축되었는지 그 정보를 미리 기억시켜 두어야 한다는 점이다. 이는 Run-Length 압축법이나 Lempel-Ziv 압축법과 같이 헤더가 식별자와 파일 이름만으로 구성되는 것이 아니라 문자에 대한 코드 또한 기록해 두어야 한다는 것을 의미한다. 기록되는 코드는 코드 자체뿐 아니라, 가변 길이라는 특성 때문에 코드의 길이 또한 기록되어야 한다. 이렇게 되어서 가변길이 압축법은 헤더가 매우 길어지게 된다.
뒤에 나올 Huffman Tree가 가변 길이 압축법의 한 종류이기 때문에 가변 길이 압축법 자체는 자세히 다루지 않겠다.
6 Huffman Tree
만일 압축하고자 하는 파일이 전체 문자 집합의 모든 원소를 사용한다면 가변길이 압축법은 여전히 유용할까? 답은 그렇다 이다. 그리고 그것을 가능케 하는 것은 이 절에서 소개하는 Huffman 나무(Huffman Tree)이다.
앞 절에서 살펴본 것과 같이 기수 트라이로 코드를 구성하는 경우 각 정보를 포함하고 있는 외부 노드의 레벨(Level)이 얼마냐에 따라 코드의 길이가 결정되었다. 예를 들어 <그림 5‑4>의 ‘A’문자의 경우는 겨우 비트의 길이가 1이며, ‘F’의 경우는 4가 된다.
그렇다면 압축하고자 파일이 비록 모든 문자를 사용한다 할지라도 그 출현 빈도수가 고르지 않다면 출현빈도가 큰 문자에 대해서는 짧은 길이의 코드를, 출현 빈도가 작은 문자에 대해서는 긴 길이의 코드를 할당하면 전체적으로 압축되는 효과를 가져올 것이다.
그렇다면 압축축하고자 하는 파일을 먼저 읽어서 각 문자에 대한 빈도를 계산해야 한다는 결론이 나오게 되는데, 이러한 빈도가 freq[]라는 배열에 저장되어 있다면 이 빈도를 이용하여 어떻게 빈도와 레벨이 반비례하는 기수 트라이를 만들 것인가 하는 것이 이 절의 문제이며, 그 해결 방법은 Huffman 나무이다.
우선 Huffman 나무의 노드를 다음의 huf 구조체와 같이 정의해 보자.
typedef struct _huf
{
long count; // 빈도
int data; // 문자
struct _huf *left, *right
} huf;
huf 구조체는 Huffman 나무의 노드로서 그 멤버로 빈도를 저장하는 count, 어떤 문자의 노드인지 알려주는 data를 가진다. 이 huf 구조체의 멤버를 의미있는 정보로 채우기 위해서는 우선 문자열에서 각 문자에 대한 빈도를 계산해야 한다. <그림 6‑1> (가)와 같은 문자열이 있다고 할 때 그 빈도수를 나타내면 (나)와 같다.
<그림 6‑1> 빈도수 계산
이제 <그림 6‑1> (나)의 정보를 이용하여 각 노드를 생성하여 죽 배열한다. 그 다음 작은 빈도의 두 노드를 뽑아내어 그것을 자식으로 가지는 분기 노드(Branch Node, 정보를 저장하지 않는 트라이의 내부 노드)를 새로 생성하여 그것을 다시 노드의 배열에 집어넣는다. 이 때 분기 노드의 count에는 두 자식 노드의 count의 합이 저장된다. 이런 과정을 노드가 하나 남을 때까지 반복하면 Huffman 나무가 얻어진다. 이 과정을 <그림 6‑2>에 나타내었다.
<그림 6‑2> Huffman Tree 구성과정
<그림 6‑2>를 차례로 따라가다 보면 그 방법을 자연히 느끼게 될 것이다. 최종적인 결과로 얻어지는 Huffman Tree는 (하) 그림과 같다. (하) 그림을 보면 빈도수가 적은 노드들은 상대적으로 레벨이 크고, 빈도수가 많은 노드들은 레벨이 작음을 알 수 있다.
이제 이런 과정을 수행하는 함수를 작성해 보기로 하자. 우선 빈도와 문자를 저장하고 있는 노드들을 죽 배열하는 장소를 정의해야 할 것이다. 그것은 다음의 head[] 배열이며, nhead는 노드의 개수를 저장하고 있다.
huf *head[256];
int nhead;
앞에서 설명한 바와 같이 문자 i의 빈도가 freq[i]에 저장되어 있다고 한다면 다음의 construct_trie() 함수가 Huffman 나무를 구성해 준다.
void construct_trie(void)
{
int i;
int m;
hum *h, *h1, *h2;
/* 초기 단계 */
for ( i = nhead = 0; i < 256; i++)
{
if(freq[i] != 0) /* 빈도가 0이 아닌 문자에 대해서만 노드를 생성 */
{
if((h = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
h->count = freq[i];
h->data = i;
h->left = h->right = NULL;
head[nhead++] = h;
}
}
/* Huffman Tree 생성 단계 */
while (nhead > 1) /* 노드의 개수가 1이면 종료 */
{
m = find_minimum(); /* 최소의 빈도를 가지는 노드를 찾음 */
h1 = head[m];
head[m] = head[--nhead]; /* 그 노드를 빼냄 */
m = find_minimum(); /* 또 다른 최소의 빈도를 가지는 노드를 찾음 */
h2 = head[m];
if((h = (huf*)malloc(sizeof(huf))) == NULL) /* 분기 노드 생성 */
{
printf("\nError : Out of memory");
exit(1);
}
/* 두 자식 노드의 count 합을 저장 */
h->count = h1->count + h2->count;
h->data = 0;
h->left = h1; /* h1, h2를 자식으로 둠 */
h->right = h2;
head[m] = h; /* 생성된 분기 노드를 노드 배열 head[]에 삽입 */
}
huf_head = head[0]; /* Huffman Tree의 루트 노드를 저장 */
}
construct_trie() 함수는 앞에서 보인 Huffman 나무 생성 과정을 그대로 직관적으로 표현했다. 그리고 huf_head라는 전역 변수는 Huffman 나무의 뿌리 노드(Root)를 가리키도록 함수의 마지막에서 설정해 둔다.
이렇게 <그림 6‑2> (하) 그림과 같은 Huffman 나무에서 각 문자에 대한 코드의 길이를 뽑아내어 보면 <그림 6‑3>과 같다.
<그림 6‑3> Huffman Tree에서 얻어진 코드
6.1 Huffman Encoding
Huffman 압축 알고리즘은 한마디로 말해서 원래의 고정 길이 코드를 <그림 6‑3>의 가변 길이 코드로 변환하는 것이다. 그러므로 Huffman 나무에서 코드를 얻어내는 방법이 반드시 필요하다.
다음의 _make_code() 함수와 make_code() 함수가 Huffman 나무에서 코드를 생성하는 함수이다. _make_code() 함수가 재귀 호출 형태이어서 그것의 입구 함수로 make_code() 함수를 준비해 둔 것이다. 얻어진 코드는 전역 배열인 code[]에 저장되며, 코드의 길이는 len[]배열에 저장된다.
void _make_code(huf *h, unsigned c, int l)
{
if(h->left != NULL || h->right != NULL) /* 내부 노드(분기 노드)이면 */
{
c <<= 1; /* 코드를 시프트, 결과적으로 0을 LSB에 집어넣는다. */
l++; /* 길이 증가 */
_make_code(h->left, c, l); /* 오른쪽 자식으로 재귀 호출 */
c >>= 1; /* 부모로 돌아가기 위해 다시 원상 복구 */
l--;
}
else /* 외부 노드(정보 노드)이면 */
{
code[h->data] = c; /* 코드와 코드의 길이를 기록 */
len[h->data] = l;
}
}
void make_code(void)
{
/* _make_code()의 입구 함수 */
int i;
for (i = 0; i < 256; i++) /* code[]와 len[]의 초기화 */
code[i] = len[i] = 0;
_make_code(huf_head, 0u, 0);
}
위의 make_code()함수를 이용하면 이제 가변 길이 레코드를 얻어낼 수 있다. 그렇다면 이제 실제로 압축 함수 제작에 들어가야 하는데, 약간의 문제가 있다. 그것은 가변 길이의 코드를 사용하기 때문에 한 바이트씩 디스크로 입출력하게 되어 있는 기존의 시스템과는 좀 다른 점을 어떻게 표현하는가 하는 것이다.
이럴 때 필요한 것이 문제를 추상화 하는 것이다. 즉 디스크 파일을 한 바이트씩 쓰는 것이 아니라 한 비트씩 쓰는 것으로 착각하게 만드는 것이다. 이것을 담당하는 함수가 바로 put_bitseq()함수이다. put_bitseq() 함수를 사용하면 입력 파일에서 읽은 문자에 해당하는 코드를 비트별로 차례로 put_bitseq()의 인자로 주면 put_bitseq() 함수 내에서 알아서 한 바이트를 채워 출력 파일로 출력한다.
#define NORMAL 0
#define FLUSH 1
void put_bitseq(unsigned i, FILE *dst, int flag)
{
/* 한 비트씩 출력하도록 하는 함수 */
static unsigned wbyte = 0;
/* 한 바이트가 꽉 차거나 FLUSH 모드이면 */
/* bitloc는 입력될 비트 위치를 지정하는 전역 변수 */
if (bitloc < 0 || glag == FLUSH)
{
putc(wbyte, dst);
bitloc = 7; /* bitloc 재설정 */
wbyte = 0;
}
wbyte |= i << (bitloc--); /* 비트를 채워넣음 */
}
put_bitseq() 함수는 두 가지 모드로 작동한다. NNORMAL은 일반적인 경우로서 한 바이트가 꽉 차면 파일로 출력하는 모드이고, FLUSH 모드는 한 바이트가 꽉 차 있지 않더라도 현재의 wbyte를 파일로 출력한다. 이 두 가지 모드를 둔 이유는 파일의 끝에서 가변 길이 코드라는 특성 때문에 한 바이트가 채워지지 않는 경우가 생기기 때문이다.
<Huffman 압축 알고리즘(FILE *src, char *srcname)>
{
FILE *dst = 출력 파일;
length = src 파일의 길이;
헤더를 출력; /* 식별자, 파일 이름, 파일 길이 */
get_freq(src); /* 빈도를 구해 freq[] 배열에 저장 */
construct_trie(); /* freq[]를 이용하여 Huffman Tree 구성 */
make_code(); /* Huffman Tree를 이용하여 code[], len[] 배열 설정 */
code[]와 len[] 배열을 출력;
destruct_trie(huf_head); /* Huffman Tree를 제거 */
rewind(src);
bitloc = 7;
while(1)
{
cur = getc(src);
if(feof(src)) break;
for (b = len[cur] - 1; b >= 0; b--)
put_bitseq(bits(code[cur], b, 1), dst, NORMAL);
/* 비트별로 읽어서 put_bitseq() 수행 */
}
put_bitseq(0, dst, FLUSH); /* 남은 비트열을 FLUSH 모드로 씀 */
fclose(dst);
}
Huffman 압축 알고리즘의 본체는 매우 간단 명료하다.
그런데 한 가지 살펴볼 것이 있다. 일반적으로 실제 파일을 이용하여 Huffman 나무를 구성하여 코드를 구현해 보면 그 길이가 대략 14를 넘지 않는다. 그렇다면 code[] 배열을 위해서는 여분을 생각해서 16비트를 할당하면 될 것이다. 그런데 코드의 길이인 len[] 배열을 위해서는 최대 0~14 까지만 표현 가능하면 되므로 한 바이트를 모두 사용하는 것보다 4비트만 사용하면 상당히 헤더의 길이를 줄일 수 있을 것이다. 이것을 <그림 6‑4>에 나타내었다.
<그림 6‑4> code[]와 len[]의 저장
<그림 6‑4>와 같이 저장하면 총 128 * 5 바이트 즉 640 바이트의 헤더가 덧붙게 된다. 이렇게 저장하는 방법은 소스의 huffman_comp() 함수에 구현되어 있으므로 참고하기 바란다.
또한 Huffman 압축법과 같은 가변 길이 압축법은 앞에서 설명한 바와 같이 원래 파일의 길이도 저장하고 있어야 복원이 제대로 이루어진다. 결국 다른 압축법에 비해서 Huffman 압축법은 헤더의 길이가 매우 긴 편이다.
6.2 Huffman Decoding
앞 절과 같은 방법으로 압축된 파일을 다시 원상태로 복원하는 방법을 생각해 보자. 압축된 파일의 헤더에는 code[]와 len[]에 대한 정보가 실려있다. 이 둘을 이용하면 원래의 Huffman 나무를 새로 구성할 수 있다. 우선 압축 파일의 헤더를 읽어 code[]와 len[]을 다시 설정했다고 하자.
그렇다면 다음의 trie_insert() 함수와 restruct_trie() 함수를 이용하여 Huffman 나무를 재구성할 수 있다. trie_insert() 함수는 인자로 받은 data의 노드를 code[data]와 len[data]를 이용하여 적절한 위치에 삽입한다. 삽입하는 방법은 매우 간단하다. code[data]의 비트를 차례로 분석하여 트라이를 타고 내려가면서 노드가 생성되어 있지 않으면 노드를 생성한다. 그래서 제 위치인 외부 노드에 도착하면 노드의 data 멤버에 인자 data를 설정하면 된다.
void trie_insert(int data)
{
int b = len[data] -1; /* 비트의 최좌측 위치(MSB) */
huf *p, *t;
if (huf_head == NULL) /* 뿌리 노드가 없으면 생성 */
{
if ((huf_head = (huf*)malloc(sizeof(huf)) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
huf_head->left = huf_head->right = NULL;
}
p = t = huf_head;
while (b >= 0)
{
if (bits(code[data], b, 1) == 0) /* 현재 검사 비트가 0이면 왼쪽으로 */
{
t = t->left;
if (t == NULL) /* 왼쪽 자식이 없으면 생성 */
{
if ((t = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
t->left = t->right = NULL;
p->left = t;
}
}
else /* 현재 검사 비트가 1이면 오른쪽으로 */
{
t = t->right;
if (t == NULL) /* 오른쪽 자식이 없으면 생성 */
{
if ((t = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
t->left = t->right = NULL;
p->right = t;
}
}
p = t;
b--;
}
t->data = data; /* 외부 노드에 data 설정 */
}
다음의 restruct_trie()함수는 위의 trie_insert() 함수에 코드의 길이가 0이 아닌 문자에 대해서만 Huffman 나무를 재구성하도록 인자를 보급한다.
void restruct_trie(void)
{
int i;
huf_head = NULL;
for (i = 0; i < 256; i++)
if (len[i] > 0) trie_insert(i);
}
압축을 푸는 과정도 압축을 하는 과정과 유사하게 매우 간단하다. 압축을 푸는 과정을 한마디로 말하면 압축 파일에서 한 비트씩 읽어와서 그 비트대로 Huffman 나무를 순회한다. 그러다가 외부 노드에 도착하면 외부 노드의 data 멤버에 실린 값을 복원 파일에 써넣으면 되는 것이다.
여기서 문제가 되는 점은 압축 파일에서 한 비트씩 읽어내는 방법인데, 이것 또한 앞절에서 살펴본 바와 같이 파일에서 한 비트씩 읽어들이는 것처럼 착각할 수 있도록 다음의 get_bitseq() 함수를 작성하는 것으로 해결된다.
int get_bitseq(FILE *fp)
{
static int cur = 0;
if (bitloc < 0) /* 비트가 소모되었으면 다음 문자를 읽음 */
{
cur = getc(fp);
bitloc = 7;
}
return bits(cur, bitloc--, 1); /* 다음 비트를 돌려 줌 */
}
위의 부함수들을 이용하여 다음과 같이 Huffman 압축의 복원 알고리즘을 정리할 수 있다
<Huffman 압축 복원 알고리즘(FILE *src)>
{
FILE *dst = 복원 파일;
huf *h;
헤더를 읽어들임; /* 식별자와 파일 이름, 파일 길이 */
code[]와 len[]을 읽어들임;
restruct_trie(); /* Huffman Tree를 재구성 */
n = 0;
bitloc = -1;
while (n < length) /* length 는 파일의 길이 */
{
h = huf_head;
while (h->left && h->right)
{
if (get_bitseq(src) == 1) /* 읽어들인 비트가 1이면 오른쪽으로 */
h = h->right;
else /* 0이면 왼쪽으로 */
h = h->left;
}
putc(h->data, dst);
n++;
}
destruct_trie(huf_head); /* Huffman Tree 제거 */
fclose(dst);
}
6.3 Huffman 압축 알고리즘 구현
이제까지의 논의를 바탕으로 Huffman 압축 알고리즘을 실제로 구현한 C 소스이다.
/* */
/* HUFFMAN.C : Compression by Huffman's algorithm */
/* */
#include <stdio.h>
#include <string.h>
#include <alloc.h>
#include <dir.h>
#include <time.h>
#include <stdlib.h>
/* Huffman 압축에 의한 것임을 나타내는 식별 코드 */
#define IDENT1 0x55
#define IDENT2 0x66
long freq[256];
typedef struct _huf
{
long count;
int data;
struct _huf *left, *right;
} huf;
huf *head[256];
int nhead;
huf *huf_head;
unsigned code[256];
int len[256];
int bitloc = -1;
/* 비트의 부분을 뽑아내는 함수 */
unsigned bits(unsigned x, int k, int j)
{
return (x >> k) & ~(~0 << j);
}
/* 파일에 존재하는 문자들의 빈도를 구해서 freq[]에 저장 */
void get_freq(FILE *fp)
{
int i;
for (i = 0; i < 256; i++)
freq[i] = 0L;
rewind(fp);
while (!feof(fp))
freq[getc(fp)]++;
}
/* 최소 빈도수를 찾는 함수 */
int find_minimum(void)
{
int mindex;
int i;
mindex = 0;
for (i = 1; i < nhead; i++)
if (head[i]->count < head[mindex]->count)
mindex = i;
return mindex;
}
/* freq[]로 Huffman Tree를 구성하는 함수 */
void construct_trie(void)
{
int i;
int m;
huf *h, *h1, *h2;
/* 초기 단계 */
for (i = nhead = 0; i < 256; i++)
{
if (freq[i] != 0)
{
if ((h = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
h->count = freq[i];
h->data = i;
h->left = h->right = NULL;
head[nhead++] = h;
}
}
/* 생성 단계 */
while (nhead > 1)
{
m = find_minimum();
h1 = head[m];
head[m] = head[--nhead];
m = find_minimum();
h2 = head[m];
if ((h = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
h->count = h1->count + h2->count;
h->data = 0;
h->left = h1;
h->right = h2;
head[m] = h;
}
huf_head = head[0];
}
/* Huffman Tree를 제거 */
void destruct_trie(huf *h)
{
if (h != NULL)
{
destruct_trie(h->left);
destruct_trie(h->right);
free(h);
}
}
/* Huffman Tree에서 코드를 얻어냄. code[]와 len[]의 설정 */
void _make_code(huf *h, unsigned c, int l)
{
if (h->left != NULL || h->right != NULL)
{
c <<= 1;
l++;
_make_code(h->left, c, l);
c |= 1u;
_make_code(h->right, c, l);
c >>= 1;
l--;
}
else
{
code[h->data] = c;
len[h->data] = l;
}
}
/* _make_code()함수의 입구 함수 */
void make_code(void)
{
int i;
for (i = 0; i < 256; i++)
code[i] = len[i] = 0;
_make_code(huf_head, 0u, 0);
}
/* srcname[]에서 파일 이름만 뽑아내어서 그것의 확장자를 huf로 바꿈 */
void make_dstname(char dstname[], char srcname[])
{
char temp[256];
fnsplit(srcname, temp, temp, dstname, temp);
strcat(dstname, ".huf");
}
/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
long file_length(char filename[])
{
FILE *fp;
long l;
if ((fp = fopen(filename, "rb")) == NULL)
return 0L;
fseek(fp, 0, SEEK_END);
l = ftell(fp);
fclose(fp);
return l;
}
#define NORMAL 0
#define FLUSH 1
/* 파일에 한 비트씩 출력하도록 캡슐화 한 함수 */
void put_bitseq(unsigned i, FILE *dst, int flag)
{
static unsigned wbyte = 0;
if (bitloc < 0 || flag == FLUSH)
{
putc(wbyte, dst);
bitloc = 7;
wbyte = 0;
}
wbyte |= i << (bitloc--);
}
/* Huffman 압축 함수 */
void huffman_comp(FILE *src, char *srcname)
{
int cur;
int i;
int max;
union { long lenl; int leni[2]; } length;
char dstname[13];
FILE *dst;
char temp[20];
int b;
fseek(src, 0L, SEEK_END);
length.lenl = ftell(src);
rewind(src);
make_dstname(dstname, srcname); /* 출력 파일 이름 만듬 */
if ((dst = fopen(dstname, "wb")) == NULL)
{
printf("\n Error : Can't create file.");
fcloseall();
exit(1);
}
/* 압축 파일의 헤더 작성 */
putc(IDENT1, dst); /* 출력 파일에 식별자 삽입 */
putc(IDENT2, dst);
fputs(srcname, dst); /* 출력 파일에 파일 이름 삽입 */
putc(NULL, dst); /* NULL 문자열 삽입 */
putw(length.leni[0], dst); /* 파일의 길이 출력 */
putw(length.leni[1], dst);
get_freq(src);
construct_trie();
make_code();
/* code[]와 len[]을 출력 */
for (i = 0; i < 128; i++)
{
putw(code[i*2], dst);
cur = len[i*2] << 4;
cur |= len[i*2+1];
putc(cur, dst);
putw(code[i*2+1], dst);
}
destruct_trie(huf_head);
rewind(src);
bitloc = 7;
while (1)
{
cur = getc(src);
if (feof(src))
break;
for (b = len[cur] - 1; b >= 0; b--)
put_bitseq(bits(code[cur], b, 1), dst, NORMAL);
}
put_bitseq(0, dst, FLUSH);
fclose(dst);
}
/* len[]와 code[]를 이용하여 Huffman Tree를 구성 */
void trie_insert(int data)
{
int b = len[data] - 1;
huf *p, *t;
if (huf_head == NULL)
{
if ((huf_head = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
huf_head->left = huf_head->right = NULL;
}
p = t = huf_head;
while (b >= 0)
{
if (bits(code[data], b, 1) == 0)
{
t = t->left;
if (t == NULL)
{
if ((t = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
t->left = t->right = NULL;
p->left = t;
}
}
else
{
t = t->right;
if (t == NULL)
{
if ((t = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
t->left = t->right = NULL;
p->right = t;
}
}
p = t;
b--;
}
t->data = data;
}
/* trie_insert()의 입구 함수 */
void restruct_trie(void)
{
int i;
huf_head = NULL;
for (i = 0; i < 256; i++)
if (len[i] > 0) trie_insert(i);
}
/* 파일에서 한 비트씩 읽는 것처럼 캡슐화 한 함수 */
int get_bitseq(FILE *fp)
{
static int cur = 0;
if (bitloc < 0)
{
cur = getc(fp);
bitloc = 7;
}
return bits(cur, bitloc--, 1);
}
/* Huffman 압축 복원 알고리즘 */
void huffman_decomp(FILE *src)
{
int cur;
char srcname[13];
FILE *dst;
union { long lenl; int leni[2]; } length;
long n;
huf *h;
int i = 0;
rewind(src);
cur = getc(src);
if (cur != IDENT1 || getc(src) != IDENT2)
{
printf("\n Error : That file is not Run-Length Encoding file");
fcloseall();
exit(1);
}
while ((cur = getc(src)) != NULL)
srcname[i++] = cur;
srcname[i] = NULL;
if ((dst = fopen(srcname, "wb")) == NULL)
{
printf("\n Error : Disk full? ");
fcloseall();
exit(1);
}
length.leni[0] = getw(src);
length.leni[1] = getw(src);
for (i = 0; i < 128; i++) /* code[]와 len[]을 읽어들임 */
{
code[i*2] = getw(src);
cur = getc(src);
code[i*2+1] = getw(src);
len[i*2] = bits(cur, 4, 4);
len[i*2+1] = bits(cur, 0, 4);
}
restruct_trie(); /* 헤더를 읽어서 Huffman Tree 재구성 */
n = 0;
bitloc = -1;
while (n < length.lenl)
{
h = huf_head;
while (h->left && h->right)
{
if (get_bitseq(src) == 1)
h = h->right;
else
h = h->left;
}
putc(h->data, dst);
n++;
}
destruct_trie(huf_head);
fclose(dst);
}
void main(int argc, char *argv[])
{
FILE *src;
long s, d;
char dstname[13];
clock_t tstart, tend;
/* 사용법 출력 */
if (argc < 3)
{
printf("\n Usage : HUFFMAN <a or x> <filename>");
exit(1);
}
tstart = clock(); /* 시작 시각 기록 */
s = file_length(argv[2]); /* 원래 파일의 크기 구함 */
if ((src = fopen(argv[2], "rb")) == NULL)
{
printf("\n Error : That file does not exist.");
exit(1);
}
if (strcmp(argv[1], "a") == 0) /* 압축 */
{
huffman_comp(src, argv[2]);
make_dstname(dstname, argv[2]);
d = file_length(dstname); /* 압축 파일의 크기를 구함 */
printf("\nFile compressed to %d%%.", (int)((double)d/s*100.));
}
else if (strcmp(argv[1], "x") == 0) /* 압축의 해제 */
{
huffman_decomp(src);
printf("\nFile decompressed & created.");
}
fclose(src);
tend = clock(); /* 종료 시각 저장 */
printf("\nTime elapsed %d ticks", tend - tstart); /* 수행 시간 출력 : 단위 tick */
}
6.4 실행 결과
filetype Huffman
random-bin 113.80
random-txt 97.32
wave 94.76
pdf 92.34
text(big) 63.18
text(small) 572.88
sql 60.08
앞의 두 알고리즘과는 다르고 random-txt에서 압축이 되었다. 이는 전체 파일에 나타나는 문자가 몇 개 안되기 때문에 허프만 코드에 의해서 압축이 되었다고 생각할 수 있다. random-bin에서 압축이 안된 것은 상대적으로 많은 문자가 사용되었기 때문에 Trie의 Depth가 깊어져서 코드 값이 길어졌기 때문이다. 또한 text(small)의 경우 값이 커진 것은, 허프만 압축의 특성상 헤더가 추가 되는데, 원래 파일이 워낙 작았기 때문에 헤더의 크기에 영향을 받은 것이다.
7 Compare
filetype Run-Length Lempel-Zip Huffman
random-bin 100.59 100.59 113.80
random-txt 100.24 100.24 97.32
wave 98.20 92.34 94.76
pdf 99.03 83.54 92.34
text(big) 85.04 66.64 63.18
text(small) 98.71 89.69 572.88
sql 96.78 55.18 60.08
주로 텍스트 파일을 이용한 테스트 였기 때문에, Lempel-Zip압축 방법이 대체로 우수한 압축률을 보여주고 있다. Huffman 압축 방식도 파일이 극히 작은 경우만 아니라면 어느정도의 압축률을 보여주고 있다. Run-Length는 text파일의 경우가 아니고선 거의 압축을 하지 못했다.
8 JPEG (Joint Photographic Experts Group)
8.1 JPEG이란
1982년, 국제 표준화 기구 ISO(International Standard Organization)는 정지 영상의 압축 표준을 만들기 위해 PEG(Photographic Exports Group:영상 전문가 그룹)을 만들었다. PEG의 목표는 ISDN을 이용하여 정지 영상을 전송하기 위한 고성능 압축 표준을 만들자는 것이 주 목적이 되어 이를 수행하게 된 것이다.
1986년 국제 전신 전화 위원회 CCITT(International Telegraph and Telephone Consultative Committee)에서는 팩스를 이용해 전송하기 위한 영상 압축 방법을 연구하기 시작하였다. CCITT의 연구 내용은 PEG의 그것과 거의 비슷하였기 때문에 1987년 이 두 국제 기구의 영상 전문가가 연합하여 공동 연구를 수행하게 되었고, 이 영상 전문가 연합을 Joint Photographic Expert Group이라고 하였으며, 이것의 약자를 따서 만든 말이 바로 JPEG이다. 1990년 JPEG에서는 픽셀당 6비트에서 24비트를 갖는 정지 영상을 압축할 수 있는 고성능 정지 영상 압축 방법에 대한 국제 표준을 만들어 내게 되었다. 후에 JPEG에서는 만든 압축 알고리즘을 이용한 파일 포맷이 만들어 지게 되고 이것이 오늘날까지 오게 된 것이다.
8.2 다른 기술과의 비교
다른 기술과 차별화 되는 JPEG의 압축기술 GIF파일 포맷에 대해서 먼저 알아보기로 한다. 이 영상이미지 데이터는 최대 256컬러 영상까지만 저장할 수 있었기 때문에 실 세계의 이미지와 같은 것들을 저장하는데 한계가 있다. 지금은 트루컬러까지 모니터에서 지원이 되는데 이를 다른 곳에 응용하기에는 무리가 있었던 것이다.
GIF파일에서 사용하는 알고리즘을 LZW라고 하는데 이는 이를 개발한 Abraham Lempel과 Jakob Ziv이고 이를 개선시킨 Terry Welch등 세 사람의 이름을 따서 만든 압축 알고리즘으로 press, zoo, lha, pkzip, arj등과 같은 우리가 잘 알고 있는 프로그램에서 널리 사용되는 것이다. 이 압축 방법의 특징은 잡음의 영향을 크게 받기 때문에 애니메이션이나 컴퓨터 그래픽 영상을 압축하는 데는 비교적 효과적이라고 할 수 있었지만, 스캐너로 입력한 사진이나 실 세계의 이미지 같은 경우에 이를 압축하는 데는 효과적이지 못하다고 평가되고 있다.
이에 비해 TIFF나 BMP등의 파일 포맷은 24비트 트루컬러까지 지원하여 시진 등의 이미지를 잘 표현해 낼 수 있지만 압축 알고리즘 자체가 LZW, RLE등의 방식을 사용하였으므로 압축률이 그렇게 좋지 않다는 단점이 있다.
이에 반해 현재의 JPEG기술은 사진과 같은 자연 영상을 약 20:1이상 압축할 수 있는 성능을 가지고 있어서 현재 사용되고 있는 정지 영상 파일 포맷 중에서는 최고의 압축률을 자랑하고 있다.
하지만 장점이 있으면 단점도 존재하기 마련이다. 단점이라면 기존의 영상 파일을 압축하는 시점에서 영상의 일부 정보를 손실 시키기 때문에 의료 영상이나 기타 중요한 영상 혹은 자연 영상 등에는 사용하는데 무리가 있다. 즉, GIF, TIFF등의 영상 파일은 영상을 압축한 후 복원하면 압축하기 전과 완전히 동일한 비손실 압축 방법이지만 JPEG이미지 포맷의 경우 손실 압축방법이라는 것이다. 하지만 손실이 된다고 해도 원래의 이미지와 그렇게 다르지 않은(거의 동일한) 이미지를 얻을 수 있기 때문에 영상 정보가 중요한 부분이 아니라면 효율적인 방법이라고 할 수 있다.
8.3 압축 방법
JPEG이 압축을 대상으로 삼는 사진과 같은 자연의 영상이 인접한 픽셀간에 픽셀 값이 급격하게 변하지 않는다는 속성을 이용하여 사람의 눈에 잘 띄지 않는 정보만 선택적으로 손실 시키는 기술을 사용하고 있기 때문이다.
이러한 압축 방법으로 인한 또 다른 단점이 있다. 인접한 픽셀간에 픽셀 값이 급격히 변하는 컴퓨터 영상이나 픽셀당 컬러 수가 아주 낮은 이진 영상이나, 16컬러 영상 등은 JPEG으로 압축하게 되면 오히려 압축 효율이 좋지 않을 뿐더러 손실된 부분이 상당히 거슬려 보인다는 것이다.
즉, 다른 이미지 압축 기술과 차별화 되는 신기술임에는 분명하지만 사용목적에 따라서 적절한 압축 알고리즘을 사용하는 것은 기본이라 하겠다.
JPEG의 압축방법 JPEG압축 알고리즘을 사용했다고 해서 이게 단 한가지의 압축 알고리즘만이 존재한다는 의미가 아님을 알고 있어야 한다. 다음과 같이 JPEG압축 알고리즘은 크게 네부분으로 나누어 볼 수 있다.
1. DCT(Discrete Cosine Transform) 압축 방법 :
일반적으로 JPEG영상이라고 하면 통용되는 압축 알고리즘이다.
2. 점진적 전송이 가능한 압축 방법 :
영상 파일을 읽어 오는 중에도 화면 출력을 할 수 있는 것을 의미하며 전송 속도가 낮은 네트워크를 통해 영상을 전송 받아 화면에 출력할 때 유용한 모드라고 할 수 있다. 즉, 영상의 일부를 전송 받아 저해상도의 영상을 출력할 수 있으며, 영상 데이터가 전송됨에 따라서 영상의 화질을 개선시키면서 화면에 출력이 가능하다는 것이다.
3. 계층 구조적 압축 알고리즘 :
피라미드 코딩 방법이라고도 하며, 하나의 영상 파일에 여러 가지 해상도를 갖는 영상을 한번에 저장하는 방법이다.
4. 비손실 압축 :
JPEG압축이라고 하여 손실 압축만 존재하는 것은 아니다. 이 경우에는 DCT압축 알고리즘을 사용하지 않고 2D-DPCM이라고 하는 압축방법을 이용하게 된다.
이처럼 JPEG표준에는 이와 같은 여러 가지 압축 방법이 규정되어 있지만, 일반적으로 JPEG로 영상을 압축하여 저장한다고 하면, DCT를 기반으로 한 압축 저장방법을 의미 한다.
이러한 방법을 또 다른 용어로 Baseline JPEG이라고 하며, JPEG영상 이미지를 지원하는 모든 어플리케이션은 이 이미지 데이터를 처리할 수 있는 알고리즘을 반드시 포함하고 있어야 한다. 즉, 나머지 3가지의 압축 방법을 꼭 지원하지 않아도 되는 선택사항이라는 의미이다.
8.4 Baseline 압축 알고리즘
이 방법은 손실 압축 방법이기 때문에 영상에 손실을 많이 주면 화질이 안 좋아지는 대신 압축이 많이 되고, 손실을 적게 주면 좋은 화질을 유지하기는 하지만 압축이 조금밖에 되지 않는다는 것이다. 이처럼 손실의 정도를 나타내는 값을 Q펙터라고 말하는데 이 값의 범위는 1부터 100까지의 값으로 나타나게 된다. Q펙터가 1이면 최대의 손실을 내면서 가장 많이 압축되는 방식이고 100이면 이미지 손실을 적개 주기는 하지만 압축은 적게 되는 방식이다. Q펙터가 100이라고 하여 비손실 압축이 이루어 지는 것은 아니라는데 주의할 필요가 있다.
베이스라인 JPEG은 JPEG압축 최소 사양으로, 모든 JPEG관련 애플리케이션은 적어도 이 방법을 반드시 지원해야 한다고 했다. 이러한 방식이 어떤 단계를 거치면서 수행되게 되는지 알아보도록 하자.
1. 영상의 컬러 모델(RGB)을 YIQ모델로 변환한다.
2. 2*2 영상 블록에 대해 평균값을 취해 색차(Chrominance)신호 성분을 다운 샘플링 한다.
3. 각 컬러 성분의 영상을 8*8크기의 블록으로 나누고, 각 블록에 대해 DCT알고리즘을 수행시킨다.
4. 각 블록의 DCT계수를 시각에 미치는 영향에 따라 가중치를 두어 양자화 한다.
5. 양자화된 DCT계수를 Huffman Coding방법에 의해 코딩하여 파일로 저장한다.
이렇게 압축된 파일을 다시 원 이미지로 복원할 때는 반대의 과정을 거치게 된다. 이러한 압축과 복원에 관해 어떤 식으로 처리가 되는지 그림으로 살펴보면 아래와 같다
<그림 7‑1> JPEG Encoding / Decoding 단계
8.5 JPEG의 실제 압축 / 복원 과정
1. 컬러모델 변환 :
컬러를 표현하는 방법에는 여러 가지가 있다. 가장 흔하게 사용하는 방법으로 RGB가 있다. 하지만 이러한 표현방법이 이것뿐이라면 좋겠지만 실제로는 그렇질 않다는 것이다.
RGB컬러는 모니터에서 사용하는 색상이고 빛의 3원색을 조합했을 때 나오는 색도 세 가지인데 이들은 하늘색(Cyan), 주황색(Magenta), 노랑색 (Yellow)이고, 이들의 조합으로도 모든 컬러를 표현 할 수 있게 된다. 이러한 방법을 CMY모델이라고 하며, 컬러 프린터가 이 모델을 이용해서 프린팅을 하게 된다.
우리가 논의 하려고 하는 YIQ라고 하는 모델은 밝기(Y : Luminance)와 색차(Chrominance : Inphase & Quadrature) 정보의 조합으로 컬러를 표현하는 방법이다.
다른 방법도 있다. 색상(Hue), 채도(Saturation), 명도(Intensity)의 색의 3요소로 색을 표현하는 HSI모델 등 여러 가지 컬러 모드가 있는 것이다.
RGB모델은 YIQ모델로 변환하는 방법이 있는데.. 이른 각각의 모델들도 서로 변환이 될 수 있다. RGB를 YIQ모델로 변환하는 식은 다음과 같다.
Y 0.299 0.587 0.114 R
I = 0.596 -0.275 -0.321 G
Q 0.212 -0.523 -0.311 B
<그림 7‑2> RGB의 YIQ 변환 식
이와 같은 식을 이용해서 JPEG압축을 하기 위해서는 컬러 모델을 YIQ모델로 변환을 한다. 많은 모델 중에서 이 모델로 변환을 하는 이유는 이중에서 Y성분은 시각적으로 눈에 잘 띄는 성분이지만 I, Q성분은 시각적으로 잘 띄지 않는 정보를 담고 있는 성질이 있어서, Y값만을 살려두고 I, Q값을 손실시키면 사람이 봤을 때에는 화질의 차이를 별로 느끼지 않으면서 정보를 양을 줄일 수 있는 장점이 있기 때문이다.
2. 색차 신호 성분 다운샘플링 : 앞에서도 이야기 했던 바와 같이 I와 Q의 성분은 시각적으로 눈에 잘 띄지 않는 정보들이기 때문에 이정보는 손실을 시켜도 사람이 보는데 특별한 지장을 주지 않는다.
손실을 시킨다는 의미이지 지워버린다는 의미는 아니다. 즉, Y값은 기억시키고, I, Q값은 가로 세로 2x2혹은 2x1크기를 블록당 한 개 만을 기억시키는 방식으로 정보만을 줄인다는 개념이다.
즉, 두번째 단계인 지금은 컬러모델을 변환한 것을 ‘다운 샘플링’ 한다는 것이다.
3. DCT적용 : JPEG알고리즘을 적용할 이미지 영상 블록에 어떤 주파수 성분이 얼마만큼 포함되어 있는지를 나타내는 8x8크기의 계수를 얻을 수 있게 된다. 픽셀간의 값의 변화율이 작은 밋밋한 영상은 저주파 성분을 나타내는 계수가 크게 나오게 되고, 픽셀간의 변화율이 큰 복잡한 영상은 고주파 성분을 나타내는 계수가 크게 나온다. 컬러를 표시하기 위한 각각의 YIQ성분은 8x8크기의 블록으로 나뉘어지고, 각 블록에 대해 DCT가 수행이 된다.
DCT는 Discrete Cosine Transform의 약자로 영상 블록을 서로 다른 주파수 성분의 코사인 함수로 분해하는 과정을 일컷는다.
이처럼 DCT를 수행하는 이유는 영상데이터의 경우 저주파 성분은 시각적으로 큰 정보를 가지고 있는 반면 고주파 성분의 경우는 시각적으로 별 의미가 없는 정보를 가지고 있기 때문에 시각적으로 적은 부분을 손실을 줌으로써 시각적인 손실을 최소화하면서 데이터 양을 줄이기 위한 것이다.
4. DCT 계수의 양자화 : 이론적으론 DCT자체만으로는 영상에 손실이 일어나지 않으며, DCT계수들을 기억하고 있으면 DCT역 변환을 통해 원 영상을 그대로 복원해 낼 수 있다. 실제로 영상에 손실을 주며, 데이터 량을 줄이는 부분은 DCT계수를 양자화 하는 바로 이 단계에서 이다.
계수 양자화란 여러 개의 값을 하나의 대표 값으로 대치시키는 과정을 말한다. 예를 들어 0에서 10까지의 값은 5로 대치시키고 10에서 20까지의 값은 15로 대치시키면 0부터 20까지의 값으로 분포되는 수많은 수들을 5와 15라는 두 개의 값으로 양자화 시킨 것이 된다. 이처럼 양자화 과정을 거치면 기억해야 할 수많은 경우의 수가 단지 몇 개의 경우의 수로 축소되기 때문에 데이터에 손실이 일어나지만 데이터 량을 크게 줄이는 장점이 있다.
양자화를 조밀하게 하면 데이터의 손실이 적어지는 대신 데이터 량은 그만큼 조금 줄게 되고, 양자화가 성기면 데이터의 손실은 많아지는 대신 데이터 량은 그만큼 많이 줄게 됩니다.
저주파 영역을 조밀하게 양자화하고 고주파 영역은 성기게 양자화하면 전체적으로 영상의 손실이 최소화 되면서 데이터 량의 감소를 극대화 시킬 수 있게 된다.
이처럼 주파수 성분 별로 어느 정도 간격으로 양자화를 하느냐에 따라 데이터 이미지의 질이 결정이 되는데 ISO에서는 실험적으로 결정한 양자화 테이블을 이용하여 양자화를 수행하는 것이 통상적이다.
영상의 화질과 압축률을 결정하는 변수인 Q펙터가 작용하는 부분도 바로 이 단계로. Q펙터를 크게 하면 전체적으로 양자화를 조밀하게 해서 손실을 줄임으로써 영상의 화질을 좋게 하고, Q펙터를 크게 하면 전체적으로 양자화 간격을 넓혀 화질에 손상을 많이 주어서 압축이 많이 되도록 하게 된다.
5. Huffman Coding : 양자화된 DCT계수는 자체로서 압축 효과를 갖지만 이를 더 효율적으로 압축하기 위해서 Huffman Coding으로 다시 한번 압축하여 파일에 저장을 한다.
JPEG의 실제 압축과 복원과정 알아보기 지금까지 영상데이터가 인코딩되는 과정을 단계적으로 알아보았다.
8.6 확장 JPEG
베이스라인 JPEG은 JPEG에 필요한 최소의 기능만을 규정한 것이라고 설명을 했다. 이 외에도 JPEG내에는 많은 압축 방법이 존재한다. 확장 JPEG의 기능은 반드시 지원할 필요는 없지만, JPEG파일 내에서 사용될 수 있으므로 확장 JPEG의 기능을 일단 인식은 할 수 있어야 하고, 지원되지 않는 기능이 파일에 들어 있을 경우 에는 에러메시지를 출력하도록 하여야 한다.
9 MPEG (Moving Picture Expert Group)
9.1 MPEG의 개념
MPEG은 동영상 압축 표준이다. MPEG 표준에는 MPEG1과 MPEG2, MPEG4, MPEG7 이 있다. 각각에 대해 비디오(동화상 압축), 오디오(음향 압축), 시스템(동화상과 음향 등이 잘 섞여있는 스트림)에 대한 명세가 존재한다.
MPEG1은 1배속 CD 롬 드라이버의 데이터 전송속도인 1.5 Mbps에 맞도록 설계되었다. 즉 VCR 화질의 동영상 데이터를 압축했을 때 최대비트율이 1.15 Mbps가 되도록 MPEG1-비디오 압축 알고리즘이 정해졌으며, 스테레오 CD 음질의 음향 데이터를 압축했을 때 최대비트율이 128 Kbps(채널당 64Kbps)가 되도록 MPEG1-오디오 압축 알고리즘이 정해졌다. MPEG1-시스템은 단순히 음향과 동화상의 동기화를 목적으로 잘 섞어놓은(interleave) 것이다.
MPEG2는 보다 압축 효율이 향상되고 용도가 넓어진 것으로서, 보다 고화질/고음질의 영화도 대상으로 할 수 있고 방송망이나 고속망 환경에 적합하다. 즉 방송 TV (스튜디오 TV, HDTV) 화질의 동영상 데이터를 압축했을 때 최대비트율이 4 ( 6, 40)Mbps가 되도록 MPEG2-비디오 압축 알고리즘이 정해졌으며, 여러 채널의 CD 음질 음향 데이터를 압축했을 때 최대 비트율이 채널당 64 Kbps 이하로 되도록 MPEG2 오디오 압축 알고리즘이 정해졌다.
MPEG2 -시스템은 여러 영화를 한데 묶어 전송하여주고 이때 전송시 있을 수 있는 에러도 복구시켜줄 수 있는 일종의 트랜스포트 프로토콜이다.
MPEG4는 매우 높은 압축 효율을 얻음으로써 매우 낮은 비트율로 전송하기 위한 것이다. 이를 사용함으로써 이동 멀티미디어 응용을 구현할 수 있다. MPEG4는 아직 표준이 완전히 만들어지지 않았으며, 매우 높은 압축 효율을 위해 내용기반(model-based) 압축 기법이 연구되고 있다.
9.2 MPEG의 표준
9.2.1 MPEG 1
MPEG 1의 표준은 4 부분으로 나누어져 있다.
1. 다중화 시스템부 : 동영상 및 음향 신호들의 비트열(Bit-stream) 구성 및 동기화 방식을 기술
2. 비디오부 : DCT와 움직임 추정(Motion Estimation)을 근간으로 하는 동영상 압축 알고리즘을 기술
3. 오디오부 : 서브밴드 코딩을 근간으로 하는 음향 압축 알고리즘을 기술
4. 적합성 검사부 : 비트열과 복호기의 적합성을 검사하는 방법
MPEG 1 영상 압축 알고리즘의 기본 골격은 움직임 추정과 움직임 보상을 이용하여 시간적인 중복 정보 제거한다.
1. 시간적인 중복성 - 수십 장의 정지 영상이 시간적으로 연속하여 움직일 때 앞의 영상과 현재의 영상은 서로 비슷한 특징을 보유
2. 제거방법 - DPCM(Differential PCM) 사용
3. DCT 방법을 이용하여 공간적인 중복 정보 제거
4. 공간 중복성 - 서로 인접한 화소끼리는 서로 비슷한 값을 소유
5. 제거방법 - DCT와 양자화를 이용
9.2.2 MPEG 2
MPEG 2의 표준화는 1990년 말부터 본격화 되었고 디지털 TV와 고선명 TV(HDTV) 방송에 대한 요구 사항이 추가되었고, 그 후 1995년 초 국제 표준으로 채택되었다.
MPEG 1과 마찬가지고 4 부분으로 나누어져 있지만 비디오부에서 디지털 TV와 고선명 TV 방송에 대한 사항이 첨가 되어있다.
1. 다중화 시스템부 : 음향, 영상, 다른 데이터 전송, 저장하기 위한 다중화 방법 정의
2. 비디오부 : 고화질 디지털 영상의 부호화를 목표로 MPEG-1에서 요구하는 순방 향 호환성을 만족, 격행 주사(Interlaced scan) 영상 형식과 HDTV 수준 의 해상도 지원 명시. 5개의 프로파일(Profile)과 4개의 레벨(Level)이 정 의
3. 오디오부 : 다중 채널 음향(샘플링 비율=16, 22.05, 24KHz)의 저전송율 부호화를 목표. 5개의 완전한 대역 채널(Left, Right, Center, 2 surround), 부가적 인 저주파수 강화 채널, 7개 해설 채널, 여러나라의 언어 지원 채널들 이 지원. 채널당 64Kbits/sec 정도의 고음질로 스테레오와 모노음을 부 호화
4. 적합성 검사부
MPEG 2 영상 압축 과정
1. 움직임 추정과 움직임 보상을 이용하여 시간적인 중복성을 제거
2. DCT와 양자화를 이용하여 공간적인 중복성을 제거
앞의 두 가지의 기본적인 압축 방법에 의하여 얻어진 데이타들의 발생 확률에 따라 엔트로피(Entrophy) 부호화 방법을 적용함으로써 최종적으로 압축 효율을 극대화
MPEG 2 표준은 멀티미디어 응용 서비스에 필수적인 디지털 저장 매체와 ISDN(Integrated Service Digital Network), B-ISDN(Broadband ISDN), LAN과 같은 디지털 통신 채널, 위성, 케이블, 지상파에 의한 디지털 방송매체 등을 응용 대상으로 삼고 있다.
9.2.3 MPEG 4
MPEG 4의 목적은 빠른 속도로 확산되고 있는 고성능 멀티미디어 통신 서비스 고려하여 기존의 방식과 새로운 기능들을 모두 지원할 수 있는 부호화 도구 제공를 제공하는 것이다. 그리고 양방향성, 높은 압축율 및 다양한 접속을 가능케 하는 AV(Audio/Video) 표준 부호화 방식을 지원한다. 또한 내용 기반 부호화(Content-based coding) 기술을 개발하고 초저속 전송에서부터 초고속 전송에 이르기까지 모든 영상 응용 분야에 융통성있게 대응할 수 있도록 한다.
주요 기능으로는 내용 기반 대화형 기능과 압축 기능, 광범위한 접근 기능을 갖고 있으며 내용 기반 대화형 기능은 멀티미디어 데이터 접근 도구, 처리 및 비트열 편집, 복합 영상 부호화, 향상된 시간 방향으로의 임의 접근을 할 수 있고 압축기능은 향상된 압축 효율, 복수개의 영상물을 동시에 부호화 할 수 있다. 그리고 광범위한 접근 기능은 내용 기반의 다단계 등급 부호화, 오류에 민감한 환경에서의 견고성을 갖도록 한다.
9.3 MPEG의 기본적인 압축 원리
처음에 MPEG-1은 352 * 240에 30을 기준으로 하는 낮은 해상도로 출발하였다. 그러나 음향 부분에서만은 CD수준인 16BIT 44.1Khz STEREO 수준으로 표준안이 제정되었다. MPEG에서 사용하는 동영상 압축원리는 두가지 기본 기술을 바탕으로 하고 있다.
9.3.1 시간,공간의 중복성 제거
동영상은 정지 영상과 달리 정지영상을 여러장 연속하여 저장하여 이루어지는 파일이다. 예를들어 AVI 파일을 동영상 편집 프로그램으로 풀어서 본다면 거의 비슷한 화면이 프레임수에 따라 여러장 있는 것을 알 수가 있다. MPEG은 이러한 시간에 따른 화면의 중복성을 제거하고 착시현상을 이용하여 실제와 비슷한 영상을 만들어내는 원리를 가지고 있다. 이러한 중복성은 시간적 중복성(TEMPORAL REDUDANCY)과 공간적 중복성(SPATIAL REDUDANCY)이 있는데 앞의 AVI화일의 예가 시간적 중복성이 되고 공간적 중복성은 예를 들어 카메라가 정지영상이나 한 인물을 집중적으로 촬영할 때 그 영상들의 공간 구성값의 위치는 비슷한 값들이 비슷한 위치에서 이동이 적어지는 확률이 높아지기 때문에 나타나는 중복성이라고 할 수 있다.
위에서 설명한 두가지 항목을 해결하기 위한 방법으로 시간의 중복성을 해결하기 위한 방법으로는 각 화면의 움직임 예상(Motion Estimation)의 개념을 응용하고 공간의 중복성을 해결하기 위한 방법으로는 DCT (Discreate Cosine Transforms)라는 개념과 양자화(quantigation)의 개념을 응용한다. vMotion Estimation은 16 * 16 크기의 블록으로 수행을 하며 DCT는 8 * 8 크기로 수행된다.
v DCT(Discreate Cosine Transforms)
영상에 있어서 고주파 부분을 버리고 저주파 부분에 집중시켜 공간적 중복성을 꾀하는 개념이다. 예를들어 에지(EDGE)가 많은 부분, 즉 얼굴의 윤곽이나, 머리카락이 흩날리는 부분 등은 화소 변화가 많으므로 이 부분을 제거하여 압축률을 높인다.
v 양자화(quantigation)
DCT로 구해진 화상정보의 계수값을 더 많은 '0'이 나오도록 일정한 값(quantizer value)으로 나오게 나누어 주다. 따라서 영상 데이터의 손실이 있더라도 사람의 눈에서 이를 시각적으로 감지하기 힘들게 된다면 어느 정도의 데이터에 손실을 가하여 압축률을 높이게 되는 것이다. 가장 단순한 양자화기는 스칼라(Scalar)양자화기로써 VLC(가변길이 부호기)와 병행하여 사용된다. 우선 입력 데이터가 가질 수 있는 값의 범위를 제한된 숫자의 구역으로 분할하여 각 구역의 대표 값을 지정한다. 스칼라 양자화기는 입력되는 화소값이 속하는 구역의 번호를 출력하고 구역의 번호로부터 이미 지정된 대표 값을 출력한다. 여기서 구역의 번호를 양자화 인덱스(quantigation index)라 하고 각 구역의 대표 값을 양자화 레벨(quantigation level)이라고 한다.
이 과정에서 최종적으로 나오는 이진 부호를 연속적으로 연결한 것을 비트 열이라 부르고 이보다 진보된 방법이 벡터 양자화기로서 전자의 스칼라 양자화기보다 압축률이 높다.
이 방법의 경우 입력이 인접한 화소의 블럭으로 이루어지며 양자화 코드에서 가장 유사한 코드 블록(양자화 레벨값에 해당)을 찾아 인덱스 부호값으로 결정한다. 간단하게 말하자면 스칼라(Scalar)양자화기는 2차원 적으로 압축하는 방식이며 벡터 양자화기는 3차원적으로 압축하는 방법이다.
MPEG-1에서는 버퍼의 상태에 따라서 이 값이 가변적으로 바뀌게 되어있고 MPEG-2에서는 이 방법에 화면의 복잡도를 미리 예측하여 양자화 값이 변하도록 미리 분석(forward analysys)하는 방법도 사용되어 화질을 향상시킬 수 있다..
v Motion Estimation
일반적인 실시간 동영상 압축방식에서는 아날로그 시그널(영상)을 이용해서 디지털 화하는데 일정한 움직임을 연산하여 추정할 수 있는 기능이 필요한데 이 기능을 수행해 주는 역할을 Motion Estimation이라고 한다.
9.3.2 I,P,B영상
이 세가지 영상은 MPEG 화상정보를 구성하고 있는 세가지 요소이다. 각 요소의 역할은 다음과 같다.
① I-FRAME (Intra-Frame) : 정지 영상을 압축하는 것과 동일한 방법을 사용하는 것으로 연속되는 화면의 기준을 이루는 화면이다.
② P-FRAME (Predict-Frame) : 이전에 재생된 영상을 기준으로 삼아 기준 영상 (I-PRAME)과의 차이점만을 보충하여 재생하는 화면이며 그 다음에 재생될 P-영상의 기준이 되기도 한다.
③ B-FRAME (Bidirectional-Frame) : I영상과 P영상 또는 P영상과 다음 P영상 사이에 들 어가는 재생된 영상인데 두 개의 기준영상을 양방향 에서 예측해서 붙여내는 영상이라서 이러한 이름을 갖는다.
④ 각 프레임의 배열 및 진행순서는 다음과 같다. (MPEG-1의 경우)
영상의 진행 방향
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
┃I┃B┃B┃P┃B┃B┃P┃B┃B┃I┃B┃B┃P┃B┃B┃P┃B┃B┃I┃B┃...
└── MPEG의 1프레임 ───┘
10 Conclusion
지금까지 세 가지의 압축 알고리즘을 살펴 보았다. Run-Length 압축법과 Lempel-Ziv 압축법은 고정 길이 압축법이고, Huffman 압축법은 가변 길이 압축법이라는 점에서 크게 구분된다. 그리고 그 프로그래밍도 판이하게 달랐다.
일반적으로 압축 알고리즘의 속도 면에서 보면 Run-Length 압축법이 가장 빠르지만 압축률은 가장 낮다. Run-Length 압축법은 파일 내에 동일한 문자의 연속된 나열이 있어야만 압축이 가능하기 때문이다.
이에 비해 Lempel-Ziv 압축법은 동일한 문자의 나열을 압축할 뿐 아니라, 동일한 패턴까지 압축하기 때문에 대부분의 경우에서 압축률이 가장 뛰어나다. 그러나 패턴 검색 방법이 최적화되지 않으면 속도면에서 불만을 안겨준다.
Huffman 압축법은 텍스트 파일처럼 파일을 구성하는 문자의 종류가 적거나, 파일을 구성하는 문자의 빈도의 편차가 클수록 압축률이 좋아진다. Huffman 압축법은 많은 빈도수의 문자를 짧은 길이의 코드로, 적은 빈도수의 문자를 긴 길이의 코드로 대치하는 방법이어서 Huffman 나무가 한쪽으로 쏠려 있을수록 압축률이 좋다.
그러나 빈도수가 고를 경우 Huffman 나무는 대체로 균형을 이루게 되어 압축률이 현저히 떨어진다. 또한 Huffman 압축법은 빈도수의 계산을 위해서 파일을 한번 미리 읽어야 하고, 다음에 실제 압축을 위해서 파일을 또 읽어야 하는 부담이 있어 실행 속도가 그리 빠르지는 않다.
실제 상용 압축 프로그램들은 주로 Huffman 압축법의 개량이나 Lempel-Ziv 압축법의 개량, 혹은 이 둘과 Run-Length 압축법까지 총동원해서 최대의 압축률과 최소의 실행시간을 보이도록 최적화되어 있다.
MPEG에 대해서는 가볍게 알아본 수준이므로 따로 결론을 내리지 않는다.
10.1 테스트 실행 결과 표
Lempel-Ziv Huffman Run-Length
압축전 압축후 압축률 시간
(tick) 압축후 압축률 시간
(tick) 압축후 압축률 시간
(tick)
10485760 10526665 100.39 519 10481196 99.96 333 10526667 100.39 63
1048576 1052778 100.40 52 1048699 100.01 33 1052778 100.40 6
102400 102837 100.43 4 103000 100.59 3 102837 100.43 0
10240 10287 100.46 0 10888 106.33 0 10287 100.46 0
1024 1037 101.27 0 1660 162.11 0 1037 101.27 0
10485760 10485745 100.00 672 8755440 83.50 282 10485759 100.00 61
1048576 1048586 100.00 68 875895 83.53 29 1048587 100.00 6
102400 102413 100.01 6 86042 84.03 3 102413 100.01 0
10240 10252 100.12 0 9162 89.47 0 10252 100.12 0
1024 1035 101.07 0 1496 146.09 0 1035 101.07 0
194166 186055 95.82 17 180201 92.81 5 189436 97.56 1
23030 22474 97.59 2 19720 85.63 0 23024 99.97 0
11140 9946 89.28 1 7094 63.68 0 10642 95.53 0
4290 3876 90.35 0 3212 74.87 0 4212 98.18 0
1837 1590 86.55 0 1628 88.62 0 1836 99.95 0
616 582 94.48 0 1004 162.99 0 604 98.05 0
10586696 8461305 79.92 1093 8588778 81.13 290 9952827 94.01 61
2855505 1752182 61.36 218 2435711 85.30 80 2829020 99.07 18
1578364 1314265 83.27 102 1519472 96.27 49 1574894 99.78 9
1325260 949081 71.61 84 1196847 90.31 39 1314600 99.20 7
1224317 874194 71.40 93 947260 77.37 31 1211083 98.92 8
500156 455638 91.10 30 483908 96.75 15 498860 99.74 2
319310 300707 94.17 20 313423 98.16 9 319376 100.02 2
238011 234044 98.33 12 238312 100.13 7 238467 100.19 1
132195 129917 98.28 7 132607 100.31 4 132438 100.18 1
103552 98095 94.73 5 102657 99.14 3 103245 99.70 0
122858 91968 74.86 9 111645 90.87 3 121114 98.58 1
9506895 6618476 69.62 1278 5490732 57.76 188 8535883 89.79 53
647976 470069 72.54 83 374771 57.84 12 596136 92.00 3
598794 361639 60.39 93 328800 54.91 11 489528 81.75 3
575805 375515 65.22 71 331114 57.50 11 525112 91.20 3
556584 240776 43.26 111 272773 49.01 9 367820 66.09 2
265104 144257 54.42 45 139221 52.52 5 196960 74.30 1
103894 79976 76.98 12 61884 59.56 2 97805 94.14 0
51266 39614 77.27 7 29175 56.91 1 47574 92.80 0
20529 15489 75.45 2 12665 61.69 0 19418 94.59 0
10304 7602 73.78 1 6800 65.99 0 9065 87.98 0
5121 3166 61.82 1 3384 66.08 0 4069 79.46 0
1021 704 68.95 0 1209 118.41 0 781 76.49 0
4114 2919 70.95 1 2984 72.53 0 3542 86.10 0
3081 1752 56.86 0 2350 76.27 0 2282 74.07 0
2051 1592 77.62 0 1769 86.25 0 1762 85.91 0
1541 1147 74.43 0 1543 100.13 0 1328 86.18 0
118 130 110.17 0 728 616.95 0 132 111.86 0
27 40 148.15 0 671 2485.19 0 40 148.15 0
2121600 993817 46.84 441 922054 43.46 33 2121615 100.00 14
980031 572607 58.43 93 623844 63.66 21 921999 94.08 5
186032 100912 54.24 15 121494 65.31 3 173524 93.28 1
56073 34332 61.23 4 38071 67.90 1 55945 99.77 0
11 참고문헌
C언어로 설명한 알고리즘, 황종선 외 1인
C로 배우는 알고리즘, 이재규
알고리즘 분석
|
장 |
내 용 |
파일명 |
|---|---|---|
|
1 |
1. 서론 |
|
|
2 |
2.1 기본 개념 |
|
|
2.3 퀵 정렬 |
||
|
2.4 합병 정렬 |
||
|
2.5 히프 정렬 |
||
|
2.7 특정 원소 순서 찾기 |
||
|
3 |
3.1 기본적인 탐색법 |
|
|
3.2 균형 탐색 |
||
|
3.3 해싱 |
||
|
4 |
4.1 기본 개념 |
|
|
4.4 유한 상태 자동 장치 |
||
|
5 |
5.1 기본 개념 |
|
|
5.3 블록 껍질 찾기 |
||
|
5.4 최근접 점쌍 찾기 |
||
|
7 |
7.1 서론 |
|
|
7.3 최적 이진 탐색 나무 |
||
|
8 |
8.1 기수 탐색 알고리즘 |
|
|
8.2 매턴 매칭 |
||
|
8.3 화일 압축 |
||
|
8.4 암호화 기법 |
- 점화식 풀이 [한글 97 | 한글 2002 ]
- 지난 시험문제
- UNIX에서 C 프로그램의 컴파일 및 디버그
- vi editor 사용법
- gcc, gdb 사용법
- 난수 발생기 및 시간 측정 방법
- 삽입정렬 알고리즘의 C 소스 프로그램
- Homework [ #1 | #2 ]
| 그래프 이론 Graph Theroy | | |||
| 링크 페이지 | |||
|
|||
|
|||
| |||
| 최적화 문제 Optimal Prob | ||||
| 링크 페이지 | ||||
|
||||
|
||||
|
||||
|
||||
| 유전자 알고리즘 Genetic Algo | ||||
| 링크 페이지 | ||||
|
||||
|
||||
|
||||
|
||||
|
||||
|
||||
|
||||
| 기술정보 | ||||
| 링크 페이지 | ||||
|
||||
|
||||
|
||||
|
||||
/********************************************************************
**
** Copyright (c) 1989 Mark R. Nelson
**
** LZW data compression/expansion demonstration program.
**
** April 13, 1989
**
*****************************************************************************/
#include <stdio.h>
#define BITS 12 /* Setting the number of bits to 12, 13*/
#define HASHING_SHIFT BITS-8 /* or 14 affects several constants. */
#define MAX_VALUE (1 << BITS) - 1 /* Note that MS-DOS machines need to */
#define MAX_CODE MAX_VALUE - 1 /* compile their code in large model if*/
/* 14 bits are selected. */
#if BITS == 14
#define TABLE_SIZE 18041 /* The string table size needs to be a */
#endif /* prime number that is somewhat larger*/
#if BITS == 13 /* than 2**BITS. */
#define TABLE_SIZE 9029
#endif
#if BITS <= 12
#define TABLE_SIZE 5021
#endif
void *malloc();
int *code_value; /* This is the code value array */
unsigned int *prefix_code; /* This array holds the prefix codes */
unsigned char *append_character; /* This array holds the appended chars */
unsigned char decode_stack[4000]; /* This array holds the decoded string */
/********************************************************************
**
** This program gets a file name from the command line. It compresses the
** file, placing its output in a file named test.lzw. It then expands
** test.lzw into test.out. Test.out should then be an exact duplicate of
** the input file.
**
*************************************************************************/
main(int argc, char *argv[])
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];
/*
** The three buffers are needed for the compression phase.
*/
code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
if (code_value==NULL || prefix_code==NULL || append_character==NULL)
{
printf("Fatal error allocating table space!\n");
exit();
}
/*
** Get the file name, open it up, and open up the lzw output file.
*/
if (argc>1)
strcpy(input_file_name,argv[1]);
else
{
printf("Input file name? ");
scanf("%s",input_file_name);
}
input_file=fopen(input_file_name,"rb");
lzw_file=fopen("test.lzw","wb");
if (input_file==NULL || lzw_file==NULL)
{
printf("Fatal error opening files.\n");
exit();
};
/*
** Compress the file.
*/
compress(input_file,lzw_file);
fclose(input_file);
fclose(lzw_file);
free(code_value);
/*
** Now open the files for the expansion.
*/
lzw_file=fopen("test.lzw","rb");
output_file=fopen("test.out","wb");
if (lzw_file==NULL || output_file==NULL)
{
printf("Fatal error opening files.\n");
exit();
};
/*
** Expand the file.
*/
expand(lzw_file,output_file);
fclose(lzw_file);
fclose(output_file);
free(prefix_code);
free(append_character);
}
/*
** This is the compression routine. The code should be a fairly close
** match to the algorithm accompanying the article.
**
*/
compress(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;
next_code=256; /* Next code is the next available string code*/
for (i=0;i<TABLE_SIZE;i++) /* Clear out the string table before starting */
code_value[i]=-1;
i=0;
printf("Compressing...\n");
string_code=getc(input); /* Get the first code */
/*
** This is the main loop where it all happens. This loop runs util all of
** the input has been exhausted. Note that it stops adding codes to the
** table after all of the possible codes have been defined.
*/
while ((character=getc(input)) != (unsigned)EOF)
{
if (++i==1000) /* Print a * every 1000 */
{ /* input characters. This */
i=0; /* is just a pacifier. */
printf("*");
}
index=find_match(string_code,character);/* See if the string is in */
if (code_value[index] != -1) /* the table. If it is, */
string_code=code_value[index]; /* get the code value. If */
else /* the string is not in the*/
{ /* table, try to add it. */
if (next_code <= MAX_CODE)
{
code_value[index]=next_code++;
prefix_code[index]=string_code;
append_character[index]=character;
}
output_code(output,string_code); /* When a string is found */
string_code=character; /* that is not in the table*/
} /* I output the last string*/
} /* after adding the new one*/
/*
** End of the main loop.
*/
output_code(output,string_code); /* Output the last code */
output_code(output,MAX_VALUE); /* Output the end of buffer code */
output_code(output,0); /* This code flushes the output buffer*/
printf("\n");
}
/*
** This is the hashing routine. It tries to find a match for the prefix+char
** string in the string table. If it finds it, the index is returned. If
** the string is not found, the first available index in the string table is
** returned instead.
*/
find_match(int hash_prefix,unsigned int hash_character)
{
int index;
int offset;
index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
if (index == 0)
offset = 1;
else
offset = TABLE_SIZE - index;
while (1)
{
if (code_value[index] == -1)
return(index);
if (prefix_code[index] == hash_prefix &&
append_character[index] == hash_character)
return(index);
index -= offset;
if (index < 0)
index += TABLE_SIZE;
}
}
/*
** This is the expansion routine. It takes an LZW format file, and expands
** it to an output file. The code here should be a fairly close match to
** the algorithm in the accompanying article.
*/
expand(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
char *decode_string(unsigned char *buffer,unsigned int code);
next_code=256; /* This is the next available code to define */
counter=0; /* Counter is used as a pacifier. */
printf("Expanding...\n");
old_code=input_code(input); /* Read in the first code, initialize the */
character=old_code; /* character variable, and send the first */
putc(old_code,output); /* code to the output file */
/*
** This is the main expansion loop. It reads in characters from the LZW file
** until it sees the special code used to inidicate the end of the data.
*/
while ((new_code=input_code(input)) != (MAX_VALUE))
{
if (++counter==1000) /* This section of code prints out */
{ /* an asterisk every 1000 characters */
counter=0; /* It is just a pacifier. */
printf("*");
}
/*
** This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
** case which generates an undefined code. It handles it by decoding
** the last code, and adding a single character to the end of the decode string.
*/
if (new_code>=next_code)
{
*decode_stack=character;
string=decode_string(decode_stack+1,old_code);
}
/*
** Otherwise we do a straight decode of the new code.
*/
else
string=decode_string(decode_stack,new_code);
/*
** Now we output the decoded string in reverse order.
*/
character=*string;
while (string >= decode_stack)
putc(*string--,output);
/*
** Finally, if possible, add a new code to the string table.
*/
if (next_code <= MAX_CODE)
{
prefix_code[next_code]=old_code;
append_character[next_code]=character;
next_code++;
}
old_code=new_code;
}
printf("\n");
}
/*
** This routine simply decodes a string from the string table, storing
** it in a buffer. The buffer can then be output in reverse order by
** the expansion program.
*/
char *decode_string(unsigned char *buffer,unsigned int code)
{
int i;
i=0;
while (code > 255)
{
*buffer++ = append_character[code];
code=prefix_code[code];
if (i++>=4094)
{
printf("Fatal error during code expansion.\n");
exit();
}
}
*buffer=code;
return(buffer);
}
/*
** The following two routines are used to output variable length
** codes. They are written strictly for clarity, and are not
** particularyl efficient.
*/
input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;
while (input_bit_count <= 24)
{
input_bit_buffer |=
(unsigned long) getc(input) << (24-input_bit_count);
input_bit_count += 8;
}
return_value=input_bit_buffer >> (32-BITS);
input_bit_buffer <<= BITS;
input_bit_count -= BITS;
return(return_value);
}
output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;
output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
output_bit_count += BITS;
while (output_bit_count >= 8)
{
putc(output_bit_buffer >> 24,output);
output_bit_buffer <<= 8;
output_bit_count -= 8;
}
}
zlib를 이용한 zip 압축 기능 구현 테스트 프로그램.
단순 압축 기능만 콘솔 프로그램으로 구현해본 것입니다.
소스는 다음과 같습니다.
/*
* 파일명 : ZipTest.cpp
* 사용법 : ZipTest [filename]
* 압축하고자 하는 filename를 입력하면 filename.zip이라는 압축파일이
* 생성된다.
*/
// 표준 C헤더파일
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// zlib 헤더파일
#include <zlib.h>
int main(int argc, char *argv[])
{
char *filename = NULL;
char *gzfilename = NULL;
gzFile zf;
int n;
char buf[256];
int lerrno;
FILE *fp;
if(argc !=2) {
printf("Usage : ZipTest [file name]\n");
exit(0);
}
filename = argv[1];
// 압축파일의 이름은 filename.zip 으로 한다.
gzfilename = (char *)malloc(strlen(filename)*sizeof(char));
sprintf(gzfilename, "%s.zip", filename);
if ((fp = fopen(filename, "rb")) == NULL) {
printf("file open error\n");
exit(0);
}
// 압축파일을 연다.
if ((zf = gzopen(gzfilename, "wb")) == NULL) {
exit(0);
}
// 원본파일을 에서 데이타를 읽어들이고
// gzwrite함수를 이용해서 데이터를 압축하고 파일에 쓴다.
while((n = fread(buf, sizeof(char), 255, fp)) > 0)
{
if (gzwrite(zf, buf, n) < 0) {
printf("%s\n",gzerror(zf, &lerrno));
exit(0);
}
}
gzclose(zf);
printf("compression completed : %s => %s\n", filename, gzfilename);
return 0;
}
앞서 만든 ZipTest로 만든 압축 프로그램을 풀어주는 UnzipTest 입니다.
역시 기능 구현 테스트만을 위해 간단히 콘솔 프로그램으로 만들었고 zlib를 이용했습니다..
소스는 다음과 같습니다.
// UnzipTest.cpp : Defines the entry point for the console application.
#include <stdio.h>
#include <stdlib.h>
#include <zlib.h>
#define BUF_SIZE 1024
int main(int argc, char* argv[])
{
char *srcFileName, *destFileName;
gzFile zfSrc;
FILE *fpDest;
char buf[BUF_SIZE];
int gzr;
// 파라미터가 맞지 않으면 종료
if(argc != 3) {
printf("Usage: UnzipTest [source filename] [destination filename]");
exit(0);
}
srcFileName = argv[1];
destFileName = argv[2];
// 파일이 존재하지 않으면 종료
if((zfSrc = gzopen(srcFileName, "rb")) == NULL) {
printf("can't open source file");
exit(0);
}
// destination 파일 열기
if((fpDest = fopen(destFileName, "wb")) == NULL) {
gzclose(zfSrc);
printf("can't create destination file");
exit(0);
}
// 압축 풀기
while((gzr = gzread(zfSrc, buf, BUF_SIZE)) > 0) {
fwrite(buf, sizeof(char), gzr, fpDest);
}
gzclose(zfSrc);
fclose(fpDest);
// 에러발생시 종료
if(gzr < 0) {
printf("Error occured.");
exit(0);
}
printf("Decompression completed.");
return 0;
}
일단 기본적인 압축 및 압축 푸는 기능은 구현할 수 있게 되었습니다. 하지만 여러 파일(폴더 포함)을 하나의 압축파일로 묶어서 압축하는 건 어떻게 해야 할지 아직까지는 모르겠군요. 좀더 연구를 해보야야겠습니다.
앞서 만든 두개의 ZipTest, UnzipTest 프로그램은 zip 압축 프로그램이 아니라 gz 압축 프로그램이었다. 첨엔 zlib가 zip 압축을 위한 라이브러리인줄 알았으나 사실은 gz 압축용 라이브러리였던 것이다. 이런..
(혹시 믿고 따라하신 분이 계셨다면 정말로 사과의 말씀드립니다. 사실 저도 몰랐답니다. ㅠㅠ)
그렇다면 zlib는 zip 압축을 지원하지 않는가? http://zlib.net 의 FAQ에서는 다음과 같이 대답해주고 있다.
Can zlib handle .zip archives?
Not by itself, no. See the directory contrib/minizip in the zlib distribution.
Not by itself 라니, 이 무슨 애매모호한 대답인가. -_-; 하지만 이 대답과 기타 여러 정황(?)으로 볼때 zip과 gz은 전혀 상관 없는 것도 아니라는 것이다. http://www.winimage.com/zLibDll/unzip.html 를 보면 이런 말이 나온다.
Using Unzip package
The Unzip source is only two file : unzip.h and unzip.c. But it use the Zlib files.
miniunz.c is a very simple, but real unzip program (display file in zipfile or extract them).
Using Zip package
The Zip source is only two file : zip.h and zip.c. But it use the Zlib files.
minizip.c is a very simple, but real zip program.
zip과 unzip 기능을 해주는 소스는 내부적으로 zlib를 이용한다고 한다. 이런 추리가 가능하다. gz은 단순 파일 압축이며, zip은 zlib 등의 gz 압축 알고리즘을 이용하되 이를 다수의 파일 및 폴더에 대한 압축이 가능하도록 만든 것이다라는.. 물론 틀린 추론일 수도 있다. -.-;
하지만 분명한 것은 Gilles Vollant가 만든 minizip의 네개의 소스 zip.h, zip.c, unzip.h, unzip.c를 이용하면 zip 압축 기능의 구현이 가능할 것이라는 사실이다.
헌데 여기서 한가지 문제가 있다. zip.c, unzip.c 라는 파일명을 보아도 알수 있지만 이것은 C++이 아닌 C로 쓰여진 프로그램이라는 것이다. 물론 VC++에서 C 컴파일이 가능하지만, 이를 C++로 래핑(wrapping)해 놓은 소스가 있다.
http://www.codeproject.com/cpp/zipunzip.asp 이곳에서 얻을 수 있을 것이다. Win32 Wrapper classes for Gilles Volant's Zip/Unzip API 라는 제목의 Zip/Unzip API란 바로 위에서 소개한 zip.h, unzip.h에서 찾을 수 있는 API들일 것이다. 이것을 Daniel Godson이라는 사람이 친절하게도 Win32 버전으로 래핑해놓은 것이다.
Win32 Wrapper classes for Gilles Volant's Zip/Unzip API 의 클래스 CZipper CUnzipper의 public 메소드 원형입니다.
class CZipper
{
public:
CZipper(LPCTSTR szFilePath = NULL, LPCTSTR szRootFolder = NULL, bool bAppend = FALSE);
virtual ~CZipper();
// simple interface
static bool ZipFile(LPCTSTR szFilePath); // saves as same name with .zip
static bool ZipFolder(LPCTSTR szFilePath, bool bIgnoreFilePath); // saves as same name with .zip
// works with prior opened zip
bool AddFileToZip(LPCTSTR szFilePath, bool bIgnoreFilePath = FALSE);
bool AddFileToZip(LPCTSTR szFilePath, LPCTSTR szRelFolderPath); // replaces path info from szFilePath with szFolder
bool AddFolderToZip(LPCTSTR szFolderPath, bool bIgnoreFilePath = FALSE);
// extended interface
bool OpenZip(LPCTSTR szFilePath, LPCTSTR szRootFolder = NULL, bool bAppend = FALSE);
bool CloseZip(); // for multiple reuse
void GetFileInfo(Z_FileInfo& info);
};
class CUnzipper
{
public:
CUnzipper(LPCTSTR szFilePath = NULL);
virtual ~CUnzipper();
// simple interface
static bool Unzip(LPCTSTR szFileName, LPCTSTR szFolder = NULL, bool bIgnoreFilePath = FALSE);
// works with prior opened zip
bool Unzip(bool bIgnoreFilePath = FALSE); // unzips to output folder or sub folder with zip name
bool UnzipTo(LPCTSTR szFolder, bool bIgnoreFilePath = FALSE); // unzips to specified folder
// extended interface
bool OpenZip(LPCTSTR szFilePath);
bool CloseZip(); // for multiple reuse
bool SetOutputFolder(LPCTSTR szFolder); // will try to create
// unzip by file index
int GetFileCount();
bool GetFileInfo(int nFile, UZ_FileInfo& info);
bool UnzipFile(int nFile, LPCTSTR szFolder = NULL, bool bIgnoreFilePath = FALSE);
// unzip current file
bool GotoFirstFile(LPCTSTR szExt = NULL);
bool GotoNextFile(LPCTSTR szExt = NULL);
bool GetFileInfo(UZ_FileInfo& info);
bool UnzipFile(LPCTSTR szFolder = NULL, bool bIgnoreFilePath = FALSE);
// helpers
bool GotoFile(LPCTSTR szFileName, bool bIgnoreFilePath = TRUE);
bool GotoFile(int nFile);
};
CZipper 에 대해서는 약간의 추가 설명을 찾을수 있었습니다.
출처 http://www.codeproject.com/cpp/zipunzip.asp
The CZipper class interface provides two approaches to zipping:
1. For simple file and folder zipping, you can use the static ZipFile(...) or ZipFolder(...) methods.
2. For more complex zipping requirements, you can alternatively instantiate a CZipper object, then use OpenZip(...), followed by one or more AddFileToZip(...) or AddFolderToZip(...) calls, before ending with CloseZip().
CZipper 클래스 인터페이스는 zip 압축에 대한 방법을 제공한다.
1. 한개의 파일이나 폴더 압축을 하려면, 정적 메소드 ZipFile(...)과 ZipFolder(...)를 사용하면 된다.
2. 좀더 복잡한 zip 압축을 하고 싶다면, CZipper의 인스턴스를 생성한 후, OpenZip(...)을 호출하고, AddFileToZip(...)이나 AddFolderToZip(...)를 사용하여 파일이나 폴더를 추가하고, CloseZip()으로 마무리한다.
zip 통합 라이브러리를 만들었습니다.
http://zlib.net 의 zlib,
Gilles Volant 의 Zip/Unzip API,
Daniel Godson 의 Win32 Wrapper 클래스를 모두 모아 컴파일하여 통합 라이브러리로 만들었습니다.
각각의 API 에 해당하는 헤더 파일은 관련 사이트에서 소스를 받으시면 함께 받으실 수 있을 겁니다. 윈도우에서의 간단한 zip 압축 구현을 위해서라면 Daniel Godson 의 소스중 Zipper.h, Unzipper.h 만 있어도 될 것입니다.
앞에서 만든 zip 통합 라이브러리 zipunzip.lib를 이용한 zip 압축 프로그램입니다.
역시 기능 구현 테스트를 위하여 간단히 콘솔 프로그램으로 만들었습니다.
소스는 다음과 같습니다.
// SimpleZip.cpp : Defines the entry point for the console application.
// Usage: SimpleZip [flag] [source file]
// flag: c - compress
// d - decompress
#include <stdio.h>
#include <windows.h>
#include <zipper.h>
#include <unzipper.h>
int main(int argc, char* argv[])
{
char *srcFileName;
bool bSrcIsDirectory, br;
DWORD fileAttr;
// 파라미터 확인
if(argc != 3) {
printf("Usage: SimpleZip [flag] [source file]\n");
printf(" flag: c - compress\n");
printf(" d - decompress");
exit(0);
}
srcFileName = argv[2];
// 소스 파일 확인
bSrcIsDirectory = ((fileAttr = GetFileAttributes(srcFileName)) & FILE_ATTRIBUTE_DIRECTORY) > 0;
if(fileAttr == 0xFFFFFFFF) {
printf("file not exist or has unknown problems");
exit(0);
}
switch(argv[1][0]) {
case 'c':
case 'C':
// 디렉토리인 경우
if(bSrcIsDirectory) {
br = CZipper::ZipFolder(srcFileName, FALSE);
}
// 파일인 경우
else {
br = CZipper::ZipFile(srcFileName);
}
printf(br ? "compression completed." : "error occured.");
break;
case 'd':
case 'D':
// 디렉토리인 경우
if(bSrcIsDirectory) {
printf("%s isn't a file", srcFileName);
exit(0);
}
// 파일인 경우
else {
CUnzipper uz;
br = uz.OpenZip(srcFileName);
if(br) br = uz.UnzipTo(".");
printf(br ? "decompression completed." : "error occured.");
}
break;
default:
printf("wrong flag.");
break;
}
return 0;
}
|
간단하게 디렉토리를 압축할수 있게하는 라이브러리이다. http://joyholic.kr/trackback/32 위 사이트를 참고하여 Zlib( http://www.winimage.com/zLibDll/index.html ) MiniZip( http://www.winimage.com/zLibDll/minizip.html ) zipunzip 라이브러리( http://www.codeproject.com/KB/cpp/zipunzip.aspx ) 사이트에 가.. |
이미지 압축에서 기본은 RLE(Run Length Encoding)라는 압축입니다. 이는 비손실 압축방식이며
복잡한 압축 알고리즘이 많지만 보다 적용하기 간단하다는 장점이 있습니다.
그렇지만 여전히 그 조금 부족한 부분이 있는데요.
그건 바로 복잡한 패턴을 가진 이미지일경우
오히려 압축한 데이터가 원본보다 더 커진다는데 있습니다.
게임 프로그래밍에서는 엄밀히 말해서 2D에서는 이방식을 많이 사용하고 있습니다.
왜냐하면 많은 공간이 키컬러(Key Color;투명색)이 차지하는 이미지가 많기 때문이죠.
따라서 RLE 방식을 조금 개선하여 만들어본 이미지 압축루틴을 소개할까 합니다.
아울러서 고속 블렌딩 기법도 팁으로 소개도 해드리죠... 오늘은 늦은 관계로
일단 클래스 해더만 보도록 하겠습니다.
다음 이미지 해더 정보는 보통 비트맵 해더와 비슷합니다. 간단히 매직번호로
이미지데이터를 식별하도록 하며 버저정보도 지원하도록 하죠. 이때 DWORD로 하였으므로
비트연산으로 한꺼번에 매직과 버전을 dwSignature 에 넣을 수 있도록 매크로도 만들었습니다.
// JR-Image Header
#define JRI_MAGIC (0x01<<24|'I'<<16|'R'<<8|'J')
#define JRI_VERSION(x) ((x&0xFF000000)>>24)
struct JRI_HEADER
{
DWORD dwSignature; // 파일식별코드
DWORD dwWidth; // 이미지의 넓이
DWORD dwHeight; // 이미지의 높이
DWORD dwRGBBitCount; // Used RGB Bit Count - 15, 16, 24
DWORD dwSize; // Compressed size
DWORD dwBitmapSize; // Uncompressed size
DWORD dwColorKey; // 투명색
};
/**
* JRI 압축형식의 이미지 클래스
* @author 장지락
* @date 2004-03-03 1:50오전
* @version 1.0
*/
class CImageEx
{
public:
// JRI static member data
JRI_HEADER * m_lpHeader;
WORD * m_lpImage;
// JRI dynamic member data(runtime)
BOOL m_bIndirected;
BOOL m_bAutoColorKey;
RECT m_ClipRect;
public:
CImageEx();
virtual ~CImageEx();
/**
* JRI 생성
*/
HRESULT Create(const char * cszFilename );
HRESULT Create(const BYTE * lpCache, DWORD lSize, BOOL bIndirected=FALSE);
HRESULT Change(const BYTE * lpCache, DWORD lSize);
/**
* Image Validate
*/
static
HRESULT Validate(const BYTE * lpHead);
DWORD GetWidth(){ return m_lpHeader->dwWidth; }
DWORD GetHeight(){ return m_lpHeader->dwHeight; }
/**
* Clipper
*/
BOOL ClipRect(RECT * Rect);
BOOL ClipRect(RECT * srcRect, RECT * destRect);
BOOL ValidateBlt(RECT * tRect, LONG * lDestX, LONG *lDestY, RECT * srcRect);
/**
* Display
*/
HRESULT Blt(WORD * lpTarget, LONG x, LONG y, LONG dPitch, RECT *dstRect=NULL, RECT *srcRect=NULL);
HRESULT BltHFlip(WORD * lpTarget, LONG x, LONG y, LONG dPitch, RECT *dstRect=NULL, RECT *srcRect=NULL);
/**
* Set AutoColorKey
*/
void AutoColorKey(void){ m_bAutoColorKey=FALSE; }
/**
* Image convert
*/
HRESULT RGB555To565(void);
HRESULT RGB565To555(void);
HRESULT BMP2JRI(LPCSTR szSrcBMP, LPCSTR szDstJRI, BYTE *pHeader=NULL);
HRESULT JRI2BMP(LPCSTR szSrcJRI, LPCSTR szDstBMP);
/**
* JRI or BMP File I/O
*/
HRESULT Open(const char * cszFilename ); // JRI Open
HRESULT Save(const char * cszFilename ); // JRI Save
HRESULT OpenAsBMP(const char * cszFilename );
HRESULT SaveAsBMP(const char * cszFilename );
/**
* Save routine for AFSprite!
*/
HRESULT Appendix(HANDLE hFile);
protected:
/**
* DECODE 관련
*/
HRESULT DecodeBlt1( const WORD * lpSource, WORD * lpTarget, LONG x, LONG y, LONG dPitch, RECT *dstRect=NULL, RECT *srcRect=NULL );
HRESULT DecodeBlt2( const WORD * lpSource, WORD * lpTarget, LONG x, LONG y, LONG dPitch, RECT *dstRect=NULL, RECT *srcRect=NULL );
HRESULT DecodeJRI( const WORD * lpSource, WORD * lpTarget );
/**
* ENCODE 관련
*/
WORD * Encode( const BYTE * lpSrc, UINT nWidth, UINT nHeight, DWORD& dwRefSize );
UINT ProcessLn( BYTE* lpSrc, WORD* lpDst, WORD nWidth );
WORD CountRuns( BYTE * lpSrc, UINT nLength );
WORD CountSkip( BYTE * lpSrc, UINT nLength );
WORD CountDraw( BYTE * lpSrc, UINT nLength );
};
기본적인건 이렇구요... 좀더 객체지향적으로 꾸밀 수도 있겠죠... 인터페이스 클래스를
정의해서 상속받는것도 좋은 방법이 되겠지요...
그러나 여기선 그런건 일단 넘어가기로 하고... 위의 클래스 구조가 잡혔으니 다음엔 구현을 하나씩 하나씩 집어 가면서 예기하겠습니다.
좀 부족한 감이 있지만 일단 오늘은 이까지하고 혹시 질문 있으시면 댓글을 이용해주시길...
[P.S. 1] 게임 프로그래밍에 관심있으신 분은 한번쯤은 보셔야할 부분입니다.
[P.S. 2] 앗~ 빨간색으로 된건 아주 위험한 코드입니다. public이므로 외부에서 멋도 모르고
호출했다면 segmentation fault가 나겠죠... 아무 생각없이 한 코드고 별로 이쁘지도
않고... 쩜 옛날엔 이렇게나 생각없는 코드와 클래스 구성을 했네욥 ㅠ.ㅠ
// 기본 생성자(Constructor)
CImageEx::CImageEx()
{
m_lpHeader = NULL;
m_lpImage = NULL;
m_bIndirected = FALSE;
m_bAutoColorKey = TRUE;
}
// 기본 소멸자(Destructor)
CImageEx::~CImageEx()
{
if( m_bIndirected )
{
m_lpHeader = NULL;
m_lpImage = NULL;
} else {
FREE_SAFE( m_lpHeader );
FREE_SAFE( m_lpImage );
}
}
class 해더에 보면 기본생성자와 소멸자가 있었죠? 뭐 별다른 건 없구 그냥 포인터들을
초기화 시키는 것 밖에 없네요 ^^ 물론 소멸자가 호출되면 할당되어 있는 메모리를 다시
시스템에 환원시켜주는 코드가 있네요. 어딘지는 알겠죠? ㅋㅋㅋ 모르시면 C++ 강좌를
읽어 보세요.
// 이미 존재하는 파일로 부터 객체 생성하기
HRESULT CImageEx::Create(const char * cszFilename)
{
HRESULT hr = AF_OK;
DWORD dwBytesRead = 0;
HANDLE hFile = NULL;
DWORD dwFileSize = 0;
BYTE * lpCache = NULL;
// Encoded Image 읽기위해서 파일 핸들을 생성함.
hFile = ::CreateFile( cszFilename, GENERIC_READ,
FILE_SHARE_READ, NULL,
OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0 );
// 만약 실패했다면?
if( hFile == INVALID_HANDLE_VALUE )
{
return ERR_FILE_OPEN;
}
// WIN32 루틴으로 파일 주어진 파일핸들로 부터 사이즈를 구한다.
if( (dwFileSize = ::GetFileSize(hFile, NULL)) <= 0 )
{
hr = ERR_FILE_SIZE;
goto L_ERROR; // 고투가 무조건 나쁜건 아닙니다.
}
// 이미지 데이터를 읽어올 메모리 공간 확보
if( (lpCache = (BYTE*)malloc( dwFileSize )) == NULL )
{
hr = ERR_MEM_ALLOC;
goto L_ERROR;
}
// 메모리로 이미지 데이터를 읽어 오자.
if( !::ReadFile( hFile, lpCache, dwFileSize, &dwBytesRead, NULL) )
{
hr = ERR_FILE_READ;
goto L_ERROR;
}
hr = Create(lpCache, dwFileSize, FALSE);
// 실패시 처리
L_ERROR:
FREE_SAFE(lpCache);
::CloseHandle(hFile);
return hr;
}
HRESULT CImageEx::Create(const BYTE * lpCache, DWORD lSize, BOOL bIndirected)
{
// 항상 이렇게 넘어온 데이터들을 의심하는 자세가 필요하다.
if( !lpCache || lSize <= sizeof(JRI_HEADER) )
{
return ERR_NO_INITIAL;
}
// 주어진 데이터가 올바른지 validate한다.
if( JRI_FAILED( Validate(lpCache) ) )
{
return ERR_BAD_JRI;
}
if( bIndirected )
{
// 이미 로드되었거나 기존에 있던 메모리를 그대로 변수
// 포인터만 가지고 생상, 동일한 많은 데이터가 생성되면 그냥
// 이렇게 하는거 더 퍼포먼스가 좋다.
m_lpHeader = (JRI_HEADER*)lpCache;
m_lpImage = (WORD*)(&lpCache[sizeof(JRI_HEADER)]);
} else {
// 직접적으로 생으로 메모리를 할당하고 데이터를 로드한다.
m_lpHeader = (AFI_HEADER*)malloc( sizeof(JRI_HEADER) );
::CopyMemory( m_lpHeader, lpCache,sizeof(JRI_HEADER) );
m_lpImage = (WORD*)malloc( m_lpHeader->dwSize );
::CopyMemory( m_lpImage, &lpCache[sizeof(JRI_HEADER)], m_lpHeader->dwSize );
}
// 기본적으로 이미지는 클리핑 되지 않구 전체를 나타낼수 있도록 한다.
m_ClipRect.top = 0;
m_ClipRect.left = 0;
m_ClipRect.right = m_lpHeader->dwWidth;
m_ClipRect.bottom = m_lpHeader->dwHeight;
return JRI_OK;
}
// 이미지를 검증하는 루틴이다.
HRESULT CImageEx::Validate(const BYTE * lpHead)
{
if( *((DWORD*)lpHead) == JRI_MAGIC ) return JRI_OK;
return ERR_BAD_JRI;
}
BOOL CImageEx::ClipRect(RECT * Rect)
{
// Check if Rect is completely outside of the m_clipRect (Screen Space)
if (Rect->top >= m_ClipRect.bottom)
return FALSE;
if (Rect->left >= m_ClipRect.right)
return FALSE;
if (Rect->bottom <= m_ClipRect.top)
return FALSE;
if (Rect->right <= m_ClipRect.left)
return FALSE;
// Clip rect to the surface's clipRect
if (Rect->top < m_ClipRect.top)
Rect->top = m_ClipRect.top;
if (Rect->left < m_ClipRect.left)
Rect->left = m_ClipRect.left;
if (Rect->bottom > m_ClipRect.bottom)
Rect->bottom = m_ClipRect.bottom;
if (Rect->right > m_ClipRect.right)
Rect->right = m_ClipRect.right;
return TRUE;
}
BOOL CImageEx::ClipRect(RECT * srcRect, RECT * dRect)
{
// Check if Rect is completely outside of the m_clipRect (Screen Space)
if (srcRect->top >= dRect->bottom)
return FALSE;
if (srcRect->left >= dRect->right)
return FALSE;
if (srcRect->bottom <= dRect->top)
return FALSE;
if (srcRect->right <= dRect->left)
return FALSE;
// Clip rect to the surface's clipRect
if (srcRect->top < dRect->top)
srcRect->top = dRect->top;
if (srcRect->left < dRect->left)
srcRect->left = dRect->left;
if (srcRect->bottom > dRect->bottom)
srcRect->bottom = dRect->bottom;
if (srcRect->right > dRect->right)
srcRect->right = dRect->right;
return TRUE;
}
나머지 부분은 잠이 오는 관계로 다음에 올릴려구 한다. ㅡ,,ㅡ 아구구 졸려랑...
처음에는 나머지 부분들 즉 파일 open/save 같은것두 올렸는데...
너무 코드만 나와서 보기가 좀 그렇더군요.
그래서 다시 핵심 이미지 인코딩/디코딩 부분만 올립니다.
사실 이것만 있으면 bmp같은 이미지를 컨버팅하여 자신만의 이미지 포맷을
만들 수 있습니다. JPEG나 GIF 같은 이미지들은 복잡한 압축 알고리듬을 사용하지만
그것들도 용량상의 이점이 있지만 실제 압축을 하고/푸는데 시간이 많이
든다는 단점이 있으므로 좋고 나쁨이 없습니다. 다음 코드들을 보다가
다소 어려운 점이나 궁금한 점은 댓글을 남겨주시면 답변해드리겠습니다.
HRESULT CImageEx::DecodeJRI( const WORD * lpSource, WORD * lpTarget )
{
DWORD dwWPL = 0; // Words Per Line
DWORD dwBPL = 0; // Bytes Per Line
WORD nSkip = 0; // Skip to Draw
WORD nDraw = 0; // Need to Draw
WORD nRuns = 0; // Runs Counter
int register i = 0;
int register j = 0;
// Word Per Line
dwBPL = ((((m_lpHeader->dwWidth * m_lpHeader->dwRGBBitCount) + 31) & ~31) >> 3);
dwWPL = ((((m_lpHeader->dwWidth * m_lpHeader->dwRGBBitCount) + 31) & ~31) >> 3) >> 1;
// Perform some boundry checking
WORD * lpLine = NULL;
#ifdef JR_NORMAL_ENCODE
WORD * lpDst = (WORD*)lpTarget;
#else
WORD * lpDst = (WORD*)lpTarget + (dwWPL * (m_lpHeader->dwHeight-1));
#endif
WORD * lpSrc = (WORD*)lpSource;
#ifdef JR_NORMAL_ENCODE
i = 0;
while( i < m_lpHeader->dwHeight )
#else
i = m_lpHeader->dwHeight;
while( i > 0 )
#endif
{
lpLine = lpDst;
nRuns = *lpSrc; // getting runs count
lpSrc++; // forward source image mem-pointer
// skipping whole line
switch( nRuns )
{
case 0: break;
// drawing whole line
case 1:
::CopyMemory( lpLine, lpSrc, dwBPL );
lpSrc += dwWPL;
break;
// drawing & skip
default :
while( (--nRuns) > 0 )
{
nSkip = *lpSrc; // get skip length
lpSrc++; // increment source image pointer
lpLine += nSkip;// increment target image pointer with skip length
nDraw = *lpSrc; // get draw length
lpSrc++; // increment source image pointer
::CopyMemory( lpLine, lpSrc, nDraw<<1 );
lpLine += nDraw;
lpSrc += nDraw;
}
}
#ifdef JR_NORMAL_ENCODE
lpDst += dwWPL;
i++;
#else
lpDst -= dwWPL;
i--;
#endif
}
return JR_OK;
}
WORD * CImageEx::Encode( const BYTE * lpSrc, UINT nWidth, UINT nHeight, DWORD& dwRefSize )
{
INT nCWL = 0; // Current Work Line
UINT nBPL = 0; // Bytes Per Line
UINT nPS = 0; // Prediction Image Size
UINT nCount = 0; // Compressed Image Size
WORD * lpRetImg = NULL; // 최종 압축 결과 이미지
WORD * lpWorkImgMem = NULL; // 압축 작업 공간
WORD * lpWorkImg = NULL; // 압축 작업 공간
BYTE * lpSrcImg = NULL; // 원본 이미지...
// 작업을 하기전에 Ref변수는 초기화 한다...
dwRefSize = 0;
// 최악의 경우 오리지널 이미지 보다 커진다.
nPS = (nWidth*nHeight) * 4;
int nPadding = (8 * abs(nWidth)) % 4;
if( nPadding > 0 )
{
nPadding = ( 4 - nPadding );
}
// Current Work Line
#ifdef JR_NORMAL_ENCODE
nCWL = 0;
lpSrcImg = (BYTE*)( lpSrc ); // 압축할 이미지의 데이터를 가리키는 포인터
#else
nCWL = nHeight;
lpSrcImg = (BYTE*)( lpSrc ) + (nWidth*(nHeight-1))*3; // 압축할 이미지의 데이터를 가리키는 포인터
#endif
// 압축된 이미지의 크기가 얼마나 될지 모르기때문에 충분히 크게 잡아줌
lpWorkImgMem = (WORD*)malloc( sizeof(WORD) * nPS );
// 메모리 할당이 되지 않았을때...
if( lpWorkImgMem == NULL )
{
return NULL;
}
// 작업 공간 클리어...
::ZeroMemory( lpWorkImgMem, nPS );
// 일단 압축 작업하는 이미지의 시작 주소를 백업 받아둠...
lpWorkImg = lpWorkImgMem;
#ifdef JR_NORMAL_ENCODE
while( nCWL < nHeight )
#else
while( nCWL > 0 )
#endif
{
// 일단 압축을 한다.
nCount = ProcessLn( lpSrcImg, lpWorkImg, nWidth );
#ifdef JR_NORMAL_ENCODE
lpSrcImg += nWidth * 3 + nPadding;
nCWL++;
#else
lpSrcImg -= nWidth * 3 + nPadding;
nCWL--;
#endif
lpWorkImg += nCount;
// 레퍼런스 변수에 압축된 이미지의 크기를 넣는다.
dwRefSize += nCount * sizeof(WORD);
}
// 메모리 할당...
lpRetImg = (WORD*)malloc( dwRefSize );
::ZeroMemory( lpRetImg, dwRefSize );
// 메모리 할당이 되지 않았을때...
if( lpRetImg == NULL )
{
dwRefSize = 0;
FREE_SAFE( lpWorkImgMem );
return NULL;
}
::CopyMemory( lpRetImg, lpWorkImgMem, dwRefSize );
FREE_SAFE( lpWorkImgMem );
return lpRetImg;
}
UINT CImageEx::ProcessLn ( BYTE* lpSrc, WORD* lpDst, WORD nWidth )
{
WORD nRun = 0;
WORD nSkip = 0;
WORD nDraw = 0;
UINT nWords = 0;
int i = 0;
// Source Image로 부터 run개숫를 구한다..
nRun = CountRuns( lpSrc, nWidth );
*lpDst = nRun;
lpDst++;
// 압축 크기를 1 WORD(2 bytes) 증가
nWords++;
switch( nRun )
{
// 0. 라인이 여백으로만 이루어졌을 경우
case 0:
return nWords; // 압축된 크기가 2 byte 이다.
// 1. 라인 전체가 그려야 할 부분인 경우
case 1:
for( i=0; i<nWidth; i++ )
{
if( m_lpHeader->dwRGBBitCount == 15 )
{
JR_COLOR15( *lpDst, *(lpSrc+2), *(lpSrc+1), *(lpSrc) );
} else {
JR_COLOR16( *lpDst, *(lpSrc+2), *(lpSrc+1), *(lpSrc) );
}
lpDst++;
lpSrc += 3;
}
// 압축 크기를 nWidth WORD(2 bytes) 증가
nWords += nWidth;
return nWords;
/**
*
* << NOTE >>
*
* 1. 라인이 적어도 한 개 이상의 run을 가지고 있을 경우.
*
* 2. 라인이 여백으로 시작해서 여백으로 끝난다고 가정한다.
* Run 개수 카운터가 2부터 시작하므로 먼저 1을 빼고 시작한다.
* 라인 끝의 여백은 고려하지 않는다.
*
*/
default:
while( (--nRun) > 0 )
{
/////////////////////////////////////////////////////
// Skip Pixels 처리
/////////////////////////////////////////////////////
nSkip = CountSkip( lpSrc, nWidth );
// Skip 픽셀수를 저장한다.
*lpDst = nSkip;
lpDst++;
// 이미지의 포인터를 그려야 할 부분으로 옮긴다.
// 24bit 이미지이므로 3byte씩 증가
lpSrc += nSkip * 3;
// skip된 길이 만큼 앞으로 남은 width를 감소시킨다.
nWidth -= nSkip;
// 압축 크기를 1 WORD(2 bytes) 증가
nWords++;
/////////////////////////////////////////////////////
// Image Pixels 처리
/////////////////////////////////////////////////////
// 이제 그려야 할 부분을 카운트 한다.
nDraw = CountDraw( lpSrc, nWidth );
// 실제 이미지 영역 픽셀수를 저장한다.
*lpDst = nDraw;
lpDst++;
// 압축 크기를 1 WORD(2 bytes) 증가
nWords++;
// 그려야 할 부분의 이미지를 카피한다.
for( i=0; i<nDraw; i++ )
{
if( m_lpHeader->dwRGBBitCount == 15 )
{
JR_COLOR15( *lpDst, *(lpSrc+2), *(lpSrc+1), *(lpSrc) );
} else {
JR_COLOR16( *lpDst, *(lpSrc+2), *(lpSrc+1), *(lpSrc) );
}
lpDst++;
lpSrc += 3;
}
// 압축 크기를 nDraw WORD(2 bytes) 증가
nWords += nDraw;
// 처리된것은 감산 시켜줘야 한다...
nWidth -= nDraw;
} // end of while-loop
break;
} // end of switch
// 모든 데이터가 압축되고 반환 한다.
return nWords;
}
WORD CImageEx::CountRuns( BYTE * lpSrc, UINT nLength )
{
WORD nRuns = 0;
WORD nSkip = 0;
WORD nDraw = 0;
int nWidth = 0;
while( nWidth < (signed)nLength )
{
nSkip = CountSkip( lpSrc, nLength-nWidth );
nWidth += nSkip;
lpSrc += nSkip * 3; // 24 bit 이므로
// 1. 한 라인 전체가 압축을 다 한 경우...
// 2. 라인 전체가 skip color로만 되어있을 경우...
if( nWidth == (signed)nLength )
{
break;
}
nDraw = CountDraw( lpSrc, nLength-nWidth );
lpSrc += nDraw * 3; // 24 bit 이므로
nWidth += nDraw;
if( nRuns == 0 )
{
// 카운터의 시작이 2부터이므로 초기값을 1로 준다.
nRuns = 1;
// 라인전체가 그려야 할 부분인 경우다.
if( nWidth == (signed)nLength && nSkip == 0 )
{
break;
}
}
nRuns++;
// 한 라인 전체 압축을 끝낸 경우
if( nWidth == (signed)nLength )
{
break;
}
}
return nRuns;
}
WORD CImageEx::CountSkip( BYTE * lpSrc, UINT nLength )
{
WORD nSkip = 0;
DWORD dwPixel = 0;
while( nSkip < nLength )
{
dwPixel = RGB( lpSrc[nSkip*3+2], lpSrc[nSkip*3+1], lpSrc[nSkip*3] );
if( dwPixel != m_lpHeader->dwColorKey ) break;
nSkip++;
}
return nSkip;
}
WORD CImageEx::CountDraw( BYTE * lpSrc, UINT nLength )
{
WORD nDraw = 0;
DWORD dwPixel = 0;
while( nDraw < nLength )
{
dwPixel = RGB( lpSrc[nDraw*3+2], lpSrc[nDraw*3+1], lpSrc[nDraw*3] );
if( dwPixel == m_lpHeader->dwColorKey ) break;
nDraw++;
}
return nDraw;
}
손실 압축과 비손실 압축이라는 단어를 한번쯤을 들어보았을 것이다. 손실 압축은 말 그대로 원본의 데이터를 압축한 후 이 압축을 풀었을 때의 데이터가 원본 데이터와는 100% 동일하지 않은 압축을 말한다. 그림이나 동영상, 음성 데이터 등은 원본과 100% 같지 않아도 데이터를 사용하는 것이 가능하므로 약간의 손실을 갖지만 높은 압축율을 갖는 손실 압축을 주로 사용하게 된다. 그에 반해 TEXT 데이터나 GBA에서 사용되는 폰트 데이터 등 약간의 손실로도 원본 데이터를 알아보는데 지장이 생긴다면 압축을 하지 않으니만 못할 것이다. 따라서 이 경우에는 압축율이 다소 낮지만 원본의 데이터가 100% 복원되는 비손실 압축이 주로 사용된다. 손실 압축과 비손실 압축의 구분은 본 강좌에서 그다지 큰 영향을 갖지는 않으나 앞으로 소개할 알고리즘이 비손실 알고리즘이라는 사실은 기본적으로 알아두시길.
1. RLE(Run Length Encoding)란?
만약 33 33 33 33 33 33 33 이라는 데이터가 존재한다면 어떻게 압축을 하면 될까?
대부분의 사람들이 33이 7개 연속으로 존재한다고 저장하면 되지 않겠는가 하는 생각을 할 것이다.
이런 기본적인 concept으로부터 시작하는 압축 알고리즘이 RLE방식이다.
RLE방식은 한 문자(한 byte)가 몇 번 반복되는지를 저장하는 방식이다. 따라서 RLE방식은 같은 문자가 여러번 반복되는 데이터에 대해 효율적인 압축방법이 되리란 것을 쉽게 예상할 수 있을 것이다. 텍스트의 경우 여러번 반복되는 데이터가 존재하기 힘드므로 텍스트를 RLE로 압축할 경우 효율이 낮고 오히려 압축데이터의 크기가 더 커지는 경우가 허다하다. 게임을 시작할 때의 로고를 생각해보자. 대부분 검은 바탕이나 단색바탕에 로고 자체도 매우 단순하여 타일전체가 단색인 경우가 많다. 따라서 이런 그림의 경우에 RLE방식으로 압축하는 게 효율적일때가 많다.
2. 어떻게 압축하면 될까?
0x33이라는 문자가 7번 반복된다는 사실을 어떻게 저장하면 될까.
반복되는 문자 뒤에 반복회수를 적어준다면 33 07 형태가 되는데 이 방법에는 약간의 문제가 있다.
만약 01 02 03 04 형태의 데이터가 존재한다면 01 01 02 01 03 01 04 01 로 저장해야 되는데 이 경우 데이터가 2배로 늘어나게 되므로 "압축"의 의미와는 다소 거리가 멀게 된다.
그렇다면 반복되는 문자가 존재할 때만 "반복이 시작된다"의 의미를 갖는 문자가 나타나게 한다면 0x01 0x02 0x03 0x04는 그대로 01 02 03 04 로 저장하면 될 것이다. 편의상 이 문자를 < 로 표현하도록 하겠다. 주의할 점은 반복이 시작됨을 알리는 구분자(separator)가 '<'가 아닐수도 있다는 점이다.
구분자는 알고리즘을 구현하는 사람 맘대로 결정하는 것이 가능하다.
그럼 이 구분자 < 로 RLE방식으로 압축해 보도록 하자. 주어진 데이터는 다음과 같다.
33 33 33 33 33 33 33 11 11 11 22 33 22
33이 7번 반복되고 11 이 3번, 22 33 22 는 반복되는 문자가 없다는 것을 알 수 있다.
그러면 이를 압축할 경우
< 33 07 < 11 03 22 33 22
의 형태로 압축이 되는 것이다. 33의 경우 7개의 바이트가 단지 3바이트만으로 표현되므로 50% 이상 압축되었다. 그러나 11의 경우 3바이트를 압축하여 3바이트가 되었으므로 압축하지 않는 것과 그 크기가 같으므로 압축의 의미를 갖지 못하게 된다. 따라서 이 방식으로 압축할 경우 4바이트 이상 반복되는 문자가 출현할 경우 압축을 시도하면 될 것이다.
그런데 이 방식으로 저장할 경우 구분자와 같은 문자가 출현할 경우 압축 데이터가 판별하기 모호해지게 된다. 구분자로 < 를 사용하는데 데이터 중 < 라는 데이터가 존재할 경우 위의 방식을 그대로 적용하면
< < 33 33 =>(압축)=> < < 33 33
과 같이 저장되게 된다. 그렇다면 이를 역으로 압축을 해제할 경우 제대로 압축이 해제 될리가 없다.
구분자 < 가 출현했으니 그 다음 바이트 < 가 33번 반복된다는 의미를 갖는다고도 볼 수 있으므로 원래의 데이터와는 달라져버린다. 따라서 구분자로 사용되는 문자가 출현할 경우에는 별도의 압축 방법을 생각해야 한다.
이 경우 구분자가 문자로 출현할 경우 구분자를 한번 더 써주는 방식을 택하면 된다.
위의 데이터를 압축한다면
< < < < 33 33
이 되는데 < 뒤에 <가 존재할 경우 <를 그대로 저장하는 것이므로 이 방식으로 압축을 해제할 경우
< < 33 33
으로 원하는 결과를 얻을 수 있게 된다. 이 방법은 위에서와 마찬가지로 구분자가 두배의 용량이 된다는 단점이 있으므로 전체 데이터에서 출현 빈도수가 낮은 문자를 구분자로 사용하면 가능한한 효율을 높일 수 있게 된다.
여기서 설명한 방식은 RLE방식의 한가지 방법일 뿐이다. 압축알고리즘이 워낙 간단한데가 구현이 간단해 수많은 압축형식이 있을 수 있다. 따라서 앞의 설명은 RLE가 뭐다 라는 정도의 설명이라고만 생각해도 충분하다.
3. GBA에서의 구현방식
GBA에서는 압축데이터 앞에 4 바이트의 헤더가 존재한다. 이 4 byte를 뒤에서부터 읽어들인다.
왜 뒤에서부터 읽는가에 대한 내용은 빅 엔디언, 리틀 엔디언의 차이이므로 관심이 있는 사람은 이에 대해 찾아보면 금방 이해할 수 있을 것이다. 어쨌든 이 4 byte의 정보가 압축 데이터에 대한 내용을 담고 있다.
30 00 0e 00 .. .. .. .. ..
이라면 4byte를 뒤에서부터 읽을 경우 00 0e 00 30 이 된다. 이 때 맨 뒤의 바이트는 압축방법에 대한 정보를 담고 있고 앞의 세 바이트는 압축을 풀었을 때의 크기를 담고 있다.
맨 뒤의 바이트가 30 인 것은 이 데이터가 RLE방식으로 압축되었다는 것을 의미하고 앞의 세 바이트 00 0e 00은 압축을 해제했을 때의 데이터의 크기가 0e 00 즉 0xe00 byte가 된다는 것을 의미한다.
그 뒤의 데이터는 역시 위에서 설명한 RLE방식으로 압축되어 있으나 GBA에서 사용하는 방식은 약간 다르다. GBA에서는 Flag_byte(앞에서의 구분자 역할) 1 byte 뒤에 Data_byte N byte가 뒤따르는 방식을 사용한다. 이 설명만으로는 정확한 압축 방법을 알기 힘들테니 우선 Flag_byte에 어떤 정보가 담겨 있는지 알아보자.
Flag_byte는 1 byte이므로 8 bit 인데 MSB는 압축이 되었는가에 대한 정보를 갖고 있고 MSB를 제외한 bit들은 반복횟수를 의미한다.
Flag_byte : _ _ _ _ _ _ _ _
^
1이면 압축데이터, 0이면 압축되지 않은 데이터
가 된다. 따라서 압축이 되었는지의 여부는 ( flag_byte & 0x80 ) 으로 알 수 있고 반복 횟수는 ( flag_byte & 0x7f ) 로 알 수 있다.
우선은 Flag_byte를 읽어 압축이 되었는가, 반복 횟수는 몇번인가 를 알 수 있을 것이다.
압축이 되었을 경우, 즉 Flag_byte가 1일 경우 Flag_byte에 뒤따르는 1 byte의 문자가 반복되게 되는데 이 반복회수는 ( flag_byte & 0x7f ) + 3 이 된다. 즉 80 33 이라면 Flag_byte가 80으로 1000 0000이므로 압축이 되었고 그 뒤의 33이 0+3번, 즉 3번 반복된다는 의미를 갖게 되는 것이다. 따라서 80 33은 압축을 풀면 33 33 33 이 된다.
압축이 되지 않는 부분에 대해서는 이 반복 횟수의 의미가 다르다. MSB가 0일 경우 그 뒤의 데이터들이 압축이 되지 않았다는 뜻인데 그 압축되지 않은 데이터의 개수가 ( flag_byte & 0x7f ) + 1 개라는 뜻이다. 따라서 04 01 02 03 04 05 를 압축을 해제하려면 우선 04를 읽어 압축되지 않은 데이터가 5개라는 내용이므로 01 02 03 04 05 가 된다.
실제로 나리키리2 의 남코 오프닝 부분에 대한 데이터를 이용하여 압축을 해제하는 전체적인 과정을 보도록 하자.
30 00 0E 00 85 00 81 88 81 11 00 14 80 11 00 14
^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^
80 11 00 14 80 11 00 14 80 11 85 00 81 88 91 11
^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^
85 00 81 88 91 11 85 00 07 88 88 A8 00 11 11 21
^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^
C7 80 11 00 51 89 11 8D 00 00 0A 80 00 00 B5 80
^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^
....
압축된 데이터의 앞부분 0x40 byte만을 뽑아내어 구분자와 데이터를 group화 한 것이다.
밑줄쳐진 부분은 한 덩어리로 맨 앞이 flag_byte, 그 뒤가 모두 data_byte라고 생각하면 된다.
앞에서의 설명과 같이 00 0E 00 30이므로 RLE로 0xE00만큼의 데이터가 압축되었음을 알 수 있다.
85 00 은 0x00이 8번 반복되었음을 의미하고 81 88은 0x88이 4번 반복됨을 의미한다.
역시 마찬가지로 81 11은 0x11이 4번 반복되는 것이고 00 14의 경우 압축되지 않은 데이터가 1개 존재하는 것이므로 14가 1개가 존재함을 알 수 있다. 위의 압축을 풀면 다음과 같다.
00 00 00 00 00 00 00 00 88 88 88 88 11 11 11 11
^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^ ^^^^^^^^^^^
14 11 11 11 14 11 11 11 14 11 11 11 14 11 11 11
^^ ^^^^^^^^ ^^ ^^^^^^^^ ^^ ^^^^^^^^ ^^ ^^^^^^^^
00 00 00 00 00 00 00 00 88 88 88 88 11 11 11 11
^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^ ^^^^^^^^^^^
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
....
역시 압축할 때 한덩어리가 되는 부분을 group지어 놓았다. 다소 보기 난해한 면은 있으나 쓸 줄 아는 것이라곤 그림판 뿐인데다가 미적 센스는 빵점이니 텍스트가 오히려 나을것이다 -_-;;;
혹시나 저 텍스트를 이쁘게 그려주실 분 계시면 연락바란다 =_=-b
4. 코드를 보여달라고?
코드는 직접 짜보는 것이 좋다는 것이 지론이긴 하지만 직접 적용하는 과정을 보여주는 것이 더 낫지 않을까 하여 압축을 푸는 부분에 대한 코드만 간략히 소개하도록 한다. 다시 압축하는 코드는 압축 방법을 곰곰히 잘 생각해보면 금방 짤 수 있을 것이다.
C 코드와 압축 데이터가 저장된 file과 압축을 해제했을 때의 데이터가 저장된 file을 링크하니 압축하는 코드를 만들게 된다면 두 파일들의 내용으로 제대로 동작하는지 확인하면 될 것이다.
다운로드
int RLUnComp(FILE *src, FILE *dst)
{
long header=0; // 헤더를 저장한다.
long len; // 압축을 해제했을 때의 데이터 크기
long count=0; // 압축을 얼마나 해제했는가
int i;
int flag_byte; // flag_byte
int data_byte; // data_byte
for(i=0;i<4;i++) {
header|=((fgetc(src))<<(8*i)); // 뒤에서부터 4바이트를 읽는다
}
if((header&0xff)!=0x30) {
printf("This is not an RLE data\n");
return -1;
}
printf("This is compressed with RLE\n");
len=header>>8; // 뒤의 한 바이트는 잘라낸다
while(count<len) {
flag_byte=fgetc(src); // flag_byte를 읽고
if(flag_byte&0x80) { // 압축 데이터라면
data_byte=fgetc(src); // data_byte를 읽어
for(i=0;i<(flag_byte&0x7f)+3;i++) {
fputc(data_byte,dst);
count++; // (flag_byte&0x7f)+3 만큼 반복한다.
}
}
else { // 압축되지 않은 데이터라면
for(i=0;i<(flag_byte&0x7f)+1;i++) {
data_byte=fgetc(src);
fputc(data_byte,dst); // (flag_byte&0x7f)+1 만큼의
count++; // data_byte를 그대로 출력한다.
}
}
}
return 0;
}
0. LZ 알고리즘을 소개하기 앞서
LZ77 압축 알고리즘은 1977년 Lempel과 Ziv가 고안해낸 알고리즘으로 LZ77, LZSS, LZ78, LZW 등 많은 변형이 존재합니다. 이 알고리즘을 모두 설명하는 것은 본 강좌의 목적에도 맞지 않고 분량만 늘어날 우려가 있어 LZ77과 LZSS에 대해서만 간략하게 설명하려 합니다. LZ78, LZW 등은 모두 기본적인 개념은 같으니 필요하신 분은 직접 찾아보시길 바랍니다. 게다가 이 강좌를 쓰는 필자조차도 저 알고리즘을 모두 알고 있는게 아닌데다가 사실 LZ77과 LZSS가 정말로 어떻게 다른지에 대해서도 정확히 알지 못합니다. -_-;;; 따라서 본 강좌의 내용이 LZ알고리즘을 설명하는 측면에서는 미흡할 가능성이 많으나 GBA에서 사용되는 알고리즘을 이해하는데는 무리가 없을 테니 걱정은 저리로 던져주세요.
1. LZ 알고리즘
전 강좌에서 RLE 알고리즘을 알아보았다. 연속되는 데이터가 많이 존재하는 경우 RLE방식도 상당히 높은 효율을 보여주기는 하나 abababab와 같이 같은 패턴이 연속되는 경우 RLE로는 압축을 할 수 가 없다. 따라서 이 경우 dictionary, 즉 사전 이라는 개념을 사용하여 압축하는 방법을 사용하면 높은 압축률로 압축하는 것이 가능해진다. dictionary는 정적 사전(static dictionary)와 동적 사전(dynamic dictionary)로 구분한다는 얘기를 어디선가 얼핏 들은 것 같기도 하나 확실치 않은 정보이니 그냥 잊으셔도 좋다. 어쨌든 abababaaaa라는 데이터가 존재할 경우 1. ab, 2. aaaaa 라고 정의하고 1112이라고 저장하면 데이터의 크기를 줄일 수가 있는데 LZ알고리즘은 이 개념으로부터 시작하게 된다.
2. 실제로 어떻게 적용하는가
1) LZ77
먼저 LZ알고리즘을 설명하기 전에 알아두어야 할 용어들이 있다. Input Stream, Coding Position, Lookahead Buffer, Window 이다. r'Arc 님께서 자유게시판에 올려주신 http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/ 의 설명에 따르면 각각은 다음과 같다.
Input Stream : 압축될 데이터들의 순차적 집합(sequence)
Coding Position : 이제 곧 압축할 데이터. Lookahead Buffer 시작 지점
Lookahead buffer : Coding Position 이후의 데이터의 순차적 집합
Window : Coding Position 이전의 데이터
먼저 설명만으로는 이해하기가 매우 난해하니 그림으로 설명하면 다음과 같다.
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 ... => Input Stream
----------------------- | ================================
Window Coding Position Lookahead buffer
현재의 그림은 00 01 02 03 04 05 06 07 08 까지가 압축이 된 상태이고 09가 이제 곧 압축이 될 데이터들의 시작지점이며 09를 포함한 그 뒤의 데이터들이 lookahead buffer라는 것을 의미한다. 여기서 주의할 점은 window가 압축된 데이터를 의미하지 압축한 결과와는 다르다는 점이다. 이 점은 꼭 염두에 두어야 한다. Window의 데이터들이 압축된 결과는 다른 공간에 저장되어 있다고 생각해야 한다.
LZ77은 현재 Coding position이후의 lookahead buffer에서 window내의 데이터들과 같은 패턴을 갖는 데이터가 존재하는지 검사하고, 만약 window에 그런 데이터가 존재할 경우 Coding Position에서부터의 상대적인 위치와 크기를 표현하게 된다. 이 표현은 (A,B)라고 사용하도록 한다. (A,B)는 "Coding Position으로부터 A만큼 앞에서부터 B만큼의 데이터"를 의미한다. 그리고 Coding position으로부터 B번째의 데이터를 그대로 출력하고 Coding Position을 B+1 만큼 오른쪽으로 이동시킨다.
이제 예시를 통해 구체적인 압축 알고리즘을 알아보도록 하자. 설명의 편의를 위해 데이터는 알파벳으로 표현하도록 한다.
우선 Input Stream, 즉 압축하려고 하는 데이터가 다음과 같다고 생각하자.
A A B B C C D A A B B A A B B
| ===========================
먼저 해야할 일은 Coding Position 을 맨 처음 byte로 옮기는 일이다. 그러면 window에는 아무 데이터가 없고 coding position은 A가 되고 Lookahead buffer는 A A B B C C ... 이 될 것이다. Window에 아무 데이터가 없으므로 Lookahead buffer에서 window와 같은 패턴을 찾을 수 없고 따라서 (0,0)과 A를 출력하고 0+1, 즉 1만큼 coding position을 이동시킨다. 따라서 압축결과는 (0,0) A 가 된다.
_ _
A A B B C C D A A B B A A B B
- | ==========================
Output : (0,0) A
두번째 A가 Coding Position이 되는데 이 때 window에서 lookahead buffer와 같은 패턴 "A" 가 존재하므로 coding position 에서의 상대적인 위치와 그 길이를 저장하면 되는 것이다. 이 때 상대적인 위치는 왼쪽으로 몇 바이트인가 를 저장해주게 된다. 따라서 (1,1) 을 출력한 후 coding position으로부터 오른쪽으로 1번째 문자를 출력하고 1+1, 즉 2만큼 Coding position을 이동시킨다. 따라서 그 결과는 다음과 같다.
_ _
A A B B C C D A A B B A A B B
----- | ======================
Output : (0,0) A (1,1) B
lookahead buffer에서 window와 같은 패턴을 갖는지 검사한다. "B" 가 가장 긴 패턴이 되므로 (1,1)을 출력한 후 C를 출력하고 coding position 은 2만큼 이동시킨다.
_ _
A A B B C C D A A B B A A B B
--------- | =================
Output : (0,0) A (1,1) B (1,1) C
C도 마찬가지로 같은 패턴이 존재하므로 (1,1) D를 출력하고 coding position을 2만큼 이동시킨다.
_ _ _ _ _ _ _ _
A A B B C C D A A B B A A B B
-------------- | =============
Output : (0,0) A (1,1) B (1,1) C (1,1) D
AABB가 coding position으로부터 7만큼 앞에 길이 4만큼 같은 패턴을 가지므로 (7,4)를 입력하고 현재 Coding position으로부터 오른쪽으로 4번째의 data를 출력 후 coding position은 4+1=5만큼 이동시킨다.
_ _ _ _ _ _
A A B B C C D A A B B A A B B
------------------------ | ===
Output : (0,0) A (1,1) B (1,1) C (1,1) D (7,4) A
ABB가 현재 coding position으로부터 4번째 앞에 길이 3만큼 같은 패턴을 가지므로 (4,3)을 출력하면 압축이 끝나게 된다.
따라서 압축한 결과는 (0,0) A (1,1) B (1,1) C (1,1) D (7,4) A (4,3) 이다.
위의 압축한 결과를 해제하는 과정도 살펴보자. 이 때 중요한 점은 window에 들어가는 data가 압축을 푼 후의 data라는 점이다.
(0,0) A (1,1) B (1,1) C (1,1) D (7,4) A (4,3)
| ==================================
Output :
(0,0)을 읽고 0만큼 앞에 0만큼의 data를 출력한다. 즉, 아무것도 출력하지 않는다.
A (1,1) B (1,1) C (1,1) D (7,4) A (4,3)
| ================================
Output :
A를 출력한다.
A (1,1) B (1,1) C (1,1) D (7,4) A (4,3)
- | ===========================
Output : A
(1,1)을 읽고 1만큼 앞에서 1개의 data를 출력한다. 1만큼 앞에서 1개의 data는 A이므로 window에는 A가 들어가게 된다.
A A B (1,1) C (1,1) D (7,4) A (4,3)
--- | ========================
Output : A A
B를 출력한다.
A A B (1,1) C (1,1) D (7,4) A (4,3)
------ | ====================
Output : A A B
(1,1)을 읽고 1만큼 앞에서 1개의 data를 출력한다. B를 출력하고 window에는 B가 들어가게 된다.
A A B B C (1,1) D (7,4) A (4,3)
------- | ==================
Output : A A B B
C를 출력한다.
A A B B C (1,1) D (7,4) A (4,3)
--------- | =============
Output : A A B B C
(1,1)을 읽고 1만큼 앞에서 1개의 data를 출력한다. C를 출력하고 window에는 C가 들어가게 된다.
A A B B C C D (7,4) A (4,3)
------------ | ===========
Output : A A B B C C
D를 출력한다.
A A B B C C D (7,4) A (4,3)
-------------- | ======
Output : A A B B C C D
(7,4)를 읽고 7만큼 앞에서 4개의 data, 즉 A A B B를 출력하고 window에 A A B B를 넣는다.
A A B B C C D A A B B A (4,3)
--------------------- | ====
Output : A A B B C C D A A B B
A를 출력한다.
A A B B C C D A A B B A (4,3)
------------------------ |
Output : A A B B C C D A A B B A
(4,3)을 읽고 4만큼 앞에서 3개의 data, 즉 A B B를 출력하고 window에 A B B를 넣는다.
A A B B C C D A A B B A A B B
------------------------------ |
Output : A A B B C C D A A B B A A B B
위에서 압축한 데이터와 같음을 알 수 있다. 이 과정이 LZ77알고리즘이 data를 압축하고 해제하는 과정이다. 복잡한 과정인 듯 하나 차근차근 생각해보면 그리 어렵지 않으니 이해가 되지 않은 분은 다시 한번 따라가면 금방 이해할 수 있을 것이다. 여기서 문제 하나. DATA의 양이 매우 방대해질 경우 lookahead buffer와 window는 어떻게 해야 할까? 같은 pattern을 찾는 일이 사람이 눈으로 직접 찾기에는 그리 어렵지 않은 일이나 같은 pattern을 찾는 알고리즘은 그 계산에 상당히 많은 시간을 필요로 한다. 따라서 보통 LZ알고리즘을 사용할 때는 lookahead buffer와 window의 크기를 제한하고 사용한다. 만약 window의 크기는 4이고 lookahead buffer의 크기는 3이라면 압축하는 중의 한 과정은 다음과 같아진다.
A A B B C C D A A B B A A B B
------- | =====
Output : (0,0) A (1,1) B (1,1) C
이 때 window와 lookahead buffer는 각각 queue로서 동작하게 된다. queue가 뭔지 모르는 사람은 queue, FIFO로 검색해보면 쉽게 그 설명을 찾을 수 있다.
GBA에서는 0x12의 lookahead buffer와 0x1000의 window를 사용하는 것으로 알려져 있다. 직접 확인해본 결과가 아니니 정확한 값이 아니라면 연락바란다.
@. 헉헉.. LZ77 알고리즘 생각보다 설명하기가 매우 힘들군요 -_-;; 몇 시간째 썼다 지웠다 하는 중에 좀 괜찮으려나 하는 설명만 뽑아서 정리했습니다. 이 과정에서 매끄럽지 않은 문장이 생길 수 있으니 그럴 경우 코멘트 달아주세요.
@2. LZ 알고리즘은 2부로 나눕니다;;; 2부에서는 LZSS는 어떻게 다른가 와 GBA에서는 어떻게 저장하는가를 다룰 생각입니다.
@3. 허프만 압축을 사용하는 롬을 찾지 못해 허프만 압축은 기본적인 원리만 소개할 생각입니다. 허프만 압축을 사용하는 롬을 발견하시면 제보(-_-;;) 부탁드립니다.
0. 저번 강좌를 올린지 어느새 일주일이나 지나버렸군요 -.-;;; 울트라에딧만으로 대사를 모두 한글화하려니 노가다가 장난이 아니라 그냥 직접 툴을 만들자 라는 생각에 VC++을 좀 붙들고 있었더니 밀린 숙제와 레포트덕에 시간이 전혀 안나더라구요;;;; 기다리신 분들(-_-;; 있나요;;;;) 죄송합니다. 저번 강좌에 이어 LZSS 들어가겠슴다~
2) LZSS
LZSS알고리즘은 LZ77과 거의 모든 알고리즘이 동일하다. 차이점이 있다면 LZ77에서의 단점을 보완했다는 점이다. LZ77은 알다시피 ((포인터,길이) 데이터) 와 같은 형태가 반복되는 구조로 되어있다. 저번 강좌에서 직접 주어진 데이타를 압축한 결과에서 볼 수 있듯이 임의의 데이터에 대해 압축을 시도했을 때 (0,0)과 같은 형태가 자주 입력될 것이란 걸 예상할 수 있고, (1,1)이나 (2,2)는 실제로는 전혀 압축이 되지 않는다는 점도 알 수 있을 것이다. 데이터를 저장할 때 (포인터,길이) 정보가 약 두바이트 내지는 세바이트 정도가 되는데 이 정보를 이용하여 압축을 푼 결과가 1~2바이트 뿐이라면 전혀 압축되지 않은 데다 오히려 더 많은 공간을 차지하게 되는 경우도 있다. 따라서 LZSS에서는 LZ77에서의 이러한 단점을 보안하여 좀 더 높은 압축률을 갖게 된 알고리즘이다.
우선 (0,0)과 같은 (포인터,길이) 가 저장되지 않게 하기 위해 LZSS에서는 key byte 내지는 separator를 사용하는 경우가 많다. key byte는 GBA의 자체압축에서 사용하고 separator의 경우 구현의 간단함으로 인해 필자가-_- 자주 사용하는 방식이다. 다만 separator의 경우 데이터 자체에 separator와 같은 데이터가 존재하는 골때리는 경우가 생기므로 그래픽 자료에는 적합하지 않으나 텍스트 데이터에는 사용하지 않는 문자가 존재하기 마련이므로 separator의 사용이 용이하다. 허나 강좌의 목적이 GBA에서 사용하는 압축방법을 소개하는데 있고 하니 key byte로 표현하는 방법을 설명하도록 한다.
또한 압축을 풀었을 때 그 실제적인 크기가 (포인터, 길이) 정보보다 작은 경우를 막기 위해 LZSS에서는 최소길이를 정해놓고 패턴의 길이가 이 최소길이보다 클 경우에는 압축을 시도하도록 되어 있다. 이 min_length는 알고리즘을 구현하는 프로그래머에 의해 정해지며 (포인터,길이)정보가 실제적으로 몇 바이트를 이용하여 저장되는가에 따라 정해지게 된다.
우선 간단하게 LZSS는 어떤 방식으로 인코딩, 디코딩하는지에 대해 알아보도록 하자. 참고로 압축,해제하는 과정을 인코딩, 디코딩으로 표현하는 경우가 대부분이므로 가능한한 encoding, decoding으로 병행하여 표현하도록 하니 참고하도록 하자.
저번강좌에서도 압축하는데 사용했던 데이터를 이용하여 압축하는 과정을 살펴보도록 하자. 우선 주어진 데이터들을 lookahead buffer에 모두 저장한 후, coding position을 이동시켜가며 압축을 하도록 한다. 이 점은 LZ시리즈에서 대부분 변하지 않는 기본적인 방식이므로 저번 강좌를 다시 확인하여 lookahead buffer, coding position, sliding window 등의 용어를 정확히 알도록 하자. 그리고 예제에서 사용하는 최소길이는 2로 정하도록 한다.
A A B B C C D A A B B A A B B
| ============================
window에 저장된 정보가 아무것도 존재하지 않으므로 A를 그대로 출력하고 이를 윈도우에 저장한다. 압축을 시작할 당시 (0,0)을 출력하는 LZ77과는 그 시작이 다르다는 것을 알 수 있을 것이다.
A A B B C C D A A B B A A B B
- | ==========================
Output : A
coding position이 두번째 A가 되었다. lookahead buffer에서 window와 같은 패턴을 찾을 수 있는가? A와 A가 같으니 같은 패턴을 찾을 수 있다 가 답이 되겠지만 LZSS에서는 min_length, 즉 예제에서의 2보다 작은 길이가 되므로 압축을 하지 않는다. 따라서 A를 그대로 출력하고 coding position을 한바이트 이동시킨다.
A A B B C C D A A B B A A B B
--- | ========================
Output : A A
B B C C D에 대해서는 앞의 A와 같은 과정을 거친다. 즉, 압축을 하지 않는다. 따라서 D까지 인코딩한 결과는 다음과 같다.
A A B B C C D A A B B A A B B
------------- | ==============
Output : A A B B C C D
자, window와 lookahead buffer를 살펴보자. 같은 패턴이 있는가? A A B B라는 같은 패턴이 존재하고 이 길이가 최소길이 이상이므로 이 때 비로소 lookahead buffer의 A A B B를 압축하도록 하게 되는 것이다. 압축할 때의 정보는 LZ77과 같이 (포인터, 길이)를 이용하도록 한다. A A B B가 7번째 앞에서부터 4바이트 같으므로 (7,4)를 저장하면 된다.
A A B B C C D A A B B A A B B
---------------------- | =====
Output : A A B B C C D (7,4)
역시 Lookahead buffer에 A A B B가 저장되어 있고 window에 A A B B가 두번 출현한다. 이 경우 어떤 패턴을 선택할 것인가에 대한 문제는 전적으로 프로그래머에게 달려있다. 사실 어느 패턴을 선택하든 그 결과는 같다. (11,4)로 표현하든 (4,4)로 표현하든 (p, len) 은 항상 일정한 크기를 차지하도록 되어 있기 때문이다. 여러 LZSS 알고리즘의 구현을 살펴본 결과 대부분의 경우 후자를 택하도록 되어 있으니 참고하도록 하자. 따라서 마저 압축하면 그 결과는 다음과 같다.
A A B B C C D A A B B A A B B
----------------------------- |
Output : A A B B C C D (7,4) (4,4)
(p, len)이 2byte를 차지한다고 생각하면 15 byte의 데이터를 압축한 결과가 11 byte로 압축되었음을 알 수 있다. LZ77로 같은 데이터를 압축했을 때의 결과가 몇 byte가 되는지를 직접 계산해보자. (p,len)이 5개, data가 5개이므로 15 byte로 LZ77에서보다 압축효율이 높아졌다는 것을 확인할 수 있을 것이다.
역시 LZ77에서와 같이 이 데이터를 이용하여 디코딩하는 과정을 살펴보도록 하자.
A A B B C C D (7,4) (4,4)
| ======================
A A B B C C D의 경우 전혀 압축되어 있지 않으므로 차례대로 한바이트씩 출력하고 coding position을 이동시키면 된다. 그 결과는 다음과 같다.
A A B B C C D (7,4) (4,4)
-------------- | =======
Output : A A B B C C D
(7,4)로 압축 정보가 나타났다. 7번째 앞쪽에서부터 4개의 데이터이므로 A A B B를 출력하고 window에도 A A B B 를 저장하도록 한다. 인코딩 알고리즘이 LZ77과 거의 다를바가 없었듯이 디코딩 알고리즘도 LZ77과 크게 다르지 않다.
A A B B C C D A A B B (4,4)
---------------------- | ==
Output : A A B B C C D A A B B
(4,4)도 마찬가지로 4번째 앞에서부터 4개의 데이터, 즉 A A B B를 의미한다. 따라서 디코딩한 결과는 다음과 같다.
A A B B C C D A A B B A A B B
----------------------------- |
Output : A A B B C C D A A B B A A B B
디코딩한 결과와 원본 데이터를 비교해보도록 하자.
3. GBA에서는
이제 기본적인 LZ77과 LZSS의 encoding, decoding 알고리즘을 살펴보았으니 GBA에서는 어떻게 압축하고 저장하는가에 대해 알아보도록 한다. GBA의 bios call의 이름이 LZ77UnCompWram과 LZ77UnCompVram으로 LZ77알고리즘을 사용한 듯 보이나 실제적인 구조는 LZSS와 같다. 닌텐도의 계략인지-_- 어떤 이유에서인지는 알 수 없으나 데이터의 압축구조가 LZSS에 가까우므로 이 점 유념해두길 바란다.
그럼 GBA에서 사용한 LZSS알고리즘은 어떻게 데이터와 (p,len)을 구별할 수 있을까? 차근차근 읽어보신 분이라면 key byte를 이용한다고 하지 않았나? 라고 생각할 수 있을 테니 언제 그런 말을 했는지 기억나지 않으신 분은 이 문서에서 (3655, 480)가 어느 지점을 의미하는지 디코딩하여 다시 읽어보도록 하자.
key byte는 어떤 구조로 되어 있을까에 대한 답은 대략적인 데이터들이 어떤 덩어리로 엮여-_-져 있나를 먼저 아는 것이 이해가 빠를 것이라 생각한다. 그림으로 표현하면 데이터들의 뭉텡이는 다음과 같이 구성되어 있다.
┌──────┐┌─────┐┌───┐┌───┐┌───┐┌───┐
│header 4byte││key 1byte ││덩어리││덩어리││덩어리││덩어리│
└──────┘└─────┘└───┘└───┘└───┘└───┘
┌───┐┌───┐┌───┐┌───┐
│덩어리││덩어리││덩어리││덩어리│
└───┘└───┘└───┘└───┘
┌─────┐┌───┐┌───┐┌───┐┌───┐
│key 1byte ││덩어리││덩어리││덩어리││덩어리│
└─────┘└───┘└───┘└───┘└───┘
┌───┐┌───┐┌───┐┌───┐
│덩어리││덩어리││덩어리││덩어리│
└───┘└───┘└───┘└───┘
.
.
.
header는 RLE방식과 같다. LZ으로 압축했음을 표현하는 0x10과 디코딩한 데이터의 크기를 알리는 3byte가 header 4byte가 된다. 그 이후부터는 key byte와 8개의 덩어리가 연속되는데 이 덩어리는 key byte에서의 bit에 따라 (p,len)인지 압축되지 않은 데이터인지가 결정되게 되는 것이다.
1 byte는 8bit이므로 key byte가 0x00 이라면 0000 0000 을 의미하는데 이 때 앞에서부터의 각 1bit씩이 각 덩어리가 압축되어 있는지에 대한 정보를 담고 있는 것이다. 따라서 역시 그림으로 살펴보자면 key byte가 0x00일 경우 8개의 data가 존재한다는 것이고
┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐
│0x00││data││data││data││data││data││data││data││data│
└──┘└──┘└──┘└──┘└──┘└──┘└──┘└──┘└──┘
key byte가 0x33 (0011 0011)이라면 다음과 같다는 뜻이다.
┌──┐┌──┐┌──┐┌────┐┌────┐┌──┐┌──┐┌────┐┌────┐
│0x33││data││data││(p,len) ││(p,len) │ │data││data││(p,len) ││(p,len) │
└──┘└──┘└──┘└────┘└────┘└──┘└──┘└────┘└────┘
즉, 디코딩하는 과정은 요약하면 다음과 같다. key byte를 읽고, 데이타 덩어리를 8개를 읽는데 이 데이타 덩어리가 압축이 되었는가 되지 않았는가에 대한 정보를 key byte의 각 bit로부터 얻어 각각의 덩어리를 디코딩한 후 이를 출력하는 것이다. 이 때 GBA에서 min_length는 3을 이용한다. (p,len)은 두바이트로 이루어져 있는데 p와 len이 일정한 bit로 쪼개어져 저장되어 있다.
0000 0000 0000 0000
^^^^ ^^^^^^^^^^^^^^^
len pointer
즉, (p,len)을 의미하는 두 바이트 중, 앞 바이트에서의 상위 4비트가 len을 의미하고 앞 바이트에서의 하위 4bit와 뒷 바이트의 8bit가 pointer를 의미한다. 이 때 RLE와 마찬가지로 실제적인 패턴의 길이에서 3을 뺀 수치가 len에 저장되어 있고, 패턴의 위치에서 1을 뺀 수치가 pointer에 저장되어 있다. 무슨 말이냐면 압축된 데이터 덩어리가 0x30 0x01이라면 0011 0000 0000 0001 이므로 len은 0011+3, 즉 패턴의 길이가 3+3으로 6개이고 그 위치는 0000 0000 0001 +1, 즉 2번째 앞에서부터 라는 의미가 된다.
역시 실제적으로 예제를 통해 살펴보도록 하자. 나리키리2에서 메뉴 그래픽이 저장되어 있는 부분의 데이터는 다음과 같다.
10 00 10 00 10 F3 FF FF 30 01 4F 54 55 FF 01 E4
───── ─ ─ ─ ─ ── ─ ─ ─ ─ ─ ─
header k d d d (l,p) d d d d k d
EE EE FF E9 DD 1E 20 03 14 E4 DD EE 00 03 9E 50
─ ─ ─ ─ ─ ─ ── ─ ─ ─ ─ ── ─
d d d d d d (l,p) k d d d (l,p) d
. . .
의미를 갖는 그룹으로 묶고 그 밑에 key일 경우 k, data일 경우 d, 압축된 정보일 경우 (l,p)로 표현하였다. 앞에서 k의 각 bit가 데이타 덩어리가 압축이 되었는지 되지 않았는지를 결정한다고 했으므로 key byte를 2진법으로 표현하고 저 위의 구성이 맞나 직접 확인해보길 바란다.
이제 key byte가 어디에 있는지, 각각의 덩어리가 압축되었는지에 대한 여부도 알 수 있으므로 위의 데이터를 이용하여 압축을 풀어보도록 하자.
F3 FF FF는 압축이 되지 않았으므로 그대로 출력하고 30 01은 len=6, pointer=2이므로 window에서 두바이트 앞에서 6개의 문자를 의미하므로
F3 FF FF (6,2) 4F 54 55 FF
-------- | ===============
Output : F3 FF FF
F3 FF FF FF FF FF FF FF FF 4F 54 55 FF
-------------------------- | =========
Output : F3 FF FF FF FF FF FF FF FF
와 같이 디코딩할 수 있다. 뒤의 4F 54 55 FF는 압축되지 않았으므로 그대로 출력한다. 따라서 첫번째 key byte를 이용하여 8개의 덩어리를 디코딩한 결과는 F3 FF FF FF FF FF FF FF FF 4F 54 55 FF가 된다.
위의 데이터를 이용하여 디코딩한 결과는 다음과 같다. 직접 디코딩해보고 그 결과를 비교해보도록 하자.
F3 FF FF FF FF FF FF FF FF 4F 54 55 FF E4 EE EE
FF E9 DD 1E FF E9 DD 1E FF E4 DD EE FF E4 DD 9E
4. C로 표현하면 어떻게 될까?
RLE에 비해 소스가 길다. CowBite라는 GBA 에뮬레이터에서 가져온 소스이니 '필자가 직접 짠 소스면 도저히 믿을 수가 없을 것 같은데' 라면서 고개돌리는 저 분 안심하시라 -_-;;;; 이런 제길 -_-;;;
위의 알고리즘을 변경없이 그대로 적용한 코드이므로 알고리즘을 하나하나 따라가면서 소스를 한줄한줄 따라내려가면 될 것이다.
int LZ77UnComp(FILE *src, FILE *dst)
{
long header=0;
long outSize;
long bytesDecompressed=0;
long windowPtr=0;
long length;
long offset;
int mask;
int key;
int flag_byte;
int data_byte;
int *dest;
int i,j;
long k;
for(i=0;i<4;i++) {
header|=((fgetc(src))<<(8*i)); // 헤더를 읽는다.
}
outSize=header>>8;
dest=(int*)malloc(sizeof(int)*outSize); // 배열을 할당한다.
while(bytesDecompressed < outSize) {// 헤더에 나타난 길이만큼 압축을 푼다.
key = fgetc(src); // key를 읽고
mask = 0x80;
for(i=0; (i<8) && (bytesDecompressed<outSize);i++) {
if(key&mask) { // key에 해당하는 bit가 1이면
flag_byte=fgetc(src);
length=(flag_byte>>4)+3;
offset=(flag_byte&0x0F) << 8;
offset |= fgetc(src);
offset++; // (l,p)정보를 읽고
for(j=0;j<length;j++) {
data_byte=dest[windowPtr-offset];
dest[windowPtr]=data_byte;
windowPtr++;
bytesDecompressed++;
} // 디코딩한다.
}
else { // key에 해당하는 bit가 0이면
data_byte=fgetc(src);
dest[windowPtr]=data_byte;
windowPtr++;
bytesDecompressed++; // 그대로 출력한다.
}
mask=mask>>1;
}
printf("bytesDecompressed=%d\n",bytesDecompressed);
}
for(k=0;k<outSize;k++) {
fputc(dest[k],dst);
} // 배열을 파일에 저장
return 0;
}
@. bios call을 이용한 데이터 위주로 설명하다보니 역시 부족한 점이 많습니다. 료우트님 많이 기다리셨을 텐데 많이 도움되지 못해 죄송합니다. 허나 이미 분석해놓은신 내용이 좀 있으니 금방 압축을 풀어내실 수 있을 겁니다 !+_+!! 화이팅!!
@2. 어제 숙제를 하느라 밤을 샜습니다. 수면시간 2시간 -_-;;; 강의시간이 다가와 여러번 검토할 시간이 없음에도 불구하고 언능 올립니다. 수정할 사항이 있으면 코멘트 달아주세요 즉시 수정하겠습니다.
@3. Huffman 알고리즘... 아직 분석 시작도 안했거든요 -.-;;; 다음 강좌는 언제 올라갈지 모릅니다. 이번 주 내내 실험과 레포트와 숙제와 씨름하고 주말에 시간이 나면 대략 1,2주 쯤 후에나 올릴 수 있지 않을까 합니다.
@4. 압축데이터가 어디에 존재하는가 찾는법!!
VBA 개발자 버전을 받습니다. 일반 버전은 logging window가 제대로 동작하지 않으므로 꼭 dev 버전으로 받으세요. 해당 그래픽이 뜨기 전에 Ctrl+P로 일시정지 시킨 후 logging window를 켜고 SWI를 체크해줍니다. 그리고 Ctrl+N으로 한프레임씩 진행시키면서 타일 에디터와 맵 에디터를 관찰합니다. 타일 에디터나 맵 에디터에 수정을 원하는 그래픽이 뜨면 그 때 logging window에서 RLUncompVram이나 LZ77UnCompVram을 찾습니다. LZ77UncompVram 0x8... 0x6... 으로 나타나는데 이는 각각 롬에 저장된 주소와 압축이 해제될 장소를 뜻합니다. 이 때 주의할 점은 0x8333333 이면 롬을 HE로 열어 333333에 해당하는 주소를 찾아야 합니다. 왜 맨 앞의 8을 제거하느냐에 대한 답은 자세한 설명은 생략;;;;
<** 공백압축 알고리즘 **>
1. 16비트 칼라 포멧
1.1 RGB 5:5:5 시스템
(최상위 비트) 0RRR RRGG GGGB BBBB (최하위비트)
남는 1비트를 사용하지 않는다.
1.2 RGB 5:6:5 시스템
(최상위 비트) RRRR RGGG GGGB BBBB (최하위비트)
초록색을 1비트 더 사용한다.
1.2 BGR 5:6:5 시스템
(최상위 비트) BBBB BGGG GGGR RRRR (최하위비트)
거의 사용되지 않는 포멧
2. 그래픽 모드 알아내기
RGB565로 저장된 비트멥을 RGB555모드에서 출력하면 정상적인 색상이 나오지 않으므로 다이렉트 초기화시에 반드시 픽셀모드를 체크 한 뒤 포멧에 맞게 이미지 데이터를 변경하여 출력해야 한다.
<함수 예제>
bool Check565Mode()
{
DDPIXELFORMAT ddpf; // 픽셀포멧구조체
memset(&ddpf, 0, sizeof(DDPIXELFORMAT)); // 구조체 초기화
ddpf.dwSize = sizeof(DDPIXELFORMAT); // 구조체 사이즈 할당
g_pDDSPrimary->GetPixelFormat(&ddpf); // 픽셀포멧구조체에 정보를 셋팅
if(ddpf.dwGBitMask == 0x7e0) // RGB565모드인지 검사
return true;
else // RGB555모드
return false;
}
2. 24비트 비트맵 16비트 비트맵(픽셀)으로 변환
쉬프트연산을 통해 24비트RGB값을 16비트 RGB값으로 변환한다.
‘|’(OR)연산대신 ‘+’(더하기)로 대치될 수 있다.
<24비트->16비트 변환 매크로함수 예제>
#define CONVERT_16BIT_565(r, g, b) (((r)>>3)<<11)|(((g)>>2)<<5)|((b)>>3)
#define CONVERT_16BIT_555(r, g, b) (((r)>>3)<<10)|(((g)>>3)<<5)|((b)>>3)
2. 16비트 비트맵 압축종류
2.1 주소기억 압축방법
스캔라인에 묶음(공백개수+이미지개수+이미지데이타)개수 | 공백개수 | 이미지개수 | 데이터
00000000 1234 0000 12 0000 // 이미지의 한 라인(가로너비)
위와 같은 데이터가 있다고 가정할 때 (0번을 컬러 키로 할 경우) 압축하면 다음과 같다.
2 8 41234 4 212 4
2 : 스캔라인상의 압축이미지 묶음 (8 41234, 4 212 이므로 2묶음이다. )
8 : 공백개수
4 : 이미지개수
1234 : 실제 이미지 데이터
4 : 공백개수
2 : 이미지 개수
12 : 실제 이미지 데이터
4 : 공백개수
2.2 일반압축 방법
공백개수 | 이미지개수 | 데이터
00000000 1234 0000 12 0000 // 이미지의 한 라인(가로너비)
위와 같은 데이터가 있다고 가정할 때 (0번을 컬러 키로 할 경우) 압축하면 다음과 같다.
8 41234 4 212 4
압축이미지 묶음을 저장하지 않는 것 외에 위의 주소기억 압축방법과 동일하다
2. 공백압축 비트맵 출력 및 클리핑처리 (일반압축)
<일반 공백압축 예제>
/////////////////////////////////////////////////////////////////////////////////
// 압축 스프라이트 출력 루틴
BOOL PutSprite( int put_x, int put_y, cRect &rcClip )
{
cRect rcCheck, rcImage;
rcImage.SetRect(0,0, g_pImg->nWidth, g_pImg->nHeight); // 이미지 영역
cPoint ptBase = rcImage.CenterPoint(); // 중점이 이미지의 중앙이라고 가정
rcImage.OffsetRect(put_x-ptBase.x, put_y-ptBase.y); // 이미지를 중점에 맞게 보정
//**** 만약 클리핑영역과 이미지영역의 교차지역이 없다면 Skip
if(FALSE == rcCheck.IntersectRect(rcClip, rcImage))
return FALSE;
// 이미지 출력을 위한 서피스 고정
DDSURFACEDESC2 ddsd = { sizeof(ddsd) };
g_pDDSBack->Lock(NULL, &ddsd, DDLOCK_WAIT | DDLOCK_SURFACEMEMORYPTR, NULL); // 표면을 Lock
LPWORD pSurface = (LPWORD)ddsd.lpSurface; // 서피스의 시작포인터
DWORD pitch = ddsd.dwWidth; // 서피스의 스캔라인
// 마우스 위치값에 해당하는 서피스의 번지를 얻어낸다.
pSurface = &pSurface[ rcImage.top*pitch + rcImage.left ];
LPWORD pTemp = pSurface; // 서피스 시작 포인터 복사
LPWORD pImgData = g_pImg->pData; // 이미지 버퍼 포인터
int py=0;
int nBlank, nData;
int nRealX, nRealY;
int nScanLine, nOffset;
int nDLPixel, nDRPixel;
bool bScan = TRUE;
do
{
if(bScan || nRealX >= rcImage.right)//nScanLine)
{
pTemp += pitch; // 다음라인 시작주소 저장 (ddsd.lPitch>>1;)
pSurface = pTemp; // 다음라인 주소값 전달.
py++;
nRealX = rcImage.left ; // 현재 출력되고 있는 서피스상의 x좌표
nRealY = rcImage.top + py; // 현재 출력되고 있는 서피스상의 y좌표
nScanLine = rcImage.right; // 현재 마우스위치에서의 상대적인 스캔라인
nOffset = 0; // 버퍼포인터에서의 상대적인 거리
nDLPixel = 0; // 클리핑영역데 의해 잘려나가는 부분을 제거한 바이트수
nDRPixel = 0; // 클리핑영역데 의해 잘려나가는 부분을 제거한 바이트수
bScan = FALSE;
}
///////////////////////////////////////////////////
// nBlank 길이 검사
nBlank = *pImgData++; // 공백 길이
pSurface += nBlank;
nRealX += nBlank;
if(nRealX >= rcImage.right)
{
bScan=TRUE;
continue;
}
///////////////////////////////////////////////////
// nData 길이 검사
nData = *pImgData++; // 데이터의 길이(항상nData>0)
nRealX += nData;
if(nRealY>=rcClip.top && nRealY<=rcClip.bottom ) // 위,아래 클리핑 처리
{
// 왼쪽 클리핑 처리
if ( rcImage.left < rcClip.left && (nRealX-nData)<rcClip.left )
{
nDLPixel = rcClip.left - (nRealX-nData);
}
// 오른쪽 클리핑처리
if ( nRealX > rcClip.right ) {
nDRPixel = nRealX-rcClip.right;
}
nOffset = nData - (nDLPixel+nDRPixel);
if( nOffset > 0)
{
// 실제 데이터를 복사함
memcpy(pSurface+nDLPixel, pImgData+nDLPixel, nOffset<<1); }
}
nDLPixel = 0; nDRPixel = 0; // 사용이 끝났으므로 초기화
pImgData += nData; // 읽어들인 만큼 주소 갱신
pSurface += nData;
}while( py <=rcImage.Height() );
g_pDDSBack->Unlock(NULL);
return TRUE;
}
/////////////////////////////////////////////////////////////////////////////
Simple Compression using an LZ buffer
간단하게 사용할수 있는 압축 알고리즘이다.
압축할때 시간은 길지만, 압축 푸는 속도는 굉장히 빠르다.
따라서 boot 로더처럼 압축된 데이터를 rom으로 가지고 사용할 경우 굉장히 유용하다.
압축 푸는 코드는 경이로울 정도로 간단하다. 이해하기가 너무 힘들지만 ^^;;
아래 코드가 실제로 압축 푸는 부분이다.
void UnPackSLZ(unsigned char *inbuffer, register FILE *outfile)
{
short myTAG, mycount, myoffset;
long int loop1;
for(;;) // loop forever (until goto occurs to break out of loop)
{
myTAG=*inbuffer++;
for(loop1=0;(loop1!=8);loop1++)
{
if(myTAG&0x80)
{
if((mycount=*inbuffer++)==0) // Check EXIT
{ goto skip2; } // goto's are gross but it's efficient :(
else
{
myoffset=HISTORY_SIZE-(((MASK_upper&mycount)<<LSR_upper)+(*inbuffer++));
mycount&=MASK_lower;
mycount+=2;
while(mycount!=0)
{
writechar(LZ_history[(lzhist_offset+myoffset)&MASK_history],outfile);
mycount--;
}
}
}
else
{ writechar(*inbuffer++,outfile); }
myTAG+=myTAG;
}
}
skip2:
return;
}
사용자로부터 주어진 텍스트 파일을 압축하고 반대로 압축된 파일은 압축을 푸는 프로그램으로 호프만 코드 알고리즘을 이용하여 호프만 테이블을 작성한다.
작성된 호프만 테이블로 입력된 텍스트 파일을 하나의 버퍼에 저장 후 파일에 출력 파일에 출력할 때 호프만 코드를 같이 출력한다.
파일 압축을 풀 때 하나의 버퍼에 파일의 내용을 저장 후 현재 프로그램의 버전과의 일치 여부와 코드 파일의 내용을 비교하면서 압축을 푼다.
참고로, 2Mbyte파일 압축시 75%정도 나온다.
// 사용 방법
압축 할때
실행파일명 -e[E] text.txt output.txt
압축 풀때
실행파일명 -d[D] output.txt text.txt
////////////////////// 소스 코드 ////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VERSION 1.0
#define MAX_SIZE 256
#define CHARBITS 8
#define MAX_CODE_LENGTH 16
#define MAX_CODE_NUMBER 256
#define MAX_STRING_LENGTH 1024*100 // maximum size of compressed file is 100 kbyte
#define MAX_BIT_MASK_NUMBER 8
#define RIGHTBITS(n, x) ((x) & ((1U << (n)) - 1U))
typedef struct code_tag
{
int ascii;
char code[MAX_CODE_LENGTH];
int lengthOfCode;
unsigned frequency;
} CODE;
int HuffmanCodeTable(CODE codeTable[]);
void SetCode(CODE codeTable[], int cnt);
int EncryptString(char original_string[], int length_Of_Original_string,
CODE codeTable[], int cnt_of_Codes, char encoded_String[]);
void WriteBitString(char encoded_String[], int cnt_Of_EncodedBits);
int DecryptBitString(char encoded_String[], int cnt_Of_EncodeBit,
CODE codeTable[], int cnt_Of_Codes, char decoded_String[]);
int SearchAlphabet(char key, CODE codeTable[], int cnt_Of_Codes);
void AttachCode(char encoded_String[], int cnt_Of_Bits, char code[], int lengthOfCode);
int SearchCode(char key[], CODE codeTable[], int cnt_Of_Codes);
void WriteInFile(char encoded_String[], int cnt_Of_EncodedBits, CODE codeTable[], int cnt_of_codes);
void PrnFreq(CODE codeTable[], int cnt_of_codes);
void Error(char *msg);
void DownHeap(int i);
void GetTableSizeAndCodeBits(int *size_of_table, int *cnt_Of_EncodeBit);
int GetVersion();
void GetCodeTable(CODE codeTable[], int cnt_of_codes);
void GetCode(char encoded_string[]);
void PrnCodeTable(CODE codeTable[], int cnt_of_codes);
void WriteDecodedBit(char decoded_String[]);
char bitMask_OR[MAX_BIT_MASK_NUMBER];
char bitMask_AND[MAX_BIT_MASK_NUMBER];
int heap_size, heap[2*MAX_SIZE-1], parent[2*MAX_SIZE-1], left[2*MAX_SIZE-1], right[2*MAX_SIZE-1];
unsigned long int frequency[2*MAX_SIZE-1];
FILE *ifp, *ofp;
int main(int argc, char *argv[])
{
int i, j = 0;
char Original_String[MAX_STRING_LENGTH];
char encoded_String[MAX_STRING_LENGTH];
char decoded_String[MAX_STRING_LENGTH];
int lengthOfDecodedString;
int cnt_Of_EncodedBits = 0;
CODE codeTable[MAX_CODE_NUMBER];
int cnt_Of_Codes = 0;
char option;
if(argc != 4 || ((option = *argv[1]) != 'e' && option != 'E'
&& option != 'd' && option != 'D'))
{
printf("Usage : %s [e or E|d or D] input_file output_file\n", argv[0]);
exit(1);
}
ifp = fopen(argv[2], "rb");
if(ifp == NULL)
{
printf("Cannot open file : %s", argv[2]);
exit(1);
}
ofp = fopen(argv[3], "wb");
if(ofp == NULL)
{
printf("Cannot open file : %s", argv[3]);
exit(1);
}
for(i=0; i < 8; i++)
{
bitMask_OR[i] = 1 << (7-i);
bitMask_AND[i] = bitMask_OR[i] ^ 0xff;
}
if(option == 'e' || option == 'E')
{
while((i = getc(ifp)) != EOF)
{
Original_String[j++] = i;
if(j >= MAX_STRING_LENGTH)
Error("Error : larger than 100kbyte!\n");
}
Original_String[j]='\0';
rewind(ifp);
cnt_Of_Codes = HuffmanCodeTable(codeTable);
cnt_Of_EncodedBits = EncryptString(Original_String, strlen(Original_String), codeTable, cnt_Of_Codes, encoded_String);
WriteInFile(encoded_String, cnt_Of_EncodedBits, codeTable, cnt_Of_Codes);
}
else
{
if(GetVersion())
Error("Error : The file isn't equivalent the current program
version!\n");
GetTableSizeAndCodeBits(&cnt_Of_Codes, &cnt_Of_EncodedBits);
GetCodeTable(codeTable, cnt_Of_Codes);
GetCode(encoded_String);
lengthOfDecodedString = DecryptBitString(encoded_String, cnt_Of_EncodedBits, codeTable, cnt_Of_Codes, decoded_String);
WriteDecodedBit(decoded_String);
}
fclose(ifp);
fclose(ofp);
return 0;
}
int GetVersion()
{
int i, j = 0;
char buffer[10];
while((i = getc(ifp)) != EOF && j < 3)
{
buffer[j++] = i;
if(j >= MAX_STRING_LENGTH)
Error("Error : larger than 100kbyte!\n");
}
if(atof(buffer) == VERSION)
return 0;
else
return -1;
}
/*************************************************************
* 호프만 테이블 사이즈와 비트의 수 얻기
*
*************************************************************/
void GetTableSizeAndCodeBits(int *size_of_table, int *cnt_Of_EncodeBit)
{
int ch, i = 0;
char buffer[10];
while((ch = getc(ifp)) != EOF && ch != 0x2F)
buffer[i++] = ch;
buffer[i] = '\0';
*size_of_table = atoi(buffer);
i = 0;
while((ch = getc(ifp)) != EOF && ch != 0x20)
buffer[i++] = ch;
*cnt_Of_EncodeBit = atoi(buffer);
return;
}
/*************************************************************
* 호프만 코드 테이블을 메모리에 저장
*
*************************************************************/
void GetCodeTable(CODE codeTable[], int cnt_of_codes)
{
int i = 0, j = 0, tmp, is_block = 0;
while((tmp = getc(ifp)) != EOF || i < cnt_of_codes)
if(!is_block && tmp != '0' && tmp != '1')
{
codeTable[i].ascii = tmp;
}
else if(tmp == '0' || tmp == '1')
{
is_block = 1;
codeTable[i].code[j++] = tmp;
continue;
}
else if(is_block && tmp != '0' && tmp != '1')
{
codeTable[i].code[j] = '\0';
is_block = 0, j = 0;
if(cnt_of_codes == ++i)
break;
codeTable[i].ascii = tmp;
}
}
PrnCodeTable(codeTable, cnt_of_codes);
}
/*************************************************************
* 호프만 코드로 작성된 내용을 버퍼에 저장
*
*************************************************************/
void GetCode(char encoded_string[])
{
int ch, i = 0;
while((ch = getc(ifp)) != EOF)
{
encoded_string[i++] = ch;
if(i >= MAX_STRING_LENGTH)
Error("Error : larger than 100kbyte!\n");
}
encoded_string[i] = '\0';
}
void Error(char *msg)
{
printf("%s", msg);
exit(1);
}
void PrnFreq(CODE codeTable[], int cnt_of_codes)
{
int i, k = 0, size = 0;
printf("텍스트 분석 중...\n");
printf("---------------------------------\n");
printf("alphabet\tfrequency\n");
printf("---------------------------------\n");
for(i = 0; i <= cnt_of_codes; i++)
{
if((codeTable[i].ascii >= 65 && codeTable[i].ascii <= 90)
|| (codeTable[i].ascii >= 97 && codeTable[i].ascii <= 122))
{
printf("%c\t\t%d\n", codeTable[i].ascii, codeTable[i].frequency);
size += codeTable[i].frequency;
}
}
printf("---------------------------------\n");
printf("텍스트의 크기 : %d byte\n", size);
printf("---------------------------------\n\n\n");
}
/*************************************************************
* 버퍼에 저장된 호프만 코드를 사용 빈도수에 맞게 버퍼에 저장
*
*************************************************************/
void DownHeap(int i)
{
int j, k;
while ((j = 2 * i) <= heap_size)
{
if (j < heap_size && frequency[heap[j]] > frequency[heap[j + 1]])
j++;
if (frequency[k] <= frequency[heap[j]])
break;
heap[i] = heap[j];
i = j;
}
heap[i] = k;
}
/*************************************************************
* 호프만 알고리즘을 이용한 코드 테이블 작성
*
*************************************************************/
int HuffmanCodeTable(CODE codeTable[])
{
int i, j, k, avail, cnt_of_codes;
unsigned long int incount;
for(i = 0; i < MAX_SIZE; i++)
frequency[i] = 0;
while ((i = getc(ifp)) != EOF)
frequency[i]++;
heap[i] = 0;
heap_size = 0;
for(i = 0; i < MAX_SIZE; i++)
{
if(frequency[i] != 0)
heap[++heap_size] = i;
for(i = 1; i <= heap_size; i++)
{
codeTable[i-1].ascii = heap[i];
codeTable[i-1].frequency = frequency[heap[i]];
}
cnt_of_codes = heap_size;
PrnFreq(codeTable, cnt_of_codes);
for(i = heap_size / 2; i >= 1; i--)
DownHeap(i);
for(i = 0; i < 2 * MAX_SIZE - 1; i++)
parent[i] = 0;
k = heap[1];
avail = MAX_SIZE;
while (heap_size > 1)
{
i = heap[1];
heap[1] = heap[heap_size--];
DownHeap(1);
j = heap[1];
k = avail++;
frequency[k] = frequency[i] + frequency[j];
heap[1] = k;
DownHeap(1);
parent[i] = k;
parent[j] = -k;
left[k] = i;
right[k] = j;
}
incount = 0;
rewind(ifp);
SetCode(codeTable, cnt_of_codes);
return cnt_of_codes;
}
/*************************************************************
* 아스키 코드에 대한 코드 작성
*
*************************************************************/
void SetCode(CODE codeTable[], int cnt_of_codes)
{
int i, j, k, val = 0;
char temp[MAX_SIZE];
for(i = 0, j = 0, k = 0; i < cnt_of_codes; i++, j = 0, k = 0)
{
val = codeTable[i].ascii;
while ((val = parent[val]) != 0)
{
if (val > 0)
temp[j++] = '0';
else
{
temp[j++] = '1';
val = -val;
}
while(--j >= 0)
{
codeTable[i].code[k] = temp[j];
k++;
}
codeTable[i].code[k] = '\0';
codeTable[i].lengthOfCode = strlen(codeTable[i].code);
}
PrnCodeTable(codeTable, cnt_of_codes);
}
void PrnCodeTable(CODE codeTable[], int cnt_of_codes)
{
int i;
printf("Huffman code 생성 중...\n");
printf("---------------------------------\n");
printf("alphabet\tcode\n");
printf("---------------------------------\n");
for(i = 0; i < cnt_of_codes; i++)
if((codeTable[i].ascii >= 65 && codeTable[i].ascii <= 90) || (codeTable[i].ascii >= 97 && codeTable[i].ascii <= 122))
printf("%c\t\t%s\n", codeTable[i].ascii, codeTable[i].code);
printf("---------------------------------\n");
}
/*************************************************************
* 호프만 코드로 문자열 압축
*
*************************************************************/
int EncryptString(char original_String[], int length_Of_Original_String,
CODE codeTable[], int cnt_Of_Codes, char encoded_String[])
{
int i, pos, cnt_Of_Bits = 0;
for(i = 0; i < length_Of_Original_String; i++)
{
pos = SearchAlphabet(original_String[i], codeTable, cnt_Of_Codes);
if(pos >= 0)
{
AttachCode(encoded_String, cnt_Of_Bits, codeTable[pos].code, codeTable[pos].lengthOfCode);
cnt_Of_Bits += codeTable[pos].lengthOfCode;
}
else
{
printf("%c does not exist in code table!!\n", original_String[i]);
return -1;
}
}
return cnt_Of_Bits;
}
void WriteBitString(char encoded_String[], int cnt_Of_EncodedBits)
{
int i, pos = 0;
char a;
for(i=0; i < cnt_Of_EncodedBits; i++)
{
if(i%8==0)
{
putchar(' ');
a = encoded_String[pos++];
}
putchar(((a & bitMask_OR[0]) == 0) ? '0' : '1');
a <<= 1;
}
putchar('\n');
}
void WriteDecodedBit(char decoded_String[])
{
int i, j, length, val, tmp = 0, diff;
double progress = 0.0;
printf("압축 푸는 중 ...\n");
length = (int)strlen(decoded_String);
for(i =0; i < length; i++)
{
progress = (double)(i+1) / (double)length * 100.0;
if((int)progress%10 == 0 && (int)progress != 0 && (int)progress != 100)
{
if((val = (int)progress) != tmp)
{
if((diff = (val - tmp) / 10) > 1)
for(j = 1; j < diff; j++)
printf("%d %% 압축 품\n", tmp + j * 10);
printf("%d %% 압축 품\n", val);
tmp = val;
}
}
else if((int)progress/10 && (int)progress%10 > 5)
{
if((val = ((int)progress/10)*10) != tmp)
{
if((diff = (val - tmp) / 10) > 1)
for(j = 1; j < diff; j++)
printf("%d %% 압축 품\n", tmp + j * 10);
printf("%d %% 압축 품\n", val);
tmp = val;
}
}
else if((val = ((int)progress/10)*10) != tmp && (int)progress != 100)
{
if((diff = (val - tmp) / 10) > 1)
{
for(j = 1; j < diff; j++)
printf("%d %% 압축 품\n", tmp + j * 10);
}
printf("%d %% 압축 품\n", val);
tmp = val;
}
putc(decoded_String[i], ofp);
}
printf("완료.\n");
}
void WriteInFile(char encoded_String[], int cnt_Of_EncodedBits, CODE codeTable[],
int cnt_of_codes)
{
int i, j, ch = 0, incount, outcount, pos = 0, val, tmp = 0, diff;
double version = VERSION, progress = 0.0;
char *p, buffer[MAX_STRING_LENGTH];
printf("압축 중 ...\n");
fseek(ifp, 0L, SEEK_END);
incount = ftell(ifp);
// write a version
sprintf(buffer, "%.1f ", version);
for(i =0; i < (int)strlen(buffer); i++)
putc(buffer[i], ofp);
// write a size of the code tables
sprintf(buffer, "%d", cnt_of_codes);
for(i =0; i < (int)strlen(buffer); i++)
putc(buffer[i], ofp);
sprintf(buffer, "/%d ", cnt_Of_EncodedBits);
for(i =0; i < (int)strlen(buffer); i++)
putc(buffer[i], ofp);
// write contents of the code tables
for(i = 0; i < cnt_of_codes; i++)
{
putc(codeTable[i].ascii, ofp);
for(j = 0; j < codeTable[i].lengthOfCode; j++)
putc(codeTable[i].code[j], ofp);
}
putc(' ', ofp);
// write contents of compressed file
p = encoded_String;
for(i=0; (i < cnt_Of_EncodedBits) && (ch != EOF) && (*p != '\0'); i++)
{
progress = (double)i / (double)cnt_Of_EncodedBits * 100.0;
if((int)progress%10 == 0 && (int)progress != 0 && (int)progress != 100)
{
if((val = (int)progress) != tmp)
{
if((diff = (val - tmp) / 10) > 1)
{
for(j = 1; j < diff; j++)
printf("%d %% 압축\n", tmp + j * 10);
}
printf("%d %% 압축\n", val);
tmp = val;
}
}
else if((int)progress/10 && (int)progress%10 > 5)
{
if((val = ((int)progress/10)*10) != tmp)
{
if((diff = (val - tmp) / 10) > 1)
{
for(j = 1; j < diff; j++)
printf("%d %% 압축\n", tmp + j * 10);
}
printf("%d %% 압축\n", val);
tmp = val;
}
}
else if((val = ((int)progress/10)*10) != tmp && (int)progress != 100)
{
if((diff = (val - tmp) / 10) > 1)
{
for(j = 1; j < diff; j++)
printf("%d %% 압축\n", tmp + j * 10);
}
printf("%d %% 압축\n", val);
tmp = val;
}
if(i%8==0)
ch = putc( p[pos++], ofp );
}
printf("압축 완료.\n");
outcount = ftell(ofp);
printf("---------------------------------\n");
printf("텍스트 파일 크기 : %u bytes\n", incount);
printf("압축된 파일 크기 : %u bytes\n", outcount);
printf("압축 비율 : %.3f(%u/%u - 1)\n", ((double)incount / (double)outcount - 1.0)
, incount, outcount);
}
/*************************************************************
* 호프만 코드로 문자열 압축 풀기
*
*************************************************************/
int DecryptBitString(char encoded_String[], int cnt_Of_EncodeBit,
CODE codeTable[], int cnt_Of_Codes, char decoded_String[])
{
int i, index, pos=0, length_Of_DecodedString=0;
char code[MAX_CODE_LENGTH] = {'\0'};
char a;
for (i = 0; i < cnt_Of_EncodeBit; i++)
{
if(i%8 ==0)
a=encoded_String[pos++];
if(a & bitMask_OR[0])
strcat(code, "1");
else
strcat(code, "0");
a <<= 1;
index=SearchCode(code, codeTable, cnt_Of_Codes);
if(index != -1)
{
decoded_String[length_Of_DecodedString] = codeTable[index].ascii;
length_Of_DecodedString++;
code[0] = '\0';
}
}
decoded_String[length_Of_DecodedString] = '\0';
return length_Of_DecodedString;
}
/*************************************************************
* 호프만 테이블 내의 주어진 알파벳 문자의 인덱스 찾기
*
*************************************************************/
int SearchAlphabet(char key, CODE codeTable[], int cnt_Of_Codes)
{
int i, index = -1;
for (i = 0; i <cnt_Of_Codes; i++)
{
if(codeTable[i].ascii == key)
{
index=i;
break;
}
}
return index;
}
/*************************************************************
* 호프만 테이블 내의 주어진 코드의 인덱스 찾기
*
*************************************************************/
int SearchCode(char key[], CODE codeTable[], int cnt_Of_Codes)
{
int i, index=-1;
for (i = 0; i < cnt_Of_Codes; i++)
{
if(strcmp(codeTable[i].code, key) == 0)
{
index=i;
break;
}
}
return index;
}
/*************************************************************
* 하나의 버퍼에 호프만 코드 저장
*
*************************************************************/
void AttachCode(char encoded_String[], int cnt_Of_Bits, char code[],
int lengthOfCode)
{
int i, lengthOfEncodedString, lastBitPosition;
lengthOfEncodedString = cnt_Of_Bits/8;
lastBitPosition = cnt_Of_Bits%8;
for (i = 0; i < lengthOfCode; i++)
{
if(code[i]=='1')
encoded_String[lengthOfEncodedString] |= bitMask_OR[lastBitPosition];
else
encoded_String[lengthOfEncodedString] &= bitMask_AND[lastBitPosition];
lastBitPosition++;
if(lastBitPosition == 8)
{
lastBitPosition = 0;
lengthOfEncodedString = lengthOfEncodedString + 1;
}
}
}
