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.