Dictionary coder
Encyclopedia
A dictionary coder, also sometimes known as a substitution coder, is a class of lossless data compression
algorithms which operate by searching for matches between the text to be compressed and a set of string
s contained in a data structure
(called the 'dictionary') maintained by the encoder. When the encoder finds such a match, it substitutes a reference to the string's position in the data structure.
in the limited storage space of a PDA
generally builds a static dictionary from a concordance
of the text and then uses that dictionary to compress the verses.
More common are methods where the dictionary starts in some predetermined state but the contents change during the encoding process, based on the data that has already been encoded. Both the LZ77 and LZ78 algorithms work on this principle. In LZ77, a data structure called the "sliding window" is used to hold the last N bytes of data processed; this window serves as the dictionary, effectively storing every substring that has appeared in the past N bytes as dictionary entries. Instead of a single index identifying a dictionary entry, two values are needed: the length, indicating the length of the matched text, and the offset (also called the distance), indicating that the match is found in the sliding window starting offset bytes before the current text.
LZ78 uses a more explicit dictionary structure; at the beginning of the encoding process, the dictionary only needs to contain entries for the symbols of the alphabet used in the text to be compressed, but the indexes are numbered so as to leave spaces for many more entries. At each step of the encoding process, the longest entry in the dictionary that matches the text is found, and its index is written to the output; the combination of that entry and the character that followed it in the text is then added to the dictionary as a new entry.
The LZ78 decoder receives each symbol and, if it already has a previous prefix, adds the prefix plus the symbol to its own separate dictionary. It then outputs the symbol and sets the prefix to the last character of the symbol. One "gotcha" here is that if the encoder sees a sequence of the form STRING STRING CHARACTER, where STRING is currently in the dictionary, it will output a symbol that is one higher than the decoder's last dictionary entry. The decoder must detect such an event and output the previous symbol plus its first character. This symbol will always be only one higher than the last numbered symbol in the decoder's dictionary.
Example: The encoder is encoding BANANANANA; after outputting the indexes for B, A, N and AN the encoder has in its dictionary entries for BA, AN, NA, and ANA and the decoder has entries for BA, AN, and NA. The encoder can match "ANA" so it sends the index for "ANA" and adds "ANAN" to the dictionary. However, the decoder doesn't have "ANA" in its dictionary. It must guess that this new symbol is the prefix (the last symbol it received, "AN") plus its first character ("A"). It then outputs "ANA" and adds the prefix plus the last character of the output ("A" again) to the dictionary. Decoding can continue from there.
Another dictionary coding scheme is byte pair encoding
, where a byte that does not appear in the source text is assigned to represent the most commonly appearing two-byte combination. This can be done repeatedly as long as there are bytes that do not appear in the source text, and bytes that are already representing combinations of other bytes can themselves appear in combinations.
Lossless data compression
Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be reconstructed, in exchange...
algorithms which operate by searching for matches between the text to be compressed and a set of string
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
s contained in a data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
(called the 'dictionary') maintained by the encoder. When the encoder finds such a match, it substitutes a reference to the string's position in the data structure.
Methods and applications
Some dictionary coders use a 'static dictionary', one whose full set of strings is determined before coding begins and does not change during the coding process. This approach is most often used when the message or set of messages to be encoded is fixed and large; for instance, a software package that stores the contents of the BibleBible
The Bible refers to any one of the collections of the primary religious texts of Judaism and Christianity. There is no common version of the Bible, as the individual books , their contents and their order vary among denominations...
in the limited storage space of a PDA
Personal digital assistant
A personal digital assistant , also known as a palmtop computer, or personal data assistant, is a mobile device that functions as a personal information manager. Current PDAs often have the ability to connect to the Internet...
generally builds a static dictionary from a concordance
Concordance (publishing)
A concordance is an alphabetical list of the principal words used in a book or body of work, with their immediate contexts. Because of the time and difficulty and expense involved in creating a concordance in the pre-computer era, only works of special importance, such as the Vedas, Bible, Qur'an...
of the text and then uses that dictionary to compress the verses.
More common are methods where the dictionary starts in some predetermined state but the contents change during the encoding process, based on the data that has already been encoded. Both the LZ77 and LZ78 algorithms work on this principle. In LZ77, a data structure called the "sliding window" is used to hold the last N bytes of data processed; this window serves as the dictionary, effectively storing every substring that has appeared in the past N bytes as dictionary entries. Instead of a single index identifying a dictionary entry, two values are needed: the length, indicating the length of the matched text, and the offset (also called the distance), indicating that the match is found in the sliding window starting offset bytes before the current text.
LZ78 uses a more explicit dictionary structure; at the beginning of the encoding process, the dictionary only needs to contain entries for the symbols of the alphabet used in the text to be compressed, but the indexes are numbered so as to leave spaces for many more entries. At each step of the encoding process, the longest entry in the dictionary that matches the text is found, and its index is written to the output; the combination of that entry and the character that followed it in the text is then added to the dictionary as a new entry.
Examples
Example: The text to be compressed starts "HURLYBURLY". In the first six steps of the encoding, we output the indexes for H, U, R, L, Y, and B, and we add to the dictionary new entries for HU, UR, RL, LY, YB, and BU. On the seventh step, we are at the start of "URLY"; the longest entry in our dictionary that matches the text is "UR", an entry we added on the second step. We send the index for "UR" to the output, and add an entry for "URL" to the dictionary. On the eighth step, we send the index for "LY" to the output, and assuming that a space follows HURLYBURLY in the text, we add an entry for "LY " to the dictionary. If later in the text we were to encounter the word "HURLYBURLY" again, we could encode it this time (assuming we started at the H) in no more than five indexes:- HU, RL, YB, URL, and Y.The LZ78 decoder receives each symbol and, if it already has a previous prefix, adds the prefix plus the symbol to its own separate dictionary. It then outputs the symbol and sets the prefix to the last character of the symbol. One "gotcha" here is that if the encoder sees a sequence of the form STRING STRING CHARACTER, where STRING is currently in the dictionary, it will output a symbol that is one higher than the decoder's last dictionary entry. The decoder must detect such an event and output the previous symbol plus its first character. This symbol will always be only one higher than the last numbered symbol in the decoder's dictionary.
| Encoding HURLYBURLY | |
|---|---|
| H | H |
| U | HU |
| R | UR |
| L | RL |
| Y | LY |
| B | YB |
| U | BU |
| R | |
| L | URL |
| Y | RLY (doesn't matter) |
Example: The encoder is encoding BANANANANA; after outputting the indexes for B, A, N and AN the encoder has in its dictionary entries for BA, AN, NA, and ANA and the decoder has entries for BA, AN, and NA. The encoder can match "ANA" so it sends the index for "ANA" and adds "ANAN" to the dictionary. However, the decoder doesn't have "ANA" in its dictionary. It must guess that this new symbol is the prefix (the last symbol it received, "AN") plus its first character ("A"). It then outputs "ANA" and adds the prefix plus the last character of the output ("A" again) to the dictionary. Decoding can continue from there.
Another dictionary coding scheme is byte pair encoding
Byte pair encoding
Byte pair encoding or digram coding is a simple form of data compression in which the most common pair of consecutive bytes of data is replaced with a byte that does not occur within that data. A table of the replacements is required to rebuild the original data...
, where a byte that does not appear in the source text is assigned to represent the most commonly appearing two-byte combination. This can be done repeatedly as long as there are bytes that do not appear in the source text, and bytes that are already representing combinations of other bytes can themselves appear in combinations.