Lossless text compression using Prediction by Partial Matching (PPM) and arithmetic coding.
This project implements an adaptive statistical compression algorithm based on a limited-order PPM model. The implementation uses PPMC for escape-symbol probability estimation and an arithmetic coder for entropy encoding.
Several PPM improvements were implemented and experimentally evaluated, including exclusion and update exclusion.
Prediction by Partial Matching (PPM) is an adaptive statistical compression algorithm based on context modeling.
For every input symbol, PPM analyzes the symbols that precede it and uses the corresponding context to estimate the probability of the next symbol.
The model attempts to encode a symbol using the highest available context order. If the symbol cannot be encoded in the current context, an escape code is generated and the algorithm falls back to a lower-order context.
Input text
│
▼
┌──────────────────────────────┐
│ Context model │
│ │
│ order N │
│ order N-1 │
│ ... │
│ order 1 │
│ order 0 │
│ order -1 / static model │
└──────────────┬───────────────┘
│
│ symbol / escape
▼
┌──────────────────────────────┐
│ Arithmetic Encoder │
└──────────────┬───────────────┘
│
▼
Compressed data
The PPM model itself estimates symbol probabilities. The actual entropy coding is performed by the arithmetic coder.
The implementation uses a limited-order PPM model.
Each context model stores:
- contexts of the corresponding order;
- symbols observed in each context;
- symbol frequencies;
- statistics required for escape-code estimation.
Two special models are also used:
- order 0 — stores frequencies of individual symbols without a preceding context;
- order -1 / static model — used when there is no information about the current symbol.
The model follows the standard PPM fallback strategy:
Try order N
│
├── symbol known ──────► encode symbol
│
└── symbol unknown
│
▼
encode escape
│
▼
Try order N-1
│
▼
...
│
▼
order -1
This allows the encoder to use long contexts when they provide useful information while still being able to encode previously unseen symbols.
The project uses the PPMC method for estimating escape probabilities.
The escape mechanism is important because it allows the encoder to move from a higher-order context to a lower-order context when the current symbol cannot be encoded using the available statistics.
The project also experimentally compares different approaches to estimating the order -1 distribution.
The PPM model is combined with an arithmetic encoder.
The arithmetic coder operates using cumulative frequencies:
cumulative frequency
│
▼
┌─────────────────────────────┐
│ Arithmetic Encoder │
│ │
│ symbol frequency │
│ total frequency │
│ cumulative frequency │
└──────────────┬──────────────┘
│
▼
encoded bit stream
The arithmetic coder used in the project is implemented using fixed-point arithmetic.
For each encoded symbol, the PPM model provides:
- cumulative frequency;
- frequency of the symbol;
- total cumulative frequency.
The arithmetic coder uses these values to update the current coding interval.
Decoding uses the same PPM model and configuration as encoding, allowing the original text to be reconstructed without loss.
Several techniques were implemented and evaluated.
Exclusion prevents symbols that have already appeared in higher-order contexts from being considered again in lower-order models.
The idea is that if a symbol was already observed in a higher-order context but the encoder had to emit an escape code, including that symbol again in a lower-order model may provide redundant information.
Exclusion can therefore improve the probability distribution used for lower-order contexts.
Update exclusion changes how the context models are updated after encoding a symbol.
Instead of updating every context order, only the relevant context orders are updated starting from the order where the symbol was successfully encoded.
This reduces the amount of model updating and can improve execution speed.
The project also investigated two additional PPM improvements:
- Local Order Estimation (LOE) — attempts to determine an appropriate context order instead of always starting from the maximum order;
- Secondary Escape Estimation (SEE) — adaptively estimates escape probabilities using statistics from higher-order contexts.
LOE and SEE were considered as possible improvements but were not implemented in the final version due to project time constraints.
The compression algorithm was evaluated using several text datasets:
| Dataset | Type | Size |
|---|---|---|
war_and_peace.ru.txt |
Russian/French text | 2,609,729 bytes |
Evgeniy_Zamyatin_My.txt |
Russian text | 294,042 bytes |
hamlet.txt |
English text | 191,726 bytes |
enwik7.txt |
Mixed/English Wikipedia text | 10,000,000 bytes |
The experiments investigated:
- the influence of PPM improvements on compression ratio;
- the influence of model order;
- comparison with other compression algorithms.
The following PPMC configurations were compared using model order 4:
| Configuration | War and Peace | My | Hamlet | enwik7 |
|---|---|---|---|---|
| PPMC without improvements | 2.443 | 1.440 | 1.5965 | 1.840 |
| PPMC + exclusion | 2.500 | 1.6142 | 1.7993 | 1.946 |
| PPMC + update exclusion | 2.4756 | 1.4967 | 1.667 | 1.910 |
| PPMC + exclusion + update exclusion | 2.5015 | 1.615 | 1.800 | 1.967 |
The experiments show that exclusion had a more noticeable effect on the compression ratio, while update exclusion primarily reduced the amount of model updating and therefore improved execution efficiency.
The optimal PPM order depends on the characteristics of the input data.
For hamlet.txt:
| Model order | Compression ratio |
|---|---|
| 1 | 1.2167 |
| 2 | 1.5555 |
| 3 | 1.747 |
| 4 | 1.800 |
| 5 | 1.795 |
| 6 | 1.760 |
For war_and_peace.ru.txt:
| Model order | Compression ratio |
|---|---|
| 1 | 1.7245 |
| 2 | 2.0761 |
| 3 | 2.2155 |
| 4 | 2.500 |
| 5 | 2.6352 |
| 6 | 2.9152 |
| 7 | 2.972 |
| 8 | 3.045 |
| 9 | 3.010 |
The results demonstrate that increasing the model order does not universally improve compression.
For hamlet.txt, the best result in the tested range was obtained at order 4. For war_and_peace.ru.txt, the compression ratio continued to improve up to order 8 before decreasing at order 9.
Therefore, there is no single PPM order that is optimal for every type of text.
The best PPMC configuration was also compared with several other compression approaches.
For war_and_peace.ru.txt:
| Algorithm | Compression ratio |
|---|---|
| Huffman | 2.90 |
| Arithmetic Coding | 2.93 |
| RLE | 0.99 |
| BWT + RLE | 1.37 |
| BWT + MTF + Huffman | 5.17 |
| BWT + MTF + Arithmetic Coding | 5.23 |
| LZ77 | 2.1737 |
| LZ77 + Huffman | 2.668 |
| LZ77 + Arithmetic Coding | 2.812 |
| PPMC8 | 3.045 |
The results show that PPM provides useful compression for text data, but more complex compression pipelines such as BWT + MTF + arithmetic coding achieved higher compression ratios on the tested datasets.
This comparison also illustrates an important characteristic of PPM: its effectiveness strongly depends on the statistical structure of the input data and the selected model order.
The experiments demonstrate several properties of the implemented PPM compressor:
- PPM can provide effective lossless compression for textual data.
- The choice of model order has a significant impact on compression ratio.
- The optimal order depends on the input dataset.
- Exclusion improves the compression ratio in the tested configurations.
- Update exclusion reduces the amount of model updating and can improve execution speed.
- PPM performs competitively with simpler compression approaches such as standalone Huffman coding and arithmetic coding on the tested text files.
- More complex transformation pipelines can achieve higher compression ratios.
.
├── PPM.py
├── PPM_compressor.py
├── PPM_decompressor.py
├── ArithmeticCoding.py
├── ArithmeticCodingCompress.py
├── ArithmeticCodingDecompress.py
├── BitsBuffer.py
├── ac.py
├── CompressTextTest.py
├── test.py
└── test data
Contains the context model and PPM-specific compression logic.
Provide the high-level compression and decompression procedures.
Contains the arithmetic coding implementation used as the entropy-coding stage.
Provides bit-level operations required by the coding process.
- Python
- Prediction by Partial Matching (PPM)
- PPMC
- Arithmetic coding
- Adaptive statistical modeling
- Context modeling
- Lossless compression
- Fixed-point arithmetic
This project was developed as a university course project for the Algorithms and Data Structures discipline in 2024.
The task was to implement a compressor based on Prediction by Partial Matching (PPM) and investigate how different model configurations and compression improvements affect the resulting compression ratio.
The project included both the implementation of the compressor/decompressor and an experimental evaluation using text datasets in different languages and with different statistical characteristics.
The project was developed as a team course project.
This project provided practical experience with:
- implementing adaptive statistical compression algorithms;
- context-based probability modeling;
- PPM model construction;
- escape-symbol handling;
- arithmetic coding;
- fixed-point arithmetic;
- adaptive model updates;
- evaluating compression algorithms using real datasets;
- analyzing the relationship between model complexity and compression ratio;
- comparing different compression techniques experimentally.
The project also demonstrated an important practical aspect of compression algorithms: increasing model complexity does not automatically produce better results, and the optimal configuration depends on the characteristics of the input data.
The final implementation does not include all known PPM optimization techniques.
In particular, Local Order Estimation (LOE) and Secondary Escape Estimation (SEE) were not implemented due to the time constraints of the course project.
Possible future improvements include:
- implementing LOE;
- implementing SEE;
- improving model memory management;
- optimizing context lookup;
- evaluating larger and more diverse datasets;
- benchmarking encoding and decoding speed;
- comparing memory consumption between different model orders.
This project implements a lossless text compressor based on Prediction by Partial Matching with arithmetic coding.
The implementation combines an adaptive context model with entropy coding and includes additional PPM techniques such as exclusion and update exclusion.
Experimental results show that the effectiveness of PPM depends strongly on the input data and selected model order. The project therefore focuses not only on implementing the algorithm, but also on experimentally studying the trade-offs between compression ratio, model complexity and execution efficiency.