2011/10/20 by Paul Vitányi, Vitanyi, Paul M. B.
Computer Science · #Computability, Logic, AI Algorithms #Algorithms and Data Compression #Cellular Automata and Applications
paper · pdf · doi:10.48550/arxiv.1110.4544
First we consider pair-wise distances for literal objects consisting of finite binary files. These files are taken to contain all of their meaning, like genomes or books. The distances are based on compression of the objects concerned, normalized, and can be viewed as similarity distances. Second, we consider pair-wise distances between names of objects, like "red" or "christianity." In this case the distances are based on searches of the Internet. Such a search can be performed by any search engine that returns aggregate page counts. We can extract a code length from the numbers returned, use the same formula as before, and derive a similarity or relative semantics between names for objects. The theory is based on Kolmogorov complexity. We test both similarities extensively experimentally.