Byte-pair encoding was a data compression algorithm published by Philip Gage in 1994 and repurposed for neural machine translation by Sennrich, Haddow and Birch at ACL 2016. It is simple enough to implement over a coffee, and implementing it is the fastest way to stop finding tokenizer behaviour mysterious.
The algorithm, in one sentence
Start with every text represented as a sequence of single characters, repeatedly find the adjacent pair that occurs most often across the whole corpus, and replace every occurrence of that pair with a new single symbol. Record the merges in order. That ordered list is the tokenizer.
Everything else — vocabulary size, compression ratio, which languages are cheap — is a consequence of what corpus you counted pairs in and how many merges you stopped after.
Two things about that are worth holding on to before the code. The algorithm has no notion of meaning, morphology or language; it is counting adjacent symbol pairs and nothing else. And it is greedy at training time as well as at encoding time — it takes the most frequent pair now rather than the pair that would lead to the best vocabulary eventually, which is why BPE vocabularies contain a certain amount of visible junk alongside the sensible prefixes and suffixes.
