2000년에 작성한 글입니다.
제가 압축 프로그램을 처음 봤을 때는 93년 여름이었습니다. 처음 압축 프로그램을 접했을 때 5.25“디스켓에 다 들어가지 않던 데이터나 프로그램이 압축되어 다 들어갈 때 정말로 신기했고 재미있어서 제 친구들한테 이야기도 많이 하고 돌아 다녔죠. 어느덧 시간이 흘러 MS-DOS에서 윈도우로 넘어가고 인터넷의 등장으로 압축이 아주 중요하게 되었죠. 그 느려터진 인터넷으로 자료를 주고받을 때 자료의 크기를 조금이라도 줄여서 이동시키는 것이 요금도 절약되고 신경에도 좋죠. 제가 압축에 대해서 공부를 하게 된 것은 리눅스 상에서 프로그램 공부를 하던 중 WINZIP과 같은 압축 프로그램이 없어서 불편을 느끼게 되었죠. 목마른 놈이 우물을 판다고 압축에 대해 공부도 하고 또한 WINZIP과 같은 프로그램을 만들고 싶었죠. 그래서 자료도 찾고 했지만 압축에 대한 서적은 거의 없더군요. 어렵사리 인터넷에서 구한 자료를 연필로 줄 그어가면 공부를 했습니다. 자 이제 제가 조금이라도 알고 있는 것을 풀어 놓고자 합니다.
압축이란 그리 어려운 방법은 아닙니다. 많이 쓰이고 있는 zip, arj, rar, gzip.. 등은 모두 같거나 비슷한 방식으로 압축을 수행합니다. 하지만 자기들 나름대로 수행 속도나 어떻게 하면 조금이라도 쥐어 짤 수 있을까를 고민한 끝에 약간의 변형과 변칙(?)을 수행하고 있습니다.
1. RUN-LENGTH
가장 간단한 방식이죠. 즉 연속으로 나타나는 문자를 연속되는 숫자 + 문자로 표현하는 방식이죠. 제가 알기로는 BMP나 PCX파일에서 이러한 방식을 했습니다. 하지만 그리 압축률이 높지 않아서 요즘은 거의 쓰이지 않습니다.
Example of run-length coding of digital image
Digital image_______________________________Run-length coding results
000011111000000000000000000................4w5b18w
000001111100000000000000000................5w5b17w
000000111110000000000000000................6w5b16w
000000011111000000000000000................7w5b15w
000000001111100000000000000................8w5b14w
000000000111110000000000000................9w5b13w
000000000011111000000000000................10w5b12w
000000000001111100000000000................11w5b11w
0을 흰색(white)라 하고 1을 검은색(black)이라 한 뒤 그들이 중복되는 숫자를 먼저 쓴 뒤에 해당 문자를 적어줍니다. 쉽죠...
2. HUFFMAN
이제 본격적으로 압축에 대해서 이야기 해봅시다.
허프만 코딩은 자주 나타나는 문자에는 작은 비트 열을 거의 출연하지 않는 문자열에는 큰 비트 열을 할당하여 압축을 달성하는 방식입니다.
생각해 보십시오. A가 1번, B가 5번,C가 3번, D가 10번 나타내고자 할 때 ASCII코드에서 한 문자 당 8비트를 할당하므로 위의 문자열을 표현하는데는 음.... 19바이트가 필요하죠. 하지만 자주 나타나는 D에 가령 4비트를 할당하고 그 다음 B에 6비트 C에는 10비트 A에는 12비트를 할당하면 총 필요한 바이트는 14바이트면 충분하죠. 즉 이런 방식으로 압축을 수행하는 것입니다. 위에서는 제가 임의대로 비트 수를 할당했지만 출현하는 문자가 모두 4개 즉 32바이트가 필요하죠. 밑에서도 비트 수를 임의대로 나누었지만 각 비트 수의 합이 위의 것과 같게 되어야 합니다. 한 번 생각해 보세요. 왜 그런지를
허프만 코딩에는 크게 정적 허프만과 동적 허프만 방식이 있습니다.
정적 허프만은 미리 압축하고자 하는 파일에서 출현하는 문자들의 빈도 수를 구합니다. 그리고 나서 위에서 우리가 했던 것처럼 자주 출현하는 것에는 작은 비트 수를 그 다음은 그다음 비트 수를... 쭉 쭉 나아가서 파일에서 출현하는 모든 문자에 대해서 비트 수를 할당합니다. 그럼 원래 파일보다 크기가 줄어 들겠죠. 이 것을 새로운 파일에 출력하면 압축 파일이 생성되는 겁니다.
위에서는 그냥 비트 열을 할당한다고 했는데 어떻게 비트 열을 할당하는 것이 좋은지 모두 머리 싸매고 생각해 봅시다. 압축의 효율은 이런데서 차이가 나는 것입니다. 기본적인 생각은 같지만 어떻게 알맞게 구성하는지에서 차이가 생기죠. 예를 들어가면서 생각해 봅시다.
Symbol
|
A
|
B
|
C
|
D
|
Codewords
|
0
|
1
|
10
|
11
|
이렇게 비트 열을 각 문자에 할당했다고 생각해 봅시다.
그럼 임의의 비트 열이 들어 왔을 때 유일하게 하나의 문자열로 나타낼 수 있을까요. 하나의 비트 열을 여러 개의 문자열로 나타낼 가능성이 있다면 그것은 의미가 없어집니다. 우리가 무슨 재주로 알맞은 문자열로 바꾸어 줄 수 있습니까?
그런데 이것은 0110이란 비트 열이 들어 왔을 때 ABBA , ADA , ABC로도 변환이 가능하므로 잘못된 할당이라고 할 수 있죠. 여러분은 어느 것이 맞다고 장담할 수 있나요.
그래서 다음과 같이 할당했다고 가정해 봅시다.
Symbol
|
A
|
B
|
C
|
D
|
Codewords
|
0
|
01
|
011
|
111
|
이것은 임의의 비트 열이 들어 왔을 때 유일하게 한 문자열로 변환이 가능합니다.
즉 임의의 001111101111란 문자열이 들어왔을 때 유일하게 ACDBD로만 변환이 가능합니다. 다른 변환이 되는지 찾아보세요.
하지만 이것도 문제가 있기는 마찬가지입니다. 001111101111란 비트 열이 다 들어오고서야 비로소 ACDBD로 변환이 가능하다는 것입니다. 비트 열이 들어오는 중에는 제대로 된 문자열로의 변환이 불가능하다는 이야기입니다.
이상에서 우리는 하나의 조건을 제시합니다. 각 문자에 할당된 비트 열은 자신의 비트 열로써 구별이 가능해야 한다는 겁니다. 다시 예를 들어봅시다.
Symbol
|
A
|
B
|
C
|
D
|
Codewords
|
0
|
10
|
110
|
111
|
이렇게 비트 열을 구성했다면 혼돈을 일으킬 염려가 없습니다.
그럼 대략적인 허프만 코드에 대해서 간략하게 알아봅시다.
1. 우선 압축하고자 하는 문자들을 빈도수가 높은 것부터 차례대로 세운다.
2. 두 개의 가장 낮은 문자를 합하여 하나의 새로운 문자를 구성한다. 그것의 빈도 수는 두 문자의 빈도수의 합이 된다.
3. 오직 하나의 문자가 남도록 2를 계속 수행한다. 이로써 얻어진 구조를 허프만 트리라고 하고 마지막까지 남은 문자를 트리의 루트라고 한다.
A 0.4
|
A 0.4
|
A 0.4
|
BCDE 0.6
|
root 1
|
B 0.2
|
B 0.2
|
CDE 0.4
|
A 0.4
|
|
C 0.2
|
C 0.2
|
B 0.2
|
||
D 0.1
|
DE 0.2
|
|||
E 0.1
|
Symbols
|
A
|
B
|
C
|
D
|
E
|
Codewords
|
1
|
01
|
000
|
0010
|
0011
|
2.2 동적 허프만 부호
앞에서 알아본 정적 허프만 부호는 입력 데이터를 조사하여 각 기호의 출현 빈도를 구한 후 허프만 트리를 작성하고, 입력 데이터를 처음부터 다시 읽어들여 각 기호를 부호화해 갈 필요가 있다. 이 때문에 허프만 부호는 입력 데이터 열을 2번 읽어야 하므로 온라인 데이터 압축에는 적당하지 않다.또 다른 하나의 문제점은 허프만 트리 또는 기호와 부호와의 대응표를 출력될 부호열 앞에 부가해야 하기 때문에 정보원 알파벳 수에 비례하는 정도의 오버헤드가 생긴다.
3. Lempel-Ziv(LZ77)
본격적인 압축 알고리즘에 있어서 허프만 트리와 LZ77과 그 변형들이 주를 이루고 있다. LZ77은 사전 방식(Dictionary methods)을 채택하고 있는데 이것은 RUN-LENGTH 방식과 유사하다. 즉 반복적으로 출현하는 코드(압축하고자하는 단위)들을 이용하는 것이다. 텍스트 파일에 있어서는 반복적으로 나타나는 문자들이 될 것이고 이미지 파일에 있어서는 픽셀이 될 것이다. 아래에서 설명하게 될 모든 사전식 방식은 두 그룹을 가지게 된다.
이 그룹의 모든 방법들은 1977년 Abraham Lempel and Jakob Ziv에 의해서 발표된 알고리즘에 근간을 둔다.
이러한 방법은 1978년 Lempel and Ziv에 의해 발표된 알고리즘에 근간을 두고 있다.
자 그럼 본격적으로 LZ77에 대해서 알아볼까요. 들어가기에 앞서 이 알고리즘에서 사용되는 단어들을 알아봅시다.
● Input stream : 압축할 character 들의 연속
● Character : 입력 데이터의 기본 데이터 요소
● Coding position : 입력 데이터에서 현재 부호화 되고 있는 character의 위치(the beginning of the lookahead buffer)
● lookahead buffer : 부호화되고 있는 위치에서 입력 데이터의 끝까지 character 열
윈도우 크기 W는 현재 부호화되고 있는 위치에서 뒤로 W만큼의 character들을 가지고 있다.
■부호와의 기본 원리
이 알고리즘은 윈도우와 lookahead buffer 처음에서부터 끝까지 가장 길게 일치하는 character를 찾는다. 그리고 일치하는 포인터를 출력한다. 하지만 하나도 일치하지 않을수도 있으므로 출력은 포인터만을 포함하지 않는다. LZ77은 이 문제를 다음의 방식으로 해결했다. 모든 포인터 뒤에 lookahead buffer에서 일치점의 바로 뒤의 문자를 출력하는 것이다. 그래서 만일 일치하는 것이 없다면 null-pointer와 부호화하고 있는 문자를 출력하는 것이다.
■ 부호화 알고리즘
① 부호화 위치를 입력 데이터의 시작점에 맞춘다.
② 윈도우와 lookahead buffer에서 가장 길게 일치하는 것을 찾는다.
③ (P,C)의 쌍을 출력한다. P와 C는 다음과 같은 의미를 갖는다.
P는 윈도우에서 일치하는 포인터, C는 lookahead buffer에서 일치하는 위치의 바로 다음의 문자.
④ 만일 lookahead buffer가 비어 있지 않다면 부호화 위치를 L+1(L = 일치하는 길이)만큼 뒤로 옮긴다. 그리고 2단계를 돌아간다.
■ 예제
부호화 순서는 Table 1.에 표시되어 있다.
●열의 단계는 부호화 단계를 나타내는 숫자이다. 이것은 부호화 알고리즘이 데이터를 출력할 때까지의 단계이고 LZ77에서 부호화 알고리즘의 3단계까지를 나타낸다.
●Pos는 부호화 위치를 나타낸다. 입력 데이터에서 맨 처음 문자는 부호화 위치 1을 가진다.
●Match는 윈도우에서 가장 길게 일치하는 것을 나타낸다.
●Char는 lookahead buffer에서 일치점 바로 뒤의 첫 글자를 나타낸다.
●Output은 (B,L) C와 같은 출력 포맷을 가진다.
●(B,L)은 일치하는 포인터이다. 이것은 복호화할 때 아래의 의미를 준다. “윈도우에서 B 문자만큼 뒤로 가서 L 문자만큼 출력하라”
●C는 하나의 문자이다.
부호화할 입력 데이터
Pos
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Char
|
A
|
A
|
B
|
C
|
B
|
B
|
A
|
B
|
C
|
Step
|
Pos
|
Match
|
Char
|
Output
|
1
|
1
|
--
|
A
|
(0,0) A
|
2
|
2
|
A
|
B
|
(1,1) B
|
3
|
4
|
--
|
C
|
(0,0) C
|
4
|
5
|
B
|
B
|
(2,1) B
|
5
|
7
|
AB
|
C
|
(5,2) C
|
이제껏 LZ77의 부호화 알고리즘과 간단한 예를 설명했습니다. 모두 이해를 하셨나요. 앞에서 설명했듯이 압축을 그리 어렵게 생각하실 필요가 없습니다. 우리가 일상에서 모두 생각할 수 있는 것들이니까요. 그럼 압축된 데이터를 원래대로 되돌리는 복호화 알고리즘에 대해서 알아봅시다.
■ 복호화
윈도우는 부호화할 때와 같이 동일하게 유지된다. 각 단계에서는 (P,C)의 쌍을 읽어 들인다. 그리고 P와 C에 의해서 지시되는 문자열을 출력한다. LZ77의 복호화는 부호화에 비해서 아주 쉽습니다.
LZ77의 압축율은 모든 데이터 형에 대해서 비교적 높은 수치는 나타낸다. 그러나 부호화에서 시간이 많이 걸린다. 그래서 윈도우와 lookahead buffer에 대한 많은 고찰들이 있다.
부호화에 비해서 복호화는 매우 간단하고 또한 빠르다.
4. LZSS
LZSS는 LZ77의 하나의 변형이라고 할 수 있다. 그래서 사용되는 용어도 비슷하고 해서 용어는 별도로 적지 않았다. 용어를 보려면 LZ77에서 찾아 보세요.
■LZ77과의 다른점
LZ77에서는 일치하는 문자가 없을 경우에 null-pointer뒤에 하나의 문자를 출력해 왔었다. 이러한 해결책은 불필요한 잉여물을 포함한다. 즉 부호어 중에 데이터가 압축되지 않는 기호를 항상 넣는 것은 확실히 군더더기이다. 그래서 LZ78에서는 1비트의 플래그를 사용해서 포인터를 나타내는 부호어와 기호를 나타내는 부호어를 구별한다.
그래서 출력 문자열은 포인터와 기호가 혼합된 형식을 갖는다.
The encoding algorithm
■부호화 알고리즘
●부호화 위치를 입력 데이터의 시작점에 맞춘다.
●윈도우에서 lookahead buffer와 가장 길게 일치하는 것을 찾는다.
●P는 일치하는 포인터
●L는 일치하는 길이
●L(일치하는 길이)이 MIN_LENGTH보다 큰가?
●YES : P를 출력하고 부호화 위치를 L만큼 앞으로 옮긴다.
●NO : lookahead buffer의 첫 기호를 출력하고 부호화 위치를 1만큼 앞으로 옮긴다.
●입력 데이터에 아직 기호가 남아 있다면 2단계로 간다.
■ 예제
부호화 순서는 Table 1에 나타나 있다.
●열의 단계는 부호화 단계를 나타낸다. 이것은 부호화 알고리즘이 결과를 출력할때까지의 단계이고 LZSS에서는 3단계까지 끝났음을 나타낸다.
●Pos는 부호화 위치를 나타낸다. 입력 데이터에서 가장 첫 기호는 부호화 위치 1를 가진다.
●Match는 윈도우에서 가장 길게 일치하는 것을 나타낸다.
●Output은 출력 결과를 나타낸다. Output은 다음 중 하나가 될 수 있다.
●(B,L)형식의 Match에 대한 포인터. 이것은 복호화할 때 “윈도우에서 B 기호만큼 앞으로 가서 L 기호만큼 출력하라”라고 나타낸다.
●하나의 기호를 나타낸다.
Pos
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Char
|
A
|
A
|
B
|
B
|
C
|
B
|
B
|
A
|
A
|
B
|
C
|
Step
|
Pos
|
Match
|
Output
|
1
|
1
|
--
|
A
|
2
|
2
|
A
|
A
|
3
|
3
|
--
|
B
|
4
|
4
|
B
|
B
|
5
|
5
|
--
|
C
|
6
|
6
|
BB
|
(3,2)
|
7
|
8
|
AAB
|
(7,3)
|
8
|
11
|
C
|
C
|
■ 복호화
윈도우는 복호화 알고리즘과 유사하게 유지 된다. 압축되어 있지 않다면 기호는 바로 출력되고, 압축되어 있다면 포인터가 나타내는 윈도우내의 기호열을 출력한다.
LZSS는 같은 과정, 메모리 요구에도 불구하고 LZ77에 비해 보다 나은 압축률을 보여주고 있다. 복호화는 아주 간단하고 빠르다.
대부분의 유명한 압축 관리 툴(PKZip, ARJ, LHArc, ZOO etc) 들이 이 알고리즘을 채택하고 있다. 물론 서두에서도 이야기했듯이 모든 압축 관리 도구들은 약간의 변형을 통해서 서로 조금씩 다르다. 이러한 변형들은 포인터의 길이, 윈도우의 크기, 윈도우가 움직이는 방법등이 있을 수 있다.
또 다른 압축 관리 도구들은 LZSS와 다른 방식을 혼합한 방식을 쓰고 있는데 ARJ는 허프만 방식을 혼합하고 있고 PKZip 1.x는 Shannon-Fano 방식(나중에 PKZip 역시 허프만 방식을 사용하고 있다.)을 사용하고 있다.
5. LZ78
LZ78에서 사용되는 용어를 아래에 나타내었다.
●Charstream : 부호화될 데이터의 열
●Character : charstream에서 기본 데이터 단위
●Prefix : 하나의 기호앞에 나타나는 기호열
●String : 하나의 기호를 포함하는 기호열
●Code word : codestream안의 기본 데이터 단위. 사전의 string을 표현한다.
●Codestream : code words와 기호열의 연속(부호화 알고리즘의 출력)
●Dictionary : string의 테이블. 모든 string은 사전내의 인덱스 숫자에 대응하는 code word에 할당된다.
●Current prefix : 부호화 알고리즘에서 현재 가공되고 있는 기호. P로 나타낸다.
●Current character : 부호화 알고리즘에 의해 결정된 기호. 일반적으로 기호는 현재 prefix를 뒤따른다. C로 나타낸다.
●Current code word : 복호화 알고리즘에서 현재 가공되고 있는 code word. W로 표시된다.
■부호화
부호화 시작 시에 사전은 비어 있다. 하지만 부호화 알고리즘의 기본 원리를 설명하기 위해 우리는 사전이 이미 몇 기호를 포함하고 있다고 가정하자.
우리는 새로운 prefix를 분석하기 시작한다. 만일 이것과 일치하는 기호열이 사전에 등록되어있을 경우에 prefix는 입력 기호열 다음의 한 기호까지 확장된다. 이러한 확장을 사전에 등록되어있지 않는 입력 기호열을 얻을 때까지 반복한다.
여기서 특별한 경우가 발생할 수 있는데 사전에 등록되어있는 기호가 하나도 없을 때이다.(조금 앞에서 우리는 이러한 경우를 생각했었다.) 이러한 경우에 빈 기호열을 나타내는 특수한 code word와 뒤따르는 기호(보통 입력 데이터의 첫 문자)를 출력한다. 그리고 이 기호를 사전에 등록한다.
알고리즘에서의 출력은 code word와 기호의 쌍(W,C)이다. 매 순간 code word와 기호의 쌍이 codestream에 출력되고 사전에서 W에 대응하는 기호열은 기호 C가 덧붙여져 확장된다. 그리고 그 결과가 사전에 등록된다.
■부호화 알고리즘
●부호화를 시작할 때 사전과 P는 비어있다.
●C는 기호열에서 다음 기호이다.
●P+C가 사전에 등록되어 있는가?
●등록되어 있다면, P=P+C
●등록되어 있지 않다면, 기호열에 두 개의 객체를 출력한다.
●P에 대응하는 code word(P가 비어있다면 zero를 출력한다.)
●C, 입력 데이터에서와 같은 형식
●P+C를 사전에 등록한다.
●P를 비운다.
●입력 기호열에 아직 남은 기호가 있는가?
●남은 기호가 있다면 2단계로 간다.
●남은 기호가 없다면
●P가 비어있지 않다면 P에 대응하는 code word를 출력한다.
●끝.
■복호화
복호화 시작시에는 사전이 비어있다. 사전은 복호화 과정에서 다시 구성되어진다. 각 단계에서 code word-기호(W,C)가 입력 기호열로부터 읽혀진다. code word는 항상 사전에 이미 등록되어 있는 기호열을 가르킨다. 문자열,W와 기호,C가 charstream에 출력되고, W+C가 사전에 등록된다. 복화가 끝나고 나서 사전은 부호화가 끝나고 나서의 것과 동일하다.
■복호화 알고리즘
●복호화 시작시에 사전은 비어있다.
●W는 입력 기호열의 다음 code word이다.
●C는 다음과 같은 기호이다.
●codestream에 문자열,W를 출력한다.(W는 빈 문자열이 될 수 있다.) 그리고 나서 C를 출력한다. W+C를 사전에 등록한다.
●입력 기호열에 아직 남아 있는 code words가 있는가?
●남아 있다면 2단계로 간다.
●끝
■예제
부호화 과정은 Table 1.에 표시되어 있다.
●열의 단계는 부호화 단계를 나타낸다. 각 부호화 단계는 부호화 알고리즘에서 3.b의 단계가 실행될 때 끝나게 된다.
●Pos는 입력 데이터에서 현재의 위치를 나타낸다.
●Dictionary는 사전에 등록된 문자열을 나타낸다. 스트링의 색인은 step number와 같다.
●Output은 (W,C) 형식의 출력을 나타낸다.
Pos
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Char
|
A
|
B
|
B
|
C
|
B
|
C
|
A
|
B
|
A
|
Step
|
Pos
|
Dictionray
|
Output
|
1
|
1
|
A
|
(0,A)
|
2
|
2
|
B
|
(0,B)
|
3
|
3
|
BC
|
(2,C)
|
4
|
5
|
BCA
|
(3,A)
|
5
|
8
|
BA
|
(2,A)
|
LZ77에 비해 가장 커다란 잇점은 각 부호화 과정에서 문자열의 비교 횟수를 줄인 것이다.
압출률은 LZ77과 비슷하다.
6. LZW
LZW에서 사용되는 용어는 LZ78에서 사용되는 것과 같다. 필요하신 분은 LZ78에서 확인하시기 바랍니다.
Root는 하나의 단일 기호열이다.
부호화 과정에서 LZ78과 차이점.
오직 codd word만 출력된다. 즉 이것은 부호화 시작시에 사전이 비어있지 않다는 것을 의미한다. 사전은 입력 기호열에서 발생할 수 있는 모든 단일 기호를 등록되어야 한다.
모든 발생 가능한 단일 기호가 사전에 이미 등록되어 있기 때문에 각 부호화 단계는 단일 기호 prefix로 시작된다. 그래서 사전에서 찾는 가장 첫 번째 문자열을 두 단어의 기호열이다. 새로운 prefix는 앞서 출현한 문자열의 가장 나중의 기호로 시작한다. 입력 기호열의 개별적인 도움없이 사전을 재 구성하는 복호화 알고리즘이 필요하다.
■부호화 알고리즘
●부호화 알고리즘의 시작시에 사전은 모든 가능한 roots를 등록한다. 그리고 P는 비어 있다.
●C는 입력 기호열의 다음 기호이다.
●P+C가 사전에 등록되어 있는가?
●사전에 등록되어 있다면 P=P+C
●등록되어 있지 않다면
●P를 나타내는 code word를 codestream에 출력한다.
●P+C를 사전에 등록한다.
●P=C(P는 기호 C만을 가지고 있다.)
●입력 기호열에 아직 남은 기호가 있는가?
●남은 기호가 있다면 2단계로 간다.
●남은 기호가 없다면
●P를 나타내는 code word를 codestream에 출력한다.
●끝.
복호화에 추가된 용어들.
Current code word : 현재 가공되고 있는 code word. cW로 표현된다.
Previous code word: 입력 기호열에서 current code word 앞서 출현한 code word. pW로 표현된다.
■복호화의 기본원리
복호화의 시작시에 사전은 부호화의 시작시와 같다. 즉 출현 가능한 모든 root를 가지고 있다.
자 그럼 복호화 과정을 살펴보자. 알고리즘에서 previous code word(pW)를 기억하고 있고 입력 기호열로부터 current code word(cW)를 읽어 온다. cW에 대응하는 문자열을 출력하고 pW에 대응하는 문자열에 cW의 문자열의 첫 문자를 더해 사전에 등록한다. 이 문자는 LZ78에서 입력 기호열에서 읽어온 개별적인 문자이다.
cW가 사전내에서 등록되어 있지 않을 때는 특수한 경우이다. 이것은 부호화 알고리즘 뒤에 설명된 lagging 때문에 발생할 수 있다. 만일 부호화 알고리즘에서 앞선 단계에서 사전에 등록한 단어를 읽었다면 발생할 수 있다. 복호화 과정에서 이 문자열을 아직 사전에 등록되어 있지 않다. 하나의 문자열은 첫 번째와 마지막 문자가 같다면 charstream에서 두 번 발생할 수 있다. 이것으로 말미암아 다음과 같은 복호화 과정이 필요하다. pW가 나타내는 문자열은 자신의 첫 문자로 확장되고 그 문자열을 사전에 등록한다. 그리고 charstream에 출력한다.
■복호화 알고리즘
●복호화 시작시에 사전은 모든 출현 가능한 root를 등록하고 있다.
●cW는 입력 기호열에서 첫 번째 code word이다.(root중 하나를 나타낸다.)
● cW에 대응하는 문자열을 charstream에 출력한다.
●pW=cW
●cW는 입력 기호열에서 다음 code word이다.
●사전에 cW에 대응하는 기호열이 있는가?
●일치하는 기호열이 있다면
●cW에 대응하는 문자열을 charstream에 출력한다.
●P=srtring.pW;
●C는 cW에 대응하는 첫 번째 기호이다.
●P+C에 대응하는 문자열을 사전에 등록한다.
●일치하는 기호열이 없다면
●P=string.pW;
●C는 pW에 대응하는 첫 번째 기호이다.
●P+C에 대응하는 문자열을 charstream에 출력한다. 그리고 이것을 사전에 등록한다.(이때 이것은 cW와 일치한다.)
●입력 기호열에 아직 기호가 남아 있는가?
●남아 있다면 4단계로 되돌아 간다.
●남아 있지 않다면 끝.
■예제
부호화 과정을 Table 1에 나타내었다.
●Step은 부호화 단계를 나타낸다. 각 부호화 단계는 부호화 알고리즘에 있어서 3.b단계가 실행되었을 때 끝나게 된다.
●Pos는 입력 기호열에 있어서 현재 위치를 나타낸다.
●Dictionary는 사전에 등록된 문자열과 색인 번호를 나타낸다.
●Output은 부호화 과정에서 일치하는 code word를 나타낸다.
부호화 시작 시에 사전은 다음과 같은 내용을 가지고 있다.
(1) A
(2) B
(3) C
부호화 될 기호열
부호화
Pos
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Char
|
A
|
B
|
B
|
A
|
B
|
A
|
B
|
A
|
C
|
Table 2.는 복호화 과정을 설명한다. 각 복호화 과정에서 하나의 code word를 읽어오고, 대응하는 문자열을 출력하고 사전에 등록한다.
우선 4단계를 분석해 보도록 하자. 앞에서의 code word (2)는 pW에 등록되어 있다. cW는
(4)이다.
Step
|
Pos
|
Dictionary
|
Output
|
1
|
1
|
(4)AB
|
(1)
|
2
|
2
|
(5)BB
|
(2)
|
3
|
3
|
(6)BA
|
(2)
|
4
|
4
|
(7)ABA
|
(4)
|
5
|
6
|
(8)ABAC
|
(7)
|
6
|
--
|
--
|
(3)
|
5단계로 가면 cW의 내용을 pW로 복사하고, 새로운 cW를 읽는다. 그래서 pW에 대응하는 문자열 “AB"는 cW에 대응하는 문자열의 첫 문자 ‘A'를 가지고 확장된다. 그 결과 ”ABA"가 사전에 등록된다.
LZW가 LZ77에 근간을 둔 알고리즘 보다 나은 점을 속도이다. 왜냐하면 실행하면서 문자열의 비교를 많이 줄였기 때문이다. 보다 세련된 방법은 가변의 code word 크기를 사용하는 것, 사전에서 오래된 문자열의 제거 등이 있다. 예를 들어 이러한 세련된 기법은 GIF 파일 포맷과 UNIX의 compress 유틸리티에서 사용된다. 다른 흥미있는 것은 LZMW 알고리즘이다. 앞서 출현한 두 개의 기호열을 합치는 방법이다.
LZW방식은 Unisys에서 특허를 가지고 있다. 상업적인 프로그램을 만들지 않는 이상 이 방식을 사용하는데는 무료이다.
defalte
gzip에서 사용되는 deflate 알고리즘은 LZ77의 한 변형이다. 입력 데이터에서 중복되는 문자열을 찾는다. 중복되는 문자열이 발견되면은 발견된 문자열은 앞서 발견된 문자열에 대한 포인터로 변환이 된다. 여기서 포인터는 (거리,길이)의 형태를 갖는다. 거리는 32kb로 제한이 되고 거리는 258byte로 제한이 된다. 입력 데이터의 스트링이 앞의 32kb 내에서 발견되지 않는다면 그냥 일반 문자열로 출력이 된다. 일치 문자열과 일치 길이는 허프만 트리에 의해서 압축되고 일치하는 위치는 또 다른 트리에 의해서 압축이 이루어 진다. 이러한 트리들은 각각의 압축 블록의 시작 위치에 단순한 형태로 놓여지게 된다. 이 블록의 크기는 메모리가 허용하는 한 어떠한 크기도 가질 수 있다. 중복된 문자열은 해쉬 테이블에서 찾을수가 있다. 일치 길이가 3인 모든 문자열들은 해쉬 테이블에 놓여 진다. 해쉬 인덱스는 다음 3바이트로 계산되어 진다. 인덱스에 대한 해쉬 체인이 비어 있다면, 체인에 포함되는 모든 문자열들은 현재 입력 문자열과 비교되어지고 가장 길게 일치하는 것이 선택되어 진다.
댓글
댓글 쓰기