Overview
Byte Pair Encoding builds a compact subword or byte-level vocabulary by merging the most common pair at each step.
CoreSource checked
Byte Pair Encoding
Repeatedly replaces frequent adjacent symbol pairs with new symbols.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Compression
- Difficulty
- Intermediate
- Family
- Dictionary Compression
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
pair frequencymerge ruledictionary growthsubword token
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(k n)
Worst
O(k n)
Space
O(k)
When to Use
- Use when reducing storage size needs pair frequency.
- Use when the input matches the assumptions behind dictionary Compression.
When Not to Use
- Avoid when the data is already compressed or the format overhead exceeds the savings.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Repeatedly replaces frequent adjacent symbol pairs with new symbols
- Uses pair frequency and merge rule to guide the work.
- Produces encoded stream.
Use Cases
- Reducing storage size
- Compressing repeated data
- Preparing data for transmission
Inputs
- Input byte stream
- Coding model or dictionary state
Outputs
- Encoded stream
- Decoder metadata
Key Formulas (1)
Merge choice
bestpair = argmaxpair count(pair)
best_pair = argmax_pair count(pair)Selects the adjacent pair that occurs most often.
Pseudocode
- 1.Initialize encoder state, dictionary, model, or block metadata
- 2.Read symbols or blocks in the defined order
- 3.Emit codes, references, predictions, or transformed coefficients
- 4.Update encoder state exactly as the decoder will
- 5.Return the compressed stream and required metadata
Canonical Example
- Input
- Byte Pair Encoding
- Output
- Encoded stream
- Explanation
- Byte Pair Encoding applies pair frequency to produce encoded stream.
Implementation Notes
- Define bit packing and stream termination rules before optimizing compression ratio.
- Keep the pair frequency step separate enough to test independently.
- Compression can expand small or already-compressed inputs because metadata has a cost.
Common Pitfalls
- Encoder and decoder state must evolve in exactly the same order.
- Test edge cases, not only clean examples.
- Encoder and decoder state must stay synchronized across dictionary updates, blocks, and metadata boundaries.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow symbols being transformed into codes and reconstructed by the decoder state.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Initialize encoder state, dictionary, model, or block metadata
compression-mechanismNotes
Byte Pair Encoding should be used with the assumptions and tradeoffs of dictionary Compression in mind.
Sources (2)
What each reference supports for this entry.
Neural Machine Translation of Rare Words with Subword Units
PaperReference for BPE merge operations as a practical subword coding algorithm.
Open sourceData Compression: The Complete Reference
BookCompression reference for Byte Pair Encoding's practical encoding variants and decoder-side reconstruction details.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsed byTokenization
Modern tokenizers often use byte-pair encoding to learn merge-based subword vocabularies.
Alternative toLZW
Byte Pair Encoding is an alternative to LZW within the Dictionary Compression family.
Related Algorithms
Tags
CompressionDictionary CompressionTokenizationEncoding