在本人昨晚发的强大灵活的脏字过虑：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
５点有约会，先直接上实现代码了（从一老外的例子里小改的），本人测试过我上面的方法和使用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 Dictionarychar, Node> transDict; public Node(char c, Node parent) { this.Char = c; this.Parent = parent; this.Transitions = new List this.Results = new Liststring>(); this.transDict = new Dictionarychar, Node>(); } public char Char { get; private set; } public Node Parent { get; private set; } public Node Failure { get; set; } public List { get; private set; } public Liststring> 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(IEnumerablestring> 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); } // 第一层失败指向根节点 Listnew 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) { Listnew 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 Liststring text) { Listnew 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
联系客服
