一个字符串搜索的Aho-Corasick算法

isiqi

浏览: 16499856 次
性别:
来自: 济南

最近访客更多访客>>

nison

hellohank

wangyy

devcang

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2012-07 ( 335)
2012-06 ( 252)
2012-05 ( 362)
更多存档...

算法 C C++C#

Aho和Corasick对KMP算法(Knuth–Morris–Pratt algorithm)进行了改进，Aho-Corasick算法(Aho-Corasick algorithm)利用构建树，总时间复杂度是O(n)。原理图如下(摘自Aho-Corasick string matching in C#)：

Building of the keyword tree (figure 1 - after the first step, figure 2 - tree with the fail function)

C#版本的实现代码可以从Aho-Corasick string matching in C#得到，也可以点击这里获得该算法的PDF文档。

这是一个应用示例：

预览图

它能将载入的RTF文档中的搜索关键字高亮，检索速度较快，示例没有实现全字匹配，算法代码简要如下：

/* Aho-Corasick text search algorithm implementation * * For more information visit * - http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf */ using System; using System.Collections; namespace EeekSoft.Text { /// <summary> /// Interface containing all methods to be implemented /// by string search algorithm /// </summary> public interface IStringSearchAlgorithm { #region Methods & Properties /// <summary> /// Ignore case of letters /// </summary> bool IgnoreCase { get; set; } /// <summary> /// List of keywords to search for /// </summary> string[] Keywords { get; set; } /// <summary> /// Searches passed text and returns all occurrences of any keyword /// </summary> /// <param name="text">Text to search</param> /// <returns>Array of occurrences</returns> StringSearchResult[] FindAll(string text); /// <summary> /// Searches passed text and returns first occurrence of any keyword /// </summary> /// <param name="text">Text to search</param> /// <returns>First occurrence of any keyword (or StringSearchResult.Empty if text doesn't contain any keyword)</returns> StringSearchResult FindFirst(string text); /// <summary> /// Searches passed text and returns true if text contains any keyword /// </summary> /// <param name="text">Text to search</param> /// <returns>True when text contains any keyword</returns> bool ContainsAny(string text); #endregion } /// <summary> /// Structure containing results of search /// (keyword and position in original text) /// </summary> public struct StringSearchResult { #region Members private int _index; private string _keyword; /// <summary> /// Initialize string search result /// </summary> /// <param name="index">Index in text</param> /// <param name="keyword">Found keyword</param> public StringSearchResult(int index, string keyword) { _index = index; _keyword = keyword; } /// <summary> /// Returns index of found keyword in original text /// </summary> public int Index { get { return _index; } } /// <summary> /// Returns keyword found by this result /// </summary> public string Keyword { get { return _keyword; } } /// <summary> /// Returns empty search result /// </summary> public static StringSearchResult Empty { get { return new StringSearchResult(-1, ""); } } #endregion } /// <summary> /// Class for searching string for one or multiple /// keywords using efficient Aho-Corasick search algorithm /// </summary> public class StringSearch : IStringSearchAlgorithm { #region Objects /// <summary> /// Tree node representing character and its /// transition and failure function /// </summary> class TreeNode { #region Constructor & Methods /// <summary> /// Initialize tree node with specified character /// </summary> /// <param name="parent">Parent node</param> /// <param name="c">Character</param> public TreeNode(TreeNode parent, char c) { _char = c; _parent = parent; _results = new ArrayList(); _resultsAr = new string[] { }; _transitionsAr = new TreeNode[] { }; _transHash = new Hashtable(); } /// <summary> /// Adds pattern ending in this node /// </summary> /// <param name="result">Pattern</param> public void AddResult(string result) { if (_results.Contains(result)) return; _results.Add(result); _resultsAr = (string[])_results.ToArray(typeof(string)); } /// <summary> /// Adds trabsition node /// </summary> /// <param name="node">Node</param> //public void AddTransition(TreeNode node) //{ // AddTransition(node, false); //} /// <summary> /// Adds trabsition node /// </summary> /// <param name="node">Node</param> /// <param name="ignoreCase">Ignore case of letters</param> public void AddTransition(TreeNode node, bool ignoreCase) { if (ignoreCase) _transHash.Add(char.ToLower(node.Char), node); else _transHash.Add(node.Char, node); TreeNode[] ar = new TreeNode[_transHash.Values.Count]; _transHash.Values.CopyTo(ar, 0); _transitionsAr = ar; } /// <summary> /// Returns transition to specified character (if exists) /// </summary> /// <param name="c">Character</param> /// <param name="ignoreCase">Ignore case of letters</param> /// <returns>Returns TreeNode or null</returns> public TreeNode GetTransition(char c, bool ignoreCase) { if (ignoreCase) return (TreeNode)_transHash[char.ToLower(c)]; return (TreeNode)_transHash[c]; } /// <summary> /// Returns true if node contains transition to specified character /// </summary> /// <param name="c">Character</param> /// <param name="ignoreCase">Ignore case of letters</param> /// <returns>True if transition exists</returns> public bool ContainsTransition(char c, bool ignoreCase) { return GetTransition(c, ignoreCase) != null; } #endregion #region Properties private char _char; private TreeNode _parent; private TreeNode _failure; private ArrayList _results; private TreeNode[] _transitionsAr; private string[] _resultsAr; private Hashtable _transHash; /// <summary> /// Character /// </summary> public char Char { get { return _char; } } /// <summary> /// Parent tree node /// </summary> public TreeNode Parent { get { return _parent; } } /// <summary> /// Failure function - descendant node /// </summary> public TreeNode Failure { get { return _failure; } set { _failure = value; } } /// <summary> /// Transition function - list of descendant nodes /// </summary> public TreeNode[] Transitions { get { return _transitionsAr; } } /// <summary> /// Returns list of patterns ending by this letter /// </summary> public string[] Results { get { return _resultsAr; } } #endregion } #endregion #region Local fields /// <summary> /// Root of keyword tree /// </summary> private TreeNode _root; /// <summary> /// Keywords to search for /// </summary> private string[] _keywords; #endregion #region Initialization /// <summary> /// Initialize search algorithm (Build keyword tree) /// </summary> /// <param name="keywords">Keywords to search for</param> /// <param name="ignoreCase">Ignore case of letters (the default is false)</param> public StringSearch(string[] keywords, bool ignoreCase) : this(keywords) { IgnoreCase = ignoreCase; } /// <summary> /// Initialize search algorithm (Build keyword tree) /// </summary> /// <param name="keywords">Keywords to search for</param> public StringSearch(string[] keywords) { Keywords = keywords; } /// <summary> /// Initialize search algorithm with no keywords /// (Use Keywords property) /// </summary> public StringSearch() { } #endregion #region Implementation /// <summary> /// Build tree from specified keywords /// </summary> void BuildTree() { // Build keyword tree and transition function _root = new TreeNode(null, ' '); foreach (string p in _keywords) { // add pattern to tree TreeNode nd = _root; foreach (char c in p) { TreeNode ndNew = null; foreach (TreeNode trans in nd.Transitions) { if (this.IgnoreCase) { if (char.ToLower(trans.Char) == char.ToLower(c)) { ndNew = trans; break; } } else { if (trans.Char == c) { ndNew = trans; break; } } } if (ndNew == null) { ndNew = new TreeNode(nd, c); nd.AddTransition(ndNew, this.IgnoreCase); } nd = ndNew; } nd.AddResult(p); } // Find failure functions ArrayList nodes = new ArrayList(); // level 1 nodes - fail to root node foreach (TreeNode nd in _root.Transitions) { nd.Failure = _root; foreach (TreeNode trans in nd.Transitions) nodes.Add(trans); } // other nodes - using BFS while (nodes.Count != 0) { ArrayList newNodes = new ArrayList(); foreach (TreeNode nd in nodes) { TreeNode r = nd.Parent.Failure; char c = nd.Char; while (r != null && !r.ContainsTransition(c, this.IgnoreCase)) r = r.Failure; if (r == null) nd.Failure = _root; else { nd.Failure = r.GetTransition(c, this.IgnoreCase); foreach (string result in nd.Failure.Results) nd.AddResult(result); } // add child nodes to BFS list foreach (TreeNode child in nd.Transitions) newNodes.Add(child); } nodes = newNodes; } _root.Failure = _root; } #endregion #region Methods & Properties /// <summary> /// Ignore case of letters /// </summary> public bool IgnoreCase { get; set; } /// <summary> /// Keywords to search for (setting this property is slow, because /// it requieres rebuilding of keyword tree) /// </summary> public string[] Keywords { get { return _keywords; } set { _keywords = value; BuildTree(); } } /// <summary> /// Searches passed text and returns all occurrences of any keyword /// </summary> /// <param name="text">Text to search</param> /// <returns>Array of occurrences</returns> public StringSearchResult[] FindAll(string text) { ArrayList ret = new ArrayList(); TreeNode ptr = _root; int index = 0; while (index < text.Length) { TreeNode trans = null; while (trans == null) { trans = ptr.GetTransition(text[index], this.IgnoreCase); if (ptr == _root) break; if (trans == null) ptr = ptr.Failure; } if (trans != null) ptr = trans; foreach (string found in ptr.Results) ret.Add(new StringSearchResult(index - found.Length + 1, found)); index++; } return (StringSearchResult[])ret.ToArray(typeof(StringSearchResult)); } /// <summary> /// Searches passed text and returns first occurrence of any keyword /// </summary> /// <param name="text">Text to search</param> /// <returns>First occurrence of any keyword (or StringSearchResult.Empty if text doesn't contain any keyword)</returns> public StringSearchResult FindFirst(string text) { ArrayList ret = new ArrayList(); TreeNode ptr = _root; int index = 0; while (index < text.Length) { TreeNode trans = null; while (trans == null) { trans = ptr.GetTransition(text[index], this.IgnoreCase); if (ptr == _root) break; if (trans == null) ptr = ptr.Failure; } if (trans != null) ptr = trans; foreach (string found in ptr.Results) return new StringSearchResult(index - found.Length + 1, found); index++; } return StringSearchResult.Empty; } /// <summary> /// Searches passed text and returns true if text contains any keyword /// </summary> /// <param name="text">Text to search</param> /// <returns>True when text contains any keyword</returns> public bool ContainsAny(string text) { TreeNode ptr = _root; int index = 0; while (index < text.Length) { TreeNode trans = null; while (trans == null) { trans = ptr.GetTransition(text[index], this.IgnoreCase); if (ptr == _root) break; if (trans == null) ptr = ptr.Failure; } if (trans != null) ptr = trans; if (ptr.Results.Length > 0) return true; index++; } return false; } #endregion } }

示例下载页面：http://www.uushare.com/user/m2nlight/file/2722093