Fast WordPiece Tokenization

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 2089–2103 November 7–11, 2021. c⃝2021 Association for Computational Linguistics 2089 Fast WordPiece Tokenization Xinying Song† Alex Salcianu† Yang Song‡∗ Dave Dopson† Denny Zhou† †Google Research, Mountain View, CA †{xysong,salcianu,ddopson,dennyzhou}@google.com ‡Kuaishou Technology, Beijing, China ‡yangsong@kuaishou.com Abstract Tokenization is a fundamental preprocessing step for almost all NLP tasks. In this paper, we propose efficient algorithms for the Word- Piece tokenization used in BERT, from single- word tokenization to general text (e.g., sen- tence) tokenization. When tokenizing a sin- gle word, WordPiece uses a longest-match- first strategy, known as maximum matching. The best known algorithms so far are 푂(푛2) (where 푛 is the input length) or 푂(푛푚) (where 푚 is the maximum vocabulary token length). We propose a novel algorithm whose tokeniza- tion complexity is strictly 푂(푛). Our method is inspired by the Aho-Corasick algorithm. We introduce additional linkages on top of the trie built from the vocabulary, allowing smart tran- sitions when the trie matching cannot continue. For general text, we further propose an algo- rithm that combines pre-tokenization (splitting the text into words) and our linear-time Word- Piece method into a single pass. Experimen- tal 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. 1 Introduction Tokenization is the process of splitting text into smaller units called tokens (e.g., words). It is a fundamental preprocessing step for almost all NLP applications: sentiment analysis, question answer- ing, machine translation, information retrieval, etc. Modern NLP models like BERT (Devlin et al., 2019), GPT-3 (Brown et al., 2020), and XL- Net (Yang et al., 2019) tokenize text into sub- word units (Schuster and Nakajima, 2012; Sennrich et al., 2016; Kudo, 2018). As a midpoint between words and characters, subword units retain linguis- tic meaning (like morphemes), while alleviating out-of-vocabulary situations even with a relatively small-size vocabulary. ∗ Research conducted while working at Google. In this paper, we propose efficient algorithms for WordPiece, the subword tokenization used in BERT (Devlin et al., 2019). Given Unicode text that has already been cleaned up and normalized, WordPiece has two steps: (1) pre-tokenize the text into words (by splitting on punctuation and whites- paces), and (2) tokenize each word into wordpieces. For single-word tokenization, WordPiece uses a greedy longest-match-first strategy: iteratively pick the longest prefix of the remaining text that matches a vocabulary token. This is well-known as Maximum Matching or MaxMatch (Palmer, 2000), which has also been used for Chinese word seg- mentation since 1980s (Liu and Liang, 1986). Despite its wide use in NLP for decades, to the best of our knowledge, the most efficient Max- Match algorithms so far are 푂(푛2) (where 푛 is the input word length) or 푂(푛푚) (where 푚 is the max- imum vocabulary token length) (see Section 2). It’s worth noting that the latter has a vocabulary- specific multiplicative factor 푚, which can be large when the vocabulary contains long words. We propose LinMaxMatch, …

Content truncated to 500 words