双数组Trie(Double Array Trie)实现原理的一点剖析
By Minidxer | December 24, 2007
曾经有人发来邮件询问《重写了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格式，日文，不过当中比较多的是实现的代码以及抽取的数字，应该都可以看懂吧。
Topics:
Minidx相关 |
7 Comments » |
447 views
Tags: darts, DAT, datrie, Double Array Trie, mecab, Minidx, 双数组, 实现原理
看不懂,不过,嘿嘿,听说名人录以后再进了…我来试试先…
另外,圣诞快乐啊!
@sofish
圣诞快乐啊!~
“听说名人录以后再进了”是…什么意思啊?akismet的名人录?呵呵
可能要进其他的名人录也难啦…
没关系……出来了不要紧，进去过的要再进，很容易的……
提供的链接网址无法下载
@zdq
刚才试了一下,发现Firefox正常，但是IE6.0的确有问题，现在已经改好了。谢谢！
Trackbacks