LZ77 알고리즘

LZ77 알고리즘 (LZ77 Encoding)

: LZ77알고리즘은 사전 방식 ( Dictionary methods )을 채택한다. 즉, 반복적으로 나오는 문자열을 압축한다.

zip, gzip, pkzip 등에서 사용되는 압축 알고리즘이다.

다른 알고리즘과 결합되어 deflate 방식 등으로 사용된다.

Pseudo-Code 는 다음과 같다.

1     begin

2         fill view from input

3         while (view not empty) do

4             begin

5                 find longest prefix p of view starting in coded part

6                 i = position of p in window

7                 j = length of p

8                 x = first char after p in view

9                 output( i , j , x )

10                add j+1 chars

11            end

12    end

2개의 버퍼 Search_Buffer(혹은 window)와 Lookahead_Buffer(혹은 view)가 있고, 이를 이용하여 LLD(Literal, Length, Distance) 블럭들을 만든다.

(이하 lookahead버퍼, window버퍼로 통일)

Pseudo 코드를 그대로 풀어서 간단하게 설명하고, 그림을 통해 과정을 알아보자.

2	input 값을 lookahead 버퍼에 채운다.
5	lookahead 버퍼의 첫번째 문자를 포함하는 가장 길게 일치하는 문자열을 window 블럭에서 찾는다. (여기서 p는 lookahead의 시작지점을 의미)
6	window에서 찾은 문자열의 첫번째 문자와 p와의 거리를 i에 담는다.
7	일치하는 문자열의 길이를 j에 담는다.
8	x = p+j 번째의 문자(char)  : (찾은 문자열 바로 다음 문자)
9	( i , j , x ) 를 결합하여 LLD를 만든다.
10	j+1 만큼 p를 이동시킨다. ( p왼쪽을 window, p부터 lookahead 라고 보면 됨. )
	lookahead 버퍼가 텅 빌 때까지 5~10의 과정을 반복한다.

그림을 통해 과정을 살펴보자.

Input : aohlbohlcohl

설정한 window buff size	0x06
설정한 lookahead buff size	0x04

(버퍼 크기도 결과에 영향을 많이 미침)

먼저 input을 lookahead buff에 채운다. lookahead buff size가 0x04이므로 4chars가 담긴다.

------------------------------------------------------------------------------------------------------

p에서부터 가장 길게 일치하는 문자열을 window buff에서 찾는다.

window buff에 아무것도 없으므로

window에서 찾은 문자열의 시작과 p와의 거리	i = 0(Distance)
일치하는 문자열의 길이	j = 0(Length)
x = p+j = p+0 위치의 문자	x = 'a'(Literal)

LLD = (0 , 0 , a)

j+1 ( 찾은 문자열의 길이 + x 문자 까지!) 만큼 p를 증가시킴.

(p 왼쪽은 window buff, p부터 lookahead buff)

------------------------------------------------------------------------------------------------------

o도 window buff에 없으므로 LLD = (0 , 0 , o)

------------------------------------------------------------------------------------------------------

h도 window buff에 없으므로 LLD = (0 , 0 , h)

------------------------------------------------------------------------------------------------------

l도 window buff에 없으므로 LLD = (0 , 0 , l)

------------------------------------------------------------------------------------------------------

b도 window buff에 없으므로 LLD = (0 , 0 , b)

------------------------------------------------------------------------------------------------------

p위치의 o부터 가장 길게 일치하는 문자열을 window buff에서 찾는다.

가장 길게 일치하는 문자열은 "ohl"이다.

window에서 찾은 문자열의 시작과 p와의 거리	i = 4(Distance)
일치하는 문자열의 길이	j = 3(Length)
x = p+j = p+3 위치의 문자	x = 'c'(Literal)

LLD = (4 , 3 , c)

------------------------------------------------------------------------------------------------------

p위치의 o부터 가장 길게 일치하는 문자열을 window buff에서 찾는다.

가장 길게 일치하는 문자열은 분명 "ohl"이다. 하지만 위 그림을 보면 "oh"까지만 일치한다고 표시했다. 왜냐? LLD의 L(Literal)에는 반드시 문자가 들어가야하므로 맨 마지막의 'l'을 제외시킨 것이다. 

만약 l 뒤에 다른 문자 하나가 더 있었다면 처음처럼 "ohl"이 됐을 것이다.

window에서 찾은 문자열의 시작과 p와의 거리	i = 4(Distance)
일치하는 문자열의 길이	j = 2(Length)
x = p+j = p+2 위치의 문자	x = 'l'(Literal)

LLD = (4 , 2 , l)

이게 바로 Window buff와 Lookahead buff 크기가 결과에 영향을 미치는 이유다.

"ohl"뒤에 다른 문자가 더 있더라도 만약 Lookahead buff 크기가 0x03이라면 "ohl" 까지만 lookahead buff에 들어가므로 위 경우와 똑같은 결과를 초래할 것이다.

Windows buff가 영향을 미치는 이유는 앞전에 일치하는 문자열이 있었다 하더라도 버퍼 크기가 작아 밀려나면서 windows buff에 더이상 존재하지 않는다면 일치하는 문자열이 없다고 인식하게 되므로 결과가 달라진다.

------------------------------------------------------------------------------------------------------

Input	a o h l b o h l c o h l
Output	(0 , 0 , a)(0 , 0 , o)(0 , 0 , h)(0 , 0 , l)(0 , 0 , b)(4 , 3 , c)(4 , 2 , l)

------------------------------------------------------------------------------------------------------