압축 알고리즘 궁금하시지 않으세요? 알집 알고리즘 연구하던 1人 이 들려 드립니다.

안녕하세요.
알집 8.x 버전에 들어갈 새로운 압축알고리즘 연구에 참여했던 1人입니다.

말도 많고 오해가 많은 압축 알고리즘에 대해서 간단히 설명해 드리고자 합니다.
가능한 쉽게 쓰겠지만 이쪽 분야를 전혀 모르시는 분은 조금 어려울 수도 있겠네요^^;;;

 

우선 압축 알고리즘은 크게 Entropy(엔트로피) 코딩과 사전 코딩으로 나눌 수 있습니다.

 

먼저, 두 가지 방식을 비교해 보겠습니다.

Entropy(엔트로피) 코딩이라 하면 이렇게 생각하시면 쉽습니다.  

A라는 문자가 10번 나오고 B라는 문자가 5번 나온다면

A 문자에 B문자 보다 짧은 코드를 할당해서 전체 길이를 줄이는 것입니다.

예를 들어 A:0 B:10 이런식으로 할당하는 것이지요

 

사전 코딩은 쉽게 말하자면, 특정문자를 어떤 인덱스로 표현한다고 생각하면 됩니다.

예를 들어 ABCABCABCDEFDEF 라는 문자가 나온다고 하면

ABC:1 DEF:2 로 정의하고 11122 라고 표현하는 것입니다.

 

Entropy 코딩에서 대표적인 것은

많이 들어보신 Huffman 코딩과 Arithmetic(Range) 코딩이 있고,

사전 코딩은 LZ77, LZW 등이 있습니다.

이 밖에도 BWT라는 문자를 정렬 함으로서 압축 하는 방법이 있고,

Markov Chain 이라는 예측 방법을 통해 압축하는 방법도 있습니다

  

그럼 우리가 알고 있는 zip, rar 파일 등은 어떤 알고리즘을 사용하는 것일까요?

 

어떤 분은 zip 은 huffman 을 쓴다라고 하시는 분도 있는데

zip 은 Deflate 라는 알고리즘을 사용합니다.

 

Deflate 라는 알고리즘은 위에 설명이 안되어 있는데
과연 어디에 속한 알고리즘 일까요?

 

많은 분들이 잘못 알고 있는 부분이 있는데, 

압축하면 어떤 특정 알고리즘만을 사용할 것이라는 부분입니다.

하지만 실제로는 어떤 압축이건 단 하나의 알고리즘으로 구현되어 있는 것은 없습니다.

 

기본적으로 위에서 언급한 'Entropy 코딩 + 사전 코딩 + 알파' 로

두가지 이상의 알고리즘을 사용하여 하나의 압축 알고리즘이 나오는 것입니다.

 

Deflate 같은 경우는 LZ77 + Huffman 입니다.
사전코딩 방식과 Entropy 방식의 조합이죠?

 

예를 들어, 사전 코딩을 이용해

ABCABCABCDEFDEF 란 문자를 11122 로 인코딩하고 나서,

1이 2보다 많이 나오므로

Entropy(엔트로피) 코딩을 이용해

1에 2보다 적은 코드를 할당해서 압축하는 것입니다.

 

BZIP2 에서는 RLE(Run Length Encoding) + BWT + Huffman 을 사용합니다.

RLE + BWT 가 사전 코딩과 비슷한 효과를 낸다고 보면 됩니다.

 

최근에 나온 7zip 에서 쓰는 LZMA 같은 경우는

LZ77 + Markov Chain + Range 코딩을 사용합니다,.

 

다시 말하면, 여러 압축 알고리즘은

이런 기본 알고리즘이 모여서 만들어진다고 생각하면 됩니다.

그러면 압축 알고리즘은 알고리즘을 모으기만 하면 만들어지는 걸까요?

물론 "그렇지 않다"가 답이겠지요.
이렇게 쉽다면 누구나 압축 알고리즘을 개발할 수 있었을 것입니다^^;;;

위에서 말한 Huffman 이나 LZW 등은 이론적 개념에 불과한 것이고,
실제로는 그것을 어떻게 구현하고 다른 알고리즘과 연관 시킬지가 관건이죠.

 

실제로 파일을 압축 하려면 이론과 달리

Entropy(엔트로피) 코딩은

문자별 할당 코드도 함께 저장해줘야 하고

사전 코딩 같은 경우 사전이 너무 크게 되면

인덱스 번호를 저장하는 것이

원래 문자보다 더 커질 수도 있는 문제가 있습니다.

즉, 데이타 자체는 압축이 되겠지만

기타 부가 정보가 들어가게 되므로

실제 파일은 압축이 별로 안 되겠죠.

그래서 실제로 Deflate 에서 쓰는 Huffman 과
BZIP2 쓰는 Huffman 이 다르고,
Deflate 쓰는 LZ77 과 LZMA 에 쓰는 LZ77 도 구현이 다릅니다.

따라서 압축 알고리즘이라고 하면 이런 이론적 배경을 통해 구현해 낸
Deflate, LZMA 같은 것을 말한다고 생각하면 됩니다.

 

간단히 설명할려고 했는데 좀 복잡해지네요 ^^;;;;;;;

간단히 요약하면 Huffman, LZW, BWT 라는 것은 이론적 배경이고,
(모두 사람 이름이거나 이름의 첫문자 입니다.)
압축 알고리즘에는 Deflate, LZMA, BZIP2 알고리즘 등이 있다고 생각하면 됩니다.

  

그럼 압축 포맷은 무엇일까요?

압축 포맷마다 각자의 압축 알고리즘이 존재하는 것일까요?

 

잘 모르시는 분은 압축 알고리즘과 압축 포맷을 동일시 하는 경우가 있는데요...

사실 압축 알고리즘과 압축 포맷은 엄연히 서로 다른 것입니다.

 

아시다시피 세상에는 정말 많은 압축 포맷이 있습니다.

우리가 가장 많이 쓰는 zip부터 시작해서

rar, cab, ace, arj, bz2, 7z 등등...

아... 저희 회사에서 만든 alz 란 포맷도 있습니다.

실제로 잘 안 쓰거나 우리가 잘 모르는 것까지 다 합치면

백 가지가 넘을 수도 있습니다.

 

포맷은 압축 알고리즘으로 압축된 내용을 가지고,

파일 이름과 속성 등을 저장하거나  

필요에 따라서 암호화도 하고 분할하기도 하는 등의 작업이라고 생각하면 됩니다.

 
알고리즘과 포맷은 일대일 관계가 아니고 일대다 혹은 다대다 관계입니다.

 

즉, zip 이라는 포맷은 deflate 알고리즘을 사용하지만

최근 스팩에는 LZMA도 사용할 수 있습니다.

 

7zip포맷 같은 경우 LZMA 를 기본으로 사용하지만 bzip2 알고리즘도 사용할 수 있습니다.

 

cab 과 gzip 같은 경우는 deflate 를 사용하며,  

alz 같은 경우는 deflate 와 bzip2 를 사용합니다.

 

포맷마다 새로운 암호화를 지원하고 유니코드를 지원한다거나

4기가 파일 이상을 지원 한다거나 등의 기능적인 차이만 있을 뿐

 몇 가지 공통된 알고리즘을 사용하고 있는 것입니다.

 

이상 압축 이론과 압축 알고리즘과 압축 포맷에 대해서 3가지를 설명드렸습니다.

 

이 글을 통해서 대충 이것들의 차이가 뭔지 아셨다면 충분할 것 같습니다.

알집 8.X 에 들어갈 압축 알고리즘 개발하느라 고생 좀 하다가
지금은 다른 팀으로 가게 되어 다른 프로젝트에 참여하고 있는데요,
한 동안 함께 지냈던 알집이 잘 되기를 먼 발치에서 응원하고 있습니다.
긴 글 읽어 주셔서 감사합니다.

                                                 - 이스트소프트에 몸 담고 있는 1人 -