Applications of DAWGs to Data Compression

Anselm Blumer
Additional contact information
Anselm Blumer: Tufts University, Department of Computer Science

A chapter in Sequences, 1990, pp 303-311 from Springer

Abstract: Abstract A string compression technique can compress well only if it has an accurate model of the data source. For a source with statistically independent characters, Huffman or arithmetic codes give optimal compression [11]. In this case it is straightforward to use a fixed source model if the statistics are known in advance, or to adapt the model to unknown or changing statistics. For the many sources which produce dependent characters, a more sophisticated source model can provide much better compression at the expense of the extra space and time for storing and maintaining the model. The space required by a straightforward implementation of a Markov model grows exponentially in the order of the model. The Directed Acyclic Word Graph (DAWG) can be built in linear time and space, and provides the information needed to obtain compression equal to that obtained using a Markov model of high order. This paper presents two algorithms for string compression using DAWGs. The first is a very simple idea which generalizes run-length coding. It obtains good compression in many cases, but is provably non-optimal. The second combines the main idea of the first with arithmetic coding, resulting in a great improvement in performance.

Keywords: Directed Acyclic Graph; Data Compression; Suffix Tree; Good Compression; Extra Space (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_24

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_24

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().