Algorithmic applications of data compression techniques
by Chen, Shenfeng, Ph.D., Duke University, 1996, 155 pages; AAT 9715387
Abstract (Summary)
In the process of algorithm design, an innovative use of certain data structure or computational technique suited for the given problem can greatly improve the performance of the algorithm. In this thesis we investigate the problem of using techniques and data structures in data compression area to aid design and analysis of algorithmic problems in other areas. The study is motivated by the fact that the best compression algorithms are the ones that utilize various techniques to explore and predict the statistical pattern of the inputs well and then tailor the algorithms to suit the input pattern in the most efficient way.
First we give an overview on data structures and techniques in data compression area. We then demonstrate the effectiveness of data compression techniques by case studies of four fundamental problems in different areas: sorting, string matching, volume rendering and graph compression. We assume certain statistical properties of the input source that hold widely for practical input data. For example, in the sorting problem we assume that the inputs are binary keys drawn from a stationary and ergodic source with bounded entropy, while in the volume rendering problem we assume the inputs are 3D image data samples. Based on these assumptions, we present novel algorithms for these problems which utilize various data structures and techniques in data compression area to speed up computation. The time complexities of our algorithms are determined by the specific input assumptions and data compression techniques used. Data compression techniques, such as unique parsing, prefix matching, dictionary construction, lossy image compression and Huffman coding, are used to aid many aspects of algorithm design such as algorithmic procedures, operations on data structures, theorem proving and complexity analysis.
Based on a concrete study of these problems, we propose a theoretical framework which identifies the class of problems which can be solved more efficiently by applying data compression techniques to adapt to certain statistical assumptions of the input source. Finally, we outline several interesting topics as our future work.
Part of this work was Supported by NSF Grant NSFIRI9100681, Rome Labs Contracts F3060294C0037, ARPA/SISTO contracts N0001491J1985, and N0001492C0182 under subcontract KI92010182.
Indexing (document details)
Advisor: 

School: 
Duke University 
School Location: 
United States  North Carolina 
Keyword(s): 

Source: 
DAIB 57/12, p. 7598, Jun 1997 
Source type: 
Dissertation 
Subjects: 

Publication Number: 
AAT 9715387 
ISBN: 
9780591232387 
Document URL: 


