2012年3月1日
Functional programs as compressed data
Higher-Order and Symbolic Computation
- ,
- ,
- ,
- 巻
- 25
- 号
- 1
- 開始ページ
- 39
- 終了ページ
- 84
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s10990-013-9093-z
- 出版者・発行元
- Kluwer Academic Publishers
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 β-expansions (i.e., the inverse of β-reductions) for λ-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 this article, 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.
- ID情報
-
- DOI : 10.1007/s10990-013-9093-z
- ISSN : 1388-3690
- SCOPUS ID : 84881302979