问题描述

  • 最近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;
  • 如上便是这个树的结构了

代码