Anti-unification compressor

Anti-unification takes two strings and returns the most specific pattern that fits both, with gaps where they differ. Given <title>Anarchism</title> and <title>Autism</title>, it returns <title>⟨gap⟩</title>.

I run this over a whole file to learn a table of templates. Each line is then stored as a template number plus the text that fills its gaps. The gap text goes through the same process again, so templates end up nested inside each other.

Each row is one record. The dim blocks are the parts every record shares. The bright blocks are the gaps.

16,724 ×[[Category:⟨gap⟩]]

483 ×└─ American ⟨gap⟩

217 ×└─ History of ⟨gap⟩

8,659 ×<text xml:space="preserve">⟨gap⟩

2,078 ×└─ #REDIRECT [[⟨gap⟩

370 ×└─ [[Image:⟨gap⟩.jpg|thumb|⟨gap⟩]]

7,997 ×<timestamp>200⟨gap⟩Z</timestamp>

6,819 ×<username>⟨gap⟩</username>

Real templates from one slice of Wikipedia, with how many lines each one matched. Indented rows are templates found inside the gap of the row above.

1 GBof English Wikipedia (enwik9)

4.1 sto find the templates, 244 MB/s

27%of the file is covered by templates

How much it saves

Templates only describe structure, so the gap contents still have to be compressed by a statistical coder. I tested with two. With a simple coder the templates save 40 MB. With a strong context-mixing coder they save 4 MB, because that coder already predicts most of the repeated structure without help.

Simple coder, no templates375.2 MB

Simple coder with templates335.5 MB

Strong coder, no templates232.5 MB

Strong coder with templates228.3 MB

Text coded byte by byteGap contentsWhich template each line usesThe template table

Compressed size of the 1 GB file, shorter is better.

The only generalisation allowed is replacing a differing region with a gap that matches any byte string. There are no typed gaps. At the first level 60.3% of the 13.1 million lines match a template, and the hierarchy goes 12 levels deep. A single-pass scan over line records reaches 1,888 MB/s on 16 threads.

Simple coder: an adaptive order-2 byte model, 3.001 bits per byte alone and 2.684 with templates. Strong coder: context mixing with the gap as context, 1.860 bits per byte alone and 1.826 with templates, using 835,747 templates. Template ids are coded conditioned on the parent gap.