WordPiece Tokenization (Greedy Longest-Match)

Background

WordPiece is BERT's subword tokeniser: greedy longest-match within a given vocabulary. The first piece of a word has no prefix; subsequent pieces are prefixed with ##. Out-of-vocabulary words become [UNK]. Designed so that even unseen words can be expressed via their longest known prefixes.

Problem statement

Implement wordpiece_tokenize(word, vocab, unk="[UNK]"). Walk left-to-right; at each position, find the longest piece in vocab that matches (prefixed with ## for non-first pieces). Append it and advance past it. If at any point no prefix matches, return [unk] for the entire word.

Input

• word — str, a single whitespace-free word.
• vocab — set[str] (or iterable), the allowed pieces. Whole words appear without ##; continuation pieces appear with ##.
• unk — str, the unknown-token placeholder (default "[UNK]").

Output

Returns list[str] of pieces. On OOV, returns [unk].

Examples

Example 1 — whole word in vocab

Input:  word="hello", vocab={"hello"}
Output: ["hello"]

Example 2 — split into subpieces

Input:  word="unhappy", vocab={"un", "##happy"}
Output: ["un", "##happy"]

Example 3 — three-piece split

Input:  word="unaffordable", vocab={"un", "##aff", "##ord", "##able"}
Output: ["un", "##aff", "##ord", "##able"]

Example 4 — OOV → [UNK]

Input:  word="xyz", vocab={"a"}
Output: ["[UNK]"]

Example 5 — prefers longest match

Input:  word="unhappy", vocab={"un", "##happy", "unhappy"}
Output: ["unhappy"]

Constraints

• The first piece is matched without ##; all subsequent pieces with ##.
• "Longest" wins on the first piece: try the full word first, then strip one character, etc.
• A single failed sub-piece → entire word is [unk] (one element, not per character).

Notes

• vs BPE. BPE is bottom-up (start at characters, merge pairs); WordPiece is top-down (start at the longest known piece, fall back). Both end up at similar vocabularies in practice.
• SentencePiece. Modern tokenisers (T5, LLaMA) use SentencePiece, which is BPE/Unigram-based and handles whitespace as a real character. WordPiece is the BERT-era choice.