Cover Image

Non-greedy parsing algorithms for the dictionary data compression /

We describe modifications of a data compression algorithm

Bibliographic Details
Main Author: Nagumo, Hideo, 1957-
Format: Thesis Book
Language:English
Published: [Place of publication not identified] : [publisher not identified] ; 1996.
Subjects:
Major electrical engineering.
Online Access:http://proxy.library.tamu.edu/login?url=http://proquest.umi.com/pqdweb?did=739669021&sid=1&Fmt=2&clientId=2945&RQT=309&VName=PQD
Description
Summary:We describe modifications of a data compression algorithm
based on dictionary techniques so that the resulting
algorithms can compress gray-scale images efficiently. We
also describe parallel algorithms for two parsing strategies
for static dictionary compression: optimal parsing with
dictionaries that have the prefix property, and longest
fragment first (LFF) parsing. Data compression based on
dictionary techniques works by replacing phrases in the input
string with the corresponding dictionary indexes. The
dictionary can be static or dynamic. In static dictionary
compression, the dictionary contains a predetermined fixed
set of entries. In dynamic dictionary compression, the
dictionary changes its entries during compression. In the
first part, we modify an LZ77-based compression algorithm,
which is a kind of dynamic dictionary compression algorithm,
so that the resulting algorithms can compress gray-scale
images efficiently. Our compression algorithm gives
compression comparable to JPEG lossless mode, and its speed
is about twice that of JPEG lossless mode with arithmetic
coding. In the second part, we present parallel algorithms
for two parsing strategies for the static dictionary
compression. One is optimal parsing with dictionaries that
have the prefix property, for which our algorithm requires
O(L + log n) time and O(n) processors, where n is the number
of symbols in the input string, and L is the maximum length
of the dictionary entries. Previous results run in O(L + log
n) time using O(n 2) processors, or in O(L + log2 n) time
using O(n) processors. The other strategy uses longest
fragment first (LFF) parsing, for which our algorithm
requires O(L + log n) time and 0(n log L) processors.
Previous results here obtained an O(L log n) time performance
on O(n/ log n) processors.
Item Description:Vita.
"Major Subject: Electrical Engineering".
Physical Description:xi, 125 leaves : illustrations ; 28 cm.
Issued also on microfiche from University Microfilms Inc.
Bibliography:Includes bibliographical references: pages 85-88.