一分钟搞懂的算法之BPE算法

昨天总结实验数据分析的时候发现一个机器翻译的其中的一个脚本，其中用到的算法就是BPE算法，刚开始感觉很高大上的，因为总是听到带上算法帽子的东西就觉得666。等自己好好研究研究，网上各种找资料才知道，其实还挺好理解的，所以真的应了那句老话，眼见为实呀。

总说

BPE，（byte pair encoder）字节对编码，也可以叫做digram coding双字母组合编码，主要目的是为了数据压缩，算法描述为字符串里频率最常见的一对字符被一个没有在这个字符中出现的字符代替的层层迭代过程。具体在下面描述。该算法首先被提出是在Philip Gage的C Users Journal的 1994年2月的文章“A New Algorithm for Data Compression”。

算法过程

这个算法个人感觉很简单，下面就来讲解下：

比如我们想编码：

aaabdaaabac

我们会发现这里的aa出现的词数最高（我们这里只看两个字符的频率），那么用这里没有的字符Z来替代aa：

ZabdZabac

Z=aa

此时，又发现ab出现的频率最高，那么同样的，Y来代替ab：

ZYdZYac

Y=ab

Z=aa

同样的，ZY出现的频率大，我们用X来替代ZY：

XdXac

X=ZY

Y=ab

Z=aa

最后，连续两个字符的频率都为1了，也就结束了。就是这么简单。

解码的时候，就按照相反的顺序更新替换即可。

参考

Byte pair encoding

https://en.wikipedia.org/wiki/Byte_pair_encoding

下一篇预告：

TreeLstm Sentiment Classification 树形LSTM情感分类理论篇