双数组Trie(Double Array Trie)实现原理的一点剖析

曾经有人发来邮件询问《重写了Minidx的分词模块,实现了超高速分词(2007/09/08)》的实现原理并且希望我可以公开源代码,我回复了他的邮件告之我采用了Double Array Trie来构造我的字典并发了实现的C++代码,结果没多久这位同学告诉我没看懂其中算法的原理……

双数组的本质实际上就是一个有限状态的自动机(deterministic finite automaton,简称DFA),所谓的DFA就是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符,它都能根据事先给定的转移函数转移到下一个状态(这个状态有可能就是先前那个状态)。这个不熟悉的话可以google一下DFA.另外datrie(英文)和chasen的darts(日文)都是很好的DAT的具体实现,其中京都大学情報学研究科Mecab分词就采用了chasen的DAT实现。

9月份的时候一次公司内部学习会上我曾经做过一份相关的资料,写的比较乱,制作的前提是阅读者对各种字符编码和DAT算法有一定了解(对这两点不熟悉的可能理解起来比较困难),这一资料现在提供下载(双数组Trie(Double Array Trie)实现原理 相关文档资料栏目中)。PDF格式,日文,不过当中比较多的是实现的代码以及抽取的数字,应该都可以看懂吧。

7 thoughts on “双数组Trie(Double Array Trie)实现原理的一点剖析”

Leave a Reply

Your email address will not be published. Required fields are marked *