淮安网站建设哪家好,旅游网站 建设平台分析,免费网站开发软件有哪些,flash网站引导页面制作最近写了一个高性能的敏感词检测组件【ToolGood.Words】。 一、高性能#xff0c;它的效率到底有多快#xff1f; 如果将正则表达式的算法效率设为1#xff0c;高性能可达到正则表达式的1.5万倍。 二、选一个巧妙的算法#xff1a; AC自动机#xff08;Aho-Corasick Autom… 最近写了一个高性能的敏感词检测组件【ToolGood.Words】。 一、高性能它的效率到底有多快 如果将正则表达式的算法效率设为1高性能可达到正则表达式的1.5万倍。 二、选一个巧妙的算法 AC自动机Aho-Corasick Automation算法在1975年产生于贝尔实验室是著名的多模式匹配算法之一一个常见的例子就是给定N个单词给定包含M个字符的文章要求确定多少个给定的单词在文章中出现过AC自动机在匹配文本时不需要回溯处理时间复杂度与pattern无关仅是target的长度O(N)构建AC自动机的时间复杂度。 AC自动机的构建主要由三个步骤 2.1、针对所有模式串构建Trie树。 2.2、针对所有Trie树上的接点构建Fail指针Fail指针指向的是如果当前节点匹配失败则从通过Fail指针指向的新的节点开始匹配但新的节点必须满足所在在新节点模式串的前缀必须是转移前的节点所在模式串的子串也就是已经匹配成功的部分。 2.3、正式匹配过程a从Trie树root节点开始每次根据读入的字符沿着自动机向下移动。b当读入的字符在分支中不存在时递归走Fail指针路径。如果走Fail指针路径走到了root节点则跳过该字符处理下一个字符。c因为AC自动机是沿着文本移动的所以在读取完所有输入文本后最后递归走失败路径直到到达根节点这样可以检测出所有的模式。 三、优化AC自动机算法 细看AC自动算法匹配过程在(b)步骤我们会发现节点匹配失败后会顺Fail指针继续执行这个步骤可以优化优化Fail指针将相同的节点合并成一个同一个节点。 四、填平性能低洼地 优化AC自动机算法后测试代码后会发现代码性能没有太大提升。 经测试发现TrieNode获取下一节点的方法TryGetValue占用了90%的计算量。 分析Trie树有两个特点1、root节点下有大量子节点2、中间节点的子节点数量很少。 优化TryGetValue方法 1、root的子节点转成数组类型 2、修改TryGetValue方法内 public class TrieNode { public bool End { get ; set ; } public List string Results { get ; set ; } private Dictionary char , TrieNode m_values; private uint minflag uint .MaxValue; private uint maxflag uint .MinValue; //.... public bool TryGetValue( char c, out TrieNode node) { if (minflag ( uint )c maxflag ( uint )c) { return m_values.TryGetValue(c, out node); } node null ; return false ; } } 五、优化后的代码段 public class StringSearch { TrieNode _root new TrieNode(); TrieNode[] _first new TrieNode[ char .MaxValue 1]; //..... public bool ContainsAny( string text) { TrieNode ptr null ; for ( int i 0; i text.Length; i) { TrieNode tn; if (ptr null ) { tn _first[text[i]]; } else { if (ptr.TryGetValue(text[i], out tn) false ) { tn _first[text[i]]; } } if (tn ! null ) { if (tn.End) { return true ; } } ptr tn; } return false ; } } 六、性能对比图10W次对比 ToolGood.Words内的非法词(敏感词)检测类StringSearch、WordsSearch、IllegalWordsSearch、IllegalWordsQuickSearch; 注:C#自带正则很慢StringSearch.ContainsAny是Regex.IsMatch效率的1.5万倍。 Regex.Matches的运行方式跟IQueryable的类似只返回MatchCollection,还没有计算。 TrieFilter,FastFilter来源: http://www.cnblogs.com/yeerh/archive/2011/10/20/2219035.html 七、开源项目 码云 https://git.oschina.net/toolgood/ToolGood.Words GitHub: https://github.com/toolgood/ToolGood.Words 原文地址http://www.cnblogs.com/toolgood/p/6284718.html.NET社区新闻深度好文微信中搜索dotNET跨平台或扫描二维码关注
