이걸 언제 다 읽어 -_-;;
요즘 난데없이 compression의 세계에 빠져들었다는.. 알고보니 Ziv-Lempel이 LZ알고리즘이더군여.. (ZL이라고는 안한다는군여. -_-)예전에 suffix tree로 Ziv-Lempel하기를 했었는데, 다 까먹음.. LZ가 그거인줄 알았으면 기억해둘것을.. -_-
그보다.. Shannon이란 사람이 1951년에 엔트로피의 개념을 사용하여 압축에서의 상한선을 정했다는 것을 최근에서 알게됐네요.. 모든 심볼(알파벳) s에 대해 Shannon의 엔트로피 식은 다음과 같이 정해 집니다.
여기서 Pr(s)는 심볼 s가 발생하는 확률입니다. 가령 예를들어서 동전을 던져서 head냐 tail이냐를 나타낸다고 하면, 각 사건의 발생확률이 0.5 이므로 -logPr(s)=-log0.5=1이 되는거죠. 즉 1비트가 필요하단건데.. 여기서 실제 그 사건이 일어나는게 Pr(s)=0.5니까 0.5×1=0.5 가 되어, 각 사건을 표현하는데는 통계적으로 0.5비트가 든다는 거죠. 굳이 이 식의 증명을 몰라도 그냥 식을 보면 감으로 그렇게 될 거라는 필이 오죠?
이것이 데이터 인코딩의 넘지 못하는 상한선이라는군요. 흥미로운 점은 허프만 코딩의 경우 Pr(s)가 1에 가까워질 수록 성능이 안좋다고 하는군요..
여하튼 허프만 코딩은 바이바이가 되고 이젠 허프만 코딩을 쓴다고 해도 변형 버젼인 canonical huffman encoding(이건 트리의 저장비용을 최소화 하는 기법임)이나 LZ, PPM 과 같은 방식이 most effective general purpose lossless compression technique의 왕좌를 차지하고 있나봅니다.
Leave a Reply