= Indexing within a type class
If a <decoder> already knows the length, <alphabet> and <empirical distribution>, it only needs to distinguish $|T_n(q)|$ possible strings. A fixed-length index therefore needs $\lceil\log_2|T_n(q)|\rceil$ <bits>. List the six balanced four-symbol strings in increasing lexicographic order and number them $0$ through $5$. A three-<bit> index identifies any one of them, whereas writing the original binary string directly takes four <bits>.
Knowing the <empirical distribution> is essential to that calculation. If it must also be sent, a simple fixed-length description of which of the five classes was used costs another $\lceil\log_2 5\rceil=3$ <bits>. That naive balanced-string message totals six <bits> and is longer than the raw four-<bit> string. The example demonstrates the benefit of shared constraints, rather than a free <lossless source coding> scheme for every input. For long strings over a fixed <alphabet>, the overhead for identifying a class grows only logarithmically with length, while the <information entropy> of its frequency profile controls the leading cost within the class.
Back to article page
