BPE是一种简单的数据压缩算法，它在1994年发表的文章“A New Algorithm for Data Compression”中被首次提出，是一种用于自然语言处理的子词切分算法。它的目标是找到一种最优的字符组合方式，使得整个数据集中不同单词的字符组合尽可能的少。这种算法最初被设计用于字节级的数据压缩，后来被应用于NLP。其核心思想是：
BPE每一步都将最常见的一对相邻数据单位替换为该数据中没有出现过的一个新单位，反复迭代直到满足停止条件。
举个例子：
假设我们有需要编码（压缩）的数据aaabdaaabac。相邻字节对（相邻数据单位在BPE中看作相邻字节对）aa最常出现，因此我们将用一个新字节Z替换它。我们现在有了ZabdZabac，其中Z = aa。下一个常见的字节对是ab，让我们用Y替换它。我们现在有ZYdZYac，其中Z = aa，Y = ab。剩下的唯一字节对是ac，它只有一个，所以我们不对它进行编码。我们可以递归地使用字节对编码将ZY编码为X。我们的数据现在已转换为XdXac，其中X = ZY，Y = ab，Z = aa。它不能被进一步压缩，因为没有出现多次的字节对。那如何把压缩的编码复原呢？反向执行以上过程就行了。
NLP中使用了上述算法的一个变体。首先来明确一下基础概念：token可以理解为一个符号，就代表一个语言单位（就像单词，字符等）；tokenize的意思是把一个句子或长语料分成token。
基础概念：
token可以理解为一个符号，就代表一个语言单位（就像单词，字符等）；tokenize的意思是把一个句子或长语料分成token。BPE确保最常见的词在token列表中表示为单个token，而罕见的词被分解为两个或多个subword tokens，因此BPE也是典型的基于subword的tokenization算法。
假设我们有一个语料库，其中包含单词（pre-tokenization之后）—— old, older, highest和 lowest，我们计算这些词在语料库中的出现频率。假设这些词出现的频率如下：
{“old”: 7, “older”: 3, “finest”: 9, “lowest”: 4}
让我们在每个单词的末尾添加一个特殊的结束标记</w>。
{“old</w>”: 7, “older</w>”: 3, “finest</w>”: 9, “lowest</w>”: 4}
在每个单词的末尾添加“”标记以标识单词边界能够让算法知道每个单词的结束位置（因为我们统计相邻字符对时不能把分别位于两个单词中的字符对算进去），这有助于算法查看每个字符并找到频率最高的字符配对。稍后我们将看到“”也能被算作字符对的一部分。
接下来，我们将每个单词拆分为字符并计算它们的出现次数。初始token将是所有字符和</w>标记的集合。
| Number | Token | Frequency |
|---|---|---|
| 1 | </w> | 23 |
| 2 | o | 14 |
| 3 | l | 14 |
| 4 | d | 10 |
| 5 | e | 16 |
| 6 | r | 3 |
| 7 | f | 9 |
| 8 | i | 9 |
| 9 | n | 9 |
| 10 | s | 13 |
| 11 | t | 13 |
| 12 | w | 4 |
由于我们总共有23个单词，所以我们有23个</w>token。第二高频率标记是e。我们总共有16个不同的token。
BPE算法的下一步是寻找最频繁的字符对，合并它们，并一次又一次地执行相同的迭代，直到达到我们预先设置的token数限制或迭代限制。
合并字符可以让你用最少的token来表示语料库，这也是BPE算法的主要目标，即数据的压缩。为了合并，BPE寻找最常出现的字节对。在这里，我们将字符视为与字节等价。当然，这只是英语的用法，其他语言可能有所不同。现在我们将最常见的字节对合并成一个token，并将它们添加到token列表中，并重新计算每个token出现的频率。这意味着我们的频率计数将在每个合并步骤后发生变化。我们将继续执行此合并步骤，直到达到我们预先设置的token数限制或迭代限制。
为了更清晰的理解，看完下面完整的迭代过程：
迭代1：
我们将从第二常见的标记e开始。 在我们的语料库中，最常见的带有e的字节对是e和s（在finest和lowest两个词中），它们出现了 9+4 = 13 次。 我们将它们合并以形成一个新的tokenes并将其频率记为13。我们还将从单个token（e和s）中减少计数 13，从而我们知道剩余的e或stoken数。 我们可以看到s不会单独出现，e出现了 3 次。 这是更新后的表格：
| Number | Token | Frequency |
|---|---|---|
| 1 | </w> | 23 |
| 2 | o | 14 |
| 3 | l | 14 |
| 4 | d | 10 |
| 5 | e | 16-13=3 |
| 6 | r | 3 |
| 7 | f | 9 |
| 8 | i | 9 |
| 9 | n | 9 |
| 10 | s | 13-13=0 |
| 11 | t | 13 |
| 12 | w | 4 |
| 13 | es | 9+4=13 |
迭代2：
我们现在将合并tokenes和t，因为它们在我们的语料库中出现了13次。 因此，我们有一个频率为13的新tokenest，我们会将es和t的频率减少 13。
| Number | Token | Frequency |
|---|---|---|
| 1 | </w> | 23 |
| 2 | o | 14 |
| 3 | l | 14 |
| 4 | d | 10 |
| 5 | e | 16-13=3 |
| 6 | r | 3 |
| 7 | f | 9 |
| 8 | i | 9 |
| 9 | n | 9 |
| 10 | s | 13-13=0 |
| 11 | t | 13-13=0 |
| 12 | w | 4 |
| 13 | es | 9+4=13-13=0 |
| 14 | est | 13 |
迭代3：
让我们现在考虑</w>token，我们看到字节对est和</w>在我们的语料库中出现了13次。
注意：合并停止token</w>非常重要。这有助于算法理解estimate和highest等词之间的区别。这两个词都有一个共同的est，但一个词在结尾有一个esttoken，一个在开头。因此，像est和est</w>这样的token将被不同地处理。如果算法看到tokenest</w>，它就会知道它是highest这个词的token，而不是estate的。
| Number | Token | Frequency |
|---|---|---|
| 1 | </w> | 23-13=10 |
| 2 | o | 14 |
| 3 | l | 14 |
| 4 | d | 10 |
| 5 | e | 16-13=3 |
| 6 | r | 3 |
| 7 | f | 9 |
| 8 | i | 9 |
| 9 | n | 9 |
| 10 | s | 13-13=0 |
| 11 | t | 13-13=0 |
| 12 | w | 4 |
| 13 | es | 9+4=13-13=0 |
| 14 | est | 13-13=0 |
| 15 | est</w> | 13 |
迭代4：
查看其他token，我们看到字节对o和l在我们的语料库中出现了 7 + 3 = 10` 次。
| Number | Token | Frequency |
|---|---|---|
| 1 | </w> | 23-13=10 |
| 2 | o | 14-10=4 |
| 3 | l | 14-10=4 |
| 4 | d | 10 |
| 5 | e | 16-13=3 |
| 6 | r | 3 |
| 7 | f | 9 |
| 8 | i | 9 |
| 9 | n | 9 |
| 10 | s | 13-13=0 |
| 11 | t | 13-13=0 |
| 12 | w | 4 |
| 13 | es | 9+4=13-13=0 |
| 14 | est | 13-13=0 |
| 15 | est</w> | 13 |
| 16 | ol | 7+3=10 |
迭代5：
我们现在看到字节对ol和d在我们的语料库中出现了10次。
| Number | Token | Frequency |
|---|---|---|
| 1 | </w> | 23-13=10 |
| 2 | o | 14-10=4 |
| 3 | l | 14-10=4 |
| 4 | d | 10-10=0 |
| 5 | e | 16-13=3 |
| 6 | r | 3 |
| 7 | f | 9 |
| 8 | i | 9 |
| 9 | n | 9 |
| 10 | s | 13-13=0 |
| 11 | t | 13-13=0 |
| 12 | w | 4 |
| 13 | es | 9+4=13-13=0 |
| 14 | est | 13-13=0 |
| 15 | est</w> | 13 |
| 16 | ol | 7+3=10-10=0 |
| 17 | old | 10 |
现在我们发现f、i和n的频率为9，但我们只有一个单词包含这些字符，因此我们没有将它们合并。为了本文的简单起见，让我们现在停止迭代并。看看我们最终的token列表：
| Number | Token | Frequency |
|---|---|---|
| 1 | </w> | 10 |
| 2 | o | 4 |
| 3 | l | 4 |
| 4 | e | 3 |
| 5 | r | 3 |
| 6 | f | 9 |
| 7 | i | 9 |
| 8 | n | 9 |
| 9 | w | 4 |
| 10 | est</w> | 13 |
| 11 | old | 10 |
频率计数为0的token已从表中删除。我们现在可以看到列表的总token数为11，这比我们最初列表的token数12个要少，说明token列表被有效压缩了。
你是不是想说这算法好像也没那么nb，token列表才减了1个token？但是你要知道，这是一个很小的语料库。在实际中，我们的预料库通常要大得多，从而我们能通过更多的迭代次数将token列表缩小更多的比例。
你一定也注意到，当我们添加一个token时，我们的计数既能增加也能减少，也能保持不变。在实际中，token计数先增加然后减少。算法的停止标准可以是token的计数或固定的迭代次数。我们选择一个最合适的停止标准，以便我们的数据集可以以最有效的方式分解为token。
现在让我们看看如何解码我们的示例。要解码，我们必须简单地将所有token连接在一起以获得整个单词。例如编码序列[“the</w>”,“high”,“est</w>”,“range</w>”,“in</w>”,“Seattle</w>” ]，我们将被解码为 [“the”, “highest”, “range”, “in”, “Seattle”] 而不是 [“the”, “high”, “estrange”, “in”, “Seattle”]，因为est中存在</w>token。
对新数据进行编码的过程还是比较简单的。然而，编码本身计算复杂度比较高。假设单词的序列是[“the</w>”,“highest</w>”,“range</w>”,“in</w>”,“Seattle</w>”]。我们将遍历我们在语料库中找到的所有token——从最长到最短，并尝试使用这些token替换给定单词序列中的子字符串。最终，我们将遍历所有token，并且我们的子字符串将被替换为我们token列表中已经存在的token组合。如果会留下几个子串（我们的模型在训练中没有看到的词），我们将用unknown token替换它们。
我们常用的语言模型词汇列表是很大的，但仍有可能出现不在里面的单词。在实践中，我们将tokenized好的单词保存在字典中。对于未知（新）词，我们应用上述编码方法对新词进行tokenization，并将新词的token添加到我们的token字典中以备将来用到。
为了以最有效的方式构建语料库，BPE在迭代的时候通过比较token的频率大小来穷尽每一种可能。所以，是的，它遵循一种贪婪的策略来尽可能取得最优的解决方案。
无论如何，BPE 是使用最广泛的sub-word tokenization算法之一。尽管贪婪，但它具有良好的性能！并被作为机器翻译等主流NLP任务的首选tokenize方法之一。