  Tokenization is a fundamental preprocessing step for almost all NLP tasks. In
this paper, we propose efficient algorithms for the WordPiece tokenization used
in BERT, from single-word tokenization to general text (e.g., sentence)
tokenization. When tokenizing a single word, WordPiece uses a
longest-match-first strategy, known as maximum matching. The best known
algorithms so far are O(n^2) (where n is the input length) or O(nm) (where m is
the maximum vocabulary token length). We propose a novel algorithm whose
tokenization complexity is strictly O(n). Our method is inspired by the
Aho-Corasick algorithm. We introduce additional linkages on top of the trie
built from the vocabulary, allowing smart transitions when the trie matching
cannot continue. For general text, we further propose an algorithm that
combines pre-tokenization (splitting the text into words) and our linear-time
WordPiece method into a single pass. Experimental results show that our method
is 8.2x faster than HuggingFace Tokenizers and 5.1x faster than TensorFlow Text
on average for general text tokenization.
