Data Compression Lec#4-2020

prefix property: This property requires that once a certain bit pattern has been assigned as the code of a symbol, no other codes should start with that pattern (the pattern cannot be the prefix of any other code).
Hence, a prefix code is a variable-size code that satisfies the prefix property.

As we Know earlier, designing variable-size codes is done by following two principles:
1- Assign short codes to the more frequent symbols and,
2- Obey the prefix property.
Following these principles produces short, unambiguous codes, but not necessarily the best (i.e. shortest) ones.
Binary Representation of the Integers
The binary representation of the integers has two main disadvantages:
? Does not satisfy the prefix property.
? In this representation the size n of the set of integers has to be known in advance, since it determines the code size, which is 1 + ? log2 n ?.
For example, the size of the code of the integer is
Code size ( 3 ) = 1 + ? log2 3 ? = 1 + ? 1.585 ? = 1+1 = 2
Code size ( 5 ) = 1 + ? log2 5 ? = 1 + ? 2.322 ? = 1+2 = 3
Code size ( 8 ) = 1 + ? log2 8 ? = 1 + ? 3 ? = 1+3 = 4
Code size ( 19 ) = 1 + ? log2 19 ? = 1 + ? 4.24? = 1+4 = 5 its code is 10011
Code size ( 37 ) = 1 + ? log2 37 ? = 1 + ? 5.2? = 1+5 = 6 its code is 100101