BPE Merge Step

easyFREETokenization AlgorithmsLLM 1: Foundations

Implement a single step of the Byte Pair Encoding (BPE) merge algorithm.

Given a list of tokens (strings) and a merge pair (two consecutive tokens to merge), scan through the token list and merge every adjacent occurrence of the pair into a single token.

Example:

Tokens: ["l", "o", "w", "e", "r"]
Merge pair: ("l", "o")
Result: ["lo", "w", "e", "r"]

Multiple occurrences should all be merged in a single pass (left to right).

Implement bpe_merge_step(tokens, pair): tokens is a list of strings and pair is a tuple of two strings. Return a new list of strings (not a joined string); the tests join it with spaces for display. When occurrences overlap (e.g. the pair ("a", "a") in ["a", "a", "a"]), the leftmost occurrence is merged first, giving ["aa", "a"].

Example

Input

l o w e r
l o

Output

lo w e r

Reasoning

Inputs: tokens is the current sequence of 5 single-character tokens l, o, w, e, r, and pair is the merge rule (l, o): wherever l is immediately followed by o, the two become one token.
Scan the adjacent positions: the neighbouring pairs are (l, o), (o, w), (w, e), (e, r). Only the first, at positions 1–2, matches the rule, so l and o are concatenated into the new token lo.
Everything else is copied unchanged: w, e and r are not part of a match, so they keep their order.
Output: a new list of 4 tokens, shown space-separated as lo w e r. Each merge shrinks the sequence by exactly one, so $5 - 1 = 4$ tokens.
Notice: every non-overlapping match is merged in the same pass, so a b a b c with rule (a, b) becomes ab ab c. Matches are claimed left to right: for a a a with rule (a, a) the first two fuse, giving aa a.

Constraints

Input line 1: space-separated tokens
Input line 2: two tokens separated by space (the merge pair)
Output: space-separated merged tokens
Merge all occurrences in one left-to-right pass

Learn this in

Tokenization & EmbeddingsLLM Study Plan Text PreprocessingNLP Study Plan Word EmbeddingsNLP Study Plan

More from LLM 1: Foundations

Transformer Block Forward Passhard Feed-Forward Networkeasy Layer Normalizationeasy KV-Cache Attentionhard Multi-Head Attentionmedium

Concept primer

Background Knowledge

The Byte Pair Encoding (BPE) algorithm is a lossless text encoding technique that operates by iteratively merging the most frequent pair of bytes in a given text. This process is repeated until a predetermined vocabulary size is reached. BPE is commonly used in natural language processing and text compression applications. The algorithm starts with individual characters as the initial tokens and gradually builds up to more complex tokens by merging adjacent pairs.

In the context of tokenization algorithms, BPE serves as a method to learn a vocabulary of subword units (tokens) from raw text data. This is particularly useful for handling out-of-vocabulary words and reducing the dimensionality of the input space. By merging frequent pairs of tokens, BPE can effectively capture common patterns and structures within the language, leading to more efficient and effective text representation.

The BPE merge step is a crucial component of the BPE algorithm, where the most frequent pair of adjacent tokens is merged into a single token. This process involves scanning through the list of tokens, identifying occurrences of the merge pair, and replacing them with the merged token. The goal is to perform this merge operation in a single pass, ensuring that all adjacent occurrences of the pair are merged correctly.

Algorithm/Approach

The general approach to solving this problem involves using a string processing algorithm that iterates through the list of tokens and applies the merge operation whenever the specified pair is encountered. This can be achieved using a simple linear scan approach, where each token is examined in sequence, and the merge pair is replaced with the merged token when found.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an empty list to store the merged tokens
Iterate through the input list of tokens, examining each token and the next one in sequence
Check if the current token and the next one match the merge pair
If a match is found, merge the pair into a single token and add it to the result list
If no match is found, add the current token to the result list as is
Continue this process until all tokens have been processed

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly handling the case where the merge pair occurs at the end of the list
Failing to merge multiple occurrences of the pair in a single pass
Not preserving the original order of tokens that do not match the merge pair

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the number of tokens in the input list, since we are performing a single pass through the list. The space complexity is also $O(n)$ , as we need to store the merged tokens in a new list.

solution.py

Python 3.13

Test results