Abstract | ||
---|---|---|
An n-state Markov model for symbol occurrences is extended to an equivalent source for variable length strings of symbols in a dictionary at every state i, which are to be encoded with the string index in the dictionary. The algorithm for building the n dictionaries optimizes the rate subject to a given total number of entries in the dictionaries, and it is practical even for Markov sources with thousand states.The speed of the algorithm stems from encoding by table look-ups of the strings instead of single symbols. For this the n dictionaries need be known both to the encoder and the decoder. A static version of the algorithm is very well suited for creation of compressed files with random access. An adaptive version is shown to be faster than the methods in the PPM class, while providing only slightly lower compression ratios. |
Year | DOI | Venue |
---|---|---|
2000 | 10.1109/DCC.2000.838153 | Data Compression Conference |
Keywords | Field | DocType |
string matching,text analysis,decoder,optimization,markov processes,compression ratio,markov model,random access,indexation,data compression,dictionary,dictionaries,decoding,encoding | String searching algorithm,Markov process,Computer science,Markov model,Markov chain,Theoretical computer science,Encoder,Data compression,Random access,Markov algorithm | Conference |
ISBN | Citations | PageRank |
0-7695-0592-9 | 3 | 0.56 |
References | Authors | |
4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ioan Tabus | 1 | 276 | 38.23 |
Gergely Korodi | 2 | 78 | 5.57 |
Jorma Rissanen | 3 | 1665 | 798.14 |