[강좌] 기초적인 압축 알고리즘 하이텔 퍼옴..
_____________________________________________________________________
RLE / RLE+ / FAX / FAX+ / Lempel-Zip 방식압축기법
---------------------------------------------------------------------
< RLE (Run Length Encoding) 방식 >
가장 쉽지만 모든것이 그렇듯 가장 압출률이 저조한 방법입니다.
화일을 16 진수로 나타낸 코드를 읽어서 다음과 같은 예가 있다면
<데이터>
00 00 1C 1C 1C F3 F3 F3 F3 F3 D8 11 11 11 11 11
위의 자료는 16byte의 자료입니다.
RLE 방식으로 압축을 하면 다음과 같이 나타낼수 있습니다.
<RLE 압축>
00 02 1C 03 F3 05 D8 01 11 05
대상코드와 그 코드의 갯수를 나란히 적은 것임을 알수 있습니다.
이방법은 일반적으로 독립적으로 쓰이기보다는 여러가지 기법과 혼용되어
쓰이는 방법입니다. 또한 연속된 자료가 자주 나타나는 그림화일등에서
압축률을 높일수 있습니다. 다른 일반 자료는 오히려 압축한것이
더큰 역효과를 가져옵니다. 이유는 자료코드 하나와 갯수코드 하나씩해서
최악의 경우는(연속된자료가 전혀없는경우) 꼭 원본보다 두배의 자료가
되기 때문이죠.
-----------------------------------------------------------------------
< RLE 보완형 >
RLE의 단점은 연속되지 않은 자료의 압축시에 오히려 그 압축화일의 용량
이 더욱 커진다는 것이었습니다. 그러나 일부 그림자료등을 제외하면
대부분의 자료들은 같은 코드의 반복은 그리 눈에 띄지 않습니다...
여기서 보일 방법은 RLE의 갯수를 세는 부분을 달리 하는 것입니다.
기존에 01 02 03 ...처럼 숫자를 썼던 것 대신 C0 C1 C2 ...등으로 바꾸어
쓰는 것입니다. 이 방법은 글쎄요. RLE 방법과 그다지 별차이가 없어
보이지만 코딩시에 새로운 규칙을 첨가함으로써 변화를 도모합니다.
그 규칙이라 함은 갯수를 설정하면 코드의 갯수가 바뀌지 않는이상 다시
설정하지 않는다는 것입니다. (이해가 가실까.....그렇다면 예제를..)
<데이터>
F9 03 5D E3 21 00 EE 45 33 76 DE 3D 2F F4 5C B2
위와 같은 16byte 데이터의 RLE 보완형으로 압축하면 다음과 같습니다.
<RLE 보완압축>
C0 F9 03 5D E3 21 00 EE 45 33 76 DE 3D 2F F4 5C B2
17byte 로 원본보다 1byte나 손해를 보았습니다. 그러나 RLE 보다는
훨씬 좋은 방법임을 알수 있습니다.
위의 예는 전혀 연속되는 자료가 없었다는 겁니다. 그러나 다음의 예와
같이 연속되는 자료가 존재하면 이야기는 달라집니다.
<데이터>
03 03 03 03 5F E3 21 00 EE 45 33 76 DE 3D 2F F4 5C
<RLE 보완압축>
C3 03 C0 5F E3 21 00 EE 45 33 76 DE 3D 2F F4 5C
자 1byte의 압축 효과를 가져왔습니다.
하지만 혹자는 여기서 이런 의문을 갖을수도 있겠습니다. 만일 데이터상에
C0...CF 의 자료가 존재하면 어떻게 하는가....만일 다음과 같은 자료가
있다면 예 치고는 너무 속보이는 예제입니다만....헐~
<데이터>
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB CC CD CE CF
<RLE 보완압축?>
C0 C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB CC CD CE CF
위의 압축된것이 맞을까요? 흐흐......절대 아니죠....위의 것을 다시 풀어
쓴다고 생각하면 전혀 다른 해석이 생기게 됩니다.
지금까지 쓴 RLE 보완형의 규칙을 보면 갯수는 C0...CF로적되 첨음에는 갯수
다음에 코드순이었습니다....따라서 압축된것을 거기에 준하여 해석하면
C0 C0 는 C0가 1개로 해석되지만 다음부터는 문제가 생기죠...C1 C2 에서는
엉뚱하게도 C2 라는 코드가 2개인것으로 해석된다는 맹점입니다.
따라서 이런경우를 위한 한가지의 규칙이 더 필요하게 됩니다.
* 만일 데이커상에 C0...CF 의 자료가 있으경우 그부분에 대해서 특별히
기존의 RLE 방법으로 압축한다. 갯수를 적을때는 역
C0...CF 코드를 이용
한다.
이해를 돕기위한 예제는 다음과 같습니다.
<데이터>
34 DE C3 C3 C3 F4 F4 F4 DE C0 36 8D B1 A0 00 01
위와 같은 16byte의 자료를 압축합니다. 압축시 주의할사항으로는 C# 코드발견
시 RLE로 압축하고( 갯수 + 코드 쌍형태) 다시 RLE 보완형을 시작하는 것입니다
즉, 앞에 압축한것과 별도의 압축을 한다고 생각하고 다시 C# 형태의 갯수를 쓰
는것부터 하는거죠....압축된것을 보면 다음과 같습니다.(~~ 친부분 주의할곳)
<RLE 보완압축>
C0 34 DE C2 C3 C2 F4 C0 DE C0 C0 C0 36 8D B1 A0 00 01
~~ ~~
처음부터 차근차근 살펴보겠습니다.
먼저 C0의 의미는 34 DE 라는 데이터가 한개씩 있다는 뜻입니다.
C2 C3 는 C3 데이터가 3개 있다는 이야기입니다.
C2 F4 는 F4 데이터가 3개있다는 의미인데...문제는 이전에 쓰인 C2 의 의미가
뒤에나오는 C3 C2 F4 까지 모두 3개씩이 아닌가 하는 해석의 오류를 나을수 있
다는 것입니다. 그러나 압축에서 규칙을 정한것처럼 C0...CF 자료가 둘이상 존재
할때는 이것이 특수한 규칙에 의해서 압축된 RLE 방식이라는 것을 잊어서는 안
됩니다...따라서 압축을 풀때에도 C0...CF 코드가 나오면 두개씩 짝을지어 RLE
방식으로 해석하고 풀어야 한다는 이야기입니다. 둘씩 짝을 지어 해석한후 다시
나오는 C2 는 다음에 나오는 자료가 C# 형태가 아니기 때문에 보완형으로 압축된
것임을 알수 있습니다...그래서 F4가 3개 연속이라는 뜻이죠...다음에 연속되는
C0의 해석에서는 C#형태가 연속되므로 이것은 RLE 방식의 압축입니다. 따라서 첫
C0는 갯수 다음은 코드...해서 C0 가 하나있다는 의미이구요...(역시 2개씩 짝을
짓죠...RLE 방식은 두개씩의 짝을 만들어 냅니다...) 다음에 나오는 C0는 38 8D
B1 A0 00 01 이라는 코드가 모두 하나씩 존재한다는 의미입니다.
역시 다음코드인 DE 가 1개라는 의미죠...조금은 복잡한듯 싶지만 그 규칙을 완
전히 이해한다면 별루 어려울것은 없습니다.
실전을 위해 압축된 자료의 원본을 만들어보는 연습을 하겠습니다.
<RLE 보완압축 자료>
C0 34 DE C2 C3 C2 F4 C0 DE C0 C0 C0 36 8D B1 A0 00 01
C0 34 DE 가지는 34 DE 가 하나씩 있다는 의미입니다. 다음에 나온 C2 C3 C2...
C#의 형태가 연속해있으므로 두개씩 묶어서 생각합니다. C2 C3 는 RLE 압축이
니까...C3 라는 데이터가 3개라는 의미겠죠...다음...C2는 다시 RLE 보완형의
첫부분이니까...갯수를 나타내고 다음에 나오는 F4라는 데이터의 갯수죠...
따라서 F4 3개.....C0 DE 는 DE 가 1개 다음에 역시 연속되는 C0 중에...두개를
취해서 C0가 1개있다는 의미이고....세번째 C0는 RLE 보완형 첫번째인 갯수 따라
서 36 8D B1 A0 00 01 이 하나씩... 이상을 종합하면...
<복원데이터>
34 DE C3 C3 C3 F4 F4 F4 DE C0 36 8D B1 A0 00 01
이 됩니다.....원래의 모습을 찾았죠? 이해가 가십니까?
규칙에 충실하면 어려울것이 없습니다. RLE 방식은 가장 기초적인 방식으로 다른
압축 기법을 공부하는데에 기본이 된다구나 할까요....
---------------------------------------------------------------------------
<FAX 압축>
이 압축 방법은 현재 많이 쓰이는 사무기기인 팩시밀리에서 사용하는 압축 방식입
니다. 압축률또한 위에서 언급된 RLE 계열의 방식보다 좋으며 RLE방식을 제외한
기타다른 압축방식보다 구현하기가 쉬워서 맣이 사용되고 있습니다.
간단히 설명하자면 이전까지 사용하던 16진 코드를 2진코드로 바꾸어 압축하는
방식입니다. 다른 말로 비트맵이라는 표현을 쓰기도 합니다. 마우스의 커서등을
구현할때 모눈종이에 그리던것 생각하시면 빠르겠네요..
자 우선 아래와 같은 32byte의 데이터를 읽어들입니다.
<데이터>
00 00 0F F0 1F F8 1F F8 1F F8 0F F0 00 00 00 00
0F F0 11 88 11 88 11 88 11 88 11 88 0F F0 00 00
위의 데이터를 RLE 보완압축 방식으로 압축하면 다음과 같겠죠 (쩝 압축률
0%?)
<RLE 보완압축>
C1 00 C0 0F F0 1F F8 1F F8 1F F8 0F F0 C3 00 C0
0F F0 11 88 11 88 11 88 11 88 11 88 0F F0 C1 00
비교를 위해서 RLE 방법을 쓰면 다음과 같습니다. (흐...팽창률 170%?)
<RLE 압축>
00 02 0F 01 F0 01 1F 01 F8 01 1F 01 F8 01 1F 01
F8 01 0F 01 F0 01 00 04 0F 01 F0 01 11 01 88 01
11 01 88 01 11 01 88 01 11 01 88 01 11 01 88 01
0F 01 F0 01 00 02
비교상으로도 RLE 보완형이 월등히 좋다는 것을 알수 있습니다....그럼 FAX 압축
을 위해서 우선 비트맵으로 구성해보도록 하겠습니다.
위의 데이터를 16 by 16 비트맵으로 나타내면 다음과 같습니다.(정사각형모양)
<비트맵> | <16진>
|
0000 0000 0000 0000 | 00 00
0000 1111 1111 0000 | 0F F0
0001 1111 1111 1000 | 1F F8
0001 1111 1111 1000 | 1F F8
0001 1111 1111 1000 | 1F F8
0000 1111 1111 0000 | 0F F0
0000 0000 0000 0000 | 00 00
0000 0000 0000 0000 | 00 00
0000 1111 1111 0000 | 0F F0
0001 0001 1000 1000 | 11 88
0001 0001 1000 1000 | 11 88
0001 0001 1000 1000 | 11 88
0001 0001 1000 1000 | 11 88
0001 0001 1000 1000 | 11 88
0000 1111 1111 0000 | 0F F0
0000 0000 0000 0000 | 00 00
먼저 일단계로 위의 비트맵에서 0이 많아지는 방향으로 데이터를 규칙있게
변형시키는 것입니다. 먼저 기존의 0은 그대로 두고 0에서 1로 변화되는 부분과
0 에서 1로 변화되는 부분에서마 1을 쓰는 방법이 있습니다.
변형되 형태는 다음과 같은 모습이 될것입니다.
<변형된 비트맵>
0000 0000 0000 0000
0000 1000 0000 1000
0001 0000 0000 0100
0001 0000 0000 0100
0001 0000 0000 0100
0000 1000 0000 1000
0000 0000 0000 0000
0000 0000 0000 0000
0000 1000 0000 1000
0001 1001 0100 1100
0001 1001 0100 1100
0001 1001 0100 1100
0001 1001 0100 1100
0001 1001 0100 1100
0000 1000 1000 1000
0000 0000 0000 0000
위의 데이터는 예시를 위해 조작된 것이기 때문에 확실이 0숫자가 많이 포함
되어있습니다. 그러나 일반적인 데이터는 이보다는 좋지 않은 결과가 나올경우가
더 많다는 것을 알아두셔야 합니다. 또한 FAX 압축을 풀기위한 규칙으로 가장
첫 비트가 1이면 그자리는 1로 표시해야합니다. 그렇지 않으면 나중에 압축
을 풀어나갈때 곤란한 경우가 생기게 됩니다. 우선을 그렇게 알아두시면 됩니다.
여기까지 끝이 나면 다음 단계로 넘어갑니다. 이번에는 데이터를 회전시킵니다.
프로그램상으로 구현할때에는 위에서 아래로 데이터를 읽어서 왼쪽에서 오른쪽
으로 써나가면 됩니다.(이유는 0을 많이 만들기 위함입니다)
재변형된 데이터의 형태는 아래와 같습니다.
재변형 비트맵 | 16진 | 헤더비트
---------------------------------------------
0000 0000 | 0000 0000 | 00 00 | 00
0000 0000 | 0000 0000 | 00 00 | 00
0000 0000 | 0000 0000 | 00 00 | 00
0011 1000 | 0111 1100 | 38 7C | 11
0100 0100 | 1111 1110 | 44 FE | 11
0000 0000 | 0000 0000 | 00 00 | 00
0000 0000 | 0000 0000 | 00 00 | 00
0000 0000 | 0111 1100 | 00 7C | 01
---------------------------------------------
0000 0000 | 0000 0000 | 00 00 | 00
0000 0000 | 0111 1100 | 00
7C | 01
0000 0000 | 0000 0000 | 00 00 | 00
0000 0000 | 0000 0000 | 00 00 | 00
0100 0100 | 1111 1110 | 44 FE | 11
0011 1000 | 0111 1100 | 38 7C | 11
0000 0000 | 0000 0000 | 00 00 | 00
0000 0000 | 0000 0000 | 00 00 | 00
데이터를 입력하기위해서 우선 헤더비트를 쓴후 데이터를 입력하는 방식으로
압축을 해나가는 것입니다. 여기서 헤더 비트란 것은 재변형된 비트맵상에서
1byte를 취하여 그값이 0이면 0 그외의 숫자이면 1을 부여하여 일열로 나열
한 일종의 암호데이터라고 할까요.(위에 세로줄로 나눈것은 byte 단위로 알아
볼수 있도록 한것입니다) 위에 헤더비트를 적은 것을 보면 쉽게 그 의미를
알수 있을 것입니다. 따라서 위의 데이터의 헤더비트는 다음과 같습니다.
<헤더비트>
0000 0011 1100 0001 0001 0000 1111 0000 : 03 C1 10 F0
압축된 데이터는 이 헤더비트를 가장 먼저 적고 다음에 자료를 입력하는데
단, 자료가 00일때는 적지 않습니다. 완성된 압축 데이터는 다음과 같습니다.
<FAX 압축>
03 C1 10 F0 38 7C 44 FE 7C 44 FE 38 7C
~~~~~~~~~~~
헤더비트
처음에 주어진 32 byte 데이터가 13 byte로 압축되었습니다. (압축률 약60%)
사실 위의 예제는 16 by 16 비트맵을 사용했지만 8 by 8 비트맵을 4번 압축한
것과도 같습니다...따라서 위의 예제를 8 by 8 비트맵으로 바꾸어 네번 같은
계산을 반복해도 하나의 방법으로 생각할수 있습니다.
문제는 얼마나 많은 데이터를 이용하는가와 계산상의 속도문제가 상호작용하
게 되기 때문에 적정선에서 나누는것이 좋습니다. 보통 8 by 8 비트맵이나
16 by 16 비트맵을 사용합니다.
이 FAX 압축을 푸는 방법은 지금까지 해왔던 일련의 작업을 꺼꾸로 수행하는
것입니다. 먼저 헤드를 읽어서...우선은 이 압축이 8 by 8 로 압축되었는지
16 by 16 으로 압축되었는지 알아야 하는것은 당연한것이겠죠...압축한 방법
으로 풀어야 풀리겠죠....어쨌든.. 헤드를 읽어서 데이터중에 00의위치와 0이
아닌 데이터의위치를 파악한후 자료를 순서대로 읽어 해당위치에 넣고
(여기까지는 재변형 비트맵) 회전된 것을 복구하기 위해서 데이터를 왼쪽에서
오른쪽으로 읽어서 위에서 아래로 써 원래의 변형된 비트맵을 만듭니다.
이제는 1과 0의 규칙에 따라서 원래의 자료로 복구를 하는 것입니다.
여기서 앞에서 언급했던 첫비트의 1일때 문제는 이렇습니다. 만일 첫비트가
11100 등으로 시작되었는데도....00010 등으로 쓰였을경우 복구할때...규칙에
의해서 00010 은....00011 로 복구가 되죠....원하는 값이 아닙니다....따라서
위의 경우...즉, 11100 으로 시작하는 데이터의 올바른 변형법은 10010 입니다.
그래야 규칙에 의해서 11100으로 바뀔수가 있기 때문입니다.
이점만 유의 한다면 FAX 압축도 별 어려운 것이 없을것이라고 생각합니다.
참고적으로 말씀드리자면 FAX 방법에 있어서 어떤때에는 오히려 헤더부분때문에
특히 16 by 16 비트맵 방식에서는 무려 4 byte 의 헤더가 이용되면서...압축률
에 있어서 손해를 보게 되는 경우가 많습니다...그래서 보통은 8 by 8 비트맵
의 형태를 사용하는데 그대신 많은 데이터를 한번에 읽어서 속도를 향상시키
기도 합니다. 하지만 16 by 16 의 장점은 8 by 8 보다는 데이터의 압축률에 있
어서 앞선다는 것입니다....그래서 나온것이 16 by 16 비트맵 방식에서...
헤더의 크기를 2 byte 로 줄일수 있는 방법이 있다고 합니다.
음...FAX 압축이 비록 팩시밀리에서 사용되는 방법이긴하지만 자료에 따라서는
예를 들면 실행화일을 압축하는데 있어서는 결코 쓸모있는 것은 못됩니다.
대부분의 경우....10% 내외의 압축률이나..마이너스 압축률이 나오기 쉽상
이라는 점을 알아두시기 바랍니다.
---------------------------------------------------------------------------
<FAX 보완압축>
보완형이란 다름아닌 위에서 잠시 언급한 헤더를 2byte 로 줄이는 방법입니다.
구현 원리는 FAX 와 같지만 마지막에 헤더를 쓰고 자료를 적는 부분에서만
차이를 보이는 것입니다. FAX 압축의 예제에서 보인것은 헤더를 만들때 8 bit
를 기준으로 해서 03 C1 10 F0 라는 헤더를 얻어냈었습니다... 그러나 여기서
는 16 bit 를 기준으로 해서 새로운 헤더를 만들어낼수 있습니다.
즉, 위의 헤더비트의 예에서
<8bit 헤더비트의 예>
00 00 00 11 11 00 00 01 00 01 00 00 11 11 00 00 : 03 C1 10 F0
였던 헤더비트가 16 bit를 기준으로 하면
<16bit 헤더비트로의 변형>
0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 : 19 4C
으로 변화하게 됩니다. 즉, 헤더가 8bit 일때의 절반으로 감소함으로써 데이터의
압축률이 다소 낮아지더라도 충분한 보상을 갖어오게 된다는 것입니다.
---------------------------------------------------------------------------
<Lempel-Zip 방식>
이 방식은 누구나 한번쯤은 생각했보았을만한 방법이면서 근래 많이 이용되는
압축프로그램의 원형이라고 말할수 있는 방식입니다. 크랙용 프로그램인 크랙잭을
보면 크랙을 위한 사전을 가지고 있는것을 볼수 있죠. 이와 비슷한 방식으로
같다고 볼수는 없지만 그런 접근으로 압축을 하는 것이 이방법의 개요입니다.
압축방법이라기 보다는 암호책을 대조하는 식으로 생각하면 이해가 빠를까요?
최고의 효율을 가지고 있는 방식으로 현재 압축효율이 좋은 압축 프로그램들은
모두 이 방식을 사용하거나 그 변형을 이용합니다. 이 방식의 실현은 상당히 어렵지
만 간단하게 생각하면 사전과 같이 자주 사용되는 것을 일종의 테이블로 만들어
압축하는 것입니다. 코드 필드와 서픽스로 나뉘어서 구성되는 테이블의 내용은
다중 패스를 거쳐야 하는 복잡한 알고리즘을 가지고 있지만 여기서 간단히 개념만을
파악한다면 다음과 같이 볼수 있습니다.
INDEX ENCODE 사전
┌─────┐
.. │ ..... │
... │ ..... │
... │ .... │
├─────┤
478 │ IS │
RAW DATA ├─────┤
... │ .... │
"THIS IS HOT -> ├─────┤-> INDEX OUTPUT
STUFF" 759 │ HOT │ 1295 478 759 3751
├─────┤ (12954787593751)
... │ ... │
├─────┤
1295 │ THIS │
├─────┤
.... │ .... │
├─────┤
3751 │ STUFF │
├─────┤
.... │ .... │
└─────┘
INDEX ENCODE 사전이라는 것은 압축 프로그램이 규칙에의해 보유하고 있는
일종의 사전이라고 보시면 됩니다. 각각에 번호나 약속된 기호들로 구성되어
그 인덱스 하나가 하나의 단어내지는 기호를 나타내게 되는 것입니다.
압축을 하기위해서는 해당하는 INDEX를 알아야만 가능하겠죠... 일일이 이런
사전을 개인이 구축한다는 것은 그리 쉬운 일은 아닐것입니다. 많은 노력과
시간이 들겠죠.. 파싱이라는 기법을 이용해서 인덱스를 자체 생산하는 방법
이 있긴 합니다. 간단한 텍스트 압축기는 충분히 만들수 있을것이라고
생각이 듭니다.
------------------------------------------------------------------------
마감의 글
이밖에도 가장 뛰어나다고 여겨지는 허프만 방식이라는 것이 있는데....
이것도 lempel-zip 과 유사한 점도 있구...다만 허프만 부호라는 것을 알아야
합니다....마치 방금 말씀드리 사전과 같죠...
이 글로 인해서 압축 알고리즘이나 압축기 제작에 관심이 생기신분이 한분이
라도 생기셨다면 저로서는 만족스럽습니다. 기타 너무나 난해하고 테크닉적인
부분이나 심도 깊은 부분에 대해서는 저역시 배우는 입장에서 쓴다는것은
주제넘은 짓이 아닌가 생각이 들구요....관련 서적을 찾아보시길 바랍니다.
이로써 압축 알고리즘에 대한 미진하나마 저의 글을 마칠까 합니다.
또한 한가지.....강좌/정보란에 lt 알고리즘 으로 찾아보시면 PCX 화일데이터
의 압축 알고리즘에 대한 제가 올린 설명이 있습니다...그것과 비교해
시면
(RLE 보완형 과 흡사) 더욱 좋을것 같습니다.
본 블로그는 페이스북 댓글을 지원합니다.
