2003년인가 누군가가 spam filter에서 compression ratio가 중요한 펙터로 작용한다는 글을 쓴적이 있었다. 이는 스팸문서의 경우 단순한 패턴의 연속표현일 경우가 있다는 가정이 깔려 있다. 그런 문자열의 반복성은 압축 알고리즘의 구현 원리에 따라서 압축률을 측정함으로 간접적으로 측정이 가능할 것이다.

물론 지금 이 feature를 spam 필터링에 쓴다는 이야기는 절대 아니고 다른 작업을 하고 있는데 이 compression ratio가 중요한 펙터로 쓰일 예정이라 여러 압축 알고리즘을 가지고 테스트를 해보고 있다.

내가 압축비율을 알고자 하는 대상이 굉장히 짧은 string형의 데이터다. 하지만 이를 gzip같은 알고리즘으로 압축하면 사전데이터를 헤더에 넣는 과정에서 압축률이 굉장히 떨어지게 되어있다. 그래서 심지어 압축된 데이터가 원본보다 더 커지는 경우가 비일비재했다.
그렇다면 헤더정보를 제외한 나머지 부분에 대한 것들만 취하면 좋지 않을까 하지만 이도 녹녹치 않다.

그래서 찾아본 알고리즘이 허프만 코딩(Huffman coding)방식의 압축방법이다. 이는 정보량(또는 확률)이 큰 것에 크기가 적은 비트를 할당해 이의 비트와 출현 빈도를 기재하는 방법으로 하는 아주 기본적인 알고리즘이다.

이를 Python으로 구현하려 하면서 다시 내가 하고자 하는 목표가 뭔지 생각해 봤다.

“aabbccdd”같은 문자열의 내가 예상하는 압축률은 50%다.  a:2,b:2,c:2,d:2 같은 문자열로 압축이 되어서 50%정도의 압축률을 만족할 수 있을것이다.

위의 압축률이 내가 원하는 압축률 정보이다.

이정도 정보는 단순히 Python에서 Dict객체(다른 곳에서는 Hash)만을 이용해 추출이 가능할 것이다.
문자열에서 char를 하나씩 뽑아서 hash에 넣어버리면서 중복된 char를 없애는 아주 간단한 방법이다.

이렇게 간단하고 강력한 압축률을 측정하는 함수를 만들어 성공적으로 원하는 필터를 학습시킬 수 있었다.

특히나 개발자는 어느 부분에 심취하면 가끔 주된 목적이 무엇인지 까먹고는 한다. 가끔 이런 목표를 remind하는 과정은 좀더 현실 문제를 쉽게 볼 수 있는 기회를 주는거 같다.

compression ratio 측정 해프닝 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.