一个快速 WordPiece 标记化系统

标记化是大多数自然语言处理(NLP) 应用程序的基本预处理步骤。它涉及将文本拆分为称为标记的较小单元（例如，单词或词段），以便将非结构化输入字符串转换为适用于机器学习(ML) 模型的离散元素序列。在基于深度学习的模型（例如，BERT）中，每个标记都映射到一个嵌入向量以输入模型。

典型深度学习模型中的标记化，如BERT

一种基本的标记化方法是将文本分解为单词。但是，使用这种方法，未包含在词汇表中的单词将被视为“未知”。现代 NLP 模型通过将文本标记为子词单元来解决这个问题，这些子词单元通常保留语言含义（例如，词素）。因此，即使模型可能不知道某个词，单个子词标记可能会保留足够的信息，让模型在一定程度上推断其含义。一种常用且可应用于其他 NLP 模型的子词标记化技术称为WordPiece。给定文本，WordPiece 首先将文本预先标记为单词（通过拆分标点符号和空格），然后将每个单词标记为子词单元，称为 wordpieces。

带有例句的 WordPiece 标记化过程

在EMNLP 2021 上展示的“ Fast WordPiece Tokenization ”中，Google开发了一种改进的端到端 WordPiece 标记化系统，可以加快标记化过程，减少整体模型延迟并节省计算资源。与已经使用了几十年的传统算法相比，这种方法将计算的复杂性降低了一个数量级，从而显着提高了性能，比标准方法快 8 倍。该系统已在谷歌的多个系统中成功应用，并已在TensorFlow Text公开发布。

单字 WordPiece 标记化

WordPiece 使用贪婪的最长匹配优先策略来标记单个单词——即，它迭代地选择与模型词汇表中的单词匹配的剩余文本的最长前缀。这种方法被称为最大匹配或 MaxMatch，自 1980 年代以来也被用于中文分词。然而，尽管它在 NLP 中被广泛使用了几十年，但它仍然是相对计算密集型的，通常采用的 MaxMatch 方法的计算是关于输入字长 ( n ) 的二次方。这是因为需要两个指针来扫描输入：一个用于标记开始位置，另一个用于在该位置搜索与词汇标记匹配的最长子串。

Google为 WordPiece 分词提出了 MaxMatch 算法的替代方案，称为 LinMaxMatch，其分词时间相对于n严格线性。首先，Google将词汇标记组织在一个特里（也称为前缀树）中，其中每个特里边由一个字符标记，从根到某个节点的树路径代表词汇表中某个标记的前缀。在下图中，节点用圆圈表示，树边用黑色实心箭头表示。给定一个 trie，可以通过从根遍历并沿着 trie 边缘逐个字符地匹配输入文本来定位词汇标记以匹配输入文本；这个过程被称为特里匹配。

下图显示了由“a”、“abcd”、“##b”、“##bc”和“##z”组成的词汇表创建的特里树。输入文本“abcd”可以通过从根（左上角）开始并跟随带有标签“a”、“b”、“c”、“d”的特里边缘来匹配词汇标记。（前导“##”符号是 WordPiece 标记中使用的特殊字符，下面将进行更详细的描述。）

词汇表 [“a”、“abcd”、“##b”、“##bc”、“##z”]。圆圈和箭头分别代表沿着树的节点和边。

其次，受1975 年发明的经典字符串搜索算法Aho-Corasick 算法的启发，Google引入了一种方法，它跳出无法匹配给定输入的特里树分支并直接跳到替代分支继续匹配。与标准的特里匹配一样，在标记化过程中，Google沿着特里边缘一一匹配输入字符。当 trie 匹配无法匹配给定节点的输入字符时，标准算法会回溯到匹配令牌的最后一个字符，然后从那里重新启动 trie 匹配过程，这会导致重复和浪费的迭代。Google的方法不是回溯，而是触发失败转换，这分两步完成：（1）它收集存储在该节点上的预先计算的令牌，Google称之为failure pops；(2) 然后它遵循预先计算的故障链接到一个新节点，从该节点继续进行特里匹配过程。

例如，给定具有上述词汇表（“a”、“abcd”、“##b”、“##bc”和“##z”）的模型，WordPiece 标记化区分在开头匹配的子词标记从中间开始的子词标记中的输入词（后者用两个前导哈希“##”标记）。因此，对于输入文本“abcz”，预期的标记化输出是 [“a”, “##bc”, “##z”]，其中“a”匹配输入地开头，而“##bc”和“##z”在中间匹配。对于这个例子，下图显示，在成功匹配三个字符'a'、'b'、'c'后，trie匹配无法匹配下一个字符'z'，因为“abcz”不在词汇表中。在这种情况下

与上例所示相同词汇的 Trie 结构，现在说明Google新的 Fast WordPiece Tokenizer 算法采用的方法。失败的流行音乐用括号括起来并以紫色显示。节点之间的故障链接用红色虚线箭头表示。

由于读取整个输入至少需要n 个操作，因此 LinMaxMatch 算法对于 MaxMatch 问题是最优的。

端到端 WordPiece 标记化

鉴于现有系统预先标记输入文本（通过标点符号和空白字符将其拆分为单词），然后对每个结果单词调用 WordPiece 标记化，Google提出了一种端到端 WordPiece 标记器，它结合了pre-tokenization 和 WordPiece 到一个单一的，线性时间传递。它尽可能多地使用 LinMaxMatch 树匹配和失败转换，并且只在循环未处理得相对较少的输入字符中检查标点符号和空白字符。它更高效，因为它只遍历输入一次，执行更少的标点符号/空格检查，并跳过中间词的创建。

端到端 WordPiece 标记化

基准测试结果

Google针对两个广泛采用的 WordPiece 标记化实现对Google的方法进行了基准测试，HuggingFace Tokenizers来自 HuggingFace Transformer 库，是最流行的开源 NLP 工具之一，TensorFlow Text是TensorFlow的官方文本实用程序库。Google使用与BERT-Base, Multilingual Cased model一起发布的 WordPiece 词汇表。

Google在大型语料库（数百万个单词）上将Google的算法与 HuggingFace 和 TensorFlow Text 进行了比较，发现将字符串拆分为标记的方式与单个单词和端到端标记化的其他实现方式相同。

为了生成测试数据，Google从多语言维基百科数据集中抽取了 1,000 个句子，涵盖 82 种语言。平均每个单词有四个字符，每个句子有 82 个字符或 17 个单词。Google发现这个数据集足够大，因为一个更大的数据集（由数十万个句子组成）产生了类似的结果。

Google比较了为每个系统标记单个单词或一般文本（端到端）时的平均运行时间。Fast WordPiece 分词器比 HuggingFace 快 8.2 倍，比 TensorFlow Text 快 5.1 倍，平均而言，对于一般文本端到端分词。

每个系统的平均运行时间。请注意，为了更好地可视化，单个词标记化和端到端标记化以不同的比例显示。

Google还研究了运行时如何相对于单个词标记化的输入长度增长。由于其线性时间复杂度，LinMaxMatch 的运行时间最多随输入长度线性增加，这比其他二次时间方法慢得多。

每个系统相对于单个词标记化的输入长度的平均运行时间。

Google提出了用于单字 WordPiece 标记化的 LinMaxMatch，它在输入长度的渐近最优时间内解决了几十年前的 MaxMatch 问题。LinMaxMatch 扩展了 Aho-Corasick 算法，这个想法可以应用于更多的字符串搜索和换能器挑战。Google还提出了一种端到端的 WordPiece 算法，该算法将预标记化和 WordPiece 标记化结合到单个线性时间传递中，以提高效率