라벨이 normalized compression distance인 게시물 표시

Normalized Compression Distance - 압축 알고리즘을 통해서 유사도 비교하기

이번에 소개할 Normalized Compression Distance (a.k.a. NCD) 는 압축 알고리즘을 이용해서 두 object의 유사도를 측정하는 참신하고 재밌는 방법을 소개할 것이다. 이 방법은 간단하면서도 의외로 효과적이면서 기발한 방법이다. compression 알고리즘은 보통 효율적인 압축을 위해서 자주 등장하는 sequence일수록 더 짧은 길이로 압축하도록 노력한다. 따라서 같은 길이의 sequence가 더 짧은 길이로 압축됐다면, 이 sequence에는 반복되는 sub-sequence가 많이 있다는 말이 된다. NCD는 compression의 이러한 성질을 이용한다. 입력받은 sequence를 compression 한 길이를 리턴하는 함수를 Z 라고 할때 NCD의 수식은 다음과 같다. NCD ( x , y ) = [ Z ( x + y ) - min { Z ( x ) , Z ( y ) } ] / max { Z ( x ) , Z ( y ) } 즉, 비교할 두 sequence를 합친 sequence를 압축한 길이가 sequence를 따로따로 압축한 길이에 비해서 얼마나 더 짧아졌는가를 보여주는 것이다. 압축 알고리즘은 일반적으로 Z ( x + y ) 가 Z ( x ) + Z ( y ) 보다 작아서 NCD는 0에서 1 사이의 정규화된 값을 가진다. NCD가 1에 가까울수록 둘 사이에는 공통점이 없는 것이고, 0에 가까우면 둘은 매우 비슷한 패턴을 가지고 있는 것이다. NDC는 두 object를 binary sequence로 변환할 수 있는 경우에만 사용 가능하다는 문제가 있지만, 컴퓨터로 계산하는 대부분의 경우 binary sequence로 변환할 수 있으므로 큰 문제는 되지 않는다. NCD의 재밌는 점은 어떤 압축 알고리즘이든지 사용할 수 있다는 것이다. 덕분에 gzip, bzip, 7z 등 이미 존재하는 다양한 압축 알고리즘을 이용할 수 있어서 구현이 쉽지만, 비교할 object의 패턴에 따라

이 블로그의 인기 게시물

[C++] enum class - 안전하고 쓰기 쉬운 enum

RAII는 무엇인가

Log Aggregator 비교 - Scribe, Flume, Fluentd, logstash

[Python] cache 데코레이터로 최적화하기

[Web] SpeechSynthesis - TTS API