LZ77

1.       개관

이 알고리즘은 Abraham Lempel과 Jakob Ziv가 1977년에 만들어낸 데이터 압축 알고리즘입니다. 이 알고리즘의 메인 아이디어는 이미 한번 이상 사용된 문자열은 기존의 문자열의 상대적 위치와 일치하는 길이만을 저장한다는 것입니다. 이 알고리즘은 LZSS, LZ78, LZW, LZWM과 같은 알고리즘의 기반입니다.

2. 용어

Input stream : 압축될 원본 문자열

Output stream : 압축된 결과

Character : 압축될 문자열의 기본적인 데이터 단위

Coding position : Input stream내에서 현재 압축을 진행하고 있는 처리지점의  offset. lookahead buffer의 처음과 일치한다.

lookahead buffer : CP에서 input stream의 마지막 character까지를 포함하고 있다.

Window : 이미 처리가 끝난 W(window size)개의 character들. 즉, Coding position 앞에 있는 W개의 문자열을 의미한다.

Pointer(p) : Window와 lookahead buff에서 일치한 문자열을 찾은 경우, 그 문자열의 시작 위치를 나타낸다. 표현 방법은 CP로부터 몇 character가 떨어져 있는가 이다.

Length(len) : 일치하는 문자열의 길이

3.       원리

window에서 lookahead의 앞부분과 일치하는 가장 긴 문자열을 찾아낸다. 그리고 그 위치와 일치하는 길이, 즉 ( p, len)을 output stream으로 출력한다. 문제는 1 character 조차도 window에서 일치하는 character가 없을 수도 있다. 그렇기 때문에 lookahead의 첫 character를 함께 저장해 준다.

4.       The encoding algorithm

1) Cording position을 input stream의 시작에 위치해준다.

       2) window에서 lookahead buffer의 시작부분부터 일치하는 가장 긴 문자열을 찾는다.

3) “(p,len) C”를 output시킨다.

-          p : 일치하는 문자열의 시작 부분까지의 상대적인 거리

-          len : 일치하는 문자열의 길이

-          C : lookahead에서 일치하지 않는 제일 첫 character

4) lookahead buffer가 비어있지 않다면 coding position과 window를 len+1만큼 옮겨준다. 그리고 2)로 간다.

5.       The decoding algorithm

encoding algorithm을 이해했다면 쉽게 decoding algorithm을 이해할 수 있을 것이다. 여기서 window는 encoding 때와 동일한 방법으로 유지된다.

input stream : 압축된 자료의 stream

output stream : 압축이 풀린 원래 형태의 자료

1)      input stream에서 하나의 “(p,len)C” 를 읽어 들인다. 만약 읽을게 없다면 종료

2)      window에서 p의 위치로 가서 len만큼의 character를 읽어서 output stream에 출력하고 window끝에 추가 시킨다.

3)      C를 output stream에 출력하고 window 끝에 추가 시킨다.

4)      1)로 돌아간다.

6.       Example

Input stream for encoding:

Pos : position

7. 특징

꽤 괜찮은 압축률을 가지고 있습니다. 알고리즘은 간단하지만, encoding 시에는 window에서 일일이 lookahead buffer와 대조를 하여야 하므로 속도가 상당히 느립니다. 반면 decoding은 알고리즘도 간단하고 매우 빠릅니다. 구현시에 window를 메모리에 넣고 사용하면 4kb~64kb정도의 메모리를 사용으로 구현이 가능합니다. 그리고 LZSS란 알고리즘이 있는데 이것은 LZ77에서 약간 개선된 것이며 좀더 좋은 압축률을 기대할 수가 있습니다.

참조 : http://www.rasip.fer.hr/research/compress/algorithms/fund/lz/lz77.html