최근 대충 3일 동안 이진 탐색 트라이를 구현한 이유는 허프만 압축을 구현해서 zip파일을 압축를 푸는 것을 해보고 싶기 때문이었어.

전부터 해보고 싶었는데  LZ77이랑 허프만 코드를 쓴다는데, LZ77은 연속된 윈도우를 사용한다는 건 알았지만, 허프만 코드는 정말 난감했음.

근데 작년에 알고리즘 수업에서 허프만 코드를 알려주길래 이걸 구현해보고자 했지.(수업에서는 그냥 펜으로 굴렸음)




교재의 이 부분을 참고했고, 나와있는 코드는 안봤음. 어차피 러스트로 짜기도 했고.

우선 순위 큐도 필요했는데, 원래는 힙을 이용해서 구현하려다 포기하고 그냥 crates에 공개되어 있는 라이브러리를 사용함.


노드는 이렇게 했음. 기수탐색 트라이를 구현해 보니까 어렵지 않았음.


압축성능을 테스트할 대상은 소스코드 자신. char로 받았기 때문에 한 문자당 4바이트라고 가정하기로 했음.


그렇게 해서 큐에 집어넣는데, 우선순위 큐는 가장 큰 수가 가장 먼저 나오기 때문에 할 수 없이 -1*를 곱해서 가장 작은 카운트를 가지는 것부터 나오게 만들었음.

그 후에는 큐에 하나가 남을 때까지 계속 노트를 합쳐서 큐에 넣는 과정을 반복했지.

책을 제대로 안봐서 이유는 모르지만 큐에서 뺐다 넣다 할 때 노트의 순서가 좌우좌우가 되었기 때문에 rl이라는 변수를 만들어서 교차하면서 위치를 바꿨음.


그 다음에는 허프만코드를 구하는 것만 남았지.

허프만 코드를 구하는 과정은 재귀적으로 풀었음, 그리고 char를 복사하지 않고 그냥 생명주기 제한을 둔 이유는 나중에 정말로 바이트 배열을 압축할 때 바이트 배열를 복사할 수 는 없기 때문이었음.


다음에는 키랑 코드를 출력하고, 텍스트를 코드에 매핑해서 출력해봄.


이런 결과가 나왔고

매핑한 결과는 이랬음.

코드의 길이는 2166자, 난 한 글자가 4바이트라고 가정하면 8664바이트, 압축 결과의 비트수는 8247비트로 바이트로 따지면 올림하여(남은 비트는 0으로 채울테니까) 1031바이트라는 결과가 나왔음.

4바이트라고 가정했을 때는 무려 압축률이 25%에 가깝다고 볼 수 있고, 1문자가 1바이트라고 쳐도 50%에 가까운 압축률을 보여준다는 것이 놀라웠음.


다음에는 압축 결과를 정말로 바이트 배열로 만들고, 압축을 푸는 과정까지 하고 싶음.