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

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

总说

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

算法过程

       这个算法个人感觉很简单&＃xff0c;下面就来讲解下&＃xff1a;

       比如我们想编码&＃xff1a;

              aaabdaaabac

       我们会发现这里的aa出现的词数最高&＃xff08;我们这里只看两个字符的频率&＃xff09;&＃xff0c;那么用这里没有的字符Z来替代aa&＃xff1a;

               ZabdZabac

               Z&＃61;aa

       此时&＃xff0c;又发现ab出现的频率最高&＃xff0c;那么同样的&＃xff0c;Y来代替ab&＃xff1a;

               ZYdZYac

               Y&＃61;ab

               Z&＃61;aa

       同样的&＃xff0c;ZY出现的频率大&＃xff0c;我们用X来替代ZY&＃xff1a;

               XdXac

               X&＃61;ZY

               Y&＃61;ab

               Z&＃61;aa

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

       解码的时候&＃xff0c;就按照相反的顺序更新替换即可。

参考

Byte pair encoding 

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

更多精彩内容&＃xff0c;请关注 深度学习自然语言处理 公众号&＃xff0c;就是下方啦&＃xff01;跟随小博主&＃xff0c;每天进步一丢丢&＃xff01;哈哈&＃xff01;