[알고리즘]압축 알고리즘에 관하여

  과제를 기회로 평소에 여러 프로그램을 사용하면서 자연스럽게 많이 사용하지만 잘 알지는 못하는 압축 알고리즘에 대해서 간단히 설명해 보고 압축 알고리즘에 해당하는 종류(포맷)들에 대하여 알아보겠다. 마지막으로 교수님께서 요구하신 기업에서 사용하는 압축알고리즘은 무엇인가에 대한 조사를 한 내용에 대하여 설명하겠다.

압축 알고리즘이란?

파일이나 이미지 데이터 등을 압축하기 위한 논리법으로 크게 손실알고리즘(entropy 코딩)과, 무손실알고리즘(사전 코딩)으로 나눌 수 있다.

Entropy코딩과 사전코딩

Entropy 코딩이란? -> A라는 문자가 10번 나오고 B라는 문자가 5번 나온다면 A문자에 B문자 보다 짧은 코드를 할당해서 전체 길이를 줄이는 것이다.

예를 들어) A:0 / B:10 이런식으로 할당하는 것이다.

대표적인 알고리즘으로는 Hufman 코딩(알고리즘 수업시간에 배우는 내용)과 Arithmetic(Range) 코딩 등이 있다.

사전 코딩이란? -> 특정문자를 어떤 인덱스로 표현한다고 생각하면 쉽다.

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

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

대표적인 알고리즘으로는 LZ77, LZW 등이 있다.

이 밖에도 BWT라는 문자를 정렬 함으로써 압축하는 방법이 있고, Markov Chain 이라는 예측 방법을 통해 압축하는 방법도 있다.

기업에서 사용하는 압축알고리즘 조사

우리가 흔히 아는 압축프로그램은 zip파일과 rar파일 등이 있다. 이러한 압축프로그램을 암축 혹은 복구하기 위해 쓰는 대표적인 프로그램으로는 알집이 존재한다. 본인은 알집에서 사용하는 압축알고리즘에 대하여 조사해 보았다.

zip은 Deflate라는 알고리즘을 사용한다. Deflate라는 알고리즘은 위에 설명이 안되어 있는데 많은 사람들이 잘못 알고 있는 부분이 있는데, 압축하면 어떤 특정 알고리즘만을 사용할 것이라는 생각이다. 실제로는 어떤 압축이건 단 하나의 알고리즘으로 구현되어 있는 것은 없다.

기본적으로 위에서 언급한 ‘Entropy코딩 + 사전코딩 + @’로 두 가지 이상의 알고리즘을 사용하여 하나의 압축 알고리즘이 나오는 것이다.

Deflate 같은 경우는 LZ77 + Huffman을 합친 경우이다. 즉, 사전코딩과 Entropy 방식의 조합이다.

검색을 통해 익힌 지식을 기반으로 간단히 예를 들자면, 사전 코딩을 이용해 ABCABCABCDEFDEF란 문자를 11122로 인코딩하고 나서, 1이 2보다 많이 나오므로 Entropy 코딩을 이용해 1에 2보다 적은 코드를 할당해서 압축하는 것이다.

최근에 알집에서 선 보인 7zip에서 쓰는 압축알고리즘은 LZMA이며, 이 알고리즘은 LZ77 + Markov Chain + Range 코딩을 사용한다.

다시 말하면, 인터넷보안 시간에도 여러 보안 알고리즘은 서로 결합하여 더욱 더 강력한 보안 알고리즘을 만들어 내듯이 압축 알고리즘에서도 이와 같이 여러 압축 기본 알고리즘이 모여서 더욱 더 강력한 압축 알고리즘을 만들어진다고 생각하면 된다.

이상 압축알고리즘에 대한 간단한 이론과 압축 포맷에 대하여 그리고 마지막으로 기업에서 사용하는 압축알고리즘에 대하여 알아보았다. 이 레포트를 작성하며 중간 중간에 나의 의견과 느낀 점이 들어가있다고 생각되어 따로 느낀점은 적지 않겠다.

참 고 자 료

[1] 압축알고리즘 위키백과 http://ko.wikipeda.org/wiki/분류:압축_알고리즘

[2] 압축 알고리즘 궁금하시지 않으세요? 알집 알고리즘 연구하던 1人 이 들려 드립니다. 안철수연구소 http://altools.tistory.com/60

[3] 데이터 압축 알고리즘의 분류 봉씨닷컴 http://yjbong.egloos.com/viewer/98669406_01.html

압축알고리즘.hwp