Skip to content
/ ctwz Public

A lossless compressor based on Context Tree Weighting

Notifications You must be signed in to change notification settings

meiji163/ctwz

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 

Repository files navigation

ctwz

ctwz is a lossless compressor based on the Context Tree Weighting method1. It takes byte-level contexts and makes binary predictions using an ASCII decomposition tree2. It is mainly good for large files.

Build

To build use cmake

$ cmake .
$ make

or simply compile with C++17.

Usage

$ ./ctwz -h
ctwz:
	Context tree weighting compressor
	author: Meijke Balay <mysatellite99@gmail.com>
usage:
	encode: ctwz [-d depth] file
	decode: ctwz -x file

-d Specifies the depth of the context trees (default=8). Greater depths can improve compression for large files but require more memory and computation.

Benchmarks

Some results on the Canterbury Corpus using depth 12 ctwz, with gzip (Lempel-Ziv) for comparison

file size(bytes) ctwz gzip
E.coli 4638690 1209950 1342009
bible.txt 4047392 898767 1177372
world192.txt 2473400 561751 724995
kennedy.xls 1029744 167460 204016
ptt5 513216 55562 56482
plrabn.txt 481861 151034 194357
alice29.txt 152089 47817 54428
asyoulik.txt 125179 42720 48922

Todo

  • Parallelize context tree computations
  • Lower memory requirements with pruning

References

1: Willems, F., Shtarkov, Y., & Tjalkens, T. (1995). The context-tree weighting method: basic properties. IEEE Trans. Inf. Theory, 41, 653-664.
2: Volf, P. (2002). Weighting Techniques in Data Compression Theory and Algorithms. Ph.D. thesis, Technische Universiteit Eindhoven.

About

A lossless compressor based on Context Tree Weighting

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published