Byte-pair encoding
Byte-pair encoding repeatedly replaces frequent adjacent byte pairs with unused byte values and records the substitutions needed to reconstruct the input.
Mechanism: In the original byte-oriented scheme, replacements can themselves appear in later pairs. Decoding recursively expands the stored pair table; the reduced payload alone is insufficient. [1]
Byte budget: A block needs unused values among the 256 byte codes. The original implementation splits input into blocks to retain spare codes. Re-Pair instead extends its symbol alphabet; a new grammar symbol need not fit in one byte. [1] [3]
Accounting: In the teaching format, abababab becomes two rules and two payload bytes: 14 header + 6 rule + 2 payload = 22 stored bytes for 8 input bytes. Repeating ab 128 times gives 37 stored bytes for 256 input bytes; selecting six rather than seven rules gives 36. The smallest prefix includes table cost; neither example estimates typical compression. [5]
Seeking: With its pair table available, decoding can start at a payload-code boundary. This does not identify which compressed position contains a requested original-byte offset; that needs additional mapping or expansion. [2]
Tokenization: A later adaptation learns character-sequence merges from training words, excluding cross-word pairs. Its learned symbols are not restricted to unused byte values, and token count is not stored-byte size. [4]
Relations
Limitations
- The substitution table does not authenticate the decoded bytes; a changed rule can produce different output of the same length. [5]
Citations
- Gage (1994): A New Algorithm for Data Compression, C Users Journal, February; archived article
- Gage (1997): Random Access Data Compression, C Users Journal, September; archived article
- Larsson and Moffat: Offline Dictionary-Based Compression, DCC 1999, sections 2.2-2.3
- Sennrich, Haddow and Birch: Neural Machine Translation of Rare Words with Subword Units, ACL 2016, section 3.2
- Hesela: byte-pair substitution, full representation accounting and decoder controls
Sources & caveats
- Original byte-oriented BPE is distinguished from extended-alphabet grammar compression and the 2016 character-based tokenization adaptation.
- The executable model has its own framing, tie-breaking and stopping policy; it is not Gage's wire format or a reproduction of historical performance measurements.