허프만 코딩 2 - 문자열 압축과 추출

지난 포스팅(https://taeminator1.tistory.com/51)에서 허프만 코딩이 무엇인지 알아보았고, 허프만 코드를 생성하는 방법과 허프만 코드가 "더 짧은 심벌 트릭"에서 적절한 심벌이 될 수 있는 이유에 대해 알아보았다. 

 

이번 시간에는 허프만 코드를 이용해 실제 압축과 추출을 구현하기 위한 전체 과정을 살펴보려고 한다. 크게 "압축"과 "추출" 두 가지 동작에 대해 설명할 것이다.

(추가로 동작이 제대로 이루어졌는지 확인하기 위한 "검증"도 필요할 수 있다)

1. 압축: 입력받은 문자열을 압축하여 새로운 문자열을 생성
2. 추출: 입력받은 문자열에서 원래 문자열 추출

전체 과정을 살펴본 다음, 문자열이 주어졌을 때, 각각의 과정의 결과가 어떻게 되는지 설명하려고 한다. 

 

먼저 전체 과정은 다음과 같다. 

 

이제 문자열로 "bab bdca adcb ba daba ad ab acab ca ab dd"가 주어졌을 때, 각각의 과정의 결과가 어떻게 되는지 확인해 보자. 

 

[1-A. 허프만 코드 구하기]

주어진 문자열이 이전 포스팅과 동일하기 때문에 아래 링크로 설명을 대체한다. 

https://taeminator1.tistory.com/51

 

다음과 같은 허프만 코드를 얻었다. 

 

• ["a": "01", "b": "10", "c": "000", "d": "001", " ": "11"]

[1-B. 허프만 코드를 이용해 문자열 압축하기]

 

<a. 입력된 문자열을 허프만 코드를 이용해 이진 문자열로 변환>

띄어쓰기(" ")도 문자라는 것을 잊으면 안 된다. 

 

• "bab bdca adcb ba daba ad ab acab ca ab dd"
  → "10011011100010000111010010001011100111001011001110100111011011010000110110000111011011001001"

<b. 변환된 이진 문자열을 7개씩 쪼개 십진수로 변환>

 

• "1001101" → 77
• "1100010" → 98
• "0001110" → 14
• "1001000" → 72
• "1011100" → 92
• "1110010" → 114
• "1100111" → 103
• "0100111" → 39
• "0110110" → 54
• "1000011" → 67
• "0110000" → 48
• "1110110" → 118
• "1100100" → 100
• "1" → "1000000" → 64

여기서 중요한 것은 마지막 1을 64에 대응시켰다는 것이다. 해제할 때도, 앞에서부터 7개씩 쪼갤 것이기 때문에 뒤를 0으로 채워 7자리로 맞춰줬다. 

 

<c. 변환된 십진수를 ASCII에 대응시켜 문자열로 변환>

이전 단계에서 이진 문자열을 7개씩 쪼갠 이유가 여기에 있다. 아스키는 7개의 비트로 이루어져 있어, 0부터 127까지의 십진수를 표현할 수 있다. 관련 내용은 아래 포스팅을 참고하길 바란다. 

https://taeminator1.tistory.com/50

 

• 77 → "M"
• 98 → "b"
• 14 → ""
• 72 → "H"
• 92 → "\"
• 114 → "r"
• 103 → "g"
• 39 → "'"
• 54 → "6"
• 67 → "C"
• 48 → "0"
• 118 → "v"
• 100 → "d"
• 64 → "@"

여기서 세 번째 문자는 ""이렇게 표시가 되어있는데, 실제 ASCII table을 참고하면 15 번째 ASCII는 제어 문자 SO(Shift Out)에 해당하여 문자이지만 보이질 않는다. (15번째인 이유는 0부터 시작하므로)

 

이렇게 반환된 각 문자를 붙여 문자열 "MbH\rg'6C0vd@"를 얻는다. 

 

[1-C. 추출 가능하도록 문자열을 구성하여 반환하기]

압축된 문자열만 가지고는 원래 문자열을 추출할 수 없다. 그래서 나는 허프만 코드의 개수, 허프만 코드, 원래 문자열의 길이를 추가하여 문자열을 반환하였다. 추가한 문자열의 쓰임은 추출을 구현할 때 자세히 살펴보기로 하자. 

 

"""

5

a01 b10 c000 d001  11 

41

"MbH\rg'6C0vd@

"""

 

첫 번째 줄에 허프만 코드의 개수를 넣고

두 번째 줄에는 허프만 코드를 key와 code를 붙여서 나타냈다. 각각의 허프만 코드는 공백으로 구분하여 넣었다. 

세 번째 줄에는 원래 문자열의 길이를, 

마지막 줄에는 압축된 문자열을 넣었다. 

 

2번 단계인 추출은 입력받은 문자열에서 부분 문자열들(허프만 코드의 개수, 허프만 코드, 압축된 문자열)을 추출하여, 1-B 단계를 거꾸로 진행하면 된다. 

 

이렇게 하면, 허프만 코드를 이용해 데이터를 압축하고, 압축된 데이터를 해제할 수 있다. 

 

이제 이렇게 구성한 절차를 실제 코드로 구현하는 일만 남았다. 다음 포스팅에서는 Swift를 이용해 실제 코드로 구현해 보겠다.