[Swift]허프만 코딩 구현 2 - 문자열 추출

이전 포스팅에서 Swift를 이용해 문자열 압축한 데에 이어 이번에는 문자열 추출을 구현하려고 한다. 

 

지난 포스팅의 마지막에 얻은 데이터의 형식은 다음과 같다. 문자열 형식으로 나타내었으며, 가독성을 위해 줄 바꿈 문자 뒤에는 실제로 줄 바꿈을 해주었다. 

 

"허프만 코드의 개수"\n

"허프만 코드"\n

"원래 문자열의 길이"\n

"압축된 문자열"\n

 

이제 해당 문자열을 가지고 원래 문자열을 추출해 보자. 

 

[A-a. 허프만 코드의 개수를 이용해 허프만 코드 반환]

먼저 허프만 코드의 개수를 구해야 한다. 문자열에서 해당 값은 가장 첫 문자열이다. 각각의 문자열은 줄 바꿈으로 구분되어 있기 때문에, 줄 바꿈 전까지의 문자열을 읽어 해당 문자열을 숫자로 바꿔주면 된다. 이러한 방식은 원래 문자열의 길이를 반환할 때도 사용되므로 함수로 만들었다. 

func getNumber(from index: inout Int) -> Int {
    let startIndex: Int = index
    while convertedStrInForm[index] != "\n" {
        index += 1
    }
    let res: Int = Int(convertedStrInForm[startIndex ..< index])!
    index += 1
    
    return res
}

 

그리고 입력받은 문자열을 조회하기 위한 인덱스를 추가해 주었다. 허프만 코드의 개수는 인덱스를 0으로 설정하면 반환받을 수 있다. 참고로 getNumber에서 파라미터로 전달되는 index는 입력받은 문자열을 순회하는 main index의 값을 변경시켜줘야 하므로,  inout 변수로 선언해 주었다. 

var mIndex: Int = 0             // main index
let huffmanCodesCnt: Int = getNumber(from: &mIndex)

다음으로 huffmanCodesCnt 만큼 허프만 코드를 반환받으면 된다. 

 

허프만 코드는 이전 포스팅과 마찬가지로 딕셔너리로 선언을 해주었다. 다만 제네릭 타입을 달리 해주었는데, 그 이유는 key와 value에 넣을 값이 다르기 때문이다. 이전에는 key에 문자를 넣고, value에 이진 문자열을 저장했지만, 이번에는 key에 이진 문자열을 넣고, value에 문자를 넣어 주어야 한다. 딕셔너리는 key를 기준으로 value를 조회하기 때문에, 압축된 문자열을 원래 문자열로 돌리기 위해서는 key를 이진 문자열로 해줘야 한다. 따라서 Dictionary<String, Character> 타입으로 선언해 주었다. 

 

허프만 코드도 허프만 코드의 개수를 구한 것과 마찬가지로 줄 바꿈을 기준으로 문자열을 출력하면 된다고 생각할 수도 있다. 하지만 허프만 코드를 구성하는 원소의 value 값이 줄 바꿈("\n")인 경우에는 어디까지가 허프만 코드를 구성하는 문자열인지 알 길이 없다. 따라서 허프만 코드의 개수를 먼저 반환받고 해당 값을 이용해 허프만 코드를 구하였다. 

 

입력받은 문자열에서 허프만 코드에 해당하는 부분은 다음과 같이 구성되어 있다. 

"원래 문자열을 구성하는 각각의 문자""이진 문자열"" "

끝이 공백으로 되어 있어 코드들 간에 구분을 하였는데, 여기서도 구성 문자가 공백인 경우를 생각해 볼 수 있다. 하지만 허프만 코드에서 문자는 무조건 한 글자이기 때문에, 해당 특성을 이용하면 문자에 대한 공백과 구분에 대한 공백을 구별할 수 있다. 

var huffmanCodes2: [String: Character] = [:]
while huffmanCodes2.count < huffmanCodesCnt {
    let char: Character = Character(convertedStrInForm[mIndex])
    mIndex += 1
    
    let startIndex = mIndex
    while convertedStrInForm[mIndex ..< mIndex + 1] != " " {
        mIndex += 1
    }
    
    let code: String = convertedStrInForm[startIndex ..< mIndex]
    huffmanCodes2.updateValue(char, forKey: code)
    mIndex += 1
}
mIndex += 1

압축에서 구한 huffmanCodes와 구분하기 위해 huffmanCodes2로 선언해주었다. 

 

[A-b. 원래 문자열의 길이와 압축된 문자열 반환]

문자열의 길이를 반환하는 방법은 앞에서 허프만 코드의 개수를 반환하는 방법과 동일해 설명은 생략한다. 

let strCnt: Int = getNumber(from: &mIndex)

 

그리고 압축된 문자열은 현재 mIndex부터 입력받은 문자열의 끝이므로 따로 반환할 필요는 없다. 

 

B 단계는 압축에서의 B 단계를 거꾸로 밟아 나가면 된다. 

 

[B-a. 입력된 ASCII 문자열을 십진수로 변환]

 

var decimals2: [UInt32] = []
while mIndex < convertedStrInForm.count {
    decimals2.append(UnicodeScalar(convertedStrInForm[mIndex])!.value)
    mIndex += 1
}

압축에서 구한 decimals와 구분하기 위해 decimals2로 선언해 주었다.

 

[B-b. 변환된 십진수를 7 자리의 이진 문자열로 변환]

이제 얻은 십진수들을 이진 문자열로 변환하는 작업이 필요하다. 근데 여기서 중요한 점은 십진수에 따라 이진수가 한 자리부터 일곱 자리 사이의 자릿수를 가질 수 있다는 점이다. 예를 들어 십진수 3은 이진수로 11이기 때문에 이진수로 두 자리가 되고, 십진수 38은 이진수로 100110이기 때문에 이진수로 여섯 자리가 된다. 하지만 압축을 구현할 때, 이진 문자열을 일곱 자리씩 끊어 십진수로 변환해 주었기 때문에, 일곱 자리로 맞춰 이진수로 변환하지 않으면 생략되는 문자가 존재할 수 있다. 따라서 십진수를 이진 문자열로 변환할 대 일곱 자리를 맞추기 위해 압 자리에 부족한 만큼 0을 추가해야 한다. 

 

var binStr2: String = ""
decimals2.forEach {
    let tmp: String = String($0, radix: 2)
    
    // pNumber 자리가 되도록 앞 부분을 0으로 채움
    for _ in 0 ..< (pNumber - tmp.count) {
        binStr2 += "0"
    }
    binStr2 += tmp
}

 

[B-c. 변환된 이진 문자열을 허프만 코드와 원래 문자열의 길이를 이용해 원래 문자열로 변환]

마지막으로 변환된 이진 문자열을 순서대로 조회하면서 huffmanCodes2에 key에 해당하는 값이 있으면 value를 반환해 바꿔 원래 문자열을 추출한다. 여기서 중요한 점은 이진 문자열을 언제까지 조회할 것인지 결정하는 것이다. 존재하는 이진 문자열의 끝까지 조회하면 된다고 생각할 수 있지만 그렇지 않다. 여기서 얻은 이진 문자열의 마지막 부분은, 압축에서 이진 문자열을 생성할 때, 자릿수를 맞추기 위해 채운 0일 수도 있기 때문이다. 

그래서 이진 문자열의 끝까지 반복하는 것이 아니라, 문자열의 길이가 원래 문자열의 길이와 같아질 때까지 반복하면 된다. 이러한 이유 때문에, 압축에서 마지막 문자열을 반환하기 전에 원래 문자열의 길이를 추가해 반환한 것이다. 

var originalStr: String = ""
var tmp: String = ""
var bIndex: Int = 0             // 이진 문자열 조회를 위한 index
while originalStr.count < strCnt {
    tmp += binStr[bIndex]
    if huffmanCodes2[tmp] != nil {
        originalStr += String(huffmanCodes2[tmp]!)
        tmp = ""
    }
    bIndex += 1
}

 

이렇게 추출까지 구현을 하였다. 이제 결과를 살펴보자. 

먼저 원래 문자열과 추출된 문자열은 같아 성공이다. 그리고 앞서 설명했듯이, 이진 문자열은 추출에서 구한 것이 압축에서 구한 것보다 길다. 압축에서의 이진 문자열보다 끝에 여섯 자리가 0으로 더 많다. 만약 원래 문자열의 길이를 생각하지 않고 이진 문자열의 끝까지 문자열로 변환했다면, 추출된 문자열은 끝에 000000에 해당하는 "bbb"를 더 출력했을 것이다. 

 

멀고도 먼 문자열 압축과 추출이 끝이 났다. 다음 시간에는 해당 알고리즘을 클래스로 묶고 검증하는 과정을 살펴보겠다.