LZW 알고리즘과 허프만 부호화 방법을 서로 비교하여 분석해보자.

LZW알고리즘과 허프만 부호화 방법을 비교하기에 앞서, 먼저 각각의 방법을 소개하겠습니다.

 

□LZW 알고리즘

먼저 LZW 알고리즘은 무손실 압축 알고리즘입니다. LZW 알고리즘은 크게 5가지 단계로 나뉩니다.

 

(1) input을 연다.

(2) 버퍼에 저장되어 있는 것과 합친다.

(3) 사전에 있는지 확인한다.

(4) 사전에 있으면 버퍼에 저장하고, 없으면 사전에 등록한다.

(5) 사전에 등록할 때 맨 뒷글자를 빼고 압축파일로 보낸다.

 

인터넷의 예제 중 하나를 가지고 설명해보겠습니다.

input	사전 존재 유무	사전 등록	output
a b a b c d a b c a d a c a b c d a b c	Y N N Y N N N Y Y N N Y N N Y Y N Y   N N	257 a b 258 b a   259 a b c 260 c d 261 d a     262 a b c a 263 a d   264 d a c 265 c a     266 a b c d   267 d a b 268 b c	a b   ab c d     abc a   da c     abc   da b c

위의 테이블에서 보다시피, 20개의 8bit 문자들이 13개의 9bit 문자들로 압축이 되었습니다. 압축률을 계산해보면 라는 결과를 보여줍니다.

 

□허프만 부호화

다음으로 허프만 부호화 방법입니다. 허프만 부호화는 각 문자에 대한 발생빈도를 알고 있을 때에 자주 나오는 문자에는 짧은 비트를 할당하고, 자주 나오지 않는 문자에는 긴 비트를 할당하여 압축하는 방법입니다. 허프만 부호화는 크게 3가지로 나뉩니다.

 

(1) 발생빈도가 가장 적은 부호 두 개를 합친다.

(2) 두 개 중 발생빈도가 잦았던 것에 1, 다른 하나에 0을 부여한다.

(3) 발생빈도가 같을 경우 무엇을 합치던 상관없다.

 

이 과정을 LZW예제와 비슷한 20문자 입력데이터에 적용해보겠습니다.

input	발생빈도(횟수)	압축 전 비트수	압축 후 비트 수
A B C D E F G H	0.4(8) 0.2(4) 0.15(3) 0.09(2) 0.08(2) 0.05(1) 0.02(0) 0.01(0)	24 12 9 6 6 3 0 0	8 12 9 8 6 5 0 0

 

위의 테이블로 결과를 보면 압축 전 총 60비트에서 압축 후 48비트가 된 것을 알 수 있습니다. 압축률을 계산해보면 라는 결과를 보여줍니다.

 

두 방법에 20개의 문자를 넣고 압축을 했습니다. 그 결과 LZW 알고리즘은 73.215%, 허프만 부호화는 80%의 압축률을 보여줬습니다. 그렇다면 허프만 부호화가 더 좋은 압축방법이라고 말할 수 있을까요? 아닙니다. 먼저 입력값이 문자수는 같더라도 중복값등 차이가 있을 수 있습니다. 또한 중요한 사실 중 한가지는 허프만 부호화는 ‘발생빈도’를 알고 있어야 압축이 가능합니다. 이 말은 다시 말해, 발생빈도를 알고 있지 않으면 압축할 수 없다는 말이 됩니다. 반면에 LZW알고리즘은 발생빈도를 몰라도 압축이 가능합니다. 압축률이 좋은 것, 발생빈도가 필요 없는 것 등 어느 부분들이 압축방법이 더 좋다고 말할 수 있게 결정짓는 요소일지에 대해 직접 코드를 짜보며 나오는 결과들로 결론을 내보겠습니다.

 

○ 코드실행속도 비교

뜬금없이 웬 코드 속도 비교라고 생각할 수도 있겠지만 LZW 알리고즘, 허프만 부호화 모두 일종의 ‘코딩’입니다. 그래서 생각난 것이 코드로 구현을 해서 코딩의 실행속도를 비교해 보자입니다. 이것이 큰 영향을 미칠지는 모르겠으나, 코딩의 실행속도가 오래 걸린다는 것은 어떠한 알지 못하는 효율에 영향을 끼칠 수도 있을 거라 판단했습니다. (물론 코드의 효율적 구현 등에 의해 달라질 수도 있지만 제가 할 수 있는 한에서 최대한 간결하게 짜보았습니다. 프로그래밍 언어는 python3입니다.)

 

먼저 LZW알고리즘입니다.

 

 

코드의 설명을 하자면 위에 설명했던 LZW 알고리즘의 5가지 순서를 구현했습니다. 먼저 8bit 사전을 만들어 두었습니다. 그렇게 하여 input에서 문자 하나를 꺼내어(c) 버퍼에 있는 것과 합친 것을 test, 이 test가 사전에 있으면 다시 버퍼에 넣습니다. 그러나 사전에 없다면 사전에 +1을 해줘서 등록시킵니다. 그리고 마지막 글자를 버퍼에 두고 압축파일로 보낼 문자의 사전번호를 result에 넣어둡니다. 이러한 방식으로 구성하였습니다.

 

이 코드로 LZW 예제에서 했던 입력을 그대로 코드에 넣고 실행해보겠습니다.

 

 

결과를 보면 실제 직접 구현했던 압축결과와 동일하게 나오는 것을 알 수 있습니다. 또한 코드한 실행되는데 걸린 시간은 0.05초정도가 걸렸습니다.

 

다음은 허프만 부호화입니다.

 

 

허프만 부호화 역시 위에 설명했던 3가지 단계를 따랐습니다. 먼저 발생빈도가 가장 적을 문자를 뽑아서 합치고 발생빈도가 높았던 문자에 1을 부여, 다른 문자에 0을 부여 했습니다. 그렇게하여 원하는 형태로 출력하게 해두었습니다.

 

이 코드로 LZW알고리즘과 같은 입력값을 넣었습니다.

 

 

결과를 보면 코드실행시간이 허프만 부호화 방법이 더 적게 나온 것을 알 수 있습니다. 이번엔 더 긴 입력값을 넣어보겠습니다.

 

입력값을 THIS SUBJECT IS REALLY REALLY HARD AND THANK YOU ABCDEFGHIJKLMNOPASDZXCQWEASDZXCQWE 로 넣었을 때 두가지 압축방법의 코딩 실행차이가 거의 비슷해졌습니다. 입력값을 더 다양하게 넣어도 입력문자의 수가 어느 정도 이상이면 코드 실행속도가 대부분 비슷하게 나왔습니다. 이로써 코드 실행속도 비교는 무승부입니다.

【※ 번외 :　코드구현은 허프만 부호화가 더 복잡하고 까다롭습니다. 이 부분은 확실한LZW 알고리즘의 승리입니다.】

 

○코드의 간결성

코드를 구성하면서 예상하기로는 LZW의 실행속도가 훨씬 빠를 것이라고 예상했습니다. 그 이유는 LZW 알고리즘은 주어진 입력값들을 한 번씩만 건드리고 압축을 실행합니다. 하지만 허프만 복호화는 입력값을 총 2 번 건드리고 압축을 실행하기 때문입니다. 또한 LZW 알고리즘이 (번외에서도 말했지만,) 허프만 복호화 보다 훨씬 더 단순합니다. 저는 이것이 그저 코드의 길이 혹은 복잡성에만 영향을 주는 것이 아니라, 많은 부분에 영향을 줄 것이라 생각합니다. 극단적으로 손으로 두가지 방법을 압축한다고 해도 LZW 알고리즘의 압축이 더 빨리 끝나게 될 것입니다. 이러한 이유에서는 LZW 알고리즘의 승입니다.

 

○코드의 변형여부

코드를 구성하며 한 가지 더 알게 된 것은 바로 입력값과 출력값의 형태입니다. LZW 알고리즘의 경우, 문자의 개수가 같더라도 그 배열이 달라지면 다른 결과가 나옵니다. 반면에 허프만 부호화의 경우 배열이 아무리 달라져도 문자의 개수 즉, 확률분포만 같다면 결과가 같습니다. 이것은 어느 것이 좋다 나쁘다가 아닌, 각자 복잡한 입력값을 가지고 어떠한 결과를 만들어야 할 때 원하는 결과의 방향에 맞게 사용하여야 한다고 생각이 들었습니다. 그저 입력값이 달라져도 출력값이 같고 다르고 하는 문제처럼 보일 수 있지만, 두 압축방법의 이러한 차이는 분명 어느 영역에서는 다른 결과를 낳을 것이라고 생각합니다.

 

이렇게 코드를 직접 구성해보며 직접 느낀 LZW알고리즘과 허프만 부호화의 비교를 진행해보았습니다. 수업 이외에 많은 내용들을 찾아보며 허프만 부호화에서 조금 진화한 형태, 혹은 효율적인 방법이 LZW 알고리즘이라는 내용들도 보았습니다. 그러나 제가 아는 지식과 코딩을 하며 도출해낸 결론은 무승부입니다. 딱 똑같이 좋다가 아닌, 두 가지 방법 각자 쓰임이 있다는 결론입니다.