Intradependent encodings can be compressed

https://arbital.com/p/3x3

by Nate Soares May 29 2016 updated May 29 2016


Given an encoding scheme E which gives an Intradependent encoding of a message m, we can in principle design a more efficient coding E that gives a shorter encoding of m. For example, E encodes 8-letter English words as a series of letters, m is aardvark, then E(m) is intradependent (because you already know what the message is by the time you've seen "aardv"), so you can define an alternative encoding E which encodes "aardvark" as just "aardv", thereby saving three letters.

The practice of taking an intradependent encoding and finding a more efficient one is known as [compression].