The Similarity Metric

Title: The Similarity Metric

Research Question: How can we measure similarity between sequences, such as internet documents, different language text corpora, computer programs, or chain letters, without needing background knowledge or features specific to the application?

Methodology: The researchers proposed a new "normalized information distance" (NID) based on the noncomputable notion of Kolmogorov complexity. They showed that NID is a metric and is universal, meaning it discovers all computable similarities. They also developed a practical analogue of NID called the "normalized compression distance" (NCD) and used real-world compressors like gzip and GenCompress.

Results: They applied NCD to various fields, including bioinformatics, language tree construction, and plagiarism detection. In bioinformatics, they used it to compare whole mitochondrial genomes and infer evolutionary history, resulting in the first completely automatic computed whole mitochondrial phylogeny tree. In language tree construction, they fully automatically computed the language tree for 52 different languages.

Implications: The similarity metric provides a general mathematical theory of similarity that is applicable to various fields without the need for domain-specific knowledge or features. This tool can be used for automatic comparison and classification of sequences, text, programs, and other objects, making it a valuable resource for researchers and practitioners in multiple fields.

Link to Article: https://arxiv.org/abs/0111054v3 Authors: arXiv ID: 0111054v3