LE3 .A278 2009

2009

Diamond, Jim

Acadia University

Bachelor of Science

Honours

Computer Science

Computer Science

A common method of text compression is one which replaces strings of data by a ref- erence to a dictionary. Generally, these dictionary text compression techniques will replace the longest string at every stage of the compression process (such algorithms are known as \greedy algorithms"). In previous studies it has been shown that in certain situations, selecting a smaller string for replacement (i.e., non-greedy algo- rithms) can lead to a signicant improvement in compression performance. However, if one was to create an algorithm to select the optimal way in which to select matches for replacement, every possible parsing of the input into matched strings would need to be considered. Any straight forward way of considering all of these combinations would be impractical on modern day computers. In this thesis, an algorithm is presented which is designed to reduce the complexity of storing all possible parsings. The algorithm is a variant of the LZ77 method and works by eliminating suboptimal parsings of an input string at early stages of the compression process rather than comparing all possible parsings at the very last stages of compression. It is also known that when static output methods are combined with greedy algorithms for LZ77 an optimal parsing of the input string is created. Thus, a non-greedy method is only preferred for LZ77 compression when a variable-length coding scheme is used to encode the output. A new variable-length output method is presented which is designed to be used in conjunction with the optimal parsing algorithm. The optimal parsing algorithm is then compared with a greedy parsing algorithm to show the impact that an optimal selection algorithm can have on a given LZ77 variant known as LZSS. The results show that an optimal parsing of a given input string can yield a signicant improvement in compression performance of LZSS.

The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.

https://scholar.acadiau.ca/islandora/object/theses:625