Data Compression Lec#9 PowerPoint

3-Tunstall Code
The idea is to construct a set of fixed-size codes, each encoding a variable-size string of input symbols.
The lengths of Tunstall Codes are equal but the codes represent variable length of symbols. The main advantage of this method is that there is no accumulated error due to variable-length code. Instead of giving higher probability symbol fewer bits code, Tunstall coding concatenate symbol having highest probability with every other symbol together to from strings replacing the original symbol.
An n-bit Tunstall code should use all codes. Thus, an algorithm is needed in order to develop the best n-bit Tunstall code for a given alphabet of N symbols and such an algorithm is given:
Given an alphabet of N symbols, we start with a code table that consists of the symbols. We then iterate as long as the size of the code table is less than or equal to the number of codes . (N+K(N-1)?2n ).
Each iteration performs the following steps:
1- Select the symbol with largest probability in the table. Call it S.
2- Remove S and add the N substrings Sx where x goes over all the N symbols. This step increase the table size by N ? 1 symbols (some of them may be substrings). Thus, after iteration k, the table size will be N + k(N ? 1) elements.
3- If N + k(N ? 1) ? , perform another iteration.