Parselets: An Abstraction for Fast, General-Purpose Algorithmic Information Calculus

This work describes the principled design of a theoretical framework leading to fast and accurate algorithmic information measures on finite multisets of finite strings by means of compression. One distinctive feature of our approach is to manipulate reified representations of the very entities and quantities of the theory itself: compressed strings, models, rate-distortion states, minimal sufficient models, joint and relative complexity. To do so, a programmable, recursive data structure called a parselet provides modeling of a string as a concatenation of parameterized instantiations from sets of finite strings that encode the regular part of the data. This supports another distinctive feature of this work, which is the native embodiment of Epicurus’ Principle on top of Occam's Razor, so as to produce both a most-significant and most-general explicit model for the data. This model is iteratively evolved through the Principle of Minimal Change to reach the so-called minimal sufficient model. Parselets may also be used to compute a compression score of any arbitrary hypothesis about the data. A lossless, rate-distortion oriented, compressed representation is proposed, that allows immediate reusability of the costly computations stored on disk. Two information measures are deduced: one is exact because it is purely combinatorial, and the other may occasionally incur slight numerical inaccuracies because it is an approximation of the Kolmogorov complexity of the minimal sufficient model. Symmetry of information is enforced at the bit level.