Byte Pair Encoding (BPE) Tokenizer

A simple, from-scratch implementation of the Byte Pair Encoding (BPE) subword tokenization algorithm, demonstrated on Herman Melville's Moby Dick (via NLTK's Gutenberg corpus).

Table of Contents

• Overview
• Features
• Requirements
• Usage
• How It Works
  • most_frequent_adjacent_pair(tokens)
  • merge_pair(tokens, pair)
  • bpe(corpus, k)
• Sample Input
• Applications
• Notes / Limitations
• Contributing
• License

Overview

BPE is the algorithm behind modern subword tokenizers used in NLP models (e.g. GPT-style tokenizers). It starts with individual characters and iteratively merges the most frequent adjacent pair of symbols into a new symbol, gradually building up a vocabulary of subword units.

This script:

1. Loads raw text from the NLTK Gutenberg corpus.
2. Splits each word into individual characters (with an end-of-word marker -).
3. Repeatedly finds and merges the most frequent adjacent character/symbol pair.
4. Prints a slice of the resulting tokenized corpus.

Features

• Implements the core Byte Pair Encoding algorithm
• Uses the NLTK Gutenberg Corpus (Moby Dick) as input
• Tokenizes text into character-level sequences
• Finds the most frequent adjacent character pair
• Iteratively merges character pairs
• Configurable number of merge operations (k)

Requirements

• Python 3
• NLTK (pip install nltk)
• NLTK data packages:

  import nltk
  nltk.download('punkt')
  nltk.download('gutenberg')

Usage

python BPE.py

By default, the script runs BPE on the full text of Moby Dick for 1000 merge iterations (k = 1000) and prints tokens 100 through 200 of the result.

How It Works

most_frequent_adjacent_pair(tokens)

Scans every word (a space-separated sequence of symbols) and counts all adjacent symbol pairs across the entire token list, returning the single most common pair using collections.Counter.

merge_pair(tokens, pair)

Given a pair of symbols, merges every occurrence of that pair (as adjacent, space-separated symbols) into a single combined symbol, for every word in the token list.

bpe(corpus, k)

The main driver:

1. Tokenizes and lowercases the input corpus with word_tokenize.
2. Converts each word into a sequence of individual characters, joined by spaces, with a trailing - marking the end of the word (e.g. "cat" → "c a t -").
3. Runs up to k merge iterations, each time:
   • Finding the most frequent adjacent pair across all words.
   • Merging that pair everywhere it occurs.
   • Stopping early if no pairs remain.
4. Returns the final list of (partially) merged word representations.

Sample Input

lowest
lower
newest
widest

Character representation:

l o w e s t -
l o w e r -
n e w e s t -
w i d e s t -

After several merge operations, common sequences such as:

l o
lo w
low e
est

become merged into larger subword units.

Applications

Byte Pair Encoding is commonly used for:

• NLP preprocessing
• Machine Translation
• Large Language Models (LLMs)
• Text Compression
• Vocabulary construction
• Subword tokenization

Notes / Limitations

• merge_pair uses str.replace, so a merge is applied to all occurrences of the bigram string within a word — this is efficient but assumes no unintended substring collisions between the join separators.
• The end-of-word marker - is treated as a normal symbol, so it can also be merged into subword units (e.g. "the-").
• Runtime scales with k (number of merges) and the size of the corpus, since each iteration re-scans every word to find the most frequent pair.
• This is an educational/demonstration implementation, not optimized for large-scale or production tokenizer training.

Contributing

Contributions are welcome! To contribute:

1. Fork the repository.
2. Create a new branch for your change (git checkout -b feature/my-change).
3. Make your changes, following the existing code style.
4. Test your changes locally to confirm the script still runs correctly.
5. Commit your changes with a clear message and push to your fork.
6. Open a pull request describing what you changed and why. Please open an issue first for larger changes, so we can discuss the approach before you invest time in it.

You can also reach out via email at rseyednozadi@gmail.com.

License

This project is licensed under the MIT License. See the LICENSE file for details.