A Model Conditioned Data Compression Based Similarity Measure

Many methodologies and similarity measures based on data compression have been recently introduced to compute similarities between general kinds of data. Two important similarity indices are the normalized information distance (NID), with its approximation normalized compression distance (NCD), and the pattern recognition based on data compression (PRDC). At first sight NCD and PRDC are quite different: the former is a direct metric while the latter is a methodology which computes a compression distance with an intermediate step of encoding files into texts. In spite of this, it is possible to demonstrate that they are both based on estimates of Kolmogorov complexities (when this is known for the former but not for the latter). Finally, this results in the definition of a new measure: the model conditioned data compression based similarity measure (McDCSM), which is a modified version of PRDC, and is the topic of this paper.