序列比對（26）精準匹配之KMP演算法、Trie樹以及AC自動機

2019 年 10 月 8 日
筆記

前文已經介紹過KMP演算法和Trie樹，本文將在此基礎上介紹AC自動機。

之前的序列比對文章大都在利用動態規劃演算法解決字元串的非精準匹配（允許錯配、插入和缺失），比如全局比對和局部比對問題。當然，後來我們還介紹了模序發現和中間字元串問題，並初次學習了如何用分支定界法解決這一類問題。

既然有非精準匹配問題，就有精準匹配問題。所謂精準匹配，就是兩個字元串在比對時，不允許錯配、插入和缺失。其實，筆者之前已經有過介紹：

KMP演算法

《演算法（四）（轉載）KMP演算法》一文介紹了KMP演算法，該演算法常用來解決如何在一個長字元串（模板串）中尋找一個短字元串（模式串）的問題。其特點就是要預先對模式串進行處理，對其構建一個next數組，該數組中存放著模式串每一個位置所對應的跳轉指針，這樣做的效果是模板串的指針不用回溯，一直在遞增，從而增加效率。

KMP演算法的完整程式碼：

#include <stdio.h>  #include <stdlib.h>  #include <string.h>  #define MAXLEN 1000    void getNext(const char *pat, int *next, const int n) {  /* assume n >= 2 */      int i, j;      for (next[0] = -1, next[1] = 0, i = 1, j = 0; i < n - 1;) {          while (j != -1 && pat[i] != pat[j])              j = next[j];          next[++i] = ++j;      }  }    int KMP(const char *temp, const int m, const char *pat, const int n) {      int i, j;      int *next = (int*) malloc(sizeof(int) * n);      getNext(pat, next, n);      for (i = 0, j = 0; i < m && j < n;) {          if (j == -1 || temp[i] == pat[j]) {              i++;              j++;          } else {              j = next[j];          }      }      free(next);      if (j < n)          return -1;      return i - j;  }    int main(void) {      char t[MAXLEN], p[MAXLEN];      int index;      printf("the temp str: ");      scanf("%s", t);      printf("the pattern str: ");      scanf("%s", p);      if ((index = KMP(t, strlen(t), p, strlen(p))) == -1)          printf("Not found!n");      else          printf("Index is %d.n", index);      return 0;  }

其效果如下：

Trie樹（字典樹）

《演算法（五）字典樹演算法快速查找單詞前綴》一文介紹了Trie樹，該演算法常用來解決如何在多個模板串中尋找一個模式串的問題。其特點就是將多個模板串裝填進一個樹結構中，雖然使用了較多的空間，但是查找效率得到了提升。

Trie樹的完整程式碼：

#include <stdio.h>  #include <stdlib.h>  #include <string.h>  #define N 26  #define MAXLEN 1000    struct Node {      struct Node *a[N];      int is_end;  };  typedef struct Node *tnode;    tnode init() {      tnode p;      int i;      if ((p = (tnode) malloc(sizeof(struct Node))) == NULL) {          fputs("Error: out of space!n", stderr);          exit(1);      }      for (i = 0; i < N; i++)          p->a[i] = NULL;      p->is_end = 0;      return p;  }    void delete(tnode p) {      int i;      for (i = 0; i < N; i++)          if (p->a[i] != NULL)              delete(p->a[i]);      free(p);  }    void insert(const char *s, tnode p) {      int i;      while (*s != 'n' && *s != '') {          i = *s - 'a';          if (p->a[i] == NULL) {              p->a[i] = init();          }          p = p->a[i];          s++;      }      p->is_end = 1;  }    int find(const char *s, tnode p) {      int i;      while (*s != 'n' && *s != '') {          i = *s - 'a';          if (p->a[i] == NULL)              return 0;          p = p->a[i];          s++;      }      if (p->is_end)          return 1;      return 0;  }    void strLower(char *s) {      while (*s != '') {          if (*s >= 'A' && *s <= 'Z') {              *s += 32;          }          s++;      }  }    int main(int argc, char *argv[]) {      FILE *fpp, *fpw;      char buf[MAXLEN];      tnode root = init();      if (argc < 3) {          fputs("Usage: trie.exe <pattern.txt> <words.txt>n", stderr);          exit(2);      }      if ((fpw = fopen(argv[2], "r")) == NULL) {          fprintf(stderr, "Error: cannot open %sn", argv[2]);          exit(4);      }      while (fgets(buf, MAXLEN, fpw) != NULL) {          strLower(buf);          insert(buf, root);      }      if (! feof(fpw)) {          fprintf(stderr, "Error: error while reading %sn", argv[2]);          exit(8);      }      fclose(fpw);      if ((fpp = fopen(argv[1], "r")) == NULL) {          fprintf(stderr, "Error: cannot open %sn", argv[1]);          exit(4);      }      while (fgets(buf, MAXLEN, fpp) != NULL) {          strLower(buf);          if (find(buf, root))              printf("%s", buf);      }      if (! feof(fpp)) {          fprintf(stderr, "Error: error while reading %sn", argv[1]);          exit(8);      }      fclose(fpp);      delete(root);  }

其效果如下：

其中，pat.txt文件內容（裡面是多個模式串）如下：

how are you

words.txt文件內容（裡面是多個模板串）如下：

lily we are friends

AC自動機

本文要介紹的AC自動機演算法，是用來解決如何有效地在一個模板串中查找多個模式串的問題。該演算法是建立在KMP演算法和Trie樹基礎上的。其特點是：

預先將多個模式串裝填進Trie樹中。
在進行查找（匹配）之前，對Trie樹中的每個有效節點構建fail指針，該指針的作用類似KMP演算法中next數組的作用：如果到該節點時匹配失敗，就可以利用fail指針跳轉到下一個可利用節點繼續進行匹配，從而避免了模板串的回溯而提升查找效率。

如同KMP演算法的next數組充分利用了模式串的內部資訊，AC自動機中的fail指針也是充分利用了多個模式串的內部資訊，每一次跳轉都是跳到「最大可利用後綴子字元串」的節點。

筆者在學習該演算法時，主要參考了這一篇文章（https://www.jianshu.com/p/641142c6d477），看裡面的圖非常有助於理解AC自動機原理。

關於AC自動機的實現有幾點說明：

在對Trie樹里所有有效節點構建fail指針的過程中，採用了BFS（廣度優先搜索）的策略，具體的實現是利用了隊列這種數據結構。採用BFS的原因是Trie樹中某一層節點的fail指針指向的節點一定是來自於上面的層（可能是上面第一層，也有可能是上面第二層等等，甚至是根節點）。
無論是Trie樹還是隊列，都是利用一種鏈表實現的，不得不感嘆，對鏈表進行操作真是很容易出錯，經常要填坑。

AC自動機的完整程式碼如下：

#include <stdio.h>  #include <stdlib.h>  #define ALPHA_NUM 26  #define QUEUE_EMPTY NULL  #define BUFSIZE 64  #define MAXTEMP 10000    /* Data structure for trie */  struct TNode {      struct TNode *a[ALPHA_NUM];      struct TNode *fail;      struct TNode *parent;      int c;      int is_end;  };  typedef struct TNode *tnode;    tnode initTrie(int c, tnode parent) {      tnode p;      int i;      if ((p = (tnode) malloc(sizeof(struct TNode))) == NULL) {          fputs("Error: out of space!n", stderr);          exit(1);      }      for (i = 0; i < ALPHA_NUM; i++)          p->a[i] = NULL;      p->fail = NULL;      p->parent = parent;      p->c = c;      p->is_end = 0;      return p;  }    void deleteTrie(tnode p) {      int i;      for (i = 0; i < ALPHA_NUM; i++)          if (p->a[i] != NULL)              deleteTrie(p->a[i]);      free(p);  }    void insertTrie(const char *s, tnode p) {      int i;      while (*s != 'n' && *s != '') {          i = *s - 'a';          if (p->a[i] == NULL) {              p->a[i] = initTrie(*s, p);          }          p = p->a[i];          s++;      }      p->is_end = 1;  }    /*  void printTrie(tnode p) {      int i;      printf("%c ", p->c);      for (i = 0; i < ALPHA_NUM; i++) {          if (p->a[i] != NULL)              printTrie(p->a[i]);      }  }  */    void backtrack(char *s, const int n, tnode p) {      int i, j, c;      for (i = 0; i < n - 1 && p != NULL && p->parent != NULL; i++) {          s[i] = p->c;          p = p->parent;      }      if (i >= n - 1) {          fputs("Error: pattern word is too long!n", stderr);          exit(2);      }      for (j = 0; j < i / 2; j++) {          c = s[j];          s[j] = s[i - 1 - j];          s[i - 1 - j] = c;      }      s[i] = '';  }    /* Data structure for queue */  typedef tnode QNodeType;    struct QNode {      QNodeType value;      struct QNode *next;  };  typedef struct QNode *qnode;    qnode initQueue(QNodeType v) {      qnode p;      if ((p = (qnode) malloc(sizeof(struct QNode))) == NULL) {          fputs("Error: out of space!n", stderr);          exit(1);      }      p->value = v;      p->next = NULL;      return p;  }    void addQueue(QNodeType v, qnode head) {      qnode p;      for (p = head; p->next != NULL; p = p->next)          ;      p->next = initQueue(v);  }    int isEmptyQueue(qnode head) {      return head->next == NULL ? 1 : 0;  }    QNodeType popQueue(qnode head) {      qnode p;      QNodeType q;      if (isEmptyQueue(head))          return QUEUE_EMPTY;      else {          p = head->next;          head->next = p->next;          q = p->value;          free(p);          return q;      }  }    void destroyQueue(qnode head) {      while (popQueue(head) != QUEUE_EMPTY)          ;      free(head);  }    void strLower(char *s) {      while (*s != '') {          if (*s >= 'A' && *s <= 'Z') {              *s += 32;          }          s++;      }  }    void getFailPointer(tnode root) {      int i;      qnode head = initQueue(NULL);      tnode this, tmp;      addQueue(root, head);      while (! isEmptyQueue(head)) {          this = popQueue(head);          for (i = 0; i < ALPHA_NUM; i++) {              if (this->a[i] != NULL) {                  addQueue(this->a[i], head);                  tmp = this;                  while (tmp->fail != NULL) {                      if (tmp->fail->a[i] != NULL) {                          this->a[i]->fail = tmp->fail->a[i];                          break;                      } else {                          tmp = tmp->fail;                      }                  }                  if (tmp->fail == NULL)                      this->a[i]->fail = root;              }          }      }      destroyQueue(head);  }    void ACauto(char *buf, const int n, char *temp, tnode root) {      char *s = temp;      tnode p, tmp;      int i;      for (p = root; *s != ''; s++) {          i = *s - 'a';          while (p->a[i] == NULL && p->fail != NULL)  /* 這裡必須先判斷p->a[i]，否則有可能錯過root->a[i] != NULL的情況 */              p = p->fail;          if ((p = p->a[i]) == NULL)              p = root;          for (tmp = p; tmp->fail != NULL; tmp = tmp->fail)              if (tmp->is_end) {                  backtrack(buf, BUFSIZE, tmp);                  printf("%sn", buf);              }      }  }    int main(int argc, char *argv[]) {      FILE *fpp, *fpt;      char buf[BUFSIZE];      char temp[MAXTEMP];      tnode root = initTrie('', NULL);      int n;      if (argc < 3) {          fputs("Usage: trie.exe <pattern.txt> <template.txt>n", stderr);          exit(2);      }      if ((fpp = fopen(argv[1], "r")) == NULL) {          fprintf(stderr, "Error: cannot open %sn", argv[1]);          exit(4);      }      while (fgets(buf, BUFSIZE, fpp) != NULL) {          strLower(buf);          insertTrie(buf, root);      }      if (! feof(fpp)) {          fprintf(stderr, "Error: error while reading %sn", argv[1]);          exit(8);      }      fclose(fpp);      if ((fpt = fopen(argv[2], "r")) == NULL) {          fprintf(stderr, "Error: cannot open %sn", argv[2]);          exit(4);      }      n = fread(temp, 1, MAXTEMP - 1, fpt);      temp[n] = '';      strLower(temp);      if (! feof(fpt)) {          fprintf(stderr, "Error: error while reading %sn", argv[2]);          exit(8);      }      fclose(fpt);      getFailPointer(root);      ACauto(buf, BUFSIZE, temp, root);      deleteTrie(root);  }

其效果如下：

其中pat.txt文件內容（裡面是多個模式串）如下：

how are you

temp.txt文件內容（裡面是模板串）如下：

iloveautumnhowaboutyou

至此，本文就全部結束了，謝謝大家看此長文。如果有發現錯誤或者有任何建議和意見，歡迎指正！