Implement a Byte Pair Encoding (BPE) Tokenizer

Problem Statement

Byte Pair Encoding (BPE) is a subword tokenization algorithm widely used in natural language processing and modern large language models. Starting from base characters, it iteratively merges the most frequent adjacent pair of tokens to build a subword vocabulary.

Implement the BPETokenizer class with three methods:

1. train(corpus: list[str], num_merges: int) -> None:

   • Learns at most num_merges merge rules from a list of words (corpus).
   • Each word in corpus is initially split into a sequence of individual characters followed by an end-of-word token '' (e.g., "low" becomes ['l', 'o', 'w', '']).
   • In each merge iteration, find the most frequent adjacent pair of tokens across all words (weighted by word frequency in corpus).
   • If there is a tie in pair frequency, choose the pair that is lexicographically smaller as a tuple: (a, b) < (c, d) if a < c, or if a == c and b < d.
   • Merge all occurrences of this winning pair into a single concatenated token a + b across all words.
   • If no pairs are left to merge before reaching num_merges, terminate training early.

2. encode(text: str) -> list[str]:

   • Splits text by whitespace into words.
   • Each word is initialized as list(word) + [''].
   • Applies the learned merges in the exact order they were learned during training.
   • Returns the flattened list of token strings across all words in text.

3. decode(tokens: list[str]) -> str:

   • Reconstructs the original text by concatenating all tokens, replacing '' boundaries with single whitespace characters, and trimming any trailing whitespace.

Class Interface

class BPETokenizer:
    def __init__(self):
        pass

    def train(self, corpus: list[str], num_merges: int) -> None:
        pass

    def encode(self, text: str) -> list[str]:
        pass

    def decode(self, tokens: list[str]) -> str:
        pass

Examples

Example 1

tokenizer = BPETokenizer()
corpus = ["low", "low", "low", "low", "low", "lower", "lower", "newest", "newest", "widest"]
tokenizer.train(corpus, num_merges=3)

# Initial token counts across words:
# "low": ['l', 'o', 'w', ''] x 5
# "lower": ['l', 'o', 'w', 'e', 'r', ''] x 2
# "newest": ['n', 'e', 'w', 'e', 's', 't', ''] x 2
# "widest": ['w', 'i', 'd', 'e', 's', 't', ''] x 1

# Merge 1: ('e', 's') appears 3 times, ('s', 't') appears 3 times, ('l', 'o') appears 7 times, ('o', 'w') appears 7 times.
# ('l', 'o') and ('o', 'w') tie with count 7. ('l', 'o') is lexicographically smaller -> merge ('l', 'o') into 'lo'.
# Merge 2: ('lo', 'w') appears 7 times -> merge ('lo', 'w') into 'low'.
# Merge 3: ('e', 's') appears 3 times, ('s', 't') appears 3 times, ('low', '') appears 5 times.
# ('low', '') has count 5 -> merge into 'low'.

tokens = tokenizer.encode("lower newest")
# "lower" -> ['low', 'e', 'r', '']
# "newest" -> ['n', 'e', 'w', 'e', 's', 't', '']
# Output: ['low', 'e', 'r', '', 'n', 'e', 'w', 'e', 's', 't', '']

reconstructed = tokenizer.decode(tokens)
# Output: "lower newest"

Constraints

• 1 <= len(corpus) <= 1000
• 1 <= len(word) <= 50 for each word in corpus
• Words in corpus consist of lowercase English letters a-z.
• 0 '.
• Unseen characters in encode: Characters not seen during training should remain as individual character tokens.
• Words of length 1: Handled naturally as ['a', ''].
• Early stopping: If all words are reduced to single tokens, the training loop exits before num_merges iterations.