Concept

Alphabet order — where it appears

Which symbol sorts before which, a choice an implementation usually makes by byte value and rarely records. The Burrows-Wheeler transform sorts rotations, so its run count depends on it; a parse compares characters only for equality, so its phrase count does not.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

The collection decides which index is small

Three compressed self-indexes over one text of five hundred characters measure 3,511, 7,285 and 10,974 bits. Repeat that text thirty-two times and the same three measure 34,615, 8,892 and 17,047 — the ordering has completely reversed, and nothing about any of the structures changed.

indexes · Repeat

The measure that cannot see the alphabet

Take a Fibonacci word of 4,181 characters and transform it with a before b — six runs. Transform the same word with b before a — nineteen. The parse gives eighteen phrases either way, and the gap between the two run counts grows with every word in the family.

wrong · Parse

Named alongside it

The objects these essays reach for when they reach for this one.

Compressibility Index size Lempel ziv parse Measurement Phrase R-index Repetition Run-length Self-index Alphabet Burrows-wheeler transform Copy depth

All concepts