BPE Merge

Task

Implement bpe_merge(tokens: list[str], pair: tuple[str, str]) -> list[str]. Apply one byte-pair encoding merge rule to a sequence of symbols, replacing every non-overlapping adjacent occurrence from left to right.

Requirements

• pair contains exactly two symbol strings: the left symbol and right symbol.
• Scan tokens from left to right.
• When the current and next symbols equal pair, append their string concatenation and advance by two positions.
• Otherwise append the current symbol unchanged and advance by one position.
• Merge every non-overlapping occurrence in the same pass.
• Do not reconsider a newly merged symbol during the current pass.
• Do not mutate tokens or pair.
• Return an empty list for an empty token sequence.

Example

tokens = ["l", "o", "w", "</w>"]

bpe_merge(tokens, ("l", "o"))
# ["lo", "w", "</w>"]