问题描述
- 最近Eric很头大。因为他所管理的QQ群有一群小学生总是弄得群里硝烟四起,更严重的是小学生们不懂骂人的艺术。Eric为了提升他们的语言组织能力,打算把所有人的发言都做一次敏感词检索。
解决方案
- 话说我一开始想到的是用快速字符串搜索,后来发现这个得不偿失。敏感词库有一万四,KMP算法时间复杂度是 O(字符串长度+字串长度)。 经过简单的计算得出,搜索所有的敏感词之后这个时间复杂度就变成了 O(字符串长度*敏感词库数量+敏感词库的所有词语的长度总和) 【假设原字符串长20,词库中有14000个长度为6的词,那么这里是364000】
- 经过我和另一个同学的讨论,我决定把解决方案换成字典树。字典树的构建就是初始化工作,那个我们不管。然后检索敏感词就是如百度百科中所说,如果当前字符在你现在位置的任一儿子则往下找,如果没有的话则退出递归。直到找到这个词就标记一下或者是找不到这个词就退出。这明显大大地减少了搜索次数。【虽然代码比KMP长的多】
- 但是选用了字典树就有一个很不好的问题:这是一个多叉树!
- 于是本文就来讲一下我构造多叉树的方法了。
正文?
AB
CD
ABCD
ABCDE
CDE
- 那么中规中矩的字典树应该长这样。【"√"表示截至当前已经找到一个词了】
- 我不想用链表,那我怎么样才可以把这棵树放到一个一维数组里呢?于是我啪叽地把这棵树拍扁了。
Type
T_DictTree = record
len : longint; //储存cont数组长度
cont: Array Of Record //动态数组
Str : Ansistring; //当前节点的字符。用Ansistring是为了日后如果需要分词优化而做的预留
Chl : longint; //当前节点有多少个儿子
S : integer; //标记截至当前节点是否是完整的一个词
Chls: Array of longint; //这个节点的儿子们
End;
end;
代码