Fast WordPiece Tokenization

Xinying Song, Alex Salcianu, Yang Song, Dave Dopson, Denny Zhou


Abstract
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.
Anthology ID:
2021.emnlp-main.160
Volume:
Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing
Month:
November
Year:
2021
Address:
Online and Punta Cana, Dominican Republic
Venue:
EMNLP
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
2089–2103
Language:
URL:
https://aclanthology.org/2021.emnlp-main.160
DOI:
10.18653/v1/2021.emnlp-main.160
Bibkey:
Cite (ACL):
Xinying Song, Alex Salcianu, Yang Song, Dave Dopson, and Denny Zhou. 2021. Fast WordPiece Tokenization. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 2089–2103, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
Cite (Informal):
Fast WordPiece Tokenization (Song et al., EMNLP 2021)
Copy Citation:
PDF:
https://preview.aclanthology.org/author-url/2021.emnlp-main.160.pdf
Video:
 https://preview.aclanthology.org/author-url/2021.emnlp-main.160.mp4
Code
 tensorflow/text