LZ77, LZ4, Deflate...

내친 김에 LZ77과 Deflate도 해봤다. LZ77은 구현하기가 상당히 쉬운데 이걸 특별히 LZ77 알고리즘이라고 부르기도 뭐하지 싶다. 거의 RLE와 비슷하다고 할까. LZ77의 문제는 새로 등장하는 문자열에 대해서도 모두 offset, length를 붙여주는 것이라고 볼 수 있다. LZ4는 이걸 붙여줄 필요가 없고 블록단위로 끊어내는데 bypass하거나 반복하는 문자열의 길이에 따라 이 필드도 확장이 가능하기 때문에 압축율을 늘려줄 수 있고 뭐니뭐니해도 이렇게 64KB만 들여다봐서 작업하면 되니까 실시간 압축이 빠르게 될 수 있다는 것. 그런데 실시간으로 압축이 가능하게 되려면 제법 머리를 써야지 싶다.

압축해제의 경우도 64kB 버퍼를 두고 그 안에서 블록별로 작업하면 되니까 굉장히 빠르게 이루어질 것으로 보여진다. 역시 이것은 데이터 흐름이라 C 코드 수준에서 만들었다고 그걸 다 해봤다라고는 못하지 싶다. 더구나 byte 단위로 비교한다거나 vector 같은 것을 써서 작업하면 대용량 데이터를 가지고 한다고 하면 압축속도가 대단히 느리다. 속도를 올리려면 역시나 빠르게 비교할 수 있는 알고리즘을 사용하고 작은 크기로 작업해서 작은 크기로 곧바로 내보낼 수 있게끔 그것도 매우 C 스럽게 작업해야 맞다.

어쨌든 huffman coding을 더하면 제법 압축이 된다. ZIP에서는 DEFLATE/DEFLATE64를 쓴다고 해서 비교해봤는데 zip의 압축결과가 훨씬 작았다. huffman coding을 하려면 블록별로 받아와서 작업하는 것이 불가능하고 전체 데이터 블록을 통째로 가지고 있어야 되니까 속도가 느려진다. 따라서 LZ + Huffman code도 unit 블록 단위로 해야 속도로 올리고 병렬화도 하고 할 수 있다고 본다.