Dictionary Methods

Dictionary Methods
Dictionary based compression methods do not use a statistical model, nor do they use variable length codes. Instead they select strings of symbols and encode each string as a token using a dictionary. The dictionary holds a list of strings of symbols and it
may be static or dynamic (adaptive).
Static Dictionary
Choosing a static dictionary technique is most appropriate when considerable prior knowledge about the source is available. This technique is especially suitable for use in specific applications. For example, if the task were to compress the student records at a university, a static dictionary approach may be the best. This is because we know ahead of time that certain words such as “Name” and “Student ID” are going to appear in almost all of the records.
Dynamic dictionary
Holding strings previously found in the input stream, allowing for additions and deletions of strings as new input is being read
1)LZ77 (Lempel-Ziv) coding
The first of these dictionary-based algorithms generally emerged from the work of Jacob Ziv and Abraham Lempel. They created a superior compression algorithm which is now called LZ77 or LZ1 or sometimes calling sliding window based upon their initials and the year they created it [Ziv and Lempel 1977]. This is the next major advance in data compression history after 1952’s Huffman coding. Indeed, 25 years had to pass after Huffman invented his technique just to arrive at this excellent “sliding-window” method. Decades later, LZ77 is still the main technique in the field of data compression since it is very effective for most kinds of files.
The principle of LZ77 [Ziv and Lempel 77] is to use part of the previously-seen input stream as the dictionary. The encoder maintains a window to the input stream and shifts the input in that window from right to left as strings of symbols are being encoded. Thus, the method is based on a sliding window. The window below is divided into two parts. The part on the left is the search buffer. This is the current dictionary, and it includes symbols that have recently been input and encoded. The part on the right is the look-ahead buffer, that holds the section of the file that we are trying to compress.


What happens next is that you try to find a match for the string in the look-ahead buffer in the dictionary section. Once you find a match the string in the look-ahead is coded by generating a three-element token:
offset, length, next character

So for example, the token 32,14,d means that the phrase in the look-ahead buffer matches the dictionary at position 32 and the match continues for 14 characters. The first character in the look-ahead after the match fails is "d".
This token is output as the next token in the compressed file which is simply a stream of such tokens generated in compressing the entire file.



Algorithm for LZ77
while look-ahead buffer is not empty
go backwards in
search buffer to find longest match of the look- ahead buffer
if match found
print: (offset from window boundary, length of match, next symbol
in look a head buffer);
shift window by length+1;
else
print: (0, 0, first symbol in look-ahead buffer);
shift window by 1;
end while


EX: Given an input "abbadabba" the output would look

Search buffer Symbol Output
abbadabba (0,0,a)
a bbadabba (0,0,b)
ab badabba (1,1,a)
abba dabba (0, 0, d)
abbad abba (5,4, )



EX: Given an input "aabcbbabc" the output would look:

Search buffer Symbol Output
aabcbbabc (0,0,a)
a abcbbabc (1,1,b)
aab cbbabc (0,0,c)
aabc bbabc ( 2,1,b)
aabcbb abc (5, 3, )
aabcbbabc