[압축 알고리즘] LZ77 알고리즘 이란?

LZ77 알고리즘은 ZIP 압축에 사용되는 Deflate 알고리즘을 구성하는 압축 알고리즘입니다.

Deflate 알고리즘은 LZ77 알고리즘으로 1차 압축 후에 2차로 허프만 코드 알고리즘을 사용하여 압축합니다.

 

현재 저는 ZIP 압축 및 압축해제 프로그램을 Node.js로 구현하고 있습니다.

ZIP 압축에는 다양한 압축 알고리즘을 적용할 수 있는데, 가장 대표적인 알고리즘은 Deflate 알고리즘입니다.

Deflate 알고리즘에서 1차 압축을 담당하는 LZ77 알고리즘을 조사해 봤습니다. 

 

LZ77

LZ77 알고리즘은 슬라이딩 윈도우를 사용하여 압축을 하는 알고리즘입니다.

LZ77 알고리즘에서는 search buffer와 lookahead buffer라는 윈도우가 있습니다.

lookahead buffer의 문자열을 search buffer에서 검색하여 search buffer에서 해당 문자열의 위치(offset)과 길이(length)를 가져와 (Distance, Length, Literal) 토큰 형태로 저장합니다.

 

Distance, Length, Literal란?

Distance : look ahead buffer의 맨 앞 부분과 일치하는 문자열의 시작 부분의 거리, offset이라고 부르기도 합니다.
Length : 일치하는 문자열의 길이
Literal : look ahead buffer의 맨 앞 부분에서 Length 만큼 갔을 때 위치한 문자로 nextChar이라고 부르기도 합니다.

 

 

그림으로 LZ77 알고리즘이 어떻게 작동하는지 설명하겠습니다.

압축 대상

압축 대상은 다음과 같은 문자열로 정하겠습니다.

 

윈도우

윈도우 크기는 임의로 정합니다.

윈도우 크기는 압축 성능과 연관이 있으니 적절한 값을 선택합니다.

예시에서 search buffer의 크기는 8, lookahead buffer의 크기는 4로 정하겠습니다.

압축 과정

문자열을 따라 window를 진행시킵니다.

처음에는 search buffer가 비어있어 look ahead buffer의 문자열과 일치하는 문자열을 search buffer에서 찾을 수 없습니다.

일치하는 문자 혹은 문자열이 없으니 'a'만 LLD 형태로 저장합니다.

 

Distance: a는 position(look ahead buffer의 앞부분)과 거리가 0이니 0

Length: search buffer에 일치하는 문자열이 없으니, 일치하는 문자열의 길이는 0

Literal: position + Length에 위치한 문자, 'a'

 

로 토큰은 (0,0,'a')가 됩니다.

 

'a'는 탐색이 끝났으니 윈도우를 움직입니다.

 

Look ahead buffer에 있는 문자열과 일치하는 문자열이 search buffer에 존재하는지 찾습니다.

존재하지 않으니 'b'를 LLD 형태로 저장합니다.

 

지금까지는 look ahead buffer에 있는 문자열이 search buffer에 없는 경우만 봤는데, look ahead buffer의 문자열이 search buffer에 있는 경우를 보겠습니다.

 

look ahead buffer에 있는 문자 'a'가 search buffer에 존재합니다.

이를 토큰 형태로 저장하면,

 

Distance: a는 position(look ahead buffer의 앞부분)과 거리가 3이니 3

Length: 'a'와 'a'가 일치하니, 일치하는 문자열의 길이는 1

Literal: position + Length에 위치한 문자, 'a'

 

(3,1,'a')가 됩니다.

 

그래서 이 과정을 계속 반복하면 다음과 같은 토큰들로 문자열이 압축됩니다.

압축 해제 과정

압축 해제 과정은 압축과정의 역순이라고 생각하면 됩니다.(당연한 소리)

 

역시 말로 하면 어려우니 앞선 과정에서 압축된 결과물을 압축 해제하는 방법을 그림으로 보여드리겠습니다.

 

압축 해제는 순서대로 진행됩니다.

(0,0,'a') 토큰에서 Distance가 0이고 length가 0이라는 것은 search buffer에서 참조할 문자열이 없다는 뜻입니다.

그래서 (0,0,'a')에서 복원되는 문자열은 Literal(nextChar)만 가져와서 'a'가 됩니다.

 

이후

(0,0,'b')

(0,0,'c')

도 참조하는 문자열이 없어

'abc'가 됩니다.

 

(3,1,'a')는 Distance가 3이고 Length가 1입니다.

'abc'에서 뒤에서 앞으로 3번째 문자는 'a'입니다.

또 nextChar 또한 'a'이니

'abcaa'로 복원됩니다.

 

(5,3,'f')는 Distance가 5이고 Length가 3입니다.

'abcaa'에서 뒤에서 앞으로 5번째 문자는 'a'인데 Length가 3이니 'abc'가 복원됩니다.

여기에 nextChar인 'f'를 더하면

'abcaaabcf'로 복원됩니다.

 

이 과정을 반복하면 최종적으로

 

'abcaaabcfaabcbca'가 복원됩니다.

 

유의할 점

실제 LZ77 압축알고리즘을 활용할때는 최소 3문자 이상의 문자열에만 압축을 적용한다고 합니다.

왜나하면 앞선 예시에서 봤듯이 'a' 한 문자를 압축하면 (Distance, Length, Literal) 토큰이 생성되는데 이 토큰의 크기가 3바이트 이기 때문입니다.

단일문자(1바이트)에 LZ77을 적용하면 3바이트 토큰이 생성되기 때문에 오히려 용량이 늘어나는 문제가 발생합니다.

 

참고

https://nightohl.tistory.com/entry/LZ77-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#google_vignette

LZ77 알고리즘

https://infossm.github.io/blog/2020/07/20/dictcomp/