程序员经验分享-hwhale

一个开源AC算法源码分析

2023-05-16

ps1: 本文不讲AC算法的原理及数学证明， 具体请参考这篇文章：efficient_string_matching_an_aid_to_bibliographic_search.pdf

ps2: 源码主页：multifast

下面先从例子代码分析，如下例子代码：

[cpp]  view plain  copy
  1. #include <stdio.h>  
  2. #include <string.h>  
  3.   
  4. #include "ahocorasick.h"  
  5.   
  6. AC_ALPHABET_t * sample_patterns[] = {  
  7.     "he", "she", "his", "hers"  
  8. };  
  9. #define PATTERN_COUNT (sizeof(sample_patterns)/sizeof(AC_ALPHABET_t *))  
  10.   
  11. AC_ALPHABET_t * input_text1 = {"ushers"};  
  12. AC_ALPHABET_t * input_text2 = {"whatever you are be a good one"};  
  13. AC_ALPHABET_t * input_text3 = {"out of clutter, find simplicity"};  
  14.   
  15. #define BUFFER_ROW 20000  
  16. #define BUFFER_COL 512  
  17.   
  18. int main (int argc, char ** argv)  
  19. {  
  20.     unsigned int i = 0;  
  21.   
  22.     // 1. Define AC variables:  
  23.       
  24.     AC_AUTOMATA_t   *atm;  
  25.     AC_PATTERN_t    tmp_pattern;  
  26.     AC_TEXT_t       tmp_text;  
  27.   
  28.     // 2. Get a new automata  
  29.       
  30.     atm = ac_automata_init ();  
  31.   
  32.     // 3. Add patterns to automata  
  33.       
  34.     for (i=0; i<PATTERN_COUNT; i++)  
  35.     {  
  36.         tmp_pattern.astring = sample_patterns[i];  
  37.         tmp_pattern.rep.number = i+1; // optional  
  38.         tmp_pattern.length = strlen(tmp_pattern.astring);  
  39.         ac_automata_add (atm, &tmp_pattern);  
  40.     }  
  41.   
  42.     // 4. Finalize automata  
  43.       
  44.     ac_automata_finalize (atm);  
  45.     // after you have finished with adding patterns you must finalize the automata  
  46.     // from now you can not add patterns anymore.  
  47.   
  48.     // 4.1. Display automata (if you are interested)  
  49.       
  50.     // ac_automata_display (atm, 'n');  
  51.     // the second argument determines the cast type of the pattern representative.   
  52.     // 'n': as number   
  53.     // 's': as string  
  54.     // because we use the integer part of union (tmp_patt.rep.number) so we used 'n'  
  55.       
  56.     printf ("Searching: \"%s\"\n", input_text1);  
  57.   
  58.     // 5. Set the input text  
  59.       
  60.     tmp_text.astring = input_text1;  
  61.     tmp_text.length = strlen(tmp_text.astring);  
  62.     ac_automata_settext (atm, &tmp_text, 0);  
  63.       
  64.     // 6. find  
  65.       
  66.     AC_MATCH_t * matchp;  
  67.       
  68.     while ((matchp = ac_automata_findnext(atm)))  
  69.     {  
  70.         unsigned int j;  
  71.           
  72.         printf ("@%2ld: ", matchp->position);  
  73.   
  74.         for (j=0; j < matchp->match_num; j++)  
  75.             printf("#%ld (%s), ", matchp->patterns[j].rep.number, matchp->patterns[j].astring);  
  76.             // CAUTION: be careful about using m->matched_patterns[j].astring  
  77.             // if 'astring' has permanent allocation inside your program's  
  78.             // memory area, you can use it. otherwise it will point to  
  79.             // an incorrect memory place.   
  80.           
  81.         printf ("\n");  
  82.     }  
  83.   
  84.     printf ("Searching: \"%s\"\n", input_text2);  
  85.     // you can do more search   
  86.     // just use function pair ac_automata_settext/ac_automata_findnext  
  87.       
  88.     tmp_text.astring = input_text2;  
  89.     tmp_text.length = strlen(tmp_text.astring);  
  90.     ac_automata_settext (atm, &tmp_text, 0);  
  91.       
  92.     while ((matchp = ac_automata_findnext(atm)))  
  93.     {  
  94.         unsigned int j;  
  95.           
  96.         printf ("@%2ld: ", matchp->position);  
  97.   
  98.         for (j=0; j < matchp->match_num; j++)  
  99.             printf("#%ld (%s), ", matchp->patterns[j].rep.number, matchp->patterns[j].astring);  
  100.           
  101.         printf ("\n");  
  102.     }  
  103.   
  104.     printf ("Searching: \"%s\" with \'keep\' enabled\n", input_text3);  
  105.     // and again  
  106.       
  107.     tmp_text.astring = input_text3;  
  108.     tmp_text.length = strlen(tmp_text.astring);  
  109.     ac_automata_settext (atm, &tmp_text, 1);  
  110.     // when the keep option (3rd argument) in set, then the automata  
  111.     // considers that the given text is the next chunk of the previous text.  
  112.     // to understand the difference try it with 0 and 1 and compare the result  
  113.       
  114.     while ((matchp = ac_automata_findnext(atm)))  
  115.     {  
  116.         unsigned int j;  
  117.           
  118.         printf ("@ %2ld: ", matchp->position);  
  119.   
  120.         for (j=0; j < matchp->match_num; j++)  
  121.             printf("#%ld (%s), ", matchp->patterns[j].rep.number, matchp->patterns[j].astring);  
  122.           
  123.         printf ("\n");  
  124.     }  
  125.   
  126.     // 7. Release the automata  
  127.       
  128.     ac_automata_release (atm);  
  129.     // do not forget to release the automata after you have done with it  
  130.   
  131.     return 0;  
  132. }  
哈哈， 是不是一开始被这么多代码吓住了， 没有分析的勇气了？淡定！耐心看一下， 源码的作者在例子代码中给予我们提供了AC源码的使用方式， 并列出了 1， 2， 3， 4， 5， 6， 7的步骤， 我们只需要顺藤摸瓜，即可破析源码！


第一步：

[cpp]  view plain  copy
  1. // 1. Define AC variables:  
  2.   
  3. AC_AUTOMATA_t   *atm;  
  4. AC_PATTERN_t    tmp_pattern;  
  5. AC_TEXT_t       tmp_text;  
这些数据机构宏定义， 我们跟踪到定义的最开始地方：

atm的类型：

[cpp]  view plain  copy
  1. typedef struct AC_AUTOMATA  
  2. {  
  3.     /* The root of the Aho-Corasick trie */  
  4.     struct AC_NODE * root;  
  5.   
  6.     /* maintain all nodes pointers. it will be used to access or release 
  7.     * all nodes. */  
  8.     struct AC_NODE ** all_nodes;  
  9.   
  10.     unsigned int all_nodes_num; /* Number of all nodes in the automata */  
  11.     unsigned int all_nodes_max; /* Current max allocated memory for *all_nodes */  
  12.   
  13.     /* this flag indicates that if automata is finalized by 
  14.      * ac_automata_finalize() or not. 1 means finalized and 0 
  15.      * means not finalized (is open). after finalizing automata you can not 
  16.      * add pattern to automata anymore. */  
  17.     unsigned short automata_open;  
  18.   
  19.     /* It is possible to feed a large input to the automata chunk by chunk to 
  20.      * be searched using ac_automata_search(). in fact by default automata 
  21.      * thinks that all chunks are related unless you do ac_automata_reset(). 
  22.      * followings are variables that keep track of searching state. */  
  23.     struct AC_NODE * current_node; /* Pointer to current node while searching */  
  24.     unsigned long base_position; /* Represents the position of current chunk 
  25.                                   * related to whole input text */  
  26.   
  27.     /* The input text. 
  28.      * used only when it is working in settext/findnext mode */  
  29.     AC_TEXT_t * text;  
  30.       
  31.     /* The lase searched position in the chunk.  
  32.      * used only when it is working in settext/findnext mode */  
  33.     unsigned long position;  
  34.       
  35.     /* Statistic Variables */  
  36.       
  37.     /* Total patterns in the automata */  
  38.     unsigned long total_patterns;  
  39.       
  40. } AC_AUTOMATA_t;  
又是一堆代码！还是淡定！作者给出了详细的解释，只不过是英文而已，耐心读一读。

ac自动机的root字段：类型是AC_NODE， 这个AC_NODE又是什么东东？跟踪一下，如下：

[cpp]  view plain  copy
  1. /* automata node */  
  2. typedef struct AC_NODE  
  3. {  
  4.     int id; /* Node ID : for debugging purpose */  
  5.     short int final; /* 0: no ; 1: yes, it is a final node */  
  6.     struct AC_NODE * failure_node; /* The failure node of this node */  
  7.     unsigned short depth; /* depth: distance between this node and the root */  
  8.   
  9.     /* Matched patterns */  
  10.     AC_PATTERN_t * matched_patterns; /* Array of matched patterns */  
  11.     unsigned short matched_patterns_num; /* Number of matched patterns at this node */  
  12.     unsigned short matched_patterns_max; /* Max capacity of allocated memory for matched_patterns */  
  13.   
  14.     /* Outgoing Edges */  
  15.     struct edge * outgoing; /* Array of outgoing edges */  
  16.     unsigned short outgoing_degree; /* Number of outgoing edges */  
  17.     unsigned short outgoing_max; /* Max capacity of allocated memory for outgoing */  
  18. } AC_NODE_t;  
原来代表一个节点，那么它各个字段都是什么意思呢？如下分析：

id字段：标示节点的， 比如这是第几个节点， 注释也说了， for debugging, 没什么实际作用。

final字段：代表该节点是不是模式串的最后一个节点， 也就说当我匹配到这里的时候，发现该节点的final为1， 那么就代表我们已经发现了一个匹配。

failure_node字段：该节点匹配失败的跳转节点， 如果你不懂什么叫跳转失败节点， 那么下面的分析你就不要看了， 先去看看那边论文吧。微笑

depth字段：AC自动机说穿了就是一个trie树， 既然是树的话， 那么就有深度的概念， 不懂深度？去复习一下tree这种数据结构吧。微笑

outgoing字段：边的数组。什么叫边的数组呢？就是从这个节点出发， 可以有多少种出路。好吧， 其实就是出度， 不懂出度？去复习一下数据结构吧。

outgoing_degree字段：边数组的大小， 也就是该节点的出度， 看变量名字就知道 outgoing degree, 多么直白啊。

outgoing_max字段：表示出度数组能容量的最大数目， 这里使用的是预分配的概念， 不懂吗？复习一下数据结构的动态数组吧。

其他字段不是核心字段， 在这里就不解释了。

附上edge的结构体：

[cpp]  view plain  copy
  1. /* The Edge of the Node */  
  2. struct edge  
  3. {  
  4.     AC_ALPHABET_t alpha; /* Edge alpha */  
  5.     AC_NODE_t * next; /* Target of the edge */  
  6. };  
其中alpha代表边上的字母， 一个边对应一个字母；next代表通过该边能到达哪个节点。


继续分析我们的AC自动机字段：

all_nodes字段：保存所有节点的数组。

all_nodes_num字段：节点数组大小。
all_nodes_max字段：预分配的最大节点数组。

automata_open字段：标示自动还能不能再添加模式串。
current_node字段：自动机搜查的当前节点。

text字段：自动机要查询的目标文本。

其他字段不是核心字段， 在这里就不分析了。

第二步：初始化一个AC自动机，如下代码片段：

[cpp]  view plain  copy
  1. // 2. Get a new automata  
  2.   
  3. atm = ac_automata_init ();  

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: ac_automata_init 
  3.  * Initialize automata; allocate memories and set initial values 
  4.  * PARAMS: 
  5. ******************************************************************************/  
  6. AC_AUTOMATA_t * ac_automata_init ()  
  7. {  
  8.     AC_AUTOMATA_t * thiz = (AC_AUTOMATA_t *)malloc(sizeof(AC_AUTOMATA_t));  
  9.     memset (thiz, 0, sizeof(AC_AUTOMATA_t));  
  10.     thiz->root = node_create ();  
  11.     thiz->all_nodes_max = REALLOC_CHUNK_ALLNODES;  
  12.     thiz->all_nodes = (AC_NODE_t **) malloc (thiz->all_nodes_max*sizeof(AC_NODE_t *));  
  13.     ac_automata_register_nodeptr (thiz, thiz->root);  
  14.     ac_automata_reset (thiz);  
  15.     thiz->total_patterns = 0;  
  16.     thiz->automata_open = 1;  
  17.     return thiz;  
  18. }  
从代码里面我可以清楚的看到，自动机的初始化过程(具体代码过程请参考源码)：

1. 分配自动机内存并初始化；

2. 创建自动机root节点；

3. 预分配自动机保存所有节点的数组;

4. 调用ac_automata_register_nodeptr方法把root节点加到all_nodes数组；

5. 标记自动机可以添加模式串（open = 1）

第三步：向自动机添加模式串，如下代码：

[cpp]  view plain  copy
  1. // 3. Add patterns to automata  
  2.   
  3. for (i=0; i<PATTERN_COUNT; i++)  
  4. {  
  5.     tmp_pattern.astring = sample_patterns[i];  
  6.     tmp_pattern.rep.number = i+1; // optional  
  7.     tmp_pattern.length = strlen(tmp_pattern.astring);  
  8.     ac_automata_add (atm, &tmp_pattern);  
  9. }  

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: ac_automata_add 
  3.  * Adds pattern to the automata. 
  4.  * PARAMS: 
  5.  * AC_AUTOMATA_t * thiz: the pointer to the automata 
  6.  * AC_PATTERN_t * patt: the pointer to added pattern 
  7.  * RETUERN VALUE: AC_ERROR_t 
  8.  * the return value indicates the success or failure of adding action 
  9. ******************************************************************************/  
  10. AC_STATUS_t ac_automata_add (AC_AUTOMATA_t * thiz, AC_PATTERN_t * patt)  
  11. {  
  12.     unsigned int i;  
  13.     AC_NODE_t * n = thiz->root;  
  14.     AC_NODE_t * next;  
  15.     AC_ALPHABET_t alpha;  
  16.   
  17.     if(!thiz->automata_open)  
  18.         return ACERR_AUTOMATA_CLOSED;  
  19.   
  20.     if (!patt->length)  
  21.         return ACERR_ZERO_PATTERN;  
  22.   
  23.     if (patt->length > AC_PATTRN_MAX_LENGTH)  
  24.         return ACERR_LONG_PATTERN;  
  25.   
  26.     for (i=0; i<patt->length; i++)  
  27.     {  
  28.         alpha = patt->astring[i];  
  29.         if ((next = node_find_next(n, alpha)))  
  30.         {  
  31.             n = next;  
  32.             continue;  
  33.         }  
  34.         else  
  35.         {  
  36.             next = node_create_next(n, alpha);  
  37.             next->depth = n->depth + 1;  
  38.             n = next;  
  39.             ac_automata_register_nodeptr(thiz, n);  
  40.         }  
  41.     }  
  42.   
  43.     if(n->final)  
  44.         return ACERR_DUPLICATE_PATTERN;  
  45.   
  46.     n->final = 1;  
  47.     node_register_matchstr(n, patt);  
  48.     thiz->total_patterns++;  
  49.   
  50.     return ACERR_SUCCESS;  
  51. }  

向添加模式串的过程如下：

1. 首先检查各种条件，如自动机是不是打开添加标记的，添加的模式串是不是长度在允许的范围等等；

2. 先从根节点开始查找当前字符是否在自动机节点中，如果在， 以查找到的节点开始继续查找；如果不在调用node_find_next函数创建一个新节点，更新新节点深度， 最后把新节点添加到all_nodes中；

3. 将最有添加的一个节点的final设置为1，表示该节点是该模式串的最后一个节点；

说明：实际上这里创建的就是一个trie树， 如果不懂trie树， 百度一下吧。

第四步（核心）：修正自动机的失败跳转节点，如下代码片段：

[cpp]  view plain  copy
  1. // 4. Finalize automata  
  2.   
  3. ac_automata_finalize (atm);  

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: ac_automata_finalize 
  3.  * Locate the failure node for all nodes and collect all matched pattern for 
  4.  * every node. it also sorts outgoing edges of node, so binary search could be 
  5.  * performed on them. after calling this function the automate literally will 
  6.  * be finalized and you can not add new patterns to the automate. 
  7.  * PARAMS: 
  8.  * AC_AUTOMATA_t * thiz: the pointer to the automata 
  9. ******************************************************************************/  
  10. void ac_automata_finalize (AC_AUTOMATA_t * thiz)  
  11. {  
  12.     unsigned int i;  
  13.     AC_ALPHABET_t alphas[AC_PATTRN_MAX_LENGTH];  
  14.     AC_NODE_t * node;  
  15.   
  16.     ac_automata_traverse_setfailure (thiz, thiz->root, alphas);  
  17.   
  18.     for (i=0; i < thiz->all_nodes_num; i++)  
  19.     {  
  20.         node = thiz->all_nodes[i];  
  21.         ac_automata_union_matchstrs (node);  
  22.         node_sort_edges (node);  
  23.     }  
  24.     thiz->automata_open = 0; /* do not accept patterns any more */  
  25. }  

上面函数主要处理的任务：

1. 设置失败节点跳转；

2. 对所有相同深度的节点排序；

3. 关闭自动机添加标示。

对于ac_automata_traverse_setfailure函数， 如下代码：

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: ac_automata_traverse_setfailure 
  3.  * Traverse all automata nodes using DFS (Depth First Search), meanwhile it set 
  4.  * the failure node for every node it passes through. this function must be 
  5.  * called after adding last pattern to automata. i.e. after calling this you 
  6.  * can not add further pattern to automata. 
  7. ******************************************************************************/  
  8. static void ac_automata_traverse_setfailure  
  9.     (AC_AUTOMATA_t * thiz, AC_NODE_t * node, AC_ALPHABET_t * alphas)  
  10. {  
  11.     unsigned int i;  
  12.     AC_NODE_t * next;  
  13.   
  14.     for (i=0; i < node->outgoing_degree; i++)  
  15.     {  
  16.         alphas[node->depth] = node->outgoing[i].alpha;  
  17.         next = node->outgoing[i].next;  
  18.   
  19.         /* At every node look for its failure node */  
  20.         ac_automata_set_failure (thiz, next, alphas);  
  21.   
  22.         /* Recursively call itself to traverse all nodes */  
  23.         ac_automata_traverse_setfailure (thiz, next, alphas);  
  24.     }  
  25. }  
对给定参数节点node，在该处匹配失败，自动机该跳转到哪里？分析ac_automata_set_failure代码：

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: ac_automata_set_failure 
  3.  * find failure node for the given node. 
  4. ******************************************************************************/  
  5. static void ac_automata_set_failure  
  6.     (AC_AUTOMATA_t * thiz, AC_NODE_t * node, AC_ALPHABET_t * alphas)  
  7. {  
  8.     unsigned int i, j;  
  9.     AC_NODE_t * m;  
  10.   
  11.     for (i=1; i < node->depth; i++)  
  12.     {  
  13.         m = thiz->root;  
  14.         for (j=i; j < node->depth && m; j++)  
  15.             m = node_find_next (m, alphas[j]);  
  16.         if (m)  
  17.         {  
  18.             node->failure_node = m;  
  19.             break;  
  20.         }  
  21.     }  
  22.     if (!node->failure_node)  
  23.         node->failure_node = thiz->root;  
  24. }  

这个代码是核心代码， 写的很简洁， 双重循环， 但是不好理解。首先我们考虑既然匹配到当前位置并且在当前位置失败，那么对于目标串当前位置前面的一部分肯定是匹配过的，

那么这匹配过的部分有可能是其他模式串的开始部分（前缀），如果是的话， 这些匹配过的部分就不需要再匹配了， 直接跳过其他模式串相同的前缀部分， 这样目标串就不用回溯，

这就是AC算法的核心。那么对于该函数，第二次for循环就是在找其他模式串的最大相同开始部分， 也就是最大前缀， 如果找到， 那么就跳出第一重for循环， 函数直接返回；没找到的话， 

从新的已经匹配的部分下一个位置继续寻找， 即第一重for循环保证能找到所有其他模式串的分支，最后如果什么也没找到， 那么就代表没有相同的部分， 只能跳回到root节点，从新的

位置开始继续匹配。

找完之后对所有节点进行排序，如下代码片段：

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: node_sort_edges 
  3.  * sorts edges alphabets. 
  4. ******************************************************************************/  
  5. void node_sort_edges (AC_NODE_t * thiz)  
  6. {  
  7.     qsort ((void *)thiz->outgoing, thiz->outgoing_degree, sizeof(struct edge),  
  8.             node_edge_compare);  
  9. }  

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: node_edge_compare 
  3.  * Comparison function for qsort. see man qsort. 
  4. ******************************************************************************/  
  5. int node_edge_compare (const void * l, const void * r)  
  6. {  
  7.     /* According to man page: 
  8.      * The comparison function must return an integer less than, equal to, or 
  9.      * greater than zero if the first argument is considered to be 
  10.      * respectively less than, equal to, or greater than the second. if  two 
  11.      * members compare as equal, their order in the sorted array is undefined. 
  12.      * 
  13.      * NOTE: Because edge alphabets are unique in every node we ignore 
  14.      * equivalence case. 
  15.     **/  
  16.     if ( ((struct edge *)l)->alpha >= ((struct edge *)r)->alpha )  
  17.         return 1;  
  18.     else  
  19.         return -1;  
  20. }  
至于为什么要排序， 分析到后面就明白了， 这里先不讲。

第五步：设置目标串（待匹配串）

[cpp]  view plain  copy
  1. // 5. Set the input text  
  2.   
  3. tmp_text.astring = input_text1;  
  4. tmp_text.length = strlen(tmp_text.astring);  
  5. ac_automata_settext (atm, &tmp_text, 0);  

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: ac_automata_settext 
  3. ******************************************************************************/  
  4. void ac_automata_settext (AC_AUTOMATA_t * thiz, AC_TEXT_t * text, int keep)  
  5. {  
  6.     thiz->text = text;  
  7.     if (!keep)  
  8.         ac_automata_reset(thiz);  
  9.     thiz->position = 0;  
  10. }  

第六步：开始匹配，如下代码，

[cpp]  view plain  copy
  1. // 6. find  
  2.   
  3. AC_MATCH_t * matchp;  
  4.   
  5. while ((matchp = ac_automata_findnext(atm)))  
  6. {  
  7.     unsigned int j;  
  8.       
  9.     printf ("@%2ld: ", matchp->position);  
  10.   
  11.     for (j=0; j < matchp->match_num; j++)  
  12.         printf("#%ld (%s), ", matchp->patterns[j].rep.number, matchp->patterns[j].astring);  
  13.         // CAUTION: be careful about using m->matched_patterns[j].astring  
  14.         // if 'astring' has permanent allocation inside your program's  
  15.         // memory area, you can use it. otherwise it will point to  
  16.         // an incorrect memory place.   
  17.   
  18.     printf ("\n");  
  19. }  

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: ac_automata_findnext 
  3. ******************************************************************************/  
  4. AC_MATCH_t * ac_automata_findnext (AC_AUTOMATA_t * thiz)  
  5. {  
  6.     unsigned long position;  
  7.     AC_NODE_t * current;  
  8.     AC_NODE_t * next;  
  9.     static AC_MATCH_t match;  
  10.       
  11.     if (thiz->automata_open)  
  12.         return 0;  
  13.       
  14.     if (!thiz->text)  
  15.         return 0;  
  16.       
  17.     position = thiz->position;  
  18.     current = thiz->current_node;  
  19.     match.match_num = 0;  
  20.   
  21.     /* This is the main search loop. 
  22.      * it must be as lightweight as possible. */  
  23.     while (position < thiz->text->length)  
  24.     {  
  25.         if (!(next = node_findbs_next(current, thiz->text->astring[position])))  
  26.         {  
  27.             if (current->failure_node /* we are not in the root node */)  
  28.                 current = current->failure_node;  
  29.             else  
  30.                 position++;  
  31.         }  
  32.         else  
  33.         {  
  34.             current = next;  
  35.             position++;  
  36.         }  
  37.   
  38.         if (current->final && next)  
  39.         /* We check 'next' to find out if we came here after a alphabet 
  40.          * transition or due to a fail. in second case we should not report 
  41.          * matching because it was reported in previous node */  
  42.         {  
  43.             match.position = position + thiz->base_position;  
  44.             match.match_num = current->matched_patterns_num;  
  45.             match.patterns = current->matched_patterns;  
  46.             break;  
  47.         }  
  48.     }  
  49.   
  50.     /* save status variables */  
  51.     thiz->current_node = current;  
  52.     thiz->position = position;  
  53.       
  54.     if (!match.match_num)  
  55.         /* if we came here due to reaching to the end of input text 
  56.          * not a loop break 
  57.          */  
  58.         thiz->base_position += position;  
  59.       
  60.     return match.match_num?&match:0;  
  61. }  

分析ac_automata_findnext：

1. 调用node_findbs_next函数， 查找下一个匹配位置；

2. 如果没找到跳转到failure_node继续查找；

3. 检查是不是final节点， 如果是的话， 匹配成功。

分析node_findbs_next函数：

[cpp]  view plain  copy
  1. /****************************************************************************** 
  2.  * FUNCTION: node_findbs_next 
  3.  * Find out the next node for a given Alpha. this function is used after the 
  4.  * pre-processing stage in which we sort edges. so it uses Binary Search. 
  5. ******************************************************************************/  
  6. AC_NODE_t * node_findbs_next (AC_NODE_t * thiz, AC_ALPHABET_t alpha)  
  7. {  
  8.     int min, max, mid;  
  9.     AC_ALPHABET_t amid;  
  10.   
  11.     min = 0;  
  12.     max = thiz->outgoing_degree - 1;  
  13.   
  14.     while (min <= max)  
  15.     {  
  16.         mid = (min+max) >> 1;  
  17.         amid = thiz->outgoing[mid].alpha;  
  18.         if (alpha > amid)  
  19.             min = mid + 1;  
  20.         else if (alpha < amid)  
  21.             max = mid - 1;  
  22.         else  
  23.             return (thiz->outgoing[mid].next);  
  24.     }  
  25.     return NULL;  
  26. }  

这里对每一层使用的是二分查找， 现在明白了上面为什么要排序了吧。都是为了加速后面的查找。

第七步：释放内存。

[cpp]  view plain  copy
  1. // 7. Release the automata  
  2.   
  3. ac_automata_release (atm);  

至此AC自动机源码分析完毕， 其中各个细节实现需要亲自越多源码， 细细揣摩， 方可领悟！

附上第一个例子的程序数据结构图， 如下：

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

一个开源AC算法源码分析 的相关文章

随机推荐

  • SQLServer触发器创建、删除、修改、查看...适用于级联删除

    一 触发器是一种特殊的存储过程 它不能被显式地调用 而是在往表中插入记录 更新记录或者删除记录时被自动地激活 所以触发器可以用来实现对表实施复杂的完整性约束 二 SQL Server为每个触发器都创建了两个专用表 Inserted表和Del

  • 工薪族巧理财之定期存款中整存整取、零存整取、存本取息之间的微妙区别

    银行的官方术语先给大家普及一下 xff1a 定期存款是在存款时约定存储时间 一次或按期分次 在约定存期 存入本金 xff0c 整笔或分期平均支取本金利息的一种储蓄 按存取方式定期存款分为整存整取定期存款 零存整取定期存款 存本取息定期存款

  • no module named win32com.client错误解决

    无论什么时候 xff0c 你在运行的时候发现有importError no module named win32com client这个提示 你都可以这么解决 xff1a 请下载http sourceforge net projects p

  • java.util.concurrent同步框架（AQS论文中文翻译）

    java util concurrent同步框架 摘要目录和主题描述一般条款关键字1 介绍 xff1a 需求设计实现4 使用方式5 性能6 结论7 致谢 Doug Lea SUNY Oswego Oswego NY 13126 dl 64

  • POJ2287 田忌赛马---贪心算法

    田忌赛马 题目详见http poj org problem id 61 2287 田忌赛马大家都听过 xff0c 可是如果不是上中下三等马 xff0c 而是很多匹马 xff0c 优劣有很多种分类 xff0c 就不仅仅是321的问题了 这个很

  • 贪心算法详解

    之前讲过动态规划DP xff0c 现在来说说贪心 贪心算法在解决问题的策略上目光短浅 xff0c 只根据当前已有的信息就做出选择 xff0c 而且一旦做出了选择 xff0c 不管将来有什么结果 xff0c 这个选择都不会改变 也就是说贪心对

  • 搜索智能提示suggestion,附近点搜索

    第三十六 三十七章 搜索智能提示suggestion xff0c 附近地点搜索 作者 xff1a July 致谢 xff1a caopengcs 胡果果 时间 xff1a 二零一三年九月七日 题记 写博的近三年 xff0c 整理了太多太多的

  • 多重继承及虚继承中对象内存的分布

    多重继承及虚继承中对象内存的分布 这篇文章主要讲解G 43 43 编译器中虚继承的对象内存分布问题 xff0c 从中也引出了dynamic cast和static cast本质区别 虚函数表的格式等一些大部分C 43 43 程序员都似是而非

  • Linux日志服务器配置

    配置日志服务器 环境 xff1a tibet xff1a 10 11 3 57 gaplinux xff08 日志服务器 xff09 xff1a 10 11 3 3 修改tibet上的 etc hosts xff0c 增加如下代码 xff1

  • 【Google】25匹马的角逐

    问题是这样的 xff1a 一共有25匹马 xff0c 有一个赛场 xff0c 赛场有5个赛道 xff0c 就是说最多同时可以有5匹马一起比赛 假设每匹马都跑的很稳定 xff0c 不用任何其他工具 xff0c 只通过马与马之间的比赛 xff0

  • HDOJ 1058 Humble Numbers解题报告【DP】

    Humble Numbers 题目详见http acm hdu edu cn showproblem php pid 61 1058 开始拿到这个题目的时候还纠结了半天 xff0c 英语很差的话这个题是不可能AC的 而我就是其中之一 Hum

  • 背包问题详解

    背包问题 背包问题 Knapsack problem 是一种组合优化的NP完全问题 问题可以描述为 xff1a 给定一组物品 xff0c 每种物品都有自己的体积和价值 xff0c 在限定的总体积内 xff0c 我们如何选择 xff0c 才能

  • 楼教主男人必解八题之 Coins 解题报告

    楼教主男人必解八题之 Coins 解题报告 题目详见http acm hdu edu cn showproblem php pid 61 2844 这个题目和POJ1742是一个题目 xff0c 也是楼教主的男人八题之一 说的是给出N种硬币

  • 如何证明程序的正确性？

    什么样的程序才是正确的 xff1f 如何来保证程序是正确的 xff1f 测试 xff1f NO xff01 采用测试方法确实可以发现程序中的错误 xff0c 但却不能保证和证明程序中没有错误 xff01 先来看一些概念 xff0c 有关 程

  • 平摊分析

    平摊分析 我们经常在处理数据结构的时间复杂度的时候 xff0c 大多数操作代价很低 xff0c 可是由于某些个别操作的代价较高 xff0c 导致最后求得时间复杂度的上界不是那么的紧凑 在平摊分析中 xff0c 执行一系列数据结构操作所需要的

  • intel realsense t265+rtabmap实现地形扫描（效果欠佳）

    1 intel realsense t265驱动安装 https blog csdn net crp997576280 article details 109544456 2 Rtabmap 安装 https blog csdn net z

  • Windows10下RTABMAP+T265实现三维建图

    安装Rtabmap xff1a Installation introlab rtabmap Wiki github com 文件为RTABMap 0 20 16 win64 cuda11 1 exe 安装intel realsense t2

  • 树莓派3B+（以及老版本）内网穿透 frp 后外网ssh或者vrc server连接

    1 服务器配置 xff0c 服务器选择Debian 或者 CentOS 开一个服务器 然后用ssh连上 xff0c ssh可以用本地xshell或putty连接 也可以用网页版ssh连接 先进入管理员模式 xff0c 免得后面一直sudo

  • 在雪豹10.6.2（Mac OS X）上安装Oracle10g

    1 Install preparation 基本环境 xff1a Snow Leopard10 6 2 xff0c Oracle10 2 0 4 打开Mac的终端 xff0c 执行 xff1a sudo i 创建oinstall组和orac

  • 一个开源AC算法源码分析

    ps1 本文不讲AC算法的原理及数学证明 xff0c 具体请参考这篇文章 xff1a efficient string matching an aid to bibliographic search pdf ps2 源码主页 xff1a m

热门标签