[Swift]허프만 코딩 구현 3 - 검증

검증하기 전에 압축과 추출에서 구현한 다양한 동작들을 구조체로 묶어보자. 

 

Compressor와 Extractor 구조체를 생성하였다. 코드는 지난 시간에 전부 구현을 하였기 때문에 클래스 다이어그램만 제시하고 따로 구현은 필요 없어 보인다. 

몇 가지 특성은 다음과 같다. 

 

• 두 구조체 모두 input을 속성으로 갖는데, 해당 속성은 입력받은 데이터를 의미한다. pNumber는 지난 시간과 동일하게 이진 문자열을 쪼개는 개수이다. ASCII가 7bit의 이진수를 나타내므로 기본값은 7이다. 
• Compressor 구조체의 makeHuffmanCodes()는 허프만 코드를 반환하는데, 이전에 설명한 바와 같이, 허프만 코드는 구할 때마다 값이 다를 수 있어 private으로 선언해 다른 곳에서의 사용을 방지하였다. 
• Extractor 구조체의 함수들은 Index를 기준으로 입력받은 문자열을 순회한다. 따라서 private으로 선언해 다른 곳에서의 사용을 방지하였다. 
• 각 구조체의 관련 단계는 오른쪽에 표시하였다. (참고 링크: https://taeminator1.tistory.com/52)

파일 단위로 데이터를 압축 및 추출하기 위해 다음과 같이 읽기/쓰기 함수를 추가하였다. 

아래 함수는 아래 링크를 참고하여 수정하였다. 

(https://medium.com/@CoreyWDavis/reading-writing-and-deleting-files-in-swift-197e886416b0)

// Desktop에 있는 파일 읽기
func readFileFromDesktop(fileName: String) -> String? {
    let directoryURL = FileManager.default.urls(for: .desktopDirectory, in: .userDomainMask)[0]
    let fileURL = URL(fileURLWithPath: fileName, relativeTo: directoryURL).appendingPathExtension("txt")
    
    var res: String?
    
    do {
        let data = try Data(contentsOf: fileURL)
        if let str = String(data: data, encoding: .utf8) {
            res = str
        }
    } catch {
        print("Unable to read the file")
    }
    
    return res
}

// Desktop에 파일 쓰기
func saveFileIntoDesktop(fileName: String, contents: String) {
    let directoryURL = FileManager.default.urls(for: .desktopDirectory, in: .userDomainMask)[0]
    let fileURL = URL(fileURLWithPath: fileName, relativeTo: directoryURL).appendingPathExtension("txt")
    
    guard let data = contents.data(using: .utf8) else {
        print("Unalbe to convert string to data")
        return
    }

    do {
        try data.write(to: fileURL)
        print("File saved: \(fileURL.absoluteURL)")
    } catch {
        print(error.localizedDescription)
    }
}

 

이제 검증을 위한 모든 준비가 끝났다. 

 

바탕화면에 origin이라는 텍스트 파일에 다음과 같이 입력하고 저장했다. 맥에서 .txt 파일 생성은 이전 포스팅(https://taeminator1.tistory.com/50)을 참고하면 된다. 

 

그리고 다음과 같이 코드를 작성하여 실행하였다. 

// "origin" 파일을 불러와 문자열로 반환하여 압축한 후 "conversion" 파일 저장
let originalStr: String = readFileFromDesktop(fileName: "origin")!
let compressor = Compressor(originalStr)
saveFileIntoDesktop(fileName: "conversion", contents: compressor.convertedStrInForm)

// "conversion" 파일을 불러와 문자열로 반환하여 추출한 후 "return" 파일 저장
let convertedStr: String = readFileFromDesktop(fileName: "conversion")!
let extractor = Extractor(convertedStr)
saveFileIntoDesktop(fileName: "return", contents: extractor.extractOriginalStr())

// "return" 파일을 불러와 문자열로 반환
let returnedStr: String = readFileFromDesktop(fileName: "return")!

// 원래 문자와 return 파일의 문자열 비교
if originalStr == returnedStr {
    print("SAME")
}
else {
    print("FAIL")
}

 

 

결과를 보면, 원래 문자열과 추출 후 문자열이 같은 것을 확인할 수 있다. 

 

다음은 바탕화면의 기존 파일과, 압축된 파일의 용량을 비교해 보자. 

아니 근데 이것이 웬 말인가..... 용량이 1 바이트 늘었다. 그 이유는 원래 문자열이 너무 짧아서 추출에 필요한 부가 데이터의 용량의 영향이 더 크기 때문이다. 

 

더 긴 문자열이 필요하다. 아래 사이트에서 의미 없는 문자열을 얻어 origin 파일을 수정해주었다. 

(https://www.lipsum.com)

이 번에는 무려? 2,884 바이트에 해당하는 문자열이다. 이전 문자열에 약 70배 큰 파일이다. 

이번에도 원래 문자열과 추출 후 문자열은 동일했다. 이제 얼마나 잘 압축이 되었나 확인해 보자. 

결과는 2,145 바이트! 기존 대비 25% 이상 감소한 것을 확인할 수 있었다. 

이는 아래와 같이 맥에서 제공하는 압축보다는 효율은 떨어지지만(맥에서 제공하는 압축은 기존 용량 대비 30% 이상 감소하였다), 그래도 어느 정도 압축이 잘되었다. 

 

압축 효율을 증가시킬 수 있는 방법은 없을까?? 몇 가지 시도해 보았다. 

 

첫 번째로, 쪼개는 이진 문자열의 개수에 따라 효율성이 어떻게 달라지는지 확인해 보았다. 다음과 같이 pNumber 값을 매개변수로 전달해주었다. 

// "origin" 파일을 불러와 문자열로 반환하여 압축한 후 "conversion" 파일 저장
let pNumer: Int = 6
let originalStr: String = readFileFromDesktop(fileName: "origin")!
let compressor = Compressor(originalStr, pNumber: pNumer)
saveFileIntoDesktop(fileName: "conversion", contents: compressor.convertedStrInForm)

// "conversion" 파일을 불러와 문자열로 반환하여 추출한 후 "return" 파일 저장
let convertedStr: String = readFileFromDesktop(fileName: "conversion")!
let extractor = Extractor(convertedStr, pNumber: pNumer)
saveFileIntoDesktop(fileName: "return", contents: extractor.extractOriginalStr())

// "return" 파일을 불러와 문자열로 반환
let returnedStr: String = readFileFromDesktop(fileName: "return")!

// 원래 문자와 return 파일의 문자열 비교
if originalStr == returnedStr {
    print("SAME")
}
else {
    print("DIFFERENT")
}

 

결과는 아래와 같다. 파일명 뒤에 pNumber의 값을 붙여 구분하였다. 

분리하는 자릿수에 따른 압축된 파일의 용량

7자리로 구분한 것이 가장 효율이 좋았고, 6자리, 8자리, 9자리 순으로 효율이 좋았다.

 

자릿수가 작을수록, 같은 이진 문자열에 대한 십진수의 개수가 많다. 

예를 들어, 이진 문자열의 길이가 40일 때, 6개씩 끊으면 7개의 십진수가 나오지만, 9개씩 끊으면 5개의 십진수가 나온다. 십진수는 곧 하나의 개별 문자이므로 십진수의 개수가 많아질수록 문자열의 길이도 길어져 용량을 많이 차지하게 될 것이다. 

 

자릿수가 클수록, 십진수의 개수는 적지만 UTF-8에 의하여 아스키가 아닌 유니코드에 대해서는 2~4 바이트를 할당하게 되기 때문에 용량이 늘어난다. 그래서 7자리 이상인 자릿수들에 대해서는 UTF-8에 의하여 한 문자당 최대 4바이트까지 차지할 수 있어 자릿수가 7보다 커지면 그만큼 용량도 늘어나게 될 것이다. 

(관련해서 다음 포스팅이 참고가 될 것이다. https://taeminator1.tistory.com/50)

 

그렇다면 10 자릿수 이상으로 분리하면 어떨까??  어차피 UTF-8에서 개별 문자의 최대 용량은 4바이트이므로 자릿수를 증가시킬수록 이득이지 않을까?? 하지만 숫자 중에서 유니코드가 할당되지 않은 숫자들이 있어 계속해서 늘릴 수는 없다. 0부터 767까지는 유니코드가 할당되어 있지만, 그 이후부터는 군데군데 아무것도 가리키지 않는(nil) 숫자들이 많이 있다. 

따라서 767을 넘지 않는 자릿수를 선택해야 하고, 최대가 9자리(0부터 511까지 표현)이다. 

 

이러한 점들을 고려해 가장 적합한 자릿수는 7개라는 결론이 나왔다. (물론 이번 예제 한정)

 

두 번째로 압축된 파일을 다시 압축하면 어떻게 되는지 확인해 보았다. 이진 문자열의 개수는 7로 고정하고 2번 압축하였다. 

7 자릿수로 두 번 압축된 파일의 용량

결과는 원래의 파일 보다도 용량이 증가하였다. 

한 번 압축했을 때와 두 번 압축했을 때, 생성된 파일

압축 후 생성된 파일을 확인해 보니, 두 번 압축했을 때 허프만 코드의 개수 41개에서 128개로 비약적으로 증가하였다. (약 3배) 그 이유는 원래 문자열에서는 자주 사용되는 문자들(아스키)이 사용되었지만, 한 번 압축된 문자열에서는 문자의 종류(위의 왼쪽 사진만 봐도 아스키 이외의 여러 특수문자가 즐비해 있다)가 많아져 대응되는 허프만 코드의 개수도 증가해야 했기 때문이다. 

 

그리고 압축을 두 번 진행할 때는, 한 번 압축해서 생성된 파일을 압축해야 하기 때문에, 단순히 압축된 문자열뿐만 아니라 허프만 코드와 같은 데이터도 압축을 해줘야 하는 불리함도 작용한다. 

 

따라서 압축을 여러 번 한다고 효율이 좋아지는 것은 아니다(오히려 이 번 경우에는 안 좋아졌다)

 

이번 예제에서는 다음과 같은 사실을 정리할 수 있었다. 

• UTF-8에 의해 인코딩 되는 텍스트 파일은 압축할 때 바이너리(여기서는 이진 문자열) 값을 7 비트씩(7 자리씩) 쪼개는 것이 가장 효율적이다. 
• 압축하려는 문자열에 반복되는 문자가 많을수록 압축 효율은 증가한다. 

 

이렇게 검증까지 해보았다. 처음에 허프만 코딩을 알게 되었을 때의 전율에 힘입어 시작을 하게 되었는데, 생각보다 긴 여정이었다. 우선순위 큐의 실제 활용이나, 연결 리스트를 이용한 다른 객체 참조, 문자열 다루기 등 다양한 부분을 학습할 수 있어 좋았다.