在本人昨晚发的强大灵活的脏字过虑:1万字文章过虑1万关键词用时只要1毫秒(包括扩展的高亮功能) 文章中,只是介绍过虑的功能和性能1234,这个文章主要讲一下实现的思路,另外给大家看一下Aho–Corasick算法的C#实现。
既然是要过虑,那就要先查找,如果是直接的一个字符一个字符的匹配,那是很耗时的,因为时间花在不需要匹配的工作,有不少人会用正则去解决过虑,我09年的时候也这样,但后来发现大量关键词下性能确实极低下,所以才会另想它法。上一文中的过虑主要思想是这样的,开始会先用一个字典保存保存所有关键词,同一个字母开头的会另放在一个子字典里,这样一来,扫描的范围就大大的缩小了,然后再考虑到脏字一般是2个字的占了很大的比例,所以再在第二个字母做判断,如果不存在就不需要再扫描下去了,至于可跳字符,就是在直接需要扫描的时候一一判断的,没技巧可讲,另外一点值得注意的是,大小写敏感的情况下,在判断时需要转换大小写,大量关键词影响不小,所以就初始化时再保存了一分小写的,所以在扫描的时候就不需要转换了,所以是否大小写的两个情况性能上不会有什么变化,基本的思路就这样了。如果说,你想要很准确的过虑,那就要用到分词了(判断可以人性化),我的方法只能处理比较简单匹配与过虑。实现过程并1没有使用Aho–Corasick算法。
在查找资料的时候还了解到Aho–Corasick算法,它可以帮助我们快速的找出多个子字符串。可以到这里了解算法:http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
5点有约会,先直接上实现代码了(从一老外的例子里小改的),本人测试过我上面的方法和使用Aho–Corasick过虑用的时候差不了多少:
/// /// 表示一个查找结果 /// public struct KeywordSearchResult { private int index; private string keyword; public static readonly KeywordSearchResult Empty = new KeywordSearchResult(-1, string .Empty); public KeywordSearchResult( int index, string keyword) { this .index = index; this .keyword = keyword; } /// /// 位置 /// public int Index { get { return index; } } /// /// 关键词 /// public string Keyword { get { return keyword; } } } /// /// Aho-Corasick算法实现 /// public class KeywordSearch { /// /// 构造节点 /// private class Node { private Dictionary char , Node> transDict; public Node( char c, Node parent) { this .Char = c; this .Parent = parent; this .Transitions = new List this .Results = new List string >(); this .transDict = new Dictionary char , Node>(); } public char Char { get ; private set ; } public Node Parent { get ; private set ; } public Node Failure { get ; set ; } public List { get ; private set ; } public List string > Results { get ; private set ; } public void AddResult( string result) { if (!Results.Contains(result)) { Results.Add(result); } } public void AddTransition(Node node) { this .transDict.Add(node.Char, node); this .Transitions = this .transDict.Values.ToList(); } public Node GetTransition( char c) { Node node; if ( this .transDict.TryGetValue(c, out node)) { return node; } return null ; } public bool ContainsTransition( char c) { return GetTransition(c) != null ; } } private Node root; // 根节点 private string [] keywords; // 所有关键词 public KeywordSearch(IEnumerable string > keywords) { this .keywords = keywords.ToArray(); this .Initialize(); } /// /// 根据关键词来初始化所有节点 /// private void Initialize() { this .root = new Node( ' ' , null ); // 添加模式 foreach ( string k in this .keywords) { Node n = this .root; foreach ( char c in k) { Node temp = null ; foreach (Node tnode in n.Transitions) { if (tnode.Char == c) { temp = tnode; break ; } } if (temp == null ) { temp = new Node(c, n); n.AddTransition(temp); } n = temp; } n.AddResult(k); } // 第一层失败指向根节点 List new List foreach (Node node in this .root.Transitions) { // 失败指向root node.Failure = this .root; foreach (Node trans in node.Transitions) { nodes.Add(trans); } } // 其它节点 BFS while (nodes.Count != 0) { List new List foreach (Node nd in nodes) { Node r = nd.Parent.Failure; char c = nd.Char; while (r != null && !r.ContainsTransition(c)) { r = r.Failure; } if (r == null ) { // 失败指向root nd.Failure = this .root; } else { nd.Failure = r.GetTransition(c); foreach ( string result in nd.Failure.Results) { nd.AddResult(result); } } foreach (Node child in nd.Transitions) { newNodes.Add(child); } } nodes = newNodes; } // 根节点的失败指向自己 this .root.Failure = this .root; } /// /// 找出所有出现过的关键词 /// /// /// public List string text) { List new List Node current = this .root; for ( int index = 0; index < text.length;=""> { Node trans; do { trans = current.GetTransition(text[index]); if (current == this .root) break ; if (trans == null ) { current = current.Failure; } } while (trans == null ); if (trans != null ) { current = trans; } foreach ( string s in current.Results) { list.Add( new KeywordSearchResult(index - s.Length + 1, s)); } } return list; } /// /// 简单地过虑关键词 /// /// /// public string FilterKeywords( string text) { StringBuilder sb = new StringBuilder(); Node current = this .root; for ( int index = 0; index < text.length;=""> { Node trans; do { trans = current.GetTransition(text[index]); if (current == this .root) break ; if (trans == null ) { current = current.Failure; } } while (trans == null ); if (trans != null ) { current = trans; } // 处理字符 if (current.Results.Count > 0) { string first = current.Results[0]; sb.Remove(sb.Length - first.Length + 1, first.Length -1); // 把匹配到的替换为** sb.Append( new string ( '*' , current.Results[0].Length)); } else { sb.Append(text[index]); } } return sb.ToString(); } } |
测试结果:
下载源码:http://files.cnblogs.com/kudy/KeywordSearch.rar
http://www.codeproject.com/Articles/12383/Aho-Corasick-string-matching-in-C
联系客服