Name
Abstract | ||
|---|---|---|
We propose an application of programming language techniques to lossless data compression, where tree data are compressed as functional programs that generate them. This \"functional programs as compressed data\" approach has several advantages. First, it follows from the standard argument of Kolmogorov complexity that the size of compressed data can be optimal up to an additive constant. Secondly, a compression algorithm is clean: it is just a sequence of beta-expansions for lambda-terms. Thirdly, one can use program verification and transformation techniques (higher-order model checking, in particular) to apply certain operations on data without decompression. In the paper, we present algorithms for data compression and manipulation based on the approach, and prove their correctness. We also report preliminary experiments on prototype data compression/transformation systems. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10990-013-9093-z | PEPM |
Keywords | Field | DocType |
functional program,kolmogorov complexity,data compression,transformation technique,transformation system,compression algorithm,lossless data compression,tree data,prototype data compression,certain operation | Inverse,Model checking,Program transformation,Kolmogorov complexity,Succinct data structure,Computer science,Correctness,Algorithm,Theoretical computer science,Data compression,Lossless compression | Conference |
Volume | Issue | ISSN |
25 | 1 | 1573-0557 |
Citations | PageRank | References |
6 | 0.73 | 37 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Naoki Kobayashi | 1 | 1172 | 75.17 |
| Kazutaka Matsuda | 2 | 112 | 10.75 |
| Ayumi Shinohara | 3 | 936 | 88.28 |
| Kazuya Yaguchi | 4 | 6 | 1.41 |