bpe_lex_step
Performs one greedy full BPE merge step replacing the chosen lexicographically earliest maximal pair with fresh symbol z, leaving the string unchanged if no pair occurs.
Statement
def bpe_lex_step (z : ℕ) (s : List ℕ) : List ℕ- Defined in
- OP-1536
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 2
- bpe_lex_best_pairSelects the adjacent pair with the largest number of nonoverlapping occurrences in the string, breaking ties by lexicographical order of…
- bpe_full_mergeThe string obtained by scanning left to right and replacing every available nonoverlapping occurrence of the selected pair with the given…
- Used by 1
- bpe_lex_runThe string obtained by performing k sequential greedy lexicographical full BPE merges on an initial string over symbols 0 and 1.
Read back from the Lean
bpe_lex_step z s is a function that takes a natural number z and a list of natural numbers s, and returns a List ℕ.
It computes the "best" adjacent pair (a, b) in s according to bpe_lex_best_pair:
- If s has length less than 2 (or if the best pair has count 0 in s), it returns s unchanged.
- Otherwise, it replaces every non-overlapping occurrence of (a, b) in s with z (greedily from left to right) via bpe_full_merge a b z s.
The "best" pair is chosen among all adjacent pairs (s[i], s[i+1]) by:
1. Maximizing the non-overlapping count in s (greedily counted from left to right).
2. Breaking ties by preferring smaller first element (a).
3. Breaking further ties by preferring smaller second element (b).
4. If identical pairs tie, the earliest one encountered in s.zip s.tail is preserved.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- One deterministic greedy BPE merge step replacing the chosen pair with a fresh symbol. -/ def bpe_lex_step (z : ℕ) (s : List ℕ) : List ℕ := match bpe_lex_best_pair s with | none => s | some (a, b) => bpe_full_merge a b z s