Tokenization is the first step in modern neural language model pipelines where an input text is converted to a sequence of subword tokens. We introduce from first principles a finite-state transduction framework which can efficiently encode all possible tokenizations of a regular language. We then constructively show that Byte-Pair Encoding (BPE) and MaxMatch (WordPiece), two popular tokenization schemes, fit within this framework. For BPE, this is particularly surprising given its resemblance to context-free grammar and the fact that it does not tokenize strings from left to right. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern. Here, patterns are encoded at the character level, which creates a mismatch between the constraints and the model's subword vocabulary. While past work has focused only on constraining outputs without regard to the underlying tokenization algorithm, our framework allows for simultaneously constraining the model outputs to match a specified pattern while also adhering to the underlying tokenizer's canonical tokenization.

本文研究了分词在现代神经语言模型中的重要性，提出了一个有限状态传导框架，以有效编码正规语言的所有可能分词方案。研究表明，流行的分词方案如字节对编码（BPE）和最大匹配（WordPiece）可以融入此框架中，进而实现引导生成中模式的精准匹配，这为未来的模型输出提供了新的约束方法。

基于有限状态传导的分词方法