Loading...
Please wait, while we are loading the content...
Similar Documents
Lossless Compression Via Bisection Trees (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Kieffer, John Yang, En-Hui Nelson, Gregory Cosman, Pamela |
| Abstract | Each data string over a finite alphabet of length a power of two is represented via a binary tree called a bisection tree. The nodes of the bisection tree correspond to the members of the smallest class of substrings of the data string which contains the data string and is closed with respect to bisection. A data string can be perfectly reconstructed from its bisection tree. A lossless data compression algorithm is presented which compresses the data string by compressing its bisection tree. This algorithm is shown to be a universal algorithm in the sense that it yields a compression performance at least as good as the compression performance provided by any finite-state sequential lossless data compression algorithm, asymptotically as the length of the data string goes to infinity. Index Terms: lossless data compression, arithmetic coding, entropy, universal algorithms I Introduction Throughout this paper, let A be a generic symbol denoting a finite alphabet containing at least tw... |
| File Format | |
| Language | English |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Data String Lossless Compression Via Bisection Tree Bisection Tree Compression Performance Finite Alphabet Universal Algorithm Index Term Bisection Tree Correspond Arithmetic Coding Lossless Data Compression Algorithm Generic Symbol Binary Tree Lossless Data Compression |
| Content Type | Text |
| Resource Type | Technical Report |
