[Swift] 허프만 코딩 구현 1 - 문자열 압축

Swift로 허프만 코드를 이용해 문자열을 압축하고 추출해 보려고 한다. 이번 포스팅에서는 문자열 압축을, 다음 포스팅에서는 문자열 추출을 구현하도록 하겠다. 

 

지난 시간에 살펴본 허프만 코드를 이용한 문자열 압축 및 출력 과정을 순서대로 구현해 보려고 한다. 

(압축 및 추출에 대한 전체 과정은 다음 링크 참고 https://taeminator1.tistory.com/52)

 

먼저 유용한 extension을 하나 추가하자. String에 대해 subscript를 통해 하나의 문자로 반환하거나, 범위 연산자를 통해 부분 문자열로 반환하는 확장이다. 

extension String {

    var length: Int {
        return count
    }

    subscript (i: Int) -> String {
        return self[i ..< i + 1]
    }

    func substring(fromIndex: Int) -> String {
        return self[min(fromIndex, length) ..< length]
    }

    func substring(toIndex: Int) -> String {
        return self[0 ..< max(0, toIndex)]
    }

    subscript (r: Range<Int>) -> String {
        let range = Range(uncheckedBounds: (lower: max(0, min(length, r.lowerBound)),
                                            upper: min(length, max(0, r.upperBound))))
        let start = index(startIndex, offsetBy: range.lowerBound)
        let end = index(start, offsetBy: range.upperBound - range.lowerBound)
        return String(self[start ..< end])
    }
}

(출처: https://stackoverflow.com/questions/24092884/get-nth-character-of-a-string-in-swift-programming-language)

 

이제 허프만 코드를 구해 보자. 

 

[A-a. 문자열을 구성하는 문자들에 대한빈도수를구하고 각각의 문자들에 대한 노드 생성]

문자들에 대한 빈도수를 구하기 전에, 노드에 대한 타입인 HuffmanNode를 정의해 주었다. 해당 노드의 클래스 다이어그램은 다음과 같다. 

 

먼저 속성 중에서, value는 노드를 대표하는 값이다. 처음 생성되는 각 문자에 대한 노드의 value는 빈도수이다. 그리고 문자열을 구성하는 문자에 대한 정보를 저장하기 위해 key 속성을 추가하였다. 해당 속성은 각 인스턴스마다 있을 수도 있고 없을 수도 있어 옵셔널로 선언해 주었다. 따라서 초기화 구문도 두 가지로 선언해 주었다. 

 

HuffmanNode클래스는 Comparable 프로토콜을 따르도록 해주었다. 비교는 각 인스턴스의 대푯값인 value의 대소 관계를 통해 이루어진다. 그리고 이진 트리를 생성하기 위해 관련 속성과 함수를 추가하였다. 

 

이제 본격적으로 문자열을 구성하는 문자들에 대한 빈도수를 구해 보자. 문자들에 대한 빈도수를 저장하기 위해 Dictionary<Character, Int> 타입을 이용했다.  선언된 Dictionary 타입의 속성의 key는 문자열을 구성하는 각각의 문자에 해당하고, value는 빈도수에 해당한다. key에 대한 원소를 추가하거나, value 값을 쉽게 조회하고 수정할 수 있어 해당 타입을 선택하였다. 

 

input이라는 문자열이 주어졌을 때, 빈도수를 구하는 코드는 다음과 같다. 

var keyFreqs: Dictionary<Character, Int> = [:]
input.forEach {
    if keyFreqs[$0] == nil {        // 새로운 문자 업데이트
        keyFreqs.updateValue(1, forKey: $0)
    }
    else {                          // 빈도수 증가
        keyFreqs[$0]! += 1
    }
}

 

다음으로 산출된 각 문자에 대한 빈도수에 대한 노드를 생성할 것이다. 허프만 코드를 구하기 위해서 우선순위 큐(Priority Queue)를 사용할 것이기 때문에, 노드를 생성하고 우선순위 큐에 넣는 작업까지 하였다. 우선순위 큐를 사용하는 이유는 바로 뒤에서 설명한다. 

 

우선순위 큐는 이전 포스팅에서 구현하였기 때문에 해당 포스팅을 참고하길 바란다. 

(https://taeminator1.tistory.com/46)

let priorityQueue: PriorityQueue = PriorityQueue<HuffmanNode>(handler: <)       // 최소 힙
keyFreqs.forEach { priorityQueue.insert(data: HuffmanNode($0.1, $0.0)) }

 

[A-b. 부모 노드가 없는 노드들 중 빈도수가 적은 두 노드를 선택]

다음 단계로 빈도수(HuffmanNode 인스턴스의 value에 해당)가 가장 적은 두 노드를 선택해야 한다. 여기서 생성된 노드를 우선순위 큐에 넣은 이유가 규명된다. 바로 value가 가장 작은 두 노드를 선택해야 하기 때문이다. value가 가장 작은 노드에게 가장 큰 우선순위를 부여하면(우선순위 큐의 인스턴스를 생성할 때, handler로 클로저 표현식 "<" 전달) 삭제 연산 두 번으로 원하는 두 노드를 쉽게 얻을 수 있다. 배열이나 연결 리스트로 구현하는 것보다 시간 복잡도 측면에서 효율적이기 때문에, 우선순위 큐를 사용하였다. 

 

이제 우선순위 큐의 pop 메서드를 통해 빈도수가 가장 적은 두 노드의 값을 반환받을 수 있다. 

let left: HuffmanNode = priorityQueue.pop()!.getData()
let right: HuffmanNode = priorityQueue.pop()!.getData()

 

[A-c. 선택된 두 노드의 빈도수를 더한 값에 대한 새로운 노드를 선택된 두 노드의 부모 노드로 생성]

앞에서 선택된 두 노드의 값을 더해 해당 값을 value로 갖는 새로운 노드를 생성한다. 생성된 노드는 선택된 두 노드의 부모 노드로 만들어 주기 위해 setLeft와 setRight 메서드를 사용했다. 그리고 생성된 노드는 이후에 노드를 선택할 때 후보에 포함되어야 하므로 우선순위 큐에 삽입했다. 

let tmp = HuffmanNode(left.getValue() + right.getValue())
tmp.setLeft(left)
tmp.setRight(right)
priorityQueue.insert(data: tmp)

 

[A-d. 부모 노드가 없는 노드가 한 개가 될 때까지 b 단계와 c 단계를 반복]

"부모 노드가 없는 노드가 한 개가 될 때까지"라는 말은 "우선순위 큐에 원소가 하나 남을 때까지"와 같은 말이다. 따라서 while문을 이용해 다음과 같이 구현하였다. 

while priorityQueue.getCount() != 1 {
    let left: HuffmanNode = priorityQueue.pop()!.getData()
    let right: HuffmanNode = priorityQueue.pop()!.getData()
    
    let tmp = HuffmanNode(left.getValue() + right.getValue())
    tmp.setLeft(left)
    tmp.setRight(right)
    priorityQueue.insert(data: tmp)
}

 

[A-e. 루트 노드부터 간선의 방향에 따라 0 또는 1을 대응시켜 최종적으로 각 문자에 대한 허프만 코드 도출]

허프만 코드를 저장하는 HuffmanCodes를 Dictionary<Character, String>로 선언해 주었다. key는 문자열을 구성하는 각각의 문자이고, value가 실제 허프만 코드(이진 문자열)이다. 추후 문자(value)를 통해 허프만 코드를 참조하기 위해 딕셔너리 타입으로 선언하였다. 

 

이제 우선순위 큐에 남은 노드를 반환받아(루트 노드) 해당 노드를 시작으로 자식 노드로 뻗어가면서 단말 노드에 대한 허프만 코드를 구하면 된다. 이를 위해 깊이 우선 탐색(DFS: Depth First Search)을 이용했다. 만약 해당 노드에 key 값이 존재하면(단말 노드면) 해당 노드에서 얻은 코드를 huffmanCodes에 추가하였다. 

let root: HuffmanNode = priorityQueue.pop()!.getData()
var huffmanCodes: Dictionary<Character, String> = [:]

func DFS(_ start: HuffmanNode, _ str: String) {
    if start.getKey() != nil {
        huffmanCodes.updateValue(str, forKey: start.getKey()!)
    }
    else {
        DFS(start.getLeft()!, str + "0")
        DFS(start.getRight()!, str + "1")
    }
}

DFS(root, "")

 

다음은 앞서 구한 허프만 코드를 가지고 입력 문자열을 압축하는 과정이다. 

 

[B-a. 입력된 문자열을 허프만 코드를 이용해 이진 문자열로 변환]

입력된 문자열을 이진 문자열로 반환하기 위해 map 함수를 사용하였다. 문자열을 구성하는 각 문자에 대한 허프만 코드를 조회하여 하나의 이진 문자열로 만들었다. 

let binStr: String = input.map { huffmanCodes[$0]! }.reduce("") { $0 + $1 }
let binStrCnt: Int = binStr.count

 

[B-b. 변환된 이진 문자열 7개씩 쪼개 십진수로 변환]

7이 반복적으로 사용되어 pNumber라는 속성에 할당하여 사용하였다. 

그리고 이진 문자열의 부분 문자열(7개씩 쪼개진)을 십진수로 변환해 주었다. 

let pNumber: Int = 7
var decimals: [Int] = []
var index: Int = 0
while index < binStrCnt {
    decimals.append(Int(binStr[index ..< index + pNumber], radix: 2)!)
    index += pNumber
}

 

여기에 추가로 자투리 이진 문자열에 대한 변형이 필요하다. 이전 포스팅(https://taeminator1.tistory.com/52)에서 허프만 코드를 구할 때, 7개가 안 되는 이진 문자열에 대해서는 마지막 부분을 0으로 채워 7개를 만들어 줘야 한다고 설명하였는데, 해당 작업을 여기서 구현해야 한다. 

if index != binStrCnt {
    index -= pNumber
    decimals.removeLast()        // pNumber 자리가 안 된 마지막 원소 제거
    
    var tmp: String = binStr[index ..< index + binStrCnt]
    index = binStrCnt
    // pNumber 자리가 되도록 뒷 부분을 0으로 채움
    while index % pNumber != 0 {
        tmp += "0"
        index += 1
    }
    
    decimals.append(Int(tmp, radix: 2)!)
}

 

[B-c. 변환된 십진수를 ASCII에 대응시켜 문자열로 변환]

다음으로 십진수에 대응하는 ASCII로 변환하는 작업이다. 해당 작업은 Swift에서 기본으로 제공하는 함수를 이용하면 쉽게 변환할 수 있다. 기존에 최대 7자리의 이진수를 이용해 십진수를 만들었으므로, ASCII에 대응되는 숫자가 127을 넘을 일은 없다. 

let compressedStr: String = decimals.map { String(UnicodeScalar($0)!) }.reduce("") { $0 + $1 }

 

[C-a. 추출에 필요한 데이터(허프만 코드의 개수, 허프만 코드, 원래 문자열의 길이)와 압축된 문자열을 합하여 반환]

이전 포스팅(https://taeminator1.tistory.com/52)에서 설명한 대로 추출에 필요한 데이터와 압축된 문자열을 합하여 반환한다. 각 문자열의 쓰임은 추출을 구현할 때 자세히 살펴보기로 하자. 

허프만 코드의 경우, 각각의 허프만 코드를 다음과 같이 구성하였다.

"허프만 코드에 해당하는 문자" + "허프만 코드" + " "

var convertedStrInForm: String = ""
// 허프만 코드의 개수
convertedStrInForm += String(huffmanCodes.count)
convertedStrInForm += "\n"

// 허프만 코드
huffmanCodes.forEach { convertedStrInForm += "\($0.key)\($0.value) " }
convertedStrInForm += "\n"

// 원래 문자열의 길이
convertedStrInForm += String(input.count)
convertedStrInForm += "\n"

// 압축된 문자열
convertedStrInForm += compressedStr

 

다음은 문자열 "bab bdca adcb ba daba ad ab acab ca ab dd"를 입력했을 때의 결과이다. 

최종 문자열이 이전 포스팅에서 도출한 아래의 결과와 다르다. 

"""

5

a01 b10 c000 d001  11 

41

"MbH\rg'6C0vd@

"""

 

이유는 허프만 코드가 이전 포스팅에서 구한 것과 다르기 때문이다. 허프만 코드가 다른 이유는 두 가지다.

먼저 딕셔너리에서 값을 불러올 때 순서가 정해져 있지 않기 때문이다. 우선순위 큐에 빈도수에 대한 노드를 넣기 위해서는 Dictionary로 선언된 속성에서 값을 반환받아야 하는데 반환 순서가 정해져 있지 않아 실행할 때마다, 우선순위 큐에 들어가는 노드의 순서가 달라지게 된다. 여기서 노드의 value 값이 같다면, 순서에 따라 허프만 코드가 달라질 수 있다. (이번 예제에서는 이 현상은 발생하지 않는다)

두 번째 이유는 생성한 이진 트리의 모양 때문이다. 아래 포스팅에서는 이진 트리를 보기 좋게 만들 때, 임의로 보기 좋게 만들었다. 하지만 방금 구현한 이진 트리에서는 , 부모 노드 왼쪽 자식 노드에는 작은 값을 갖는 노드를 넣고, 오른쪽 자식 노드에는 그다음 작은 값을 넣는다는 일정한 규칙에 의해 만들어졌다. 루트 노드로부터 방향에 따라 코드가 결정되기 때문에 이진 트리의 모양이 달라지면 허프만 코드 역시 달라지게 된다. 

 

하지만 아래 포스팅에서 언급했듯이 허프만 코드를 구성하는 이진 값이 중요한 것이 아니라 심벌로서 조건을 충족하느냐가 중요하기 때문에, 허프만 코드가 달라지는 것은 문제 삼지 않아도 된다. 

(https://taeminator1.tistory.com/51)