|
|
 |
|||
| Home |
|
|||
|
|||||||||
|
|
|
||
< RLE (Run Length Encoding) 방식 >
가장 쉽지만 모든것이 그렇듯 가장 압출률이 저조한 방법입니다.
화일을 16 진수로 나타낸 코드를 읽어서 다음과 같은 예가 있다면
<데이터>
위의 자료는 16byte의 자료입니다.00 00 1C 1C 1C F3 F3 F3 F3 F3 D8 11 11 11 11 11 RLE 방식으로 압축을 하면 다음과 같이 나타낼수 있습니다.
<RLE 압축>
대상코드와 그 코드의 갯수를 나란히 적은 것임을 알수 있습니다.00 02 1C 03 F3 05 D8 01 11 05 이방법은 일반적으로 독립적으로 쓰이기보다는 여러가지 기법과 혼용되어 쓰이는 방법입니다. 또한 연속된 자료가 자주 나타나는 그림화일등에서 압축률을 높일수 있습니다. 다른 일반 자료는 오히려 압축한것이 더큰 역효과를 가져옵니다. 이유는 자료코드 하나와 갯수코드 하나씩해서 최악의 경우는(연속된자료가 전혀없는경우) 꼭 원본보다 두배의 자료가 되기 때문이죠.
< RLE 보완형 >
RLE의 단점은 연속되지 않은 자료의 압축시에 오히려 그 압축화일의 용량
이 더욱 커진다는 것이었습니다. 그러나 일부 그림자료등을 제외하면 대부분의 자료들은 같은 코드의 반복은 그리 눈에 띄지 않습니다... 여기서 보일 방법은 RLE의 갯수를 세는 부분을 달리 하는 것입니다. 기존에 01 02 03 ...처럼 숫자를 썼던 것 대신 C0 C1 C2 ...등으로 바꾸어 쓰는 것입니다. 이 방법은 글쎄요. RLE 방법과 그다지 별차이가 없어 보이지만 코딩시에 새로운 규칙을 첨가함으로써 변화를 도모합니다. 그 규칙이라 함은 갯수를 설정하면 코드의 갯수가 바뀌지 않는이상 다시 설정하지 않는다는 것입니다. (이해가 가실까.....그렇다면 예제를..)
<데이터>
위와 같은 16byte 데이터의 RLE 보완형으로 압축하면 다음과 같습니다.F9 03 5D E3 21 00 EE 45 33 76 DE 3D 2F F4 5C B2
<RLE 보완압축>
17byte 로 원본보다 1byte나 손해를 보았습니다. 그러나 RLE 보다는C0 F9 03 5D E3 21 00 EE 45 33 76 DE 3D 2F F4 5C B2 훨씬 좋은 방법임을 알수 있습니다. 위의 예는 전혀 연속되는 자료가 없었다는 겁니다. 그러나 다음의 예와 같이 연속되는 자료가 존재하면 이야기는 달라집니다.
<데이터>
자 1byte의 압축 효과를 가져왔습니다.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 하지만 혹자는 여기서 이런 의문을 갖을수도 있겠습니다. 만일 데이터상에 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개인것으로 해석된다는 맹점입니다. 따라서 이런경우를 위한 한가지의 규칙이 더 필요하게 됩니다.
기존의 RLE 방법으로 압축한다. 갯수를 적을때는 역
C0...CF 코드를 이용
한다.
이해를 돕기위한 예제는 다음과 같습니다.<데이터> 34 DE C3 C3 C3 F4 F4 F4 DE C0 36 8D B1 A0 00 01 시 RLE로 압축하고( 갯수 + 코드 쌍형태) 다시 RLE 보완형을 시작하는 것입니다 즉, 앞에 압축한것과 별도의 압축을 한다고 생각하고 다시 C# 형태의 갯수를 쓰 는것부터 하는거죠....압축된것을 보면 다음과 같습니다.(~~ 친부분 주의할곳)
C0 34 DE C2 C3 C2 F4 C0 DE C0 C0 C0 36 8D B1 A0 00 01
처음부터 차근차근 살펴보겠습니다.
~~ ~~
뒤에나오는 C3 C2 F4 까지 모두 3개씩이 아닌가 하는 해석의 오류를 나을수 있 다는 것입니다. 그러나 압축에서 규칙을 정한것처럼 C0...CF 자료가 둘이상 존재 됩니다...따라서 압축을 풀때에도 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 방식은 가장 기초적인 방식으로 다른 압축 기법을 공부하는데에 기본이 된다구나 할까요....
이 압축 방법은 현재 많이 쓰이는 사무기기인 팩시밀리에서 사용하는 압축 방식입
0%?)니다. 압축률또한 위에서 언급된 RLE 계열의 방식보다 좋으며 RLE방식을 제외한 기타다른 압축방식보다 구현하기가 쉬워서 맣이 사용되고 있습니다. 간단히 설명하자면 이전까지 사용하던 16진 코드를 2진코드로 바꾸어 압축하는 방식입니다. 다른 말로 비트맵이라는 표현을 쓰기도 합니다. 마우스의 커서등을 구현할때 모눈종이에 그리던것 생각하시면 빠르겠네요.. 자 우선 아래와 같은 32byte의 데이터를 읽어들입니다.
<데이터>
위의 데이터를 RLE 보완압축 방식으로 압축하면 다음과 같겠죠 (쩝 압축률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 보완압축>
비교를 위해서 RLE 방법을 쓰면 다음과 같습니다. (흐...팽창률 170%?)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 압축>
비교상으로도 RLE 보완형이 월등히 좋다는 것을 알수 있습니다....그럼 FAX 압축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
을 위해서 우선 비트맵으로 구성해보도록 하겠습니다.
위의 데이터를 16 by 16 비트맵으로 나타내면 다음과 같습니다.(정사각형모양)
<비트맵> | <16진>
0000 0000 0000 0000 | 00 00
|
0000 1111 1111 0000 | 0F F0
먼저 일단계로 위의 비트맵에서 0이 많아지는 방향으로 데이터를 규칙있게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에서 1로 변화되는 부분과 0 에서 1로 변화되는 부분에서마 1을 쓰는 방법이 있습니다. 변형되 형태는 다음과 같은 모습이 될것입니다.
<변형된 비트맵>
0000 0000 0000 0000
0000 1000 0000 1000
위의 데이터는 예시를 위해 조작된 것이기 때문에 확실이 0숫자가 많이 포함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 되어있습니다. 그러나 일반적인 데이터는 이보다는 좋지 않은 결과가 나올경우가 더 많다는 것을 알아두셔야 합니다. 또한 FAX 압축을 풀기위한 규칙으로 가장 첫 비트가 1이면 그자리는 1로 표시해야합니다. 그렇지 않으면 나중에 압축 을 풀어나갈때 곤란한 경우가 생기게 됩니다. 우선을 그렇게 알아두시면 됩니다. 여기까지 끝이 나면 다음 단계로 넘어갑니다. 이번에는 데이터를 회전시킵니다. 프로그램상으로 구현할때에는 위에서 아래로 데이터를 읽어서 왼쪽에서 오른쪽 으로 써나가면 됩니다.(이유는 0을 많이 만들기 위함입니다) 재변형된 데이터의 형태는 아래와 같습니다.
재변형 비트맵 | 16진 | 헤더비트
---------------------------------------------
0000 0000 | 0000 0000 | 00 00 | 00
7C | 01 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
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 압축>
처음에 주어진 32 byte 데이터가 13 byte로 압축되었습니다. (압축률 약60%)03 C1 10 F0 38 7C 44 FE 7C 44 FE 38 7C ~~~~~~~~~~~
헤더비트
사실 위의 예제는 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 헤더비트의 예>
였던 헤더비트가 16 bit를 기준으로 하면00 00 00 11 11 00 00 01 00 01 00 00 11 11 00 00 : 03 C1 10 F0 <16bit 헤더비트로의 변형>
0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 : 19 4C
압축률이 다소 낮아지더라도 충분한 보상을 갖어오게 된다는 것입니다.
<Lempel-Zip 방식>
이 방식은 누구나 한번쯤은 생각했보았을만한 방법이면서 근래 많이 이용되는
시면압축프로그램의 원형이라고 말할수 있는 방식입니다. 크랙용 프로그램인 크랙잭을 보면 크랙을 위한 사전을 가지고 있는것을 볼수 있죠. 이와 비슷한 방식으로 같다고 볼수는 없지만 그런 접근으로 압축을 하는 것이 이방법의 개요입니다. 압축방법이라기 보다는 암호책을 대조하는 식으로 생각하면 이해가 빠를까요? 최고의 효율을 가지고 있는 방식으로 현재 압축효율이 좋은 압축 프로그램들은 모두 이 방식을 사용하거나 그 변형을 이용합니다. 이 방식의 실현은 상당히 어렵지 만 간단하게 생각하면 사전과 같이 자주 사용되는 것을 일종의 테이블로 만들어 압축하는 것입니다. 코드 필드와 서픽스로 나뉘어서 구성되는 테이블의 내용은 다중 패스를 거쳐야 하는 복잡한 알고리즘을 가지고 있지만 여기서 간단히 개념만을 파악한다면 다음과 같이 볼수 있습니다.
INDEX ENCODE 사전
.. │ ..... │
┌─────┐
... │ ..... │
RAW DATA ├─────┤... │ .... │
├─────┤
478 │ IS │
... │ .... │
"THIS IS HOT -> ├─────┤-> INDEX OUTPUT
STUFF" 759 │ HOT │ 1295 478 759 3751
INDEX ENCODE 사전이라는 것은 압축 프로그램이 규칙에의해 보유하고 있는
├─────┤ (12954787593751)
... │ ... │
├─────┤
1295 │ THIS │
├─────┤
.... │ .... │
├─────┤
3751 │ STUFF │
├─────┤
.... │ .... │
└─────┘
일종의 사전이라고 보시면 됩니다. 각각에 번호나 약속된 기호들로 구성되어 그 인덱스 하나가 하나의 단어내지는 기호를 나타내게 되는 것입니다. 압축을 하기위해서는 해당하는 INDEX를 알아야만 가능하겠죠... 일일이 이런 사전을 개인이 구축한다는 것은 그리 쉬운 일은 아닐것입니다. 많은 노력과 시간이 들겠죠.. 파싱이라는 기법을 이용해서 인덱스를 자체 생산하는 방법 이 있긴 합니다. 간단한 텍스트 압축기는 충분히 만들수 있을것이라고 생각이 듭니다. ------------------------------------------------------------------------ 마감의 글 이밖에도 가장 뛰어나다고 여겨지는 허프만 방식이라는 것이 있는데.... 이것도 lempel-zip 과 유사한 점도 있구...다만 허프만 부호라는 것을 알아야 합니다....마치 방금 말씀드리 사전과 같죠... 이 글로 인해서 압축 알고리즘이나 압축기 제작에 관심이 생기신분이 한분이 라도 생기셨다면 저로서는 만족스럽습니다. 기타 너무나 난해하고 테크닉적인 부분이나 심도 깊은 부분에 대해서는 저역시 배우는 입장에서 쓴다는것은 주제넘은 짓이 아닌가 생각이 들구요....관련 서적을 찾아보시길 바랍니다. 이로써 압축 알고리즘에 대한 미진하나마 저의 글을 마칠까 합니다. 또한 한가지.....강좌/정보란에 lt 알고리즘 으로 찾아보시면 PCX 화일데이터 의 압축 알고리즘에 대한 제가 올린 설명이 있습니다...그것과 비교해 (RLE 보완형 과 흡사) 더욱 좋을것 같습니다.
시지프스(Cezips) 야이야아
Magicall : WOODPARK Hitel : WOODPARK ２○●２ Ｗorld Ｃup Ｋorea.. ??????????????????????????????????????
?번 호 92 / 244 ?등록일 96년 11월 02일 11:37 Page : 1 / 10
───────────────────────────────────────?등록자 ?ZSCHAES1 ?이 름 ?조 회 409 건 ?제 목 ?강좌 압축 알고리즘 (2) ?????????????????????????????????????? 안녕하세요.. 우드팍이랍니다. W/o/o/d/P/a/r/k - 김/영/식... ??????????????????????????????????????
Nownuri ───────────────────────────────────
허프만 압축 알고리즘에 대해서...SCOM 시지프스 (C/C++ 프로그래밍)-강좌/정보 (#283/283) 1/13 ─────────────────────────────────────── 제 목 : ?강좌 lzh, lzw의 압축 알고리즘... 올린이 : softbe (신종호 ) 96/05/20 02:27 읽음 : 1 관련자료 없음 ------------------------------------------------------------------------------
우선 알아야 할것이 있다. 기타여러가지 기본적인 알고리즘에 대한선 자료
실에서 야이야아님의 강좌를 보기 바라고 여기선 LZW, LZH에 대해서 부터 시작한다.
1. LZH(Squeezing)
이것은 허프만코드라고하고 가장 기본적인 압축알고리즘이다. 이진트리(Bin ary Tree)를 이용하연 단순히 자료를 읽어서 이진 트리로 구성하고 그것을 바탕으로 데이타의 빈도수에 의해서 BIT를 할당해서 압축을 하는것이다.
예를들어 설명해보면
A B B C D D D 라는 문자 열이 있다고 해보자. 여기서 문자와 빈도수를 따져보면 아래와 같다. ┌───┬─────┐ │문자 │ 빈도수 │ ├───┼─────┤ │A │ 1 │ │B │ 2 │ │C │ 1 │ │D │ 3 │ └───┴─────┘ 여기서 많이 나오는 문자에 적은 수의 BIT를 줌으로서 압축을 이룰수있다. BIT를 준다는 의미는 어떤것인가 하면 이것은 앞서 이야기한 이진트리에 관 련되어있는 문제 이다. 이번 기회에 이진트리구성방법을 손으로 하는 것을 배워두는것도 좋을 것이 다. 벼롤 어렵지않다. 이미 많이 알려져있는 방법이니까... 위에서 나온것을 빈도수에의해서 다시 구성해보면 문자 빈도수 D 3 B 2 C 1 A 1
마지막에 두개의 빈도수를 더해서 빈도수별로 나열하면
문자 빈도수 D 3 B 2 A+C 2
또다시 마지막에 빈도수 두개를 더해서 빈도수 대로 나열하면
문자 빈도수
B+(A+C) 4 D 3
즉 2개가 남을 때가지 이렇게 적은 수의 빈도수가 나온것을 더해서 정렬을
해서 마지막에 두개가 남는다면 이제 이진 트리가 모두 구성이 된것이다.
root
┌──┴────┐
│
┌─┴─┐ │
이제 구성된 2진 트리에 앞서 이야기한 BIT를 할당해보자 왼쪽으로 뻗어나│ │ │ │ ┌┴┐ │ │ │ │ │
B A C D
간 가지는 0이고 오른쪽으로 간가면 1로 해보자.
B == 00 // 왼쪽 가지로 2번꺽였다.
A == 010 // 왼쪽, 오른쪽, 왼쪽 C == 011 // 왼쪽, 오른쪽, 오른쪽 D == 1 // 오른쪽한번
초기에 가진 문자열이
A B B C D D D 원래 이것의 실제 표현은 아스키 값으로 01100101 01100110 01100110 01100111 01101000 01101000 01101000 이며 총 BIT수는 8*7=56BIT다. 위에서 구성한 압축 코드로 바꿔보면
A B B C D D D
010 00 00 011 1 1 1 이며 총 BIT수는 3+2+2+3+1+1+1=13BIT이다.
압축률은 76.78%의 엄청난 압축 효율을 가진다.
물론 여기에 이진 트리의 정보를 더하고 그러면 압축률은 한참 떨어져 한 2 0%의 압축률을 보일것이다. 어째든 엄청난 압축효율을 보이는것이 사실이다.
그러나 문제점은 있다. 그것은 이방법은 좋은 방법이기는 하지만 자료를 모
두읽어서 이진트리화하고 처리를 해야 한다. 속도가 매우 떨어질것이 틀림 없는 방법이다. 사람이란 부단히 노력한다. 그래서 나온 방법이 있다.
2. LZW(Crunching)
이것은 미리 정의되어있는 문자열표를 이용하는 방법이다. 통상 4096개의 테이블을 가지고 작업을 하게 된다. J.Ziv와 A. Lempel두사람이 만들었고 Terry A. Welch사람이 실용화의 길을 만들었다고 모두 합쳐서 LZW이라고 부 른다든데..그건 중요한게 아니다.
여기서 생각해볼 문제는 왜 4096의 테이블인가. 왜?????
앞서 설명한 LZH의 방법에서 우린 1Byte를가지고 작업을 했지만 2byte을 가 지고 작업을 한다면 좀더 낳은 성능의 압축 효율을 보이지 않을까? 바로 그렇다. LZW에서 2Byte를 연속적으로 읽어서 처리한다. 0~511 : 9bit 512~1023 : 10bit 1024~2047 : 11bit 2048~4095 : 12bit 로 할당한다. 여기서 BIT의 할당이란 실제 값이 아니라 어드레스값을 말한 다. 4096의을 어드레스 값으로따지면 12BIT면 충분하기 때문이다(계산해보 라. 2^12의 문제다) 이것을 압출할 파일을 읽으면서 동시에 트리로서 구성해서 트리에 추가하면 서 사용할수있다. 이렇게 읽어들이다가 4096개의 테이블이 가득차면 처음부 터 다시 테이블을 구성해서 나간다. 압축을 풀때는 반대로 압축된 것을 읽 어서 테이블을 구성함으로서 간단히 해결할수있다.
예를 들어서 설명하는게 좋을듯싶다.
ABBCABDDDD
를 압축해보자.
먼저 맨처음 두개의 문자를 읽어온다. 'AB'이것을 아직 테이블에 존재하지
않는다. 그렇다면 테이블에 기록을 하는데 257번테이블에 기록을 한다. 257 번 테이블이 돼는 이유는 간단하다. 0~255까진 기본 아스키 코드로 돼어 있 기때문이다. 256은 분기점 용도로 사용을 한다. 그러니 쓸수있는 테이블의 상태는 257번부터 4095번까지 이다.
실제로 기록하는 방법은 A의 주소(***주소라고 표현했지만 실제 주소라기
보다는 원래 아스키 값과 동일하다 왜냐하면 테이블의 0~255까지 순서대로 의 값이기때문이다***)를 기록하고 그다음엔 B는 실제 값으로 구성 된다. 그것을 구조체로 만들어보면(이것은 단순한 예의 구조체다. 실제론 이렇게 선언하지 않을것이다) struct lzw {
char *First; // 2byte near pointer
}char Second; // 1byte char 의 형태라고 할수있다. 기록만 하는것이 아니라 즉각적으로 출력 화일에 출력을 시도(그래서 빠르 다는 것이다 LZH보다)하는데 우선 'AB'의 자료가 테이블에 존재하지 않으니 아스키'A'와 'B'의 어드레스(0~255번 테이블)를출력하게 된다. 출력할어드 레스의 크기는 앞서도 이야기한대로 9bit이다.
그다음을 읽는다. "BC"이것도 테이블에 없다. 앞서와 마찬가지로 테이블에
추가를 한다. 이번에 258번에 추가된다. 그것을 마찬가지로 출력을 한다.
세번째 읽었을때 값은 "AB"가 된다. 이것은 이미 테이블에 등록이 되어 있
는것이다. 그러니 그 테이블의 주소값을 그냥 써넣으면 된다. 여기서 많은 이익을 볼수있고 이것 바로 압축돼는 키포인트다. 지금 써넣을 'AB'값은 9bit로 16-9하면 7bit의 이득을 얻는것이다.
압축부분의 이득을 따져보면
원래값 ABBCABDDDD 의 실제 크기는 8*10=80Bit이다.
압축값
A B B C AB D D DD 9+9+9+9+9 +9+9+9 =72bit이다.
여기서 알수있는건 연속되어 두개의 문자가 나와야 압축이 시도가 된다는
것이다. 연속된 문자열이 존재하지 않는경우 압축줄은 팽창률로 바뀔것이다 물론 이런 팽창률이 일어나지 않도록 조취를 취해서 최악의 압축률은 100% 를 안넘도록 하고 있다.
이런것을 벋어나는 방법이 미리 자료를 Packing을 먼저 시도 한다. 패킹은
단순히 RLE의 방법을 사용하여 하기도 하도 개선된방법을 쓰기도한다. 그것 은 만드는 사람 마음 이겠지만.....여기서 설명한것은 원론적인것에 불과하 다. 0~256테이블을 8bit로 처리하면서 더욱 Bit처리 방법을 세부적으로 나눌 수도 있다. 그렇게 하는것은 당신의 마음이다.
3. 마치며
대표적인 방법의 압축 알고리즘의 설명이었다. 쉽게 한다고 한건데 잘되었 는지 몰르겠다. 아마도 이해가 잘안간다면 그건 모두 필자의 문제가 아니다 하하하하하하하하하.....
더 낳은 압축 알고리즘은 트라이구조와 깊이 제한을 가진 이진트리 또는bal
anced Tree를 사용하여 작성하는것이리라. 더욱 자세한것을 알고 싶다면 관 련 서적을 뒤적여 보라. lha를 만든분이 쓴책도 있다. 물론 소스도 들어있 다.
담천 신종호
??????????????????????????????????????Magicall : WOODPARK Hitel : WOODPARK ２○●２ Ｗorld Ｃup Ｋorea.. ??????????????????????????????????????
쓰기(W) 조회수검색(DS) 그림보기(SEE) 페이지이동(PG) 이전(B) 기타(Z)
선택 > |
|
|||
|
|
|
