AFTD Auto-Formalizing Theoretical Domains

bpe_full_merge

def

The string obtained by scanning left to right and replacing every available nonoverlapping occurrence of the selected pair with the given symbol.

Statement

def bpe_full_merge (a b z : ℕ) : List ℕ → List ℕ
Source
Definitions for OP-1288, following arXiv:2611.08671, Section 2.
Verified
10 Nov 2026
Axioms
none listed
Used by 9
  • 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_stepPerforms one greedy full BPE merge step replacing the chosen lexicographically earliest maximal pair with fresh symbol z, leaving the…
  • 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_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.
  • bpe_full_stepA full Byte-Pair Encoding merge step: either the string remains unchanged, or all nonoverlapping occurrences of some pair are replaced…

Lean source view module on GitHub

def bpe_full_merge (a b z : ℕ) : List ℕ → List ℕ
  | [] => []
  | [x] => [x]
  | x :: y :: xs => if x = a ∧ y = b then z :: bpe_full_merge a b z xs
                    else x :: bpe_full_merge a b z (y :: xs)
See it in the graphDiscuss this resultChallenge it