Normalized compression distance

We assume that the objects one talks about are finite strings of 0s and 1s. Thus we mean string similarity. Every computer file is of this form, that is, if an object is a file in a computer it is of this form. One can define the information distance between strings ${\displaystyle x}$ and ${\displaystyle y}$ as the length of the shortest program ${\displaystyle p}$ that computes ${\displaystyle x}$ from ${\displaystyle y}$ and vice versa. This shortest program is in a fixed programming language. For technical reasons one uses the theoretical notion of Turing machines. Moreover, to express the length of ${\displaystyle p}$ one uses the notion of Kolmogorov complexity. Then, it has been shown [1]

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

up to logarithmic additive terms which can be ignored. This information distance is shown to be a metric (it satisfies the metric inequalities up to a logarithmic additive term), is universal (it minorizes every computable distance as computed for example from features up to a constant additive term).[1]

While the NID metric is not computable, it has an abundance of applications. Simply approximating ${\displaystyle K}$ by real-world compressors, with ${\displaystyle Z(x)}$ is the binary length of the file ${\displaystyle x}$ compressed with compressor Z (for example "gzip", "bzip2", "PPMZ") in order to make NID easy to apply.[2] Vitanyi and Cilibrasi rewrote the NID to obtain the Normalized Compression Distance (NCD)

${\displaystyle NCD_{Z}(x,y)={\frac {Z(xy)-\min\{Z(x),Z(y)\}}{\max\{Z(x),Z(y)\}}}.}$[3]

The NCD is actually a family of distances parametrized with the compressor Z. The better Z is, the closer the NCD approaches the NID, and the better the results are.[3]

Objects can be given literally, like the literal four-letter genome of a mouse, or the literal text of War and Peace by Tolstoy. For simplicity we take it that all meaning of the object is represented by the literal object itself. Objects can also be given by name, like "the four-letter genome of a mouse," or "the text of `War and Peace' by Tolstoy." There are also objects that cannot be given literally, but only by name, and that acquire their meaning from their contexts in background common knowledge in humankind, like "home" or "red." We are interested in semantic similarity. Using code-word lengths obtained from the page-hit counts returned by Google from the web, we obtain a semantic distance using the NCD formula and viewing Google as a compressor useful for data mining, text comprehension, classification, and translation. The associated NCD, called the normalized Google distance (NGD) can be rewritten as

${\displaystyle NGD(x,y)={\frac {\max\{\log f(x),\log f(y)\}-\log f(x,y)}{\log N-\min\{\log f(x),\log f(y)\}}},}$

where ${\displaystyle f(x)}$ denotes the number of pages containing the search term ${\displaystyle x}$, and ${\displaystyle f(x,y)}$ denotes the number of pages containing both ${\displaystyle x}$ and ${\displaystyle y}$,) as returned by Google or any search engine capable of returning an aggregate page count. The number ${\displaystyle N}$ can be set to the number of pages indexed although it is more proper to count each page according to the number of search terms or phrases it contains. As rule of the thumb one can multiply the number of pages by, say, a thousand...[17]

• Word2vec

• Efficient Estimation of Word Representations in Vector Space
• M. Li and P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications,Springer-Verlag, New York, 4th Edition 2019