허프만 코딩 (3) 썸네일형 리스트형 [Swift]허프만 코딩 구현 3 - 검증 검증하기 전에 압축과 추출에서 구현한 다양한 동작들을 구조체로 묶어보자. Compressor와 Extractor 구조체를 생성하였다. 코드는 지난 시간에 전부 구현을 하였기 때문에 클래스 다이어그램만 제시하고 따로 구현은 필요 없어 보인다. 몇 가지 특성은 다음과 같다. 두 구조체 모두 input을 속성으로 갖는데, 해당 속성은 입력받은 데이터를 의미한다. pNumber는 지난 시간과 동일하게 이진 문자열을 쪼개는 개수이다. ASCII가 7bit의 이진수를 나타내므로 기본값은 7이다. Compressor 구조체의 makeHuffmanCodes()는 허프만 코드를 반환하는데, 이전에 설명한 바와 같이, 허프만 코드는 구할 때마다 값이 다를 수 있어 private으로 선언해 다른 곳에서의 사용을 방지하였다... 허프만 코딩 2 - 문자열 압축과 추출 지난 포스팅(https://taeminator1.tistory.com/51)에서 허프만 코딩이 무엇인지 알아보았고, 허프만 코드를 생성하는 방법과 허프만 코드가 "더 짧은 심벌 트릭"에서 적절한 심벌이 될 수 있는 이유에 대해 알아보았다. 이번 시간에는 허프만 코드를 이용해 실제 압축과 추출을 구현하기 위한 전체 과정을 살펴보려고 한다. 크게 "압축"과 "추출" 두 가지 동작에 대해 설명할 것이다. (추가로 동작이 제대로 이루어졌는지 확인하기 위한 "검증"도 필요할 수 있다) 압축: 입력받은 문자열을 압축하여 새로운 문자열을 생성 추출: 입력받은 문자열에서 원래 문자열 추출 전체 과정을 살펴본 다음, 문자열이 주어졌을 때, 각각의 과정의 결과가 어떻게 되는지 설명하려고 한다. 먼저 전체 과정은 다음과 같.. 허프만 코딩 1 - 허프만 코드 구하기 허프만 코딩(Huffman Coding)은 이전 포스팅(https://taeminator1.tistory.com/49)에서 언급한 "더 짧은 심벌 트릭(shorter-symbol trick)"의 일종이다. 더 짧은 심벌 트릭은 압축하려는 문자열에서 자주 사용되는 문자일수록 짧은 심벌을 부여하여 압축하는 방법이다. 허프만 코딩은 이러한 심벌을 허프만 코드를 이용해서 압축하는 방법이다. 허프만 코딩의 핵심은 아무래도 허프만 코드를 구하는 것이다. 허프만 코드를 구하는 방법을 살펴보기 전에, "더 짧은 심벌 트릭"에서 "심벌"이 되기 위한 조건을 살펴보자. 다음과 같은 두 가지 조건이 있다. 빈도수가 많을수록 심벌의 자릿수가 적어야 한다 임의의 심벌이 다른 심벌의 첫 부분이 아니어야 한다 먼저 첫 번째 조건은.. 이전 1 다음
