Greedy Longest-Match WordPiece Tokenizationhard

Greedy Longest-Match WordPiece Tokenization

hard Inside an LLM 15 min

NumPy allowed · plain Python earns 10 bonus points

Tokens attend to tokens

Q · Kᵀ / √d → softmax → weighted values, computed in the page.

Open lesson →

01tokens

02Q K V

03scores

04attention

modelslearnrelationships

models32%

learn38%

relationships30%

Q · Kᵀ / √d scores normalized with softmax

Implement WordPiece's real greedy longest-match-first tokenization algorithm (used by BERT), splitting an out-of-vocabulary word into known subword pieces.

Task

Implement wordpiece_tokenize(word, vocab, unk_token). Starting from position 0, greedily find the LONGEST prefix of the remaining substring that's in vocab (for positions after the first, the candidate must be prefixed with '##' before checking vocab membership). If no valid piece is found at any position, return [unk_token] for the WHOLE word (not partial pieces).

Function Signature

wordpiece_tokenize(word: str, vocab: set, unk_token: str) -> list[str]

Examples

Example 1: word splits into two known pieces
Input: word = 'unaffable'
vocab = ['un', '##aff', '##able']
unk_token = '[UNK]'
Output: ['un', '##aff', '##able']

Example 2: whole word is a known token
Input: word = 'hello'
vocab = ['hello']
unk_token = '[UNK]'
Output: ['hello']

Example 3: no valid tokenization falls back to unk
Input: word = 'xyz'
vocab = ['abc']
unk_token = '[UNK]'
Output: ['[UNK]']

Constraints

vocab is a set of valid tokens (continuation pieces already include the '##' prefix)

Python3Saved ✓

def wordpiece_tokenize(word, vocab, unk_token):

# Your implementation here

pass

Case 1: word splits into two known pieces

Input: word = 'unaffable'
vocab = ['un', '##aff', '##able']
unk_token = '[UNK]'

Expected: ['un', '##aff', '##able']

Case 2: whole word is a known token

Input: word = 'hello'
vocab = ['hello']
unk_token = '[UNK]'

Expected: ['hello']

Case 3: no valid tokenization falls back to unk

Input: word = 'xyz'
vocab = ['abc']
unk_token = '[UNK]'

Expected: ['[UNK]']