BPE algorithm analysis

BPE算法解析

是一种用于数据压缩和自然语言处理（NLP）的子词分词算法，通过反复合并语料库中最常见的字符或字符对来构建一个固定大小的词汇表，有效减少词汇表规模，解决罕见词问题，并支持变长子词的表示。其核心在于迭代地将高频的字符对替换为新符号，并不断更新词汇表和文本的划分，直到达到预设的词汇表大小或迭代次数。主要包含训练以及应用流程。

将语料库拆分成单词序列self.word_freq，并统计每个单词的出现频率，如{'the': 1, 'highest': 2, 'quality': 1}。
拆分每个单词，并且每个单词后面加上</w>,组成单词拆分结果集合self.splits，如{'the': ['t', 'h', 'e', '</w>'], 'highest': ['h', 'i', 'g', 'h', 'e', 's', 't', '</w>'], 'quality': ['q', 'u', 'a', 'l', 'i', 't', 'y', '</w>']}。
初始化字符表vocab，如['</w>', 'a', 'e', 'g', 'h', 'i', 'l', 'o', 'q', 's', 't', 'u', 'y']。
迭代执行，直到词汇表大小达到预设值或迭代次数达到最大值：
- 统计每个字符对的出现频率self.get_pairs_freq()，如{('h', 'i'): 2, ('i', 'g'): 2, ('g', 'h'): 2, ('h', 'e'): 2, ('e', 's'): 2, ('s', 't'): 2, ('t', '</w>'): 2, ...}。
- 比较获取出现频率最高的字符对pair = max(pair_freq, key=pair_freq.get)，如('h', 'i')。
- 更新单词拆分结果集合self.update_splits(pair[0], pair[1])，如{'the': ['t', 'h', 'e', '</w>'], 'highest': ['hi', 'g', 'h', 'e', 's', 't', '</w>'], 'quality': ['q', 'u', 'a', 'l', 'i', 't', 'y', '</w>']}
- 设置合并规则self.merges[pair] = pair[0] + pair[1]，如{('h', 'i'): 'hi'}。
- 更新字符表，self.vocab.append(pair[0] + pair[1])，如['</w>', 'a', 'e', 'g', 'h', 'i', 'l', 'o', 'q', 's', 't', 'u', 'y', 'hi']。
- 迭代次数加1。

将输入拆分成字符序列splits = [list(t) + ["</w>"] for t in s.split()]，最后加上</w>，如[["t", "h", "e", "</w>"], ["h", "i", "g", "h", "e", "s", "t", "</w>"]]。
遍历合并规则self.merges，检查每个合并规则是否符合每个字符序列，如果符合则合并更新，如合并规则('h', 'i')符合，则合并更新[["t", "h", "e", "</w>"], ["hi", "g", "h", "e", "s", "t", "</w>"]]。