허프만 코딩
핵심 아이디어: 자주 나타나는 객체를 적은 비트 수로 인코딩하고, 드물게 나타나는 객체는 더 많은 비트 수로 인코딩한다.
이 방식으로 모든 타입의 객체를 인코딩할 수 있지만, 주로 바이트 스트림을 압축하는 데 사용한다. 다음 텍스트를 예로 들어보자. 각 문자가 1바이트를 차지한다.
so much words wow many compression
각 바이트가 몇 번이나 등장하는지 세어보면, 어떤 바이트는 더 자주 나타나고 어떤 바이트는 덜 나타난다는 것을 알 수 있다.
space: 5 u: 1
o: 5 h: 1
s: 4 d: 1
m: 3 a: 1
w: 3 y: 1
c: 2 p: 1
r: 2 e: 1
n: 2 i: 1
이제 각 바이트에 비트 문자열을 할당한다. 더 자주 나타나는 바이트일수록 더 적은 비트 수를 할당한다. 결과는 다음과 같을 수 있다.
space: 5 010 u: 1 11001
o: 5 000 h: 1 10001
s: 4 101 d: 1 11010
m: 3 111 a: 1 11011
w: 3 0010 y: 1 01111
c: 2 0011 p: 1 11000
r: 2 1001 e: 1 01110
n: 2 0110 i: 1 10000
이제 원래 바이트를 이 비트 문자열로 대체하면 압축된 출력은 다음과 같이 된다.
101 000 010 111 11001 0011 10001 010 0010 000 1001 11010 101
s o _ m u c h _ w o r d s
010 0010 000 0010 010 111 11011 0110 01111 010 0011 000 111
_ w o w _ m a n y _ c o m
11000 1001 01110 101 101 10000 000 0110 0
p r e s s i o n
마지막에 추가된 0비트는 전체 바이트 수를 맞추기 위해 붙였다. 원래 34바이트를 단 16바이트로 압축했고, 이는 50% 이상의 공간 절약 효과를 보여준다.
이 비트를 디코딩하려면 원래의 빈도 테이블이 필요하다. 이 테이블은 압축된 데이터와 함께 전송되거나 저장되어야 한다. 그렇지 않으면 디코더가 비트를 어떻게 해석해야 할지 알 수 없다. 빈도 테이블의 오버헤드(약 1킬로바이트) 때문에, 작은 입력에 대해 허프만 인코딩을 사용하는 것은 이점이 없다.
동작 원리
바이트 스트림을 압축할 때, 알고리즘은 먼저 각 바이트가 얼마나 자주 나타나는지를 세는 빈도 테이블을 만든다. 이 테이블을 기반으로 알고리즘은 입력 바이트 각각에 대한 비트 문자열을 설명하는 이진 트리를 생성한다.
예제에서 이 트리는 다음과 같다:
트리에는 16개의 리프 노드(회색)가 있다. 각 리프 노드는 입력에서 나온 바이트 값을 나타내며, 해당 값이 몇 번 나타나는지도 표시한다. 다른 노드는 "중간" 노드다. 이 노드에 표시된 숫자는 자식 노드의 빈도를 합한 값이다. 따라서 루트 노드의 숫자는 입력된 바이트의 총 개수를 나타낸다.
노드 사이의 간선은 "1" 또는 "0"이다. 이 값은 리프 노드의 비트 인코딩에 해당한다. 각 왼쪽 가지는 항상 1이고, 오른쪽 가지는 항상 0임을 주목하자.
압축은 입력 바이트를 순회하면서 각 바이트에 대해 루트 노드에서 해당 바이트의 리프 노드까지 트리를 탐색하는 과정이다. 왼쪽 가지를 택할 때마다 1비트를 내보내고, 오른쪽 가지를 택할 때는 0비트를 내보낸다.
예를 들어, 루트 노드에서 c로 가려면 오른쪽(0), 다시 오른쪽(0), 왼쪽(1), 다시 왼쪽(1)으로 이동한다. 이렇게 하면 c의 허프만 코드는 0011이 된다.
압축 해제는 정확히 반대 방식으로 동작한다. 압축된 비트를 하나씩 읽어가며 트리를 탐색하다가 리프 노드에 도달하면, 그 리프 노드의 값이 압축 해제된 바이트가 된다. 예를 들어, 비트가 11010이라면 루트에서 시작해 왼쪽, 다시 왼쪽, 오른쪽, 왼쪽, 마지막으로 오른쪽으로 이동해 d에 도달한다.
코드
실제 허프만 코딩 방식을 다루기 전에, NSData 객체에 개별 비트를 쓰는 헬퍼 코드를 살펴보면 도움이 된다. NSData가 이해할 수 있는 가장 작은 데이터 단위는 바이트지만, 우리는 비트 단위로 작업하기 때문에 두 단위 간 변환이 필요하다.
public class BitWriter {
public var data = NSMutableData()
var outByte: UInt8 = 0
var outCount = 0
public func writeBit(bit: Bool) {
if outCount == 8 {
data.append(&outByte, length: 1)
outCount = 0
}
outByte = (outByte << 1) | (bit ? 1 : 0)
outCount += 1
}
public func flush() {
if outCount > 0 {
if outCount < 8 {
let diff = UInt8(8 - outCount)
outByte <<= diff
}
data.append(&outByte, length: 1)
}
}
}NSData에 비트를 추가하려면 writeBit()을 호출하면 된다. 이 헬퍼 객체는 각 새로운 비트를 outByte 변수에 담는다. 8비트를 쓰면 outByte가 NSData 객체에 실제로 추가된다.
flush() 메서드는 마지막 바이트를 출력하는 데 사용된다. 압축된 비트 수가 8의 배수로 딱 떨어지지 않을 수 있기 때문에, 끝에 여분의 비트가 남을 수 있다. 이 경우 flush()는 몇 개의 0 비트를 추가하여 전체 바이트를 쓰도록 보장한다.
다음은 NSData에서 개별 비트를 읽는 비슷한 헬퍼 객체다:
public class BitReader {
var ptr: UnsafePointer<UInt8>
var inByte: UInt8 = 0
var inCount = 8
public init(data: NSData) {
ptr = data.bytes.assumingMemoryBound(to: UInt8.self)
}
public func readBit() -> Bool {
if inCount == 8 {
inByte = ptr.pointee // 다음 바이트를 로드
inCount = 0
ptr = ptr.successor()
}
let bit = inByte & 0x80 // 다음 비트를 읽음
inByte <<= 1
inCount += 1
return bit == 0 ? false : true
}
}이 헬퍼 객체를 사용하면 NSData 객체에서 한 바이트 전체를 읽어 inByte에 저장할 수 있다. 그런 다음 readBit()은 해당 바이트에서 개별 비트를 반환한다. readBit()을 8번 호출하면 NSData에서 다음 바이트를 읽는다.
참고: 이와 같은 비트 조작에 익숙하지 않다면, 이 두 헬퍼 객체가 비트를 쓰고 읽는 작업을 단순화해 준다는 점만 이해하면 된다.
빈도 테이블
허프만 압축의 첫 단계는 전체 입력 스트림을 읽고 빈도 테이블을 만드는 것이다. 이 테이블은 가능한 모든 256개의 바이트 값을 나열하고, 입력 데이터에서 각 바이트가 얼마나 자주 나타나는지 보여준다.
이 빈도 정보를 딕셔너리나 배열에 저장할 수 있지만, 트리를 구성해야 하므로 빈도 테이블을 트리의 리프 노드로 저장할 수도 있다.
필요한 정의는 다음과 같다:
class Huffman {
typealias NodeIndex = Int
struct Node {
var count = 0
var index: NodeIndex = -1
var parent: NodeIndex = -1
var left: NodeIndex = -1
var right: NodeIndex = -1
}
var tree = [Node](repeating: Node(), count: 256)
var root: NodeIndex = -1
}트리 구조는 tree 배열에 저장되며 Node 객체로 구성된다. 이는 이진 트리이므로 각 노드는 두 개의 자식 노드인 left와 right, 그리고 부모 노드를 가리키는 parent 참조가 필요하다. 일반적인 이진 트리와 달리, 이 노드들은 서로를 가리키기 위해 포인터를 사용하지 않고 tree 배열의 간단한 정수 인덱스를 사용한다. (노드 자체의 배열 index도 저장하는데, 이 이유는 나중에 명확해진다.)
현재 tree는 256개의 항목을 담을 수 있다. 이는 리프 노드를 위한 공간으로, 가능한 256개의 바이트 값을 나타낸다. 물론 입력 데이터에 따라 이 모든 값이 사용되지는 않을 수 있다. 나중에 실제 트리를 구성하면서 더 많은 노드를 추가할 것이다. 현재는 트리가 아직 존재하지 않는다. 256개의 독립된 리프 노드가 있으며, 이들 사이에는 연결이 없다. 모든 노드의 카운트는 0이다.
입력 데이터에서 각 바이트가 얼마나 자주 나타나는지 세기 위해 다음 메서드를 사용한다:
fileprivate func countByteFrequency(inData data: NSData) {
var ptr = data.bytes.assumingMemoryBound(to: UInt8.self)
for _ in 0..<data.length {
let i = Int(ptr.pointee)
tree[i].count += 1
tree[i].index = i
ptr = ptr.successor()
}
}이 메서드는 NSData 객체를 처음부터 끝까지 순회하며 각 바이트에 대해 해당 리프 노드의 count를 증가시킨다. countByteFrequency()가 완료되면 tree 배열의 처음 256개 Node 객체가 빈도 테이블을 나타낸다.
허프만으로 압축된 데이터 블록을 압축 해제하려면 원본 빈도 테이블이 필요하다. 압축된 데이터를 파일에 쓴다면, 파일 어딘가에 빈도 테이블을 포함시켜야 한다.
tree 배열의 처음 256개 요소를 덤프할 수도 있지만, 이는 효율적이지 않다. 이 256개 요소가 모두 사용되지는 않으며, parent, right, left 포인터를 직렬화할 필요도 없다. 필요한 것은 빈도 정보뿐이며 전체 트리가 아니다.
대신, 불필요한 부분을 제외한 빈도 테이블을 내보내는 메서드를 추가한다:
struct Freq {
var byte: UInt8 = 0
var count = 0
}
func frequencyTable() -> [Freq] {
var a = [Freq]()
for i in 0..<256 where tree[i].count > 0 {
a.append(Freq(byte: UInt8(i), count: tree[i].count))
}
return a
}frequencyTable() 메서드는 트리의 처음 256개 노드를 살펴보지만, 사용된 노드만 남기고 parent, left, right 포인터는 제외한다. 이 메서드는 Freq 객체 배열을 반환한다. 이 배열을 압축된 데이터와 함께 직렬화해야 나중에 올바르게 압축 해제할 수 있다.
트리 구조
예제를 위해 압축 트리를 다시 살펴보자:
리프 노드는 입력 데이터에 실제로 존재하는 바이트를 나타낸다. 중간 노드는 리프 노드를 연결하며, 자주 사용되는 바이트 값으로 가는 경로가 덜 사용되는 값으로 가는 경로보다 짧아지도록 구성된다. 예제에서 m, s, 공백, o가 가장 빈번하게 등장하는 문자이며, 트리에서 가장 상위에 위치한다.
트리를 구축하는 과정은 다음과 같다:
- 아직 부모 노드가 없는 가장 작은 카운트를 가진 두 노드를 찾는다.
- 이 두 노드를 연결하는 새로운 부모 노드를 생성한다.
- 부모 노드가 없는 노드가 하나만 남을 때까지 이 과정을 반복한다. 이 마지막 노드가 트리의 루트 노드가 된다.
이 과정은 우선순위 큐를 사용하기에 이상적이다. 우선순위 큐는 최소값을 빠르게 찾도록 최적화된 데이터 구조다. 여기서는 가장 작은 카운트를 가진 노드를 반복적으로 찾아야 한다.
buildTree() 함수는 다음과 같이 구현된다:
fileprivate func buildTree() {
var queue = PriorityQueue<Node>(sort: { $0.count < $1.count })
for node in tree where node.count > 0 {
queue.enqueue(node) // 1
}
while queue.count > 1 {
let node1 = queue.dequeue()! // 2
let node2 = queue.dequeue()!
var parentNode = Node() // 3
parentNode.count = node1.count + node2.count
parentNode.left = node1.index
parentNode.right = node2.index
parentNode.index = tree.count
tree.append(parentNode)
tree[node1.index].parent = parentNode.index // 4
tree[node2.index].parent = parentNode.index
queue.enqueue(parentNode) // 5
}
let rootNode = queue.dequeue()! // 6
root = rootNode.index
}이 함수의 동작을 단계별로 살펴보자:
-
우선순위 큐를 생성하고, 카운트가 1 이상인 모든 리프 노드를 큐에 추가한다. (카운트가 0이면 해당 바이트 값이 입력 데이터에 존재하지 않음을 의미한다.)
PriorityQueue객체는 노드를 카운트 기준으로 정렬하므로, 가장 작은 카운트를 가진 노드가 항상 먼저 큐에서 제거된다. -
큐에 두 개 이상의 노드가 남아 있는 동안, 큐의 맨 앞에 있는 두 노드를 제거한다. 최소 우선순위 큐이므로, 이 두 노드는 아직 부모 노드가 없는 가장 작은 카운트를 가진 노드다.
-
node1과node2를 연결하는 새로운 중간 노드를 생성한다. 이 새 노드의 카운트는node1과node2의 카운트를 합한 값이다. 노드는 실제 포인터 대신 배열 인덱스를 사용해 연결되므로,node1.index와node2.index를 통해tree배열에서 해당 노드를 찾는다. (이 때문에Node는 자신의 인덱스를 알고 있어야 한다.) -
두 노드를 새로운 부모 노드에 연결한다. 이제 이 중간 노드가 트리의 일부가 된다.
-
새로운 중간 노드를 다시 큐에 추가한다. 이 시점에서
node1과node2처리가 끝났지만,parentNode는 아직 트리의 다른 노드와 연결되어야 한다. -
큐에 노드가 하나만 남을 때까지 2-5단계를 반복한다. 이 마지막 노드가 트리의 루트 노드가 되며, 이로써 트리 구축이 완료된다.
이 과정을 시각적으로 보여주는 애니메이션은 다음과 같다:
참고: 우선순위 큐 대신
tree배열을 반복적으로 순회하며 다음으로 가장 작은 두 노드를 찾을 수도 있다. 하지만 이 방법은 압축기를 **O(n^2)**로 느리게 만든다. 우선순위 큐를 사용하면 실행 시간이 **O(n log n)**로 단축되며, 여기서 n은 노드의 수를 의미한다.
재미있는 사실: 이진 트리의 특성상 x개의 리프 노드가 있다면 최대 x - 1개의 추가 노드를 트리에 포함할 수 있다. 최대 256개의 리프 노드가 존재할 수 있으므로, 트리에는 총 511개를 넘지 않는 노드만 존재한다.
압축
이제 빈도 테이블로부터 압축 트리를 만드는 방법을 알았으므로, NSData 객체의 내용을 압축하는 데 이를 사용할 수 있다. 다음은 그 코드다:
public func compressData(data: NSData) -> NSData {
countByteFrequency(inData: data)
buildTree()
let writer = BitWriter()
var ptr = data.bytes.assumingMemoryBound(to: UInt8.self)
for _ in 0..<data.length {
let c = ptr.pointee
let i = Int(c)
traverseTree(writer: writer, nodeIndex: i, childIndex: -1)
ptr = ptr.successor()
}
writer.flush()
return writer.data
}이 코드는 먼저 countByteFrequency()를 호출해 빈도 테이블을 만들고, buildTree()를 호출해 압축 트리를 구성한다. 또한 개별 비트를 쓰기 위해 BitWriter 객체를 생성한다.
그런 다음, 입력 데이터 전체를 반복하며 각 바이트에 대해 traverseTree()를 호출한다. 이 메서드는 트리 노드를 따라가며 각 노드에 대해 1 또는 0 비트를 쓴다. 마지막으로 BitWriter의 데이터 객체를 반환한다.
참고: 압축은 항상 입력 데이터를 두 번 통과해야 한다. 첫 번째는 빈도 테이블을 만들기 위함이고, 두 번째는 바이트를 압축된 비트 시퀀스로 변환하기 위함이다.
흥미로운 부분은 traverseTree()에서 일어난다. 이 메서드는 재귀적으로 동작한다:
private func traverseTree(writer: BitWriter, nodeIndex h: Int, childIndex child: Int) {
if tree[h].parent != -1 {
traverseTree(writer: writer, nodeIndex: tree[h].parent, childIndex: h)
}
if child != -1 {
if child == tree[h].left {
writer.writeBit(bit: true)
} else if child == tree[h].right {
writer.writeBit(bit: false)
}
}
}compressData()에서 이 메서드를 호출할 때, nodeIndex 파라미터는 인코딩해야 할 바이트에 해당하는 리프 노드의 배열 인덱스다. 이 메서드는 리프 노드에서 루트 노드까지 재귀적으로 올라간 다음, 다시 내려온다.
루트에서 리프 노드로 내려오는 동안, 만나는 각 노드에 대해 1 비트 또는 0 비트를 쓴다. 자식 노드가 왼쪽 노드라면 1을, 오른쪽 노드라면 0을 출력한다.
다음 그림을 보자:
트리 그림은 각 노드 사이의 간선에 0 또는 1을 표시하지만, 실제로 0과 1 비트는 트리에 저장되지 않는다! 규칙은 왼쪽 가지를 따라가면 1 비트를 쓰고, 오른쪽 가지를 따라가면 0 비트를 쓰는 것이다. 따라서 방향만 알면 쓸 비트 값을 결정할 수 있다.
compressData() 메서드는 다음과 같이 사용한다:
let s1 = "so much words wow many compression"
if let originalData = s1.dataUsingEncoding(NSUTF8StringEncoding) {
let huffman1 = Huffman()
let compressedData = huffman1.compressData(originalData)
print(compressedData.length)
}압축 해제
압축 해제는 압축의 역과정이다. 그러나 압축된 비트는 빈도 테이블 없이는 쓸모가 없다. 앞서 언급했듯이, frequencyTable() 메서드는 Freq 객체의 배열을 반환한다. 압축된 데이터를 파일에 저장하거나 네트워크로 전송할 때, 이 [Freq] 배열도 함께 저장해야 한다.
먼저 [Freq] 배열을 다시 압축 트리로 변환하는 방법이 필요하다:
fileprivate func restoreTree(fromTable frequencyTable: [Freq]) {
for freq in frequencyTable {
let i = Int(freq.byte)
tree[i].count = freq.count
tree[i].index = i
}
buildTree()
}Freq 객체를 리프 노드로 변환한 후, buildTree()를 호출해 나머지 작업을 수행한다.
다음은 Huffman으로 인코딩된 비트와 빈도 테이블을 포함한 NSData 객체를 받아 원본 데이터를 반환하는 decompressData()의 코드다:
func decompressData(data: NSData, frequencyTable: [Freq]) -> NSData {
restoreTree(fromTable: frequencyTable)
let reader = BitReader(data: data)
let outData = NSMutableData()
let byteCount = tree[root].count
var i = 0
while i < byteCount {
var b = findLeafNode(reader: reader, nodeIndex: root)
outData.append(&b, length: 1)
i += 1
}
return outData
}이 코드는 트리를 탐색하기 위한 헬퍼 메서드도 사용한다:
private func findLeafNode(reader reader: BitReader, nodeIndex: Int) -> UInt8 {
var h = nodeIndex
while tree[h].right != -1 {
if reader.readBit() {
h = tree[h].left
} else {
h = tree[h].right
}
}
return UInt8(h)
}findLeafNode()는 루트에서 시작해 nodeIndex로 주어진 리프 노드까지 트리를 탐색한다. 중간 노드마다 새로운 비트를 읽고, 그 값에 따라 왼쪽(비트가 1) 또는 오른쪽(비트가 0)으로 이동한다. 리프 노드에 도달하면, 그 인덱스를 반환한다. 이 인덱스는 원본 바이트 값과 동일하다.
이 과정을 그림으로 나타내면 다음과 같다:
압축 해제 메서드를 사용하는 방법은 다음과 같다:
let frequencyTable = huffman1.frequencyTable()
let huffman2 = Huffman()
let decompressedData = huffman2.decompressData(compressedData, frequencyTable: frequencyTable)
let s2 = String(data: decompressedData, encoding: NSUTF8StringEncoding)!먼저 빈도 테이블을 가져온다(이 경우 데이터를 인코딩한 Huffman 객체에서). 그런 다음 decompressData()를 호출한다. 결과로 나온 문자열은 처음에 압축한 문자열과 동일해야 한다.
이 과정의 세부 사항은 Playground에서 확인할 수 있다.
함께 보기
이 코드는 Dr. Dobb's Magazine의 1991년 2월호와 1992년 10월호에 실린 Al Stevens의 C 프로그래밍 칼럼을 바탕으로 작성되었다.
Swift Algorithm Club을 위해 Matthijs Hollemans가 작성