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 3-D 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 NSF-IRI-91-00681, Rome Labs Contracts F30602-94-C-0037, ARPA/SISTO contracts N00014-91-J-1985, and N00014-92-C-0182 under subcontract KI-92-01-0182.

Indexing (document details)


Reif, John H.


Duke University

School Location:

United States -- North Carolina


string matching, sorting, graphs, volume rendering


DAI-B 57/12, p. 7598, Jun 1997

Source type:



Computer science

Publication Number:

AAT 9715387



Document URL: