Disclaimer
Copyright (c) Arturo San Emeterio Campos 2000. All rights reserved. Permission is granted to make verbatim copies of this
document for private use only.
 

Articles

• What's compression, who can be interested and why, and how I'll explain it
• The introduction to Data Compression
• Bit input/output
• Huffman introduction
• Huffman algorithm, making codes from probabilities
• Implementing huffman code construction and its data structures
• Restricting huffman codes to a maximum length
• Implementing huffman decoding
• Introduction to lzp
• Implementing lzp
• Using linked lists to access higher orders

Articles and subsections
 

• What's compression, who can be interested and why, and how I'll explain it
• What is data compression?
• What is used data compression for?
• Why should I use data compression?
• What do I need to understand the articles?
• What will you exactly explain?
• How will you explain it?
• Closing words and where we go from here

• The introduction to Data Compression
• How does compression work?
• Text and signals: lossless and lossy compression
• Kind of models
• Computing probabilities with a finite context model
• Why do we use a finite context model?
• Entropy and the properties our codes must have
• Some coders
• Parts of a compressor
• A compressor, or how do we put it all together
• Text compression in the real world
• Measuring the compression rate
• Measuring another aspects of a compressor
• What to do now?
• References

• Bit input/output
• What is bitio?
• Bit operations: or, and, shift
• Writing a bit
• Pseudo code for writing a bit
• Reading a bit
• Pseudo code for reading a bit
• Writing a variable length value
• Reading a variable length value and an example
• Closing words

• Huffman
• Huffman introduction
• What is huffman?
• What do I need to know to implement it?
• How will you explain it?
• Closing words
• Huffman algorithm, making codes from probabilities
• Making binary codes from probabilities
• Huffman algorithm
• Huffman example step by step
• Introduction
• Data structures
• Making the huffman binary tree
• Sorting the list in the main loop
• Making the code table
• Outputting the codes
• Implementing huffman code construction and its data structures
• Introduction
• Data structures
• Making the huffman binary tree
• Sorting the list in the main loop
• Making the code table
• Outputting the codes
• Restricting huffman codes to a maximum length
• Introduction
• What's the maximum code length?
• The probabilities that make an unbalanced tree
• When does a code need more than 32 bits?
• How to solve this problem
• Implementing huffman decoding
• How to decode the codes
• Implementing the decompression process

• Lzp
• Introduction to lzp
• What is lzp?
• In what do lzp variations differ, and which one should I choose?
• Implementing lzp
• Lz algorithm and its chart flow
• How does the lzp algorithm chooses the phrases
• Output of the lzp algorithm and its chart flow
• Using a hash table to access context information
• Lzp algorithm with hash tables and its pseudo code
• Using pointers to access the text
• Using hashing to access order-3
• Matching two phrases
• Coding of literals, matches and flags
• Some final remarks
• Closing words
• Using linked lists to access higher orders
• Why do we have to use linked list?
• What is a linked list?
• How do we use a linked list?
• Data structures
• Implementing finding a context
• Implementing adding a new element and updating

First version of this article: 11-Sept-2000 Last update of this article: 11-Sept-2000
This is part of Compression programming by Arturo Campos (email address: arturo@arturocampos.com).
http://www.arturocampos.com Visit again soon for new and updated compression articles and software.