Practical Estimation of Kolmogorov Complexity using Highly Efficient Compression Algorithms
Angel Kuri Morales, Oscar Herrera, José Galaviz, Martha Ortiz Posadas · Research in Computing Science · 2005
In this paper we describe a heuristic approach to the problem of calculating the algorithmic information of message m by estimating Kolmogorov complexity. This is achieved by defining a basic element of information which we call a metasymbol. We show that when m is expressed as an ensemble (which we call M) of metasymbols it complies with the minimum message length principle. Therefore, M is the shortest way of encoding m and approaches Kolmogorovis bound. We discuss approaches to the problem of finding the best set of metasymbols using AI techniques