Asked about Byte pair encoding from scratch
Implement byte pair encoding: training, encoding and decoding.
An answer that works
Training: split the corpus into words, represent each as a tuple of bytes or characters, then repeatedly count every adjacent pair weighted by word frequency, merge the most frequent pair everywhere, and record it. The output is the ordered merge list. Encoding: split the input the same way and replay the merges in order against each word. Decoding: concatenate the token strings, which works exactly because leading spaces are kept inside the tokens.
Then they push further
Why does the order of the merge list matter?
Because later merges are built from the symbols earlier merges created. "the" only exists as a mergeable symbol after "t"+"h" and then "th"+"e" have happened, so " "+"the" cannot be applied before them. Replaying in a different order gives a different and generally worse segmentation, so the order is the model.
Why start from bytes rather than characters?
So that nothing is unrepresentable. There are 256 possible bytes and every input is a sequence of them, so an unknown token can never occur, whatever alphabet or emoji arrives. A character-level inventory is open-ended and would need an unknown token that the model cannot decode back.
Your encode loops over every merge for every word. How would you make it fast?
Give each merge a rank from its position in the list, then within a word repeatedly find the applicable pair with the lowest rank and apply it, stopping when no pair is applicable. That touches only relevant merges instead of all of them, and produces the same segmentation. Keep the slow version as the test oracle.
What gets marked up
Candidates who have written it keep the leading space inside the token and know decoding is plain concatenation. Handling a space as its own token, and then needing rules about when to re-insert it, is the sign of someone recalling the idea rather than having implemented it.
Reading an answer is not being able to give one. The section that teaches this is Byte pair encoding from scratch, 4 hours of Tokenization.
Learn this properlyAlso asked about Tokenization