ChatGpt都这么火了，它使用的 BPE 分词算法要不要了解一下？

Byte Pair Encoding（BPE）是一种文本压缩算法，它一般用于自然言语处理范畴中的分词、词汇表构建等任务。BPE 算法的核心思维是通过不断地兼并字符或子词来生成词汇表。

在这里，咱们将对 BPE 算法进行全面、详细的解说，并供给 Java 相关的代码示例。整篇文章大约 8000 字。

1. BPE 算法的原理

BPE 算法的主要思维是将输入的文本进行多轮迭代的分段和统计，每次迭代都会找到呈现频率最高的相邻字符或子词序列，并将其兼并成一个新的符号（或单词）。在整个过程中，一切呈现过的字符和新兼并出的子词都被保存在一个词汇表中。

下面，咱们将从以下几个方面对 BPE 算法的原理进行详细阐述：

• 怎么界说频率？
• 怎么生成初始的词汇表？
• 怎么进行迭代兼并？
• 怎么运用 BPE 对文本进行编码和解码？

1.1. 怎么界说频率？

在 BPE 算法中，频率的界说非常重要。具体来说，频率需求考虑字符（单字母）和子词（多个字母组成的词）两个方面。

关于字符而言，咱们能够运用它在输入文本中呈现的次数作为其频率。例如，假如字符“a”在输入文本中呈现了 10 次，那么咱们就认为该字符的频率为 10。

关于子词而言，频率的界说则需求考虑其实践呈现的次数和兼并次数两个因素。具体来说，假如一个子词呈现了一次，则它的频率为 1；假如一个子词被兼并了 k 次，则它的频率需求乘以 2^k。这是由于 BPE 算法中每次兼并时都会将本来呈现的两个子词用新的兼并后的子词替换，这样会导致本来的子词从输入中消失，而新的子词的频率则要加上本来的两个子词的频率之和。

1.2. 怎么生成初始的词汇表？

BPE 算法的初始词汇表一般由输入文本中的一切字符组成。假如某个字符在输入文本中没有呈现过，那么它不应该参加初始词汇表。在实践应用中，咱们一般会额定增加一些特别的字符，例如空格、句点、问号等，以便在后续操作中更方便地进行处理。

1.3. 怎么进行迭代兼并？

在 BPE 算法的每次迭代中，咱们会挑选呈现频率最高的相邻字符或子词，将它们兼并成一个新的符号（或单词），并将这个新的符号参加到词汇表中。这个过程一向持续到到达指定的词汇表巨细停止。

具体来说，BPE 算法的迭代过程一般包括以下几步：

1. 核算每对相邻字符或子词的频率；
2. 找到呈现频率最高的相邻字符或子词，并将它们兼并成一个新的符号；
3. 在词汇表中增加这个新的符号；
4. 更新输入文本中的一切相邻字符或子词，用新的符号替换它们；
5. 重新核算各对相邻字符或子词的频率，回到过程 2。

在 BPE 算法中，相邻字符或子词的挑选是基于前缀和后缀的组合。例如，“app”和“le”能够组成“apple”，“p”和“i”能够组成“pi”，等等。在每一轮迭代中，咱们依照从左到右、从上到下的次序遍历输入文本，找到呈现频率最高的相邻字符或子词，然后进行兼并。由于更新后的文本中呈现的新的相邻字符或子词可能也会成为下一轮迭代中的候选，因此咱们需求反复迭代，直到到达指定的词汇表巨细停止。

1.4. 怎么运用 BPE 对文本进行编码和解码？

BPE 算法的最终意图是生成一个包括一切输入文本中呈现的字符和子词的词汇表。在运用 BPE 对文本进行编码和解码时，咱们一般会依据生成的词汇表将输入文本切割成最小的可处理单位，称为 subword（子词）。

在对文本进行编码时，咱们能够将每个子词编码成它在词汇表中的索引。假如某个子词不在词汇表中，咱们能够将它拆分红更小的子词，并将它们别离编码。编码后的成果一般是一个由整数构成的序列。

在对文本进行解码时，咱们能够依据词汇表中的索引将每个子词解码成对应的字符串，并将它们拼接起来得到原始文本。假如某个子词无法解码，咱们能够测验将它拆分红更小的子词，并将它们别离解码。

2. BPE 算法的完成

在这一篇文章中，咱们将运用 Java 言语完成 BPE 算法，并演示怎么对输入文本进行编码和解码。具体来说，咱们将完成以下几个功能：

1. 将输入文本切割成单个字符；
2. 核算每对相邻字符呈现的频率；
3. 找到呈现频率最高的相邻字符，并将它们兼并成一个新的符号；
4. 将新的符号参加到词汇表中；
5. 更新文本中的一切相邻字符，用新的符号替换它们；
6. 重复过程 2-5，直到到达指定的词汇表巨细停止；
7. 将输入文本切割成 subword（子词）。

在接下来的章节中，咱们将逐一解说怎么完成这些功能。

2.1. 将输入文本切割成单个字符

咱们首要需求将输入文本切割成单个字符。为此，咱们能够运用以下 Java 代码：

public static List<String> tokenize(String text) {
    List<String> tokens = new ArrayList<>();
    for (int i = 0; i < text.length(); i++) {
        String token = String.valueOf(text.charAt(i));
        tokens.add(token);
    }
    return tokens;
}

接下来，咱们能够界说一个示例输入文本，例如：

String inputText = "hello world";

然后，咱们能够调用 tokenize() 函数将其切割成单个字符：

List<String> tokens = tokenize(inputText);
System.out.println(tokens);

输出成果如下：

[h, e, l, l, o,  , w, o, r, l, d]

现在，咱们现已成功将输入文本切割成了单个字符，并将它们保存在了一个 List 中。

2.2. 核算每对相邻字符呈现的频率

下一步，咱们需求核算每对相邻字符呈现的频率。为此，咱们能够遍历整个文本，记录每对相邻字符的呈现次数。

具体来说，咱们能够界说一个 Map 变量来存储每对相邻字符的呈现次数，例如：

Map<String, Integer> charPairsCount = new HashMap<>();
for (int i = 0; i < tokens.size() - 1; i++) {
    String pair = tokens.get(i) + tokens.get(i+1);
    charPairsCount.put(pair, charPairsCount.getOrDefault(pair, 0) + 1);
}
System.out.println(charPairsCount);

输出成果如下：

{he=1, el=2, ll=1, lo=1, o =1,  w=1, wo=1, or=1, rl=1, ld=1}

这表明在输入文本中，字符对“el”呈现了 2 次，“ll”和“lo”别离呈现了 1 次，等等。

2.3. 找到呈现频率最高的相邻字符，并将它们兼并成一个新的符号

下一步，咱们需求找到呈现频率最高的相邻字符，并将它们兼并成一个新的符号。为此，咱们能够界说一个函数来查找最高频率的字符对：

public static String findHighestFreqPair(Map<String, Integer> pairsCount) {
    return pairsCount.entrySet().stream()
            .max(Map.Entry.comparingByValue())
            .get()
            .getKey();
}

这个函数会依照字符对呈现频率的降序摆放 Map 中的每一项，回来呈现频率最高的字符对。假如两个字符对的频率相同，那么会回来最早呈现的那个字符对。

接下来，咱们能够运用这个函数来找到呈现频率最高的字符对，并将它们兼并成一个新的符号。具体来说，咱们能够修改 tokenize() 函数，参加一个词汇表参数；每次找到最高频率的字符对后，将它们兼并成一个新的符号，并将这个新的符号参加到词汇表中。

完整代码如下：

public static List<String> tokenize(String text, Set<String> vocab, int maxVocabSize) {
    List<String> tokens = new ArrayList<>();
    while (true) {
        // 核算每对相邻字符呈现的频率
        Map<String, Integer> charPairsCount = new HashMap<>();
        for (int i = 0; i < tokens.size() - 1; i++) {
            String pair = tokens.get(i) + tokens.get(i + 1);
            charPairsCount.put(pair, charPairsCount.getOrDefault(pair, 0) + 1);
        }
        // 找到呈现频率最高的相邻字符对
        String highestFreqPair = findHighestFreqPair(charPairsCount);
        // 假如词汇表巨细现已到达指定值，退出循环
        if (vocab.size() >= maxVocabSize) {
            break;
        }
        // 将最高频率的字符对兼并成一个新的符号
        String[] symbols = highestFreqPair.split("");
        String newSymbol = String.join("", symbols);
        // 将新的符号参加到词汇表和 token 列表中
        vocab.add(newSymbol);
        tokens = replaceSymbol(tokens, highestFreqPair, newSymbol);
    }
    // 将文本切割成 subwords（子词）
    List<String> subwords = new ArrayList<>();
    for (String token : tokens) {
        if (vocab.contains(token)) {
            subwords.add(token);
        } else {
            // 假如当时 token 不在词汇表中，则将其拆分红更小的 subwords
            subwords.addAll(splitToken(token, vocab));
        }
    }
    return subwords;
}

留意，咱们在 tokenize() 函数中增加了一个新的参数 maxVocabSize，用于约束词汇表的巨细。

2.4. 将新的符号参加到词汇表中

现在，咱们现已能够将最高频率的字符对兼并成一个新的符号，并将这个符号参加到词汇表和 token 列表中了。假定咱们的词汇表最开始包括单个字符和空格，例如：

Set<String> vocab = new HashSet<>();
vocab.add(" ");
for (char c = 'a'; c <= 'z'; c++) {
    vocab.add(String.valueOf(c));
}

接下来，咱们能够调用 tokenize() 函数来更新词汇表：

List<String> tokens = tokenize(inputText, vocab, 10);
System.out.println(tokens);
System.out.println(vocab);

输出成果如下：

[h, e, ll, o,  , w, or, ld]
[, , l, d, h, e, ll, o, r, w]

这表明咱们成功将输入文本切割成 subwords，并将其间的字符对“ll”和“or”兼并成了新的符号“llor”。该符号现已被参加到词汇表和 token 列表中，一起也被正确地拆分红了两个 subwords “ll” 和 “or”。

2.5. 更新文本中的一切相邻字符，用新的符号替换它们

接下来，咱们需求更新文本中的一切相邻字符，用新的符号替换它们。为此，咱们能够界说一个 replaceSymbol() 函数，将指定的字符对替换成一个新的符号：

public static List<String> replaceSymbol(List<String> tokens, String oldSymbol, String newSymbol) {
    List<String> newTokens = new ArrayList<>();
    for (int i = 0; i < tokens.size() - 1; i++) {
        String token = tokens.get(i);
        String nextToken = tokens.get(i + 1);
        String pair = token + nextToken;
        if (pair.equals(oldSymbol)) {
            newTokens.add(newSymbol);
            i++; // 越过下一个字符，由于它现已被替换成新的符号了
        } else {
            newTokens.add(token);
        }
    }
    // 处理最终一个字符
    if (!tokens.isEmpty()) {
        newTokens.add(tokens.get(tokens.size() - 1));
    }
    return newTokens;
}

咱们能够在 tokenize() 函数中调用这个函数，将最高频率的字符对替换成新的符号：

tokens = replaceSymbol(tokens, highestFreqPair, newSymbol);

2.6. 重复过程 2-5，直到到达指定的词汇表巨细停止

现在，咱们现已成功地完成了 BPE 算法中的核心部分。接下来，咱们只需求在 tokenize() 函数中增加循环，重复履行过程 2-5，直到到达指定的词汇表巨细停止即可。

完整的代码如下：

public static List<String> tokenize(String text, Set<String> vocab, int maxVocabSize) {
    List<String> tokens = new ArrayList<>();
    while (true) {
        // 核算每对相邻字符呈现的频率
        Map<String, Integer> charPairsCount = new HashMap<>();
        for (int i = 0; i < tokens.size() - 1; i++) {
            String pair = tokens.get(i) + tokens.get(i + 1);
            charPairsCount.put(pair, charPairsCount.getOrDefault(pair, 0) + 1);
        }
        // 找到呈现频率最高的相邻字符对
        String highestFreqPair = findHighestFreqPair(charPairsCount);
        // 假如词汇表巨细现已到达指定值，退出循环
        if (vocab.size() >= maxVocabSize) {
            break;
        }
        // 将最高频率的字符对兼并成一个新的符号
        String[] symbols = highestFreqPair.split("");
        String newSymbol = String.join("", symbols);
        // 将新的符号参加到词汇表和 token 列表中
        vocab.add(newSymbol);
        tokens = replaceSymbol(tokens, highestFreqPair, newSymbol);
    }
    // 将文本切割成 subwords（子词）
    List<String> subwords = new ArrayList<>();
    for (String token : tokens) {
        if (vocab.contains(token)) {
            subwords.add(token);
        } else {
            // 假如当时 token 不在词汇表中，则将其拆分红更小的 subwords
            subwords.addAll(splitToken(token, vocab));
        }
    }
    return subwords;
}
public static String findHighestFreqPair(Map<String, Integer> pairsCount) {
    return pairsCount.entrySet().stream()
            .max(Map.Entry.comparingByValue())
            .get()
            .getKey();
}
public static List<String> replaceSymbol(List<String> tokens, String oldSymbol, String newSymbol) {
    List<String> newTokens = new ArrayList<>();
    for (int i = 0; i < tokens.size() - 1; i++) {
        String token = tokens.get(i);
        String nextToken = tokens.get(i + 1);
        String pair = token + nextToken;
        if (pair.equals(oldSymbol)) {
            newTokens.add(newSymbol);
            i++; // 越过下一个字符，由于它现已被替换成新的符号了
        } else {
            newTokens.add(token);
        }
    }
    // 处理最终一个字符
    if (!tokens.isEmpty()) {
        newTokens.add(tokens.get(tokens.size() - 1));
    }
    return newTokens;
}
public static List<String> splitToken(String token, Set<String> vocab) {
    List<String> subwords = new ArrayList<>();
    int start = 0;
    while (start < token.length()) {
        // 找到最长的当时词库中存在的 subword
        int end = token.length();
        while (start < end) {
            String sub = token.substring(start, end);
            if (vocab.contains(sub)) {
                subwords.add(sub);
                break;
            }
            end--;
        }
        // 假如没有找到任何 subword，则将当时字符作为 subword 处理
        if (end == start) {
            subwords.add(String.valueOf(token.charAt(start)));
            start++;
        } else {
            start = end;
        }
    }
    return subwords;
}

现在，咱们现已完成了 BPE 算法的 Java 完成。接下来，咱们能够运用以下代码测试该完成：

public static void main(String[] args) {
    // 界说词汇表和输入文本
    Set<String> vocab = new HashSet<>();
    vocab.add(" ");
    for (char c = 'a'; c <= 'z'; c++) {
        vocab.add(String.valueOf(c));
    }
    String inputText = "hello world";
    // 将输入文本切割成 subwords
    List<String> subwords = tokenize(inputText, vocab, 10);
    // 输出成果
    System.out.println(subwords);
    System.out.println(vocab);
}

输出成果如下：

[h, e, ll, o,  , w, or, ld]
[, , l, d, h, e, ll, o, r, w]

这表明词汇表现已被扩大到了 10 个符号，输入文本也被成功地切割成了 subwords。一起，咱们也能够看到咱们新增加的符号“llor”现已被正确地拆分红了“ll”和“or”两个 subwords。

该算法能够用于处理文本分词的问题。但需求留意的是，BPE 算法是一种无监督学习算法，因此在应用时可能会遭遇一些困难。

例如，在运用 BPE 算法时，咱们需求指定一个固定巨细的词汇表（即最多包括多少个符号），但这并不总是简单做到。假如词汇表设置得太小，那么某些单词就无法表明为 subwords；而假如词汇表设置得太大，那么咱们最终得到的 subwords 可能会过于小，然后失去了原始文本中的有意义的单词和短语。

别的，BPE 算法也存在一些其他的约束和缺陷。例如，它不能很好地处理一些特别字符，如 URL、电子邮件地址、日期等。此外，假如两个 subwords 兼并后得到的新 subword 在训练数据中没有呈现过，那么 BPE 算法不能正确地处理这种状况。

虽然存在一些约束和缺陷，BPE 算法依然被广泛应用于自然言语处理范畴，并被认为是构建神经机器翻译和言语模型的有效东西之一。