Modeling and Coding

1. Introduction to Data Compression

Data compression methods can be divided into two main categories:

• Lossless compression: The data can be perfectly reconstructed from the compressed data.
• Lossy compression: Some information is lost, leading to an approximate reconstruction of the data.

In both lossless and lossy compression, modeling and coding are crucial.

• Modeling involves analyzing data patterns to predict probable data values, which enables efficient encoding.
• Coding is the process of mapping these values to compressed representations, typically shorter in length.

2. Theoretical Foundation of Data Compression

The theoretical foundation of data compression is based on information theory, primarily attributed to Claude Shannon’s work in 1948. Shannon introduced concepts such as entropy, which measures the minimum average length of lossless encoding, given the probabilities of different symbols in a data set.

2.1 Entropy

The entropy $H(X)$ of a discrete random variable $X$ with possible values $x_1, x_2, …, x_n$ and respective probabilities $p(x_1), p(x_2), …, p(x_n)$ is defined as:

Entropy provides a theoretical limit on the minimum average number of bits needed to represent the data. The closer we get to this limit, the more efficient our compression scheme is.

Example

Suppose we have a data source that produces symbols $A$, $B$, and $C$ with probabilities 0.5, 0.3, and 0.2, respectively.

This means that, on average, each symbol can be represented in 1.485 bits, which is less than using 2 bits per symbol.

3. Modeling in Data Compression

3.1 Statistical Modeling

The goal of statistical modeling is to assign probabilities to symbols based on their frequency. This allows us to prioritize frequently occurring symbols with shorter codes and rarer symbols with longer codes. Statistical modeling is commonly used in methods like Huffman coding and arithmetic coding.

• Huffman Coding: A type of lossless coding that uses a binary tree structure to assign shorter codes to more frequent symbols.
• Arithmetic Coding: A coding technique that represents a sequence of symbols as a single fractional number between 0 and 1.

3.2 Dictionary-Based Modeling

In dictionary-based modeling, a dictionary is created containing repeated sequences or patterns. Algorithms like Lempel-Ziv-Welch (LZW) compression exploit these repeating patterns to achieve compression by replacing sequences with shorter codes that refer to the dictionary.

Example of Statistical Modeling

Given the probabilities for symbols $A = 0.5$, $B = 0.3$, and $C = 0.2$, we can generate a Huffman Tree. Assigning 1-bit codes to $A$, 2-bit codes to $B$, and 3-bit codes to $C$ results in efficient coding for this probability distribution.

4. Coding in Data Compression

Once a model assigns probabilities to symbols, the coding step maps these symbols to binary strings.

4.1 Huffman Coding

Huffman Coding is a widely used algorithm that generates prefix-free codes based on the frequency of each symbol.

Steps of Huffman Coding

1. Sort symbols by their probability in ascending order.
2. Combine the two symbols with the lowest probabilities to form a new node.
3. Repeat this process until all symbols are combined into a single tree.
4. Assign binary values to each path in the tree.

Example

For symbols $A, B, C, D$ with probabilities $0.4, 0.3, 0.2, 0.1$:

1. Combine $C$ and $D$ to get $CD$ with probability 0.3.
2. Combine $CD$ with $B$ to get $CDB$ with probability 0.6.
3. Combine $CDB$ with $A$ to get the root of the tree.

This results in the following codes:

• $A = 0$
• $B = 10$
• $C = 110$
• $D = 111$

Using these codes minimizes the average bit length per symbol.

4.2 Arithmetic Coding

In arithmetic coding, a message is represented by a single floating-point number in the range [0, 1). This coding method is highly efficient, as it approaches entropy limits.

Steps of Arithmetic Coding

1. Divide the range [0, 1) into intervals, each corresponding to the probability of a symbol.
2. For each symbol in the sequence, narrow the interval based on its probability.
3. After encoding all symbols, select a point within the final interval as the code.

5. Examples of Lossless Compression

To illustrate both modeling and coding in practice, let’s work through an example using Huffman coding.

Example

Assume a message “ABACAB” with the following probabilities:

• $P(A) = 0.5$
• $P(B) = 0.3$
• $P(C) = 0.2$

1. Construct the Huffman tree for $A, B,$ and $C$.

2. Assign shorter binary codes to symbols with higher probabilities, as shown previously.

3. Encode the message “ABACAB” using the generated codes:

   • A = 0
   • B = 10
   • C = 110

The compressed message is: “0 10 0 110 0 10”

By grouping bits, we can decode this compressed form to reconstruct the original message, achieving lossless compression.

6. Performance Evaluation of Compression Algorithms

Two important measures in data compression are:

• Compression ratio: Measures the reduction in data size.

  $$\text{Compression Ratio} = \frac{\text{Uncompressed Size}}{\text{Compressed Size}}$$

• Compression efficiency: Indicates how close the compressed data size is to the theoretical entropy limit.