Data Compression Lec#7 Word

Statistical compression algorithms
Statistical compression algorithms are a class of lossless compression algorithms based on the probability that certain characters will occur.
Statistical methods use variable-size codes, with the shorter codes assigned to symbols or groups of symbols that appear more often in the data (have a higher probability of occurrence). Designers and implementers of variable-size codes have to deal with the two problems of (1) assigning codes that can be decoded unambiguously and (2) assigning codes with the minimum average size.
1- Shannon-Fano Coding
Shannon-Fano coding, named after Claude Shannon and Robert Fano, was the first algorithm to construct a set of the best variable-size codes. We start with a set of n symbols with known probabilities (or frequencies) of occurrence. The symbols are first arranged in descending order of their probabilities. The set of symbols is then divided into two subsets that have the same (or almost the same) sum of probabilities. All symbols in one subset get assigned codes that start with a 1, while the codes of the symbols in the other subset start with a 0. Each subset is then recursively divided into two sub subsets of roughly equal probabilities, and the second bit of all the codes is determined in a similar way. When a subset contains just two symbols, their codes are distinguished by adding one more bit to each. The process continues until no more subsets remain.