Compression algorithms...

LZ가 붙는 압축 방법에 대해서 이야기 해보기로 한다.

사실 아무것도 모르던 상황에서는 엄청나게 뛰어난 알고리즘이라 나는 죽었다 깨어나도 이해할 수 없을 것 같다고 생각할 수 있지만, 전혀 그렇지 않다는 게 신기한 일이다.

LZ를 시작하기 이전에 Huffman code라는 압축방법에 대해서 먼저 이야기 하자.

Huffman code는 압축해야 할 데이터가 있다고 하면 그것을 어떤 단위로 다 쪼개서 발생 빈도를 가지고 압축후의 정보량을 결정해서 압축하는 방법이다라고 나는 설명하고 싶다. 이게 뭔 소리인가?

대부분 byte 단위를 최소 단위로 해서 압축한다고 보면, byte단위로 발생 빈도의 히스토그램을 먼저 뽑는다. 그것을 가지고 압축 후의 정보량을 부여한다.

기본 원리는 많이 나타날 수록 작은 양의 정보량을 부여하고 (사실상 이게 엔트로피의 개념과도 연결된다) 덜 나타날 수록 많은 정보량을 부여한다. 만일 모든 경우의 발생확률이 모두 같다 라고 하면 압축이 가장 덜 되게 된다. 이걸 다시 생각해보면 내가 가진 데이터가 (바이트 단위로는) 발생확률이 모두 같은 완전히 랜덤한 데이터로구나 생각할 수 있다 - 그러니까 압축이 거의 안되는 구나.

이것은 발생빈도에 따라서 발생하는 패턴에 대해서만 코드가 부여되서 압축되는 것이니까 여기에서 정보량이 줄어드는 이득이 발생한다. 이를테면 같은 문자열 패턴(문장)이 여러 번 발생한다고 하면 문자열을 통째로 하나의 정보로 인식해서 그것을 통째로 압축해버리는 것은 할 수 없기 때문에 이런 패턴이 자주 발생한다면 압축을 더 할 수 있지만 그렇지 못한 상황이 벌어지게 될 것이다.

LZ 알고리즘으로 오면 이런 문자열/문장 패턴의 반복에 대응하게 된다.

먼저 LZ77에 대해서 이야기 하자면, 이것은 데이터를 순차적으로 스캔하면서 정보를 저장한다. 기본적으로 (문자열의 위치, 길이, 다음 문자) 이런 형태로 저장하게 된다. 그러니까 앞에 나왔던 패턴이 다시 반복되게 되면 그 패턴을 통째로 압축할 수 있는 장점이 생긴다. LZ78은 이렇게 순차적인 방법으로 압축하지 않고 dictionary를 만들고 이걸 가지고 압축한다. 그러니까 (위치, 길이, 다음 문자)가 아닌 다음문자 대신 dictionary의 index가 저장되는 방식이 된다.

LZW는 dictionary를 만드는 방법을 개선했기 때문에 (동적으로 계속해서 업데이트 함) 긴 패턴에 대해서 압축률이 좋아져서 그림처럼 비슷한 패턴이 자주 나오는 경우에 유리해서 GIF 압축에 쓰였다고 한다.

LZ4는 LZ77에서 발전했기에 dictionary는 만들지 않고 LZ77과 달리 다음 문자를 기록하지 않는다. dictionary는 만들지 않지만 이미 scan한 문자열을 가지고 다음에 오는 데이터 패턴을 비교하기 때문에 메모리를 많이 요구하지 않고 dictionary를 검색하는 과정이 없어서 순차적으로 동작하는 하드웨어로 구현하기에 유리한 장점이 있다. 마찬가지로 decompression도 빨라지는 장점이 있다.

예전에 많이 쓰였던 LZH(Lempel-Ziv-Huffman)라는 방법은 LZ77에서 스캔하는 방법을 이용해서 dictionary를 만들고 이것에 Huffman coding을 적용해서 추가적인 압축을 하게 한다. 즉, 사전을 마치 일반적인 Huffman code을 설명할 때 쓰이는 character처럼 생각해서 발생 빈도를 가지고 압축된 후의 정보량을 결정하는 방법으로 추가적인 압축을 가능하게 한다. 이 방법은 데이터를 모두 스캔해서 dictionary를 만들고 그동안 발생빈도를 계산해 놓은 뒤에 Huffman code를 또 적용해야 하기 때문에 압축시간이 증가하게 된다.

LZMA(Lempel-Ziv-Markov-chain Algorithm)라는 방법도 많이 사용되고 있는데, 이것은 Markov chain이 인과관계를 확률로 설명하는데 유리한 특징을 이용해서 압축하는 것이라고 볼 수 있다. LZH에서는 인과관계와는 상관없이 그냥 발생빈도만을 가지고 압축했는데, LZMA는 패턴 발생의 인과관계를 학습해서 다음에 나올 확률이 높은 패턴에 대해서는 상대적으로 낮은 정보량을 부과하는 식으로 압축이 이루어진다. 따라서 패턴간의 인과관계를 따져서 더 복잡한 패턴비교가 이루어져야 하므로 계산량이 많은 대신 압축률은 좋아질 수 있다. 7zip, xz가 이 알고리즘을 이용한다.

여기에 일반적으로 zip에서 쓰이는 알고리즘을 알려진 DEFLATE/DEFLATE64에 대해서 설명하자면 DEFLATE는 LZ77 + Huffman code이고 DEFLATE64는 사용하는 포인터를 64으로 (32비트로부터) 확장해서 4GB (=2^32 address range)를 넘어가는 블록의 데이터를 압축할 수 있다.