Variable-length code

In <a href="/facts/Coding_theory/SBqStoGL">coding theory</a>, a variable-length code is a <a href="/facts/Code/CSntvnEo">code</a> which maps source symbols to a variable number of <a href="/facts/Bit/S972NSaD">bits</a>. The equivalent concept in <a href="/facts/Computer_science/lN3pEyPz">computer science</a> is <a href="/facts/Bit_string/PAfzTEHB">bit string</a>.
Variable-length codes can allow sources to be <a href="/facts/Data_compression/gMFuY4FT">compressed</a> and decompressed with zero error (<a href="/facts/Lossless_data_compression/LS702KsN">lossless data compression</a>) and still be read back symbol by symbol. With the right coding strategy, an <a href="/facts/Independent_and_identically-distributed_random_variables/othIRaWt">independent and identically-distributed source</a> may be compressed almost arbitrarily close to its <a href="/facts/Information_entropy/NLg4NLvt">entropy</a>. This is in contrast to fixed-length coding methods, for which data compression is only possible for large blocks of data, and any compression beyond the logarithm of the total number of possibilities comes with a finite (though perhaps arbitrarily small) probability of failure.
Some examples of well-known variable-length coding strategies are <a href="/facts/Huffman_coding/dBgMBz48">Huffman coding</a>, <a href="/facts/Lempel%E2%80%93Ziv_coding/HGH09JM9">Lempel–Ziv coding</a>, <a href="/facts/Arithmetic_coding/WU0H4oNu">arithmetic coding</a>, and <a href="/facts/Context-adaptive_variable-length_coding/f6auheYI">context-adaptive variable-length coding</a>.

Variable-length code open-in-new

Variable-length code