字节对编码（BPE）中的合并操作是否具备最优压缩性？

给定字符串 s = "aeeefeekeelaeoae"，初始词表为 Vocab: {a, e, f, k, l, o}（即字符串s包含的字符集合）。对s执行BPE，设定合并次数为2，最终词表大小需变为8。由于"ee"出现频率最高，会优先合并该字符对，但此时存在两种合并选择：合并 (s[2] + s[3]) 或 (s[3] + s[4])。

选择合并 s[2] + s[3] 的压缩效果弱于合并 s[3] + s[4]，因为合并"ee"后，"ae"会成为出现频率最高的字符对。

场景1：合并s[2]和s[3]

• 令"ee"为Z，字符串变为 "aZefZkZlaeoae"；
• 随后合并出现频率最高的"ae"为X，字符串变为 "aZefZkZlXoX"，长度为11。

场景2：合并s[3]和s[4]

• 令"ee"为Z，字符串变为 "aeZfZkZlaeoae"；
• 随后合并出现频率最高的"ae"为X，字符串变为 "XZfZkZlXoX"，长度为10。

可见，两次合并后场景2的压缩效果更优，字符串长度更短，这表明BPE的合并选择会直接影响压缩的最优性——BPE的贪心合并策略并不能保证每次都得到全局最优的压缩结果。

内容的提问来源于stack exchange，提问作者gurjyot