22. 허프만 부호화(Huffman Coding)

  어릴적 셜록 홈즈 소설을 읽었는데 '춤추는 인형'을 참 재밌게 읽은 기억이 난다. 이 춤추는 인형도 일종의 암호화 였다. 우리가 사용하는 자연어를 컴파일 가능한 기계어로 바꾸듯이, 셜록홈즈의 춤추는 인형에서는 자연어를 춤추는 인형으로 암호화 하여 범죄에 이용했다. 이 때 셜록홈즈가 이 문제를 아주 재미있게 푼다. 춤추는 인형이 마치 글자 처럼 연속성을 가지고 있다는 점을 홈즈가 알게되고 그는 인형 중 가장 많이 나온 것을 알파벳 'E'라고 눈치챈다. 그 이유는 영어에서 가장 출현 빈도가 높은 글자가 바로 'E'이다. 홈즈는 한 인형이 E라는 가정을 알게 되자 그 이후에 여러가지 가정을 통해 쉽게 암호를 풀게 되었다. 이처럼 우리가 사용하는 글자에는 분명 많이 사용하는 빈도가 있을 것이다. 영어 뿐만 아니라 한글에서도 'ㅇ'이나 'ㄱ'을 많이 쓰고 상대적으로 'ㅌ'은 잘 쓰지 않는 것과 비슷하다.

  글자 정보를 저장하는데 가장 많이 사용되는 방식은 ASCII 코드 방식이다. 영문 글자를 정해진 미리 약속한 이진 코드로 변환하게 되고 해당 이진코드를 받아 글자를 읽는 대표적 방식이다. 우리가 웹에서 보는 문자 체계가 UTF-8인데, 바로 아스키 코드 방식을 활용해 만들었다. 하지만 아스키코드는 우리가 사용하는 알파벳의 빈도수에 대한 고려를 전혀 하지 않는다. 알파벳에서 많이 쓰게 되는 글자에 대한 고려를 하지 않고 부호화-복호화 과정을 거친다. 만약 우리가 많이 사용하는 글자를 간단한 과정으로 부호화할 수 있는 체계를 만든다면 조금 시간, 공간적 자원을 아낄 수 있지 않을까라고 생각하게 되었고, 이 이론을 만든 사람이 바로 데이비드 허프만이다.

1. 아스키 코드(ASCII Code)

  허프만 부호화를 이해하기 위해 우선 아스키 코드에 대한 이해가 필요하다. 앞서도 언급했듯이 우리가 사용하는 자연어를 기계가 이해하는 기계어로 바꾸는 작업이다. 하지만, 각자 컴퓨터에서 고안한 방식대로 암호화를 진행하게 된다면 컴퓨터 A에서 부호화 작업을 한 방식을 자료를 받는 컴퓨터 B가 알고있어야 하는 조건이 붙게 된다. 그렇다면 A는 자신이 전달 할 정보와 더불어 부호화 방식 까지도 B에게 전달해야 하고, 보내게 되는 메세지의 크기가 커지게 된다. 그래서 우리는 글자에 대한 기계어 변환 방법은 전세계 모두가 약속한 방법을 쓰게 되는데 이 체계를 아스키 코드라고 한다.

 

  아스키 코드의 크기는 총 7비트의 크기를 가지고 있다. 따라서 아스키 코드 체계에서 우리가 표현할 수 있는 문제의 갯수는 총 128개이다.(2^7) 만약 129번째 문자가 새로 생기게 된다면, 현재의 아스키 코드 체계에서는 표현이 불가능하다. 심지어 그 중 33개의 문자는 우리가 사용하는 문자가 아닌 글자 제어 언어이다. 예를 들어, Null 값에 대한 표현이나 헤더 부분 시작과 끝을 알려주고, Tab 사용 등이 포함된다. 즉, 우리가 사용하는 출력 문자는 95개이다. 알파벳 대,소문자는 총 52개이고 숫자는 0~9까지 10개이다. 공백 역시 표현해야 하므로 우리가 출력할 수 있는 특수문자 개수는 32개에 불과하다. 우리는 32개의 문자 안에 원하는 정보를 출력 해내야 한다. 

아스키 코드로 'Hello world'를 표현하면

1001000 1100101 1101100 1101100 1101111

처럼 나오게 된다.

각 글자들이 어떻게 아스키 코드로 변환되어 있는지 아래 위키피디아에 상세하게 잘 나타나있다.

(위키 백과 - 아스키코드 : https://ko.wikipedia.org/wiki/ASCII)

2. 허프만 부호화(Huffman Coding)

  허프만 부호화는 글자 압축 방법이자 무손실 압축의 일종이다. 허프만 부호화의 핵심은 글자수 출현 빈도라는 사전 정보를 알고 있어야만 한다. 즉 허프만 부호화를 구현하기 위해서 우선적으로 글자 빈도에 대한 학습 작업이 선행 되어야만 한다. 이 작업을 먼저 실시해보자. 이 분석을 위해서 아래의 문장에 대한 허프만 부호화를 실시를 예시로 들어보도록 하겠다.

"don't drink and drive"

  위의 문장에는 D가 총 4번으로 가장 많이 나오고, o는 한번, n은 총 3번의 빈도수를 가진다. 이 방식으로 모든 글자에 대한 빈도수를 표현할 수 있고 아래와 같다.

  

  이렇게 글자수 빈도 테이블을 만들었다면 이제 해당 글자를 트리 구조 안에 할당 해야 한다. 허프만 트리에서 기본적으로 왼쪽 서브트리는 0이고, 우측 서브트리는 1이다. 이점을 우선 기억하고 있자. 그리고 이와 더불어서 기억할 점이 많은 빈도수를 가진 글자 일수록 이진화된 부호 크기가 작아야 한다. 이 2가지 원칙을 알고 있다면 아래의 과정이 쉽게 이해가 될 것이다.

  앞에서 구한 테이블을 하나의 노드로 만든다. 즉 글자와 빈도수 정보를 동시에 가지고 있는 노드로 구성을 하고, 이 노드의 빈도수가 가장 적은 값 부터 순서대로 정렬한다. 정렬된 순서대로 Queue에 삽입하여 가장 빈도수가 적은 노드를 먼저 사용할 수 있도록 한다.

Queue : [o , 1] / [' , 1] / [t , 1] / [k , 1] / [a, 1] / [v , 1] / [e , 1] / [r , 2] / [i , 2] / [n , 3] / [null , 3] / [d , 4]

  위 빈도수 테이블 중 가장 적게 나온 글자를 순서대로 선택한다. 그렇다면 'o'와 ' ' ' 이 가장 먼저 선택된다. 빈도수가 모두 1 이었다는 점을 기억하고 아래와 같은 구조의 트리를 만든다. 

  문장에서 나온 두 글자 O와 '을 이용해 이진 트리를 만들게 된다. 이 때, 두 글자의 빈도수의 합계인 2도 사용하게 되므로 기억해두자. 이렇게 형성된 루트 노드를 다시 최소 Queue에 넣는다. 새로운 Queue가 형성되고, 앞서 방법을 반복한다. 새로 형성한 빈도수 2의 루트 노드 역시 해당 Queue에서 정렬 작업을 거친다. 아래 Queue에서 구분을 위해 A라고 표시하도록 하겠다.

Queue : [t , 1] / [k , 1] / [a, 1] / [v , 1] / [e , 1] / [A , 2] / [r , 2] / [i , 2] / [n , 3] / [null , 3] / [d , 4]

  이번에 선택되는 2개의 노드는 't'와 'k' 이다. 따라서 위의 그림과 같은 노드가 동일하게 만들어 질 것이다. 이 노드를 편의 상 B라고 하자. a와 v 또한 그 다음 생성 될 것이고 이 노드는 C라고 하자.

  Queue :  [e , 1] / [A , 2] / [B , 2] / [C , 2] / [r , 2] / [i , 2] / [n , 3] / [null , 3] / [d , 4]

  임의로 만든 노드라고 해도 같은 방식으로 진행하면 된다. e 노드와 A노드를 묶어 새로운 노드를 만들면 된다. 두 노드의 빈도수 합은 3이고, 아래와 같이 트리가 형성된다. 이 노드를 편의상 D라고 부르자.

  Queue :  [B , 2] / [C , 2] / [r , 2] / [i , 2] / [D , 3] / [n , 3] / [null , 3] / [d , 4]

  이와 같이 빈도수 합계가 작은 노드들을 계속 연결 시켜 나면 허프만 트리가 완성된다.

  이제 처음 말한 왼쪽 서브트리는 0, 오른쪽 서브트리는 1의 원칙을 적용시키면 된다. 루트노드 부터 시작해 가장 하위 노드에 도달 할 때 까지 이 원칙을 통해 문자 부호를 복호화 한다. 예를 들어 o의 경우 루트 노드부터 찾아 들어가게 된다면 0, 0, 0, 1, 0의 순서로 찾아 들어가게 되어 o의 부호는 00010이 된다. d의 경우에는 1, 1의 순서로 찾게 되므로 부호는 11이 된다. 이 처럼 각 문자의 부호를 구한다.

  3. 허프만 부호화 코딩

  허프만 부호화는 노드 만들기, 트리 만들기, 빈도수 체크 등 다양한 과정을 통해 만들게 된다. 보여주는 예제는 필자의 낮은 개발 능력으로 구현하였기 때문에 가장 좋은 방법이 아닐 수 있다. 그렇기에 해당 코드와 Github에 있는 다른 코드를 같이 참고하면 더욱 좋을 듯 하다. 물론, 가장 좋은 방법은 자신이 직접 코딩하고 다른 사람의 코드를 비교해 보는 것이다.

  필자가 요즘 세계2차대전 서적에 보는 것에 빠져서 아래의 글자에 대해 허프만 부호화 결과를 출력해보려고 한다. 아래 문단은 위키 백과의 '버나드 몽고메리' 항목에 있는 첫 문단이다.

Bernard Montgomery   Field Marshal Bernard Law Montgomery, 1st Viscount Montgomery of Alamein, KG, GCB, DSO, PC, DL, nicknamed Monty and The Spartan General, was a senior British Army officer who fought in both the First World War and the Second World War. He saw action in the First World War as a junior officer of the Royal Warwickshire Regiment. At Meteren, near the Belgian border at Bailleul, he was shot through the right lung by a sniper, during the First Battle of Ypres. He returned to the Western Front as a general staff officer and took part in the Battle of Arras in April and May 1917. He also took part in the Battle of Passchendaele in late 1917 before finishing the war as chief of staff of the 47th Division. In the inter-war years he commanded the 17th Service Battalion, Royal Fusiliers and, later, the 1st Battalion, Royal Warwickshire Regiment before becoming commander of 9th Infantry Brigade and then General Officer Commanding 8th Infantry Division. During the Second World War he commanded the British Eighth Army from August 1942 in the Western Desert until the final Allied victory in Tunisia in May 1943. This command included the Second Battle of El Alamein, a turning point in the Western Desert Campaign. He subsequently commanded the British Eighth Army during the Allied invasion of Sicily and the Allied invasion of Italy. He was in command of all Allied ground forces during Operation Overlord from the initial landings until after the Battle of Normandy. He then continued in command of the 21st Army Group for the rest of the campaign in North West Europe. The failed airborne attempt to bridge the Rhine at Arnhem in Holland was with 21st Army Group personnel, however was successful with a subsequent Allied Rhine crossing. When German armoured forces attacked American lines in the Battle of the Bulge forcing them to retreat, Montgomery was given command of the US First Army and the US Ninth Army, stopping the German advance and sending them into reverse. On 4 May 1945 he took the German surrender at Lüneburg Heath in Northern Germany. After the war he became Commander-in-Chief of the British Army of the Rhine in Germany and then Chief of the Imperial General Staff. From 1948 to 1951 he served as Chairman of the Commanders-in-Chief Committee of the Western Union. He then served as NATO Deputy Supreme Allied Commander Europe until his retirement in 1958.

  이번 코딩에서는 여러개의 클래스를 작성했다. 자세한 코드를 이곳에 올리게 되면 게시글의 길이가 너무 방대해 지기에 Github링크를 올려 두었습니다.

(총 6개의 클래스로 나눠 만들었습니다!)

코드 : https://github.com/adrian0220/HuffmanCode

P.S. 워낙 코드 량이 많다보니 아래 링크에 나온 코드를 참고하여 개발했습니다.

(참조 코드 : https://codereview.stackexchange.com/questions/44473/huffman-code-implementation)