基于优先级队列的BPE高效实现

Question

我认为这并不是严格意义上的BPE (字节对编码)，但也有一个类似的想法适用于字符串。

假设字典中有三个中文单词(我将使用一本像CEDICT这样的大型词典来实际使用)。

• 我
• 喜欢
• 水果

然后输入如下所示。

我喜欢水果(我喜欢水果)

由于中文文本不被空格分割，所以很难处理。

我们可以将输入字符串分解为多个单个字符。

我喜欢水果

然后在左、右查找新的符号对，并将它们组合起来。如果组合词在字典中，我们可以用一个新的符号替换组合词。

• 我喜
• 喜欢<-在dic中
• 欢水
• 水果<-在dic中

我们发现了两个新的符号，所以输入的文本变成

我喜欢水果

我们应该反复迭代，直到在字典中找不到任何组合词为止。在这种情况下，我们在字典中找不到新的符号。

• 我喜欢水果
• 喜欢水果

要天真地实现这一点并不困难，但我们需要多次扫描相邻的两个单词。有人说我们可以用优先级队列有效地实现BPE。我对压缩算法不熟悉。如果有人能告诉我实现或有用的文件，我将不胜感激。

在这种方法中，将词汇表外的单词分解为单个字符，从而避免了未知单词的问题。

诚挚的问候,

参考文献：带有子词单位的稀有词的神经机器翻译，由于计算的复杂性，他不得不从标记前的单词开始.

Answer 1

我建议在每个级别上使用散列查找将字典存储为trie。这将用哈希查找替换扫描，哈希查找是O(1)。