ShannonFanoCodierung

Shannon-Fano codierung is a binary prefix coding method used in lossless data compression. It was developed by Claude Shannon and Robert Fano in 1949 as one of the early approaches to constructing efficient codes from symbol probabilities. The method aims to assign shorter codes to more frequent symbols.

The construction proceeds as follows: first, determine the probabilities of the source symbols. Then sort the symbols in decreasing order of probability. Partition the ordered list into two groups whose total probabilities are as close as possible. Assign 0 to all symbols in one group and 1 to all symbols in the other group. Recursively apply the same partitioning and bit assignment to each subgroup until each symbol stands alone. The result is a binary code for every symbol.

Properties and performance: the Shannon-Fano code is prefix-free, which guarantees unambiguous decoding. The average code length depends on the distribution of symbol probabilities and, while it tends to approach the source entropy in favorable cases, Shannon-Fano coding is not guaranteed to be optimal. In general, Huffman coding provides a guaranteed minimum average code length for a given probability distribution, making Shannon-Fano typically less efficient in some distributions.

Complexity and usage: constructing a Shannon-Fano code generally requires sorting the symbols, giving a time complexity around O(n log n) for n symbols. The method is of historical and educational importance and is often contrasted with Huffman coding in information theory courses. Variants exist, including multiary versions and refinements, but the basic approach remains the recursive binary partitioning.