bpe_pair_count
def
The number of occurrences of the ordered symbol pair replaced by the left-to-right nonoverlapping full merge.
Statement
def bpe_pair_count (a b : ℕ) : List ℕ → ℕ- Source
- Definitions for OP-1288, following arXiv:2611.08671, Section 2.
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Used by 10
- bpe_greedy_step_withA greedy full Byte-Pair Encoding merge step with fresh symbol z: either no adjacent pair occurs with positive count in string s and t = s,…
- bpe_min_greedy_utility_one_eq_optimalFor any string s and merge budget k = 1, the minimum reduction in length achieved by a greedy full-merge step equals the optimal reduction…
- bpe_greedy_run_length_lower_boundApplying k greedy full BPE merges reduces the string length by at most a factor of 2^k: if bpe_greedy_run k s t, then s.length ≤ 2^k *…
- bpe_lex_best_pairSelects the adjacent pair with the largest number of nonoverlapping occurrences in the string, breaking ties by lexicographical order of…
- bpe_max_pair_countThe largest nonoverlapping full-merge pair count among adjacent pairs of the current string, with maximum zero for a string shorter than…
- bpe_greedy_stepA greedy full-merge step selects any most frequent adjacent pair and a fresh symbol; a string without adjacent pairs remains unchanged.
- bpe_pair_betterComparison between two symbol pairs in a string, preferring the pair with strictly more nonoverlapping occurrences, and breaking ties by…
- bpe_steps_greedy_imp_full_stepsEvery string reachable by k steps of greedy Byte-Pair Encoding merges is also reachable by k general full-merge steps.
- bpe_greedy_step_length_leAny greedy full byte-pair merge step produces an output string of length at most the input string length.
- bpe_worst_case_ratio_three_upper_boundThe worst-case ratio of greedy Byte-Pair Encoding to optimal partial-merge utility for three merges is at most 7/12.
Lean source view module on GitHub
def bpe_pair_count (a b : ℕ) : List ℕ → ℕ | [] => 0 | [_] => 0 | x :: y :: xs => if x = a ∧ y = b then 1 + bpe_pair_count a b xs else bpe_pair_count a b (y :: xs)