Name
Abstract | ||
|---|---|---|
The best schemes for text compression use large models to help them predict which characters will come next. The actual next characters are coded with respect to the prediction, resulting in compression of information. Models are best formed adaptively, based on the text seen so far. This paper surveys successful strategies for adaptive modeling that are suitable for use in practical text compression systems.The strategies fall into three main classes: finite-context modeling, in which the last few characters are used to condition the probability distribution for the next one; finite-state modeling, in which the distribution is conditioned by the current state (and which subsumes finite-context modeling as an important special case); and dictionary modeling, in which strings of characters are replaced by pointers into an evolving dictionary. A comparison of different methods on the same sample texts is included, along with an analysis of future research directions. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1145/76894.76896 | ACM Comput. Surv. |
Keywords | Field | DocType |
adaptive modeling,h.l.l models and principles: systems and information theory-information theory general terms: algorithms,measurement additional key words and phrases: adaptive modeling,sample text,state modeling,natural language,best scheme,finite-context modeling,actual next character,experimentation,context modeling,categories and subject descriptors: e.4 data: coding and information theory-data compaction and compression,ziv-lempel compression,arithmetic coding,dictionary modeling,finite-state modeling,practical text compression system,probability distribution,current state,information model,information theory,context model | Pointer (computer programming),Text compression,Computer science,Theoretical computer science,Probability distribution,Natural language processing,Artificial intelligence,Special case | Journal |
Volume | Issue | ISSN |
21 | 4 | 0360-0300 |
Citations | PageRank | References |
103 | 17.90 | 73 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tim Bell | 1 | 487 | 88.11 |
| Ian H. Witten | 2 | 15346 | 1507.14 |
| John G. Cleary | 3 | 1791 | 365.78 |