# Frequency Substitution Encoding Discussion and Implementation

### by Michael Dipperstein

Frequency Substitution is a term I made up for a transformation that I saw discussed on another web site. I have since lost the link to the site, but if somebody can find it I'll be happy to reference it.

The idea behind Frequency Substitution is simple. The goal is to transform data by replacing the highest frequency symbols with the lowest values. It sounded simple enough, so I thought that I'd give it a try.

Normally this type of transformation doesn't produce useful results, but there are a few compression techniques, such as Rice (Golomb) Coding, that produce smaller code words for lower value symbols. By making the lower valued symbols the most frequent symbols, these encoding schemes may achieve better compression ratios.

As with my other compression implementations, my intent is to publish an easy to follow ANSI C implementation of frequency substitution encoding and decoding. Anyone familiar with ANSI C should be able to follow and learn from my implementation. I'm sure that there's room for improvement of speed and memory usage, but this project is about learning and sharing, not perfection.

Click here for a link to my frequency substitution source. The rest of this page discusses the concepts involved with frequency substitution and my implementation.

## Algorithm Overview

The goal of frequency substitution is to transform data by replacing the highest frequency symbols with the lowest values. In a data set contains 256 unique symbols, the most common symbol will be replaced with 0 and the least common symbol will be replaced with 255.

### Encoding

Encoding a data stream using frequency substitution is a two pass process. The first pass is used to count the frequency of the symbols. After the first pass, a table of substitution codes is generated. Then a second pass is made, where an encoded data set is generated using the substitution table.

The first pass should be straight forward, start with a table indicating a frequency of 0 for all possible symbols, then add 1 to a symbol's frequency count every time it is encountered in the data stream. Next sort the substitution table most frequent to least frequent.

On the second pass, write out enough information for the decoder to reconstruct the table, then read in each unencoded symbol and write out the sorted position of that symbol.

**Example:**

Given a symbol set of 0 ... 9, encode the following data stream:

3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9

Based on the discussion above, encoding input consists of the following steps:

**Step 1.** Start with an empty table.

Symbol | Count |
---|---|

0 | 0 |

1 | 0 |

2 | 0 |

3 | 0 |

4 | 0 |

5 | 0 |

6 | 0 |

7 | 0 |

8 | 0 |

9 | 0 |

**Step 2.** Generate a frequency table for the data
stream.

Symbol | Count |
---|---|

0 | 0 |

1 | 2 |

2 | 4 |

3 | 7 |

4 | 3 |

5 | 3 |

6 | 3 |

7 | 2 |

8 | 3 |

9 | 4 |

**Step 3.** Sort the symbols by frequency.

Sorted Position |
Symbol | Count |
---|---|---|

0 | 3 | 7 |

1 | 2 | 4 |

2 | 9 | 4 |

3 | 4 | 3 |

4 | 5 | 3 |

5 | 6 | 3 |

6 | 8 | 3 |

7 | 1 | 2 |

8 | 7 | 2 |

9 | 0 | 0 |

**Step 4.** Write out the encoded data by substituting a
symbol for it's position in the frequency table.

3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9

becomes

0,7,3,7,4,2,1,5,4,0,4,6,2,8,2,0,1,0,6,3,5,1,5,3,0,0,6,0,1,8,2

A quick sanity check shows that the sum of the symbols in the initial string (150) is greater than the sum of symbols in the encoded string (96) so we must have lowered the average symbol value.

### Decoding

Decoding data that has been encoded by frequency substitution is a single pass process. Given a table of frequency substitutions, reverse the substitutions preformed during the encoding process.

**Example:**

The following sequence and table of frequency substitutions

0,7,3,7,4,2,1,5,4,0,4,6,2,8,2,0,1,0,6,3,5,1,5,3,0,0,6,0,1,8,2

Sorted Position |
Symbol | Count |
---|---|---|

0 | 3 | 7 |

1 | 2 | 4 |

2 | 9 | 4 |

3 | 4 | 3 |

4 | 5 | 3 |

5 | 6 | 3 |

6 | 8 | 3 |

7 | 1 | 2 |

8 | 7 | 2 |

9 | 0 | 0 |

Produces the following sequence

3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9

If you were paying attention, you're probably wondering how the encoder passed the table of frequency substitutions to the decoder. The next section provides some ideas and discusses my implementations.

### The Substitution Key

Before the decoder can do anything with the encoded data, it needs a key that tells it how to undo the substitutions. Since the key is needed immediately, it makes sense for the encoder to output the key before it outputs the encoded data.

So what kind of information do we need to have in the key? In order for the key to be useful, it must contain the original symbol and the value that it was substituted for.

If there are N possible symbols, the simplest thing to do is write out the complete list of all N (symbol, substitution) pairs. Such a list contains 2 × N entries. My goal was to use frequency substitution for data compression, so it would be nice if the list could be made even smaller.

As it turns out there are at least three ways to make the list smaller:

- Only transmit keys for symbols that appear in the data.
- Use the position of the list entries as the symbol value and the value at that position as the substitution representing the symbol.
- Use the position of the list entries as the substitution value and the value at that position as the symbol that the substitution encodes.

I chose to use the position as the code word.

#### Position As Code Word Value

Since the substitution key is the first thing output by the encoder, the key for all N symbols may be output in positions 0 ... (N - 1). Position 0 contains the symbol represented by the substitution 0, position 1 contains the symbol represented by substitution 1, and so on This method requires just N entries for N (substitution, symbol) pairs.

#### Excluding Unused Symbols

Sometimes the data being encoded is sparse; it only uses a fraction of all of the symbols in the symbol set. In this case there will be a large number of unneeded entries in a position indexed key.

For spare data sets, we can omit any symbol that isn't encoded, but to do that, the there has to be a way to indicate to the decoder that there are no more (substitution, symbol) pairs. I do this by repeating the previous symbol value.

**Example:**

The substitution key for the decoding example is
written as the sequence 3,2,9,4,5,6,8,1,7,7.

### Effectiveness

If you actually read my introduction, you'd notice that I thought frequency substitution might be helpful when used with Rice (Golomb) Coding. In order to test that theory, I used the Calgary Corpus as a test data set.

The table below shows the results of applying frequency substitution to the Calgary Corpus and then using Rice coding (with K = 4 and K = 2) to compress encoded files. Both position indexed and sparse versions of my frequency substitution implemention were used. For reference, the table also provides results for Rice coding alone and Rice coding with BWT and MTF.

The results of my test appear in the following tables:

File | Orig | K = 4 | K = 2 | ||||
---|---|---|---|---|---|---|---|

Rice | BWT + Rice | FreqSub + Rice | Rice | BWT + Rice | FreqSub + Rice | ||

bib | 111261 | 132690 | 73271 | 76575 | 310945 | 63729 | 84694 |

book1 | 768771 | 983146 | 498044 | 500220 | 2411218 | 415556 | 455421 |

book2 | 610856 | 780344 | 396846 | 404871 | 1912774 | 327191 | 395796 |

geo | 102400 | 127322 | 92851 | 90115 | 300282 | 164232 | 152588 |

news | 377109 | 466867 | 251512 | 260672 | 1122082 | 232063 | 289901 |

obj1 | 21504 | 27379 | 17040 | 19192 | 66546 | 23962 | 33112 |

obj2 | 246814 | 322336 | 179249 | 212593 | 812091 | 203702 | 358858 |

paper1 | 53161 | 66994 | 34729 | 35926 | 162996 | 29119 | 37180 |

paper2 | 82199 | 106376 | 53286 | 53804 | 262680 | 43819 | 50000 |

pic | 513216 | 392391 | 327985 | 325044 | 494376 | 227137 | 218680 |

progc | 39611 | 46306 | 26174 | 27624 | 106976 | 22658 | 31321 |

progl | 71646 | 83408 | 46170 | 47521 | 193202 | 34977 | 46736 |

progp | 49379 | 57154 | 32098 | 33668 | 130982 | 25144 | 35320 |

trans | 93695 | 105406 | 61614 | 66797 | 237650 | 51727 | 81433 |

Total | 3141622 | 3698119 | 2090869 | 2154622 | 8524800 | 1865016 | 2197750 |

Percent | 117.71% | 66.55% | 68.58% | 271.35% | 59.36% | 69.96% |

There are three things that you should learn from this table:

- The Calgary Corpus contains data ill suited for Rice encoding.
- Frequency substitution may be applied to the Calgary Corpus data to enable Rice encoding to compress the data.
- Better compression results may be achieved by applying BWT and MFT.

So why use frequency substitution? If your goal is to achieve the best possible compression ratios, most data sets don't provide a compelling reason. However, the computational and memory resources required for frequency substitution is less than that required by BWT and MFT. I didn't provide any proof of that, you'll just have to trust me or see for yourself.

## Library Code Interface

### Encoding Data

#### FreqEncodeFile

Declaration:

`int FreqEncodeFile(FILE *inFile, FILE *outFile);`

Description:

This routine reads an input file and counts character frequencies. The file is then read again and an output file is created where each input character is encoded with a value associated with its frequency. The more frequent the symbol, the lower the value.

Parameters:

`inFile`

- The file stream to be encoded. It must opened and rewindable.
NULL pointers will return an error.

`outFile`

- The file stream receiving the encoded results. It must be opened.
NULL pointers will return an error.

Effects:

`inFile`

is encoded using the using frequency
substitution and written to `outFile`

. Neither file is
closed after exit.

Returned:

0 for success, -1 for failure. `errno`

will be set in
the event of a failure.

### Decoding Data

#### FreqDecodeFile

Declaration:

`int FreqDecodeFile(FILE *inFile, FILE *outFile);`

Description:

This routine reads a frequency substitution encode file and writes a decoded version to the specified output file.

Parameters:

`inFile`

- The file stream to be decoded. It must opened. NULL pointers
will return an error.

`outFile`

- The file stream receiving the decoded results. It must be opened.
NULL pointers will return an error.

Effects:

`inFile`

is decoded using the frequency substitution
algorithm and written to `outFile`

. Neither file is
closed after exit.

Returned:

0 for success, -1 for failure. `errno`

will be set in
the event of a failure.

### Portability

All the source code that I have provided is written in strict ANSI C. I would expect it to build correctly on any machine with an ANSI C compiler. I have only tested the code compiled with gcc on Linux.

## Actual Software

I am releasing my implementations offrequency substitution encoding and decoding under the LGPL. As I add enhancements or fix bugs, I will post them here as newer versions. The larger the version number, the newer the version. I will retain the older versions for historical reasons. I recommend that most people download the newest version unless there is a compelling reason to do otherwise.

Each version is contained in its own zipped archive which includes the source files and brief instructions for building an executable. None of the archives contain executable programs. A copy of the archives may be obtained by clicking on the links below.

Version | Comment |
---|---|

Version 0.2 | Upgrade to latest optlist library. |

Changed the API so that encode and decode routines accept opened file streams instead of file names. | |

New sparse header that's never bigger than full header, so only one kind of header is provided. | |

Changed return value to 0 for success and -1 for failure with reason in errno. | |

Written with tighter adherence to Michael Barr's Top 10 Bug-Killing Coding Standard Rules. | |

Version 0.1 | Initial release. |

If you have any further questions or comments, you may contact me by e-mail. My e-mail address is: mdipper@alumni.engr.ucsb.edu