loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Data Compression Conference (DCC '95)
The structure of DMC [dynamic Markov compression]
Snowbird, Utah
March 28-March 30
ISBN: 0-8186-7012-6
S. Bunton, Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
The popular dynamic Markov compression algorithm (DMC) offers state-of-the-art compression performance and matchless conceptual simplicity. In practice, however, the cost of DMC's simplicity and performance is often outrageous memory consumption. Several known attempts at reducing DMC's unwieldy model growth have rendered DMC's compression performance uncompetitive. One reason why DMC's model growth problem has resisted solution is that the algorithm is poorly understood. DMC is the only published stochastic data model for which a characterization of its states, in terms of conditioning contexts, is unknown. Up until now, all that was certain about DMC was that a finite-context characterization exists, which was proved in using a finiteness argument. This paper presents and proves the first finite-context characterization of the states of DMC's data model Our analysis reveals that the DMC model, with or without its counterproductive portions, offers abstract structural features not found in other models. Ironically, the space-hungry DMC algorithm actually has a greater capacity for economical model representation than its counterparts have. Once identified, DMC's distinguishing features combine easily with the best features from other techniques. These combinations have the potential for achieving very competitive compression/memory tradeoffs.
Index Terms:
data compression; finite state machines; Markov processes; data structures; dynamic Markov compression algorithm; stochastic data model; finite-context characterization; states characterization; abstract structural features; data compression; finite state machines
Citation:
S. Bunton, "The structure of DMC [dynamic Markov compression]," dcc, pp.72, Data Compression Conference (DCC '95), 1995
Usage of this product signifies your acceptance of the Terms of Use.