Intradependent encodings can be compressed

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^\prime$~$ 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^\prime$~$ 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].