ace

README

Documentation

Overview

Package ace provides an Abstract Compression Engine for lossless entropy coding/decoding.

Highlights

• Similar to Re-Pair and recursive BPE.
• Zero non-stdlib dependencies. CGo-free.
• No wire/transport format, hence "Abstract".

ACE is not practical for large inputs. Both encoder and decoder consume multiple bytes of memory per symbol.

Maximum compressed sequence is 2^32 symbols. Many machines will run out of memory long before handling sequences of such length.

It is usually possible to encode and later decode a 10^9 symbol sequence on a machine with 16 GB RAM.

Compression ratios

=== RUN   Test
    all_test.go:68: abcabdabcabd   : syms in=       12 syms out=      8 k=66.67% te=       150.03µs td=          1.2µs
    all_test.go:68: bbpe           : syms in=     1521 syms out=    787 k=51.74% te=       596.18µs td=        12.22µs
    all_test.go:68: enwik3         : syms in=     1000 syms out=    370 k=37.00% te=       450.82µs td=        13.45µs
    all_test.go:68: enwik4         : syms in=    10000 syms out=   3552 k=35.52% te=     3.202368ms td=        87.96µs
    all_test.go:68: enwik5         : syms in=   100000 syms out=  25913 k=25.91% te=    26.519369ms td=     1.353479ms
    all_test.go:68: enwik6         : syms in=  1000000 syms out= 195100 k=19.51% te=   258.766563ms td=    14.052454ms
    all_test.go:68: gettysburg     : syms in=     1463 syms out=    737 k=50.38% te=       651.45µs td=        13.79µs
    all_test.go:68: gettysburgx10  : syms in=    14630 syms out=   1497 k=10.23% te=     2.052279ms td=       139.17µs
    all_test.go:68: gettysburgx100 : syms in=   146300 syms out=   1510 k= 1.03% te=    10.405846ms td=     1.069079ms
    all_test.go:68: zero3          : syms in=     1000 syms out=     22 k= 2.20% te=        84.93µs td=         6.81µs
    all_test.go:68: zero4          : syms in=    10000 syms out=     29 k= 0.29% te=       603.43µs td=        65.84µs
    all_test.go:68: zero5          : syms in=   100000 syms out=     36 k= 0.04% te=     5.077928ms td=       684.19µs
    all_test.go:68: zero6          : syms in=  1000000 syms out=     43 k= 0.00% te=    49.980859ms td=     7.459657ms
--- PASS: Test (0.39s)
PASS
ok  	modernc.org/ace	0.389s

Notes:

• abcabdabcabd content is "abcabdabcabd".
• bbpe is from What is BBPE -- Tokenizer behind LLMs.
• enwikN is the first 10^N bytes from enwik9.
• gettysburg is by A. Lincoln.
• gettysburgxN is N copies of gettysburg concatenated.
• zeroN is 10^N zero bytes.
• k = (number of output symbols) / (number of input symbols). Smaller 'k' is better.
• te = time to encode
• td = time to decode

Performance

goos: linux
goarch: amd64
pkg: modernc.org/ace
cpu: AMD Ryzen 9 3900X 12-Core Processor
BenchmarkEncodeEnwik6-24    	       4	 272302896 ns/op	   3.67 MB/s	11082472 B/op	    1078 allocs/op
BenchmarkEncodeZero6-24     	      22	  50528853 ns/op	  19.79 MB/s	    2456 B/op	      18 allocs/op
BenchmarkDecodeEnwik6-24    	      90	  19135398 ns/op	  52.26 MB/s	 9356057 B/op	      64 allocs/op
BenchmarkDecodeZero6-24     	     100	  10196645 ns/op	  98.07 MB/s	 5242147 B/op	      41 allocs/op

Index

• type Decoder
  • func NewDecoder(firstMeta uint32, write func(uint32)) (*Decoder, error)
  • func (d *Decoder) Decode(s uint32)
• type Encoder
  • func NewEncoder(firstMeta uint32, write func(uint32)) (*Encoder, error)
  • func (e *Encoder) Encode(s uint32)
  • func (e *Encoder) Flush()

Types

type Decoder

type Decoder struct {
	// contains filtered or unexported fields
}

Decoder represents the decoding state.

func NewDecoder

func NewDecoder(firstMeta uint32, write func(uint32)) (*Decoder, error)

NewDecoder returns a newly created Decoder. 'firstMeta' is the value used for encodind. 'write' is called to output symbols.

func (*Decoder) Decode

func (d *Decoder) Decode(s uint32)

Decode adds the expansion of 's' to the decoded sequence.

type Encoder

type Encoder struct {
	// contains filtered or unexported fields
}

Encoder represents the encoding state.

func NewEncoder

func NewEncoder(firstMeta uint32, write func(uint32)) (*Encoder, error)

NewEncoder returns a newly created Encoder. 'write' is called to output symbols.

func (*Encoder) Encode

func (e *Encoder) Encode(s uint32)

Encode adds the encoding of 's' to the encoded sequence. 's' < 'firstMeta'.

func (*Encoder) Flush

func (e *Encoder) Flush()

Flush flushes the output. Must be called before completing.