Normalizovaná kompresní vzdálenost

Normalizovaná kompresní vzdálenost (z angl. "normalized compression distance") je způsob, jakým se dá měřit podobnost dvou objektů, ať už se jedná o dva dokumenty, dva e-maily, dvě hudební díla, dva jazyky, dva programy, dva obrázky, dva genomy, atd. Použitelná definice podobnosti může být jak těžké je převést jeden objekt na druhý. Normalizovaná kompresní vzdálenost může být použita například pro dobývání znalostí, pro shlukovou analýzu.

Výpočet informační vzdálenosti

Pro výpočet musíme na porovnávané objekty nahlížet jako na sled jedniček a nul - jedná se o binární řetězec. Každý počítačový soubor je takto vnitřně reprezentován.

Označme si první porovnávaný objekt, ve formě binárního řetězce, jako $x$ a druhý jako $y$. Dále budeme uvažovat počítačový program, který dokáže spočítat $x$ z $y$ a navzájem. Tento program budeme brát v teoretickém zápisu turingova stroje. Délka takovéhoto (nejkratšího) programu pak budiž informační vzdáleností.

$|p|=\max \{K(x\mid y),K(y\mid x)\}$

kde $K(x\mid y)$ značí kolmogorovskou složitost programu pro výpočet $x$, když $y$ dostane program na vstupu a obdobně $K(y\mid x)$ značí kolmogorovskou složitost programu pro výpočet $y$ se vstupem $x$.

Pro výpočet normalizované informační vzdálenosti (NID) pak použijeme vzoreček:

$NID(x,y)=\frac{\max \{K(x\mid y),K(y\mid x)\}}{\max \{K(x),K(y)\}},$

Nicméně tento výpočet je bohužel v praxi nespočitatelný .

Výpočet normalizované kompresní vzdálenosti

Jelikož normalizovaná informační vzdálenost je nespočitatelná, Vitanyi a Cilibrasi přišli s vylepšenou metrikou nazvanou normalizovaná kompresní vzdálenost. Jedná se o nahrazení $K$ kompresorem - $Z(x)$ značí kompresní binární délku komprimovaného souboru (např. za použití "gzip"). Výsledný vzoreček tedy vypadá takto:

$NC{D}_Z(x,y)=\frac{Z(xy)-\min \{Z(x),Z(y)\}}{\max \{Z(x),Z(y)\}}.$

Aplikace

Normalizovaná kompresní vzdálenost může být použita v celé řadě odvětví. Jedním z příkladů je rozpoznávání podobností v obrázcích na poli počítačové grafiky , či klasifikovaní počítačových virů a malware . Dalším příkladem je Normalizovaná Google vzdálenost - jedná se o přepsání vzorce pro potřeby porovnávání vyhledávaných termů.