bpe_lex_best_pair
Selects the adjacent pair with the largest number of nonoverlapping occurrences in the string, breaking ties by lexicographical order of integer IDs, or returns none if no pair occurs.
Statement
def bpe_lex_best_pair (s : List ℕ) : Option (ℕ × ℕ)- Defined in
- OP-1536
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 2
- bpe_pair_betterComparison between two symbol pairs in a string, preferring the pair with strictly more nonoverlapping occurrences, and breaking ties by…
- bpe_pair_countThe number of occurrences of the ordered symbol pair replaced by the left-to-right nonoverlapping full merge.
- Used by 1
- bpe_lex_stepPerforms one greedy full BPE merge step replacing the chosen lexicographically earliest maximal pair with fresh symbol z, leaving the…
Read back from the Lean
A function bpe_lex_best_pair that takes a list of natural numbers s and returns an Option (ℕ × ℕ):
1. If the list of adjacent pairs s.zip s.tail is empty (that is, if s has length 0 or 1), it returns none.
2. Otherwise, let p :: ps = s.zip s.tail. It computes best by folding over ps starting from p, replacing the accumulator acc with a candidate pair q whenever bpe_pair_better s q acc is true.
3. If bpe_pair_count best.1 best.2 s = 0, it returns none; otherwise, it returns some best.
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
/-- The greedy pair with maximal nonoverlapping count, broken by lexicographic order. -/ def bpe_lex_best_pair (s : List ℕ) : Option (ℕ × ℕ) := match s.zip s.tail with | [] => none | p :: ps => let best := ps.foldl (fun acc q => if bpe_pair_better s q acc then q else acc) p if bpe_pair_count best.1 best.2 s = 0 then none else some best