Algorithmic Complexity & Compression Dynamics

The problem

Everyone reaches for complexity intuitively - how random, how compressible, how structured a signal is - but it is rarely computed rigorously. An ad-hoc gzip in a spreadsheet or a black-box library hands you a number with no provenance and no way to check it.

The local-first solution

This tool computes the actual information-theoretic complexity measures - Shannon and block entropy, exact Lempel-Ziv production count, compression-based Kolmogorov upper bounds, Normalized Compression Distance, and two-part MDL - deterministically in your browser, each one checkable against a closed-form or known value. No data leaves the device.

What it does

Honest scope

Authorities cited

• DeMoss, B., Sapora, S., Foerster, J., Hawes, N., Krueger, D. (2024). The Complexity Dynamics of Grokking. arXiv:2412.09810. - Tracks description-length / compression complexity over training and relates the generalization transition to a rise-then-fall in algorithmic complexity. This plugin computes the same FAMILY of deterministic measures; it does NOT train or demonstrate grokking.
• Lempel, A., Ziv, J. (1976). On the Complexity of Finite Sequences. IEEE Trans. Information Theory IT-22(1), 75-81. DOI 10.1109/TIT.1976.1055501. - The LZ76 production-count complexity c(S).
• Kaspar, F., Schuster, H. G. (1987). Easily calculable measure for the complexity of spatiotemporal patterns. Phys. Rev. A 36(2), 842-848. DOI 10.1103/PhysRevA.36.842. - The exhaustive-history algorithm realizing LZ76 complexity used here.
• Ziv, J., Lempel, A. (1977). A Universal Algorithm for Sequential Data Compression. IEEE Trans. Information Theory IT-23(3), 337-343. DOI 10.1109/TIT.1977.1055714. - The LZ77 sliding-window back-reference compressor; its (distance, length) matches give the NCD metric property C(x|x) ~ C(x), used here as the headline compression cost.
• Welch, T. A. (1984). A Technique for High-Performance Data Compression. IEEE Computer 17(6), 8-19. DOI 10.1109/MC.1984.1659158. - The LZW dictionary compressor (LZ78 family) implemented in pure JS as the secondary compression-ratio readout.
• Ziv, J., Lempel, A. (1978). Compression of Individual Sequences via Variable-Rate Coding. IEEE Trans. Information Theory IT-24(5), 530-536. DOI 10.1109/TIT.1978.1055934. - The LZ78 incremental-parsing basis of LZW.
• Cover, T. M., Thomas, J. A. (2006). Elements of Information Theory, 2nd ed. Wiley. Sec. 2 (entropy), Thm 4.2.1 (entropy rate, conditional entropy non-increasing toward the rate). DOI 10.1002/047174882X.
• Li, M., Vitanyi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications, 3rd ed. Springer. Ch. 2-3 - Kolmogorov complexity K is UNCOMPUTABLE; any concrete compressor C upper-bounds K up to an additive constant. DOI 10.1007/978-0-387-49820-1.
• Cilibrasi, R., Vitanyi, P. M. B. (2005). Clustering by Compression. IEEE Trans. Information Theory 51(4), 1523-1545. DOI 10.1109/TIT.2005.844059. - The Normalized Compression Distance NCD as a practical proxy for the (uncomputable) Normalized Information Distance.