Name
Abstract | ||
|---|---|---|
We consider the problem of how to compactly encode simply-typed λ-terms into bit strings. The work has been motivated by Kobayashi et al.’s recent work on higher-order data compression, where data are encoded as functional programs (or, λ-terms) that generate them. To exploit its good compression power, the compression scheme has to come with a method for compactly encoding the λ-terms into bit strings. To this end, we propose two type-based bit-encoding schemes; the first one encodes a λ-term into a sequence of symbols by using type information, and then applies arithmetic coding to convert the sequence to a bit string. The second one is more sophisticated; we prepare a context-free grammar (CFG) that describes only well-typed terms, and then use a variation of arithmetic coding specialized for the CFG. We have implemented both schemes and confirmed that they often output more compact codes than previous bit encoding schemes for λ-terms. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2951913.2951918 | ICFP |
Field | DocType | Citations |
Bit plane,Computer science,Bit field,Algorithm,Theoretical computer science,Bit numbering,Data compression,Bit manipulation,Bit array,Arithmetic coding,Context-adaptive binary arithmetic coding | Conference | 0 |
PageRank | References | Authors |
0.34 | 9 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| kotaro takeda | 1 | 0 | 0.68 |
| Naoki Kobayashi | 2 | 129 | 33.47 |
| Kazuya Yaguchi | 3 | 6 | 1.41 |
| Ayumi Shinohara | 4 | 936 | 88.28 |