|
● 시작하기 전에... linux-2.0.30.tar 25108480 이 글은 간단히 PC통신상에 올린 글이었다. 그래서 위의 예는 오래된 커널인 2.0.30을 썼었다.. 지금은 2.2.4버전이 나와 있다. 97년 당시만해도 bzip은 별로 쓰이지 않았다. 그러나 요즘은 기계의 발달로 bzip은 점차 각광받고 있으며 커널의 zImage 말고 bzip으로 된 bzImage도 쓰이고 있다. bzip은 요즘은 쓰이지 않고, bzip2를 쓰고 있다. 알고리즘상의 차이는 없으나 bzip은 최종적으로 산술코딩을 쓰고 있고, bzip2는 허프만 코드를 쓰고 있다. 두 방식 중에서는 산술코딩이 좀 더 효과가 있으나 느리다. 또한 산술코딩은 특허 문제로 사용하지 않는 것으로 알고 있다. 압축률은 bzip이 bzip2보다 조금 좋다.
● 시작하며... 지금 가장 대중적으로 쓰이는 비손실(Lossless) 압축 방식은 DBC방식이다. 우리 말로는 사전식 방식이라고도 불린다. 가장 큰 특징은 높은 압축률에 불구하고 빠른 속도를 가지고 있다는 것이다. 처음에 나온 사전식 방식은 트리를 찾아가는 방식으로 사전을 구축했지만, 요즘은 해시(hash)방식을 사용한다. hash방식을 쓸 경우 거의 선형알고리즘이다. 사전식 방식이란 한번 나온 단어(word)가 또 한번 나왔을때 사전에 있는 인덱스를 대신 저장하는 형태이다. 사전구축방식과 같은 단어를 찾아내는 방법이 기술이다. 이 방식은 현존하는 비손실 압축의 대부분을 차지하고 있고, 수많은 특허가 걸려 있다. 그러나 이 방식이 가장 높은 압축률을 나타내는 것이 아니다. 여기에 대항하는 한 알고리즘이 있으니, 그것이 바로 bzip(bzip2)이다.
● Bzip의 개요 Bzip은 Gzip의 이름을 모방적으로 지은 것 같다. Bzip에서 쓰고 있는 방식은 Block-Sorting 알고리즘이다. 일반적으로 이 방식은 Gzip보다는 높은 압축률을 나타낸다. 특히 일부분에서는 상당한 압축률을 나타낸다. 그런데 이 방식이 널리 쓰이지 않는 이유는 속도가 상당히 느리다는 것이다. 이것은 인코딩과 디코딩 두 곳에서 모두 나타난다. Gzip의 경우는 Time complexity가 대체적으로 O(n)이다. 그러나 Bzip의 경우에는 최악의 상황(Worst case)에서는 O(n^2 * log(n))이 나온다. 물론 이런 경우는 거의 없다. 이제 Bzip의 세계로 들어가 보자.
● Bzip 알고리즘 Bzip의 기본 알고리즘은 압축이 아니다. 이게 무슨 소리인가 하는 사람도 있을 것이다. Bzip에서 쓰는 Block-sorting 알고리즘은 변환(Transform)이다. 즉 스스로는 압축을 하지 못한다는 것이다. 단순히 블럭을 다른 형태로 변환시키는 것이다. 그러면 그 변환된 블럭을 기본적인 압축방식으로 압축한다. 여기서 기본적이라는 것은 Gzip과 같은 좀 발전(?)된 방식이 아니라 허프만 코드 또는 산술 코딩방식으로 압축한다는 것이다. < 초기 블럭 > --> <블럭 소팅 변환 > --> <큐를 이용한 변환> --> <압축> 물론 디코딩은 위의 역순이다. (군대식 같군요... ^^) 초기 블럭에서 블럭 소팅 변환을 하게 되면 크기는
그대로가 된다. 아니다. 좀 늘어나게 된다. 왜냐하면 역변환을 하면
제대로된 블럭이 나오지 않는다. 블럭이 로테이트된 상태로 나타난다.
그것을 보정하기 위한 정수형 헤더가 필요하다. 이것에 대한 것은
밑에 내용을 보면 이해할 수 있을 것이다. ※ 주의 : 밑에서 설명하는 것 중 좌로 옮긴다든지 우로 옮긴다는 것은 rotate를 뜻하는 것이다. 예) 1234를 좌로 옮김
=> 2341 그러면 Block-Sorting에대해서 자세히 알아보자. 예시 문장) This is his dog. 위의 문장을 한번 보자. 이 문장을 Block-sorting 알고리즘으로 변환을 해보자. 왜 이런 유치한 문장을 쓰는지는 필자도 모른다. 하나의 이유를 들자면 ‘is’가 여러번 나온다는 것 이다. This is his dog. This is his dog. 이라는 문장을 위와 같이 벌려놓는다. 벌려 놓는 방법은 문장을 한칸씩 좌로 옮기는 것이다. 자 그 다음은 가장 로드가 많이 걸리는 것이다. 위의 문장을 소트한다. (--;;) 편의상 A-Z, a-z, ‘ ‘, ‘.’의 순서라고 가정하자... (^^) This
is his dog. 위의 결과는 소팅한 결과이다. 머리로 할려니 상당히 골치 아펐다. 그러자고 프로그램 짜기는 그렇고... 이제 이 결과를 분석해보자. Lossless 압축(변환)임을 여기서 증명하고자 한다. 각 문장의 끝 문자만을 취해보자. 답(변환한 결과) => ._o_Th_hdiiisssg 이 문장만 있으면 “This is his dog.”이란 문장을 재생할 수 있다. 물론 “is his dog.This”라는 문장이 나올수도 있지만, 좌우로 옮기면 원래 문장이 재생된다. ※ 여기서 짚고 넘어갈 것이 있다. 변환된 결과의 각각의 문자의 갯수는 변환되기 전의 문자의 갯수와 같다는 것이다. 이것을 이해해야만 다음으로 넘어갈 수 있다. 의심이 나면 직접 세어 보기 바란다. 변환되기 전의 문장에서는 ‘i’의 수는 3개이다. 변환된 후에도 3개이다. 재생방법을 알아보자. 물론 “This is his dog.”이란 문장은 이제 모르는 것이다. 단지 알고 있는 것은 “변환된 결과”인 “._o_Th_hdiiisssg” 이다. <표 1>에 내용을 빌리면 아래와 같다. ‘-’부분은 현재 모르는 것이다. --------. 위의 표와 같이 나온다는 것은 앞에서
한 변환을 봤을때 쉽게 나온다. 우리는 소팅한 스트링들의 끝부분만을
취했었다. 그러므로 위의 표는 <표 1>에서 각 줄의 끝자만
남기고 지운 결과 이며 “변환된 결과”를 이용해 쉽게 만들 수
있다. 이것은 무엇을 의미하는가? 위의 표에서 앞부분을 모두 채울 수 있다는 것을 의미한다. 위의 <표 2>의 문장들은 정렬된 문장들이다. 왜냐하면 정렬한 다음 끝자만을 취했기 때문이다. 각 문자의 갯수를 알고 정렬이 되어 있으므로 ... T-------. <표 3> 앞부분은 정렬된 순서가 된다. 즉 <표 3>과 같은 결과를 얻을 수 있다. 이 문자열들을 우로 한칸씩 옮기면, .T------- <표 4> 이 부분이 어려운 부분이다. 차근차근 생각해 보길 바란다. ‘_’을 보자. ‘_’은 문자열에 3개가 있다. 위에서 보면 (1) (2) (3)이 _으로 시작된다. (1) (2) (3)을 놓고 보면 정렬이 되어있으며 이것은 항상 그렇다는 것을 알 수있다. (밑에서 더 생객해 보자.) 왜냐하면 2번재 칼럼이 정렬되어 있기 때문이다. (1) (2) (3)을 각각 (a) (b) (c)에 대응시킨다. 그럼 이제 역변환을 해보자. 첫 라인을 이용해서 .T------가 나온다. 두번째 칼럼의 T는 밑에있는 Th------에 대응된다.
그러므로 .Th-----라고 결정할 수 있다. 이제 h다음을 결정해야 한다. 우리는 (ㄱ)을 보고 T다음에 h가 나온다는 것을 알았다. 그 다음은 h이후에 무엇이 나오냐 이다. (ㄱ)의 h는 같은 칼럼에서 두번째로 위치하고 있다. 이 블럭은 정렬되어 있는 상태이므로 (A) (B)에서 (B)를 택하게 된다. 잘 생각해 보면 (A) (B)의 h도 (2)와 (ㄱ)의 순서대로 정렬되게 된다. 좀 더 이해를 돕기 위해 예제를 보면 * his
dog.... => is dog..... 즉 앞의 문자가 같기 때문에 그것을 빼도 결과는 같다.(이 부분이 핵심이다.) 그러므로 (2)와 (ㄱ)에서 앞의 한글자를 뺀 결과가 (A),(B)가 된다. (헷갈리지 말자, 소트의 기준은 2번째 칼럼 부터이다, 1번째 칼럼은 우로 옮겨서 앞으로 나오게 된 것일 뿐이다.) 그러므로 h 다음에는 i가 나온다고 할 수 있다. 이런식으로 해나가면 This is his dog으로 된다. 이때 Th가 처음 시작이라는 값을 추가로 주면 This is his dog. 이라는 문장이 재생된다. 결국 Lossless변환임을 증명하는 동시에 역변환을 살펴보았다.
● 이제 압축을 해보자 ._o_Th_hdiiisssg 위의 형태로 변환이 되었다. 같은 문자가 자주 반복됨을 알 수 있다. 이것을 이용할 수 있다. 이 변환의 특징은 같은 문자가 반복 또는 한번 나온 근처에서 나올 확률이 매우 크다는 것이다. 그러므로 다음과 같은 일종의 큐(진짜 큐는 아니다.)를 만든다. 초기치는 아스키코드가 순서대로 들어가 있다. [A][B][C]....[a][b][c]....[.][_]와 같이 들어가 있다고 하자. 처음에는 ‘.’을 인코딩하자. ‘.’은 0부터
시작한다고 하면 큐의 52번째에 있다. 그러므로 값은 52이다. [.][A][B][C]...[a][b][c]....[_] 다음은 _이고 그다음은 o이다. 다음에 _이 나오면
값이 1이된다. 이것은 허프만 코딩이나 산술코딩을 이용하면 된다. 즉 숫자가 낮을수록 짧은 비트수를 배정하고 높은 숫자는 긴 비트수를 할당한다. 그러면 압축이 된다. 만약 BAAAACCCCDDDD가 있다고 해보자. 처음 B는 1이 되고 다음 A는 1이다. 그 다음
A들은 0이고, C는 2가 된다. 문자
현재 큐 상태 값 이 결과를 값을 허프만(bzip2)이나 산술코딩(bzip)으로 인코딩한 다음 저장한다.
● Bzip... Bzip의 압축 과정을 살펴보자.(bzip2도 비슷할 것이다.) 1. 블럭을 읽어서 문자열을 만든다. (블럭에 대한 포인터가 문자열이 된다. <- 당연하다. 왜냐하면 일일이 모든 문자를 만든다면 메모리는 부족할 것이다. 블럭크기가 100k라고 가정하고 계산해 보라) ① (a) Spotblock
(블럭 군데군데마다 값을 변형시킨다. 이것은 혹시 모를
엄청난
■ Techniques in bzip(자세한 것은 bzip 소스를 보길 바란다.) SpotBlock : 블럭의 중간중간 값을 변형시킨다. 그래야 혹시 모를 프로그램이 죽은 상태와 비슷한 상황을 벗어나기 위해서이다. 한가지 예를 들면 A로만 된 파일을 생각해 보자. 이 파일에 Block-Sorting알고리즘을 적용하면, AAAAAAAAAAAAAAAAAA......A 즉 각 줄별로 서로 우위가 결정되지 않는다. 그러나 컴퓨터는 바보이므로, 우열이 가질때 까지 비교한다. 즉 한 라인을 비교하는데 블럭을 처음부터 끝까지 검색한다. 여기에 Quick sort알고리즘이 대체로 n*log(n)번을 비교하므로, n*n*log(n)이 된다. 블럭이 100k만 되도100k*100k*log(100k)=10000m*5=50 billion=약 500억의 이론적인 비교횟수가 나온다. 그러나 이와 같을 경우 quick-sort가 worst case에서 동작할 수 있으므로 더욱 최악의 상황이 된다. Quicksort with shell sort : Radix-sort before quicksort : AB..... 즉 AB로 시작하는 것을 묶고, BC로 시작하는 것을 묶어 놓는다. 그런 다음 AB로 묶인 것들끼리, BC로 묶인 것들끼리 각각 quick-sort를 한다. Modify block after Radix-sort 이런식으로 AB로 묶인 블럭이 있으면, 이것을
일단 소트한다. 그런다음 AB다음의 문자 2개를 0부터 65535까지
써넣는다. 65535를 넘어서면 65535를 써넣는다. 그러면 다른
XX로 묶인 블럭을 소트할 때 비교 비용이 적게 든다. Small first, Large Last! : Array Alignment! : 변형된 산술코딩 산술코딩에 [OFF],[ON],1,2,3,4,...255의 순으로
가중치를 둔다. [OFF][1][2].....
=> 0 1 2 ...
● 마치기전 사과의 말씀 시작하기전에서 보여준 압축 결과는 호기심(?) 유발을 위해서 본인이 의도적으로 넣은 것이다. 물론 bzip을 써보신 분들은 느끼겠지만... 압축률은 좋아도 압축하는데 드는 시간은 gzip에 비하면 장난이 아니다. 걸린 시간을 같이 써야 되나, 흥미 유발을 위해 일부러 쓰지 않았음을 양해하기 바란다.
● 마치며.... 수박 겉핥기 식으로 한번 살펴보았다. 물론 저의 작문 실력 부족으로 이해가 완벽히 되지는 않았을 테지만, 그냥 최근(?)에 나온 알고리즘을 단순히 이해한다는 차원으로 보았으면 한다. 물론 여기서 밝힌 것으로 bzip을 구성할 수 있다. 그러나 군데 군데 압축률을 높이기 위한 테크닉이 있다. 특히 위에서 문장들을 정렬하는 것에 대한 테크닉이 중요하다.. bzip에서 블럭 크기는 최대 900k까지 지정할 수 있다. 한번 900k의 길이의 문자열을 정렬한다고 해보자. 아마 엄청난 시간이 걸릴 것이다. 제 아무리 빠른 Quick-Sort를 써도 n*log(n)알고리즘이다. 거기다 문자열의 길이가 곱해진다. 이것을 좀 더 빠르게 하는 법도 있다. 그 방법은 Bzip소스에 있다. 그럼 Bzip으로 더 많은 공간을 확보하기 바라며.... Copyleft (c) 1997-1999 by 정우재 |