AC算法实现，测试通过，速度确实快（一）
时间：2010-07-06 来源：余竹
Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。
Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。
该算法的基本思想是这样的：
在预处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数failure和输出函数output，由此构造了一个树型有限自动机。
在搜索查找阶段，则通过这三个函数的交叉使用扫描文本，定位出关键字在文本中的所有出现位置。
此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关。
树型有限自动机包含一组状态，每个状态用一个数字代表。状态机读入文本串y中的字符，然后通过产生状态转移或者偶尔发送输出的方式来处理文本。树型有限自动机的行为通过三个函数来指示：转向函数g，失效函数f和输出函数output。
主要文件三个acAlgorithm.cpp,ac.h, ac.cpp其他的都是系统生成的，文件stdafx.h中有可能需要增加几个头文件。
模式集文件是一行一个模式的格式，支持中文
///////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////
//文件名 acAlgorithm.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
int main(int argc, char* argv[])
{
char out[MAX_LENGTH_FILE_NAME] = {'\0'};
char ptn[MAX_LENGTH_FILE_NAME] = {'\0'};
char mch[MAX_LENGTH_FILE_NAME] = {'\0'};
ifstream fptn,fmch;
ofstream fout;
struct AC_State root;
char a_model[MAX_LENGTH_PATTERN]={'\0'};
char isContinue;
//参数分析
switch(argc)
{
case 2:
memcpy(mch, argv[1],strlen(argv[1]));
memcpy(ptn, "pattern",strlen("pattern"));
memcpy(out, "output",strlen("output"));
break;
case 3:
memcpy(mch, argv[1],strlen(argv[1]));
memcpy(ptn, argv[2],strlen(argv[2]));
memcpy(out, "output",strlen("output"));
break;
case 4:
memcpy(mch, argv[1],strlen(argv[1]));
memcpy(ptn, argv[2],strlen(argv[2]));
memcpy(out, argv[3],strlen(argv[3]));
break;
default:
cout<<"Usage:acAlgorithm.exe [匹配文本[模式集[输出文件]]]"<<endl;
exit(0);
}
/*
memcpy(mch, "test",strlen("test"));
memcpy(ptn, "pattern",strlen("pattern"));
memcpy(out, "output",strlen("output"));
*/
cout<<"待匹配文本文件:"<<mch<<"\n模式集文件:"<<ptn<<"\n匹配结果输出文件:"<<out<<endl;
//初始化状态树
init(&root);
fptn.open(ptn);
|
if(fptn.fail())
{
cout<<"不能打开文件:"<<ptn<<endl;
exit(0);
}
//将模式串一个个加入到状态树中，并得出部分输出节点
while(fptn.getline(a_model, MAX_LENGTH_PATTERN))
{
if(strlen(a_model)>MAX_LENGTH_PATTERN)
{
cout<<"某个模式长度超过最大长度\n"<<endl;
exit(0);
}
addPattern(&root, a_model, strlen(a_model));
memset(a_model, 0, MAX_LENGTH_PATTERN);
}
fptn.close();
//得到每个状态节点的失效函数，并得到全部的输出节点
getFailFunc(&root);
L:
fmch.clear();
fmch.open(mch);
if(fmch.fail())
{
cout<<"不能打开文件:"<<mch<<endl;
exit(0);
}
fout.clear();
fout.open(out);
if(fout.fail())
{
cout<<"不能打开文件:"<<out<<endl;
exit(0);
}
//执行搜索
acSearch(&root, &fmch, &fout);
fmch.close();
fout.close();
cout<<"匹配结果已经存入文件，是否继续使用此模式集匹配？是(y or Y),否(其他)"<<endl;
cin>>isContinue;
if(isContinue == 'y' || isContinue == 'Y')
{
cout<<"输入待匹配文件以及结果输出文件，并用空格隔开"<<endl;
memset(mch, 0, MAX_LENGTH_FILE_NAME);
memset(out, 0, MAX_LENGTH_FILE_NAME);
cin>>mch>>out;
goto L;
}
cout<<"清理中。。。"<<endl;
acFree(&root);
return 0;
}
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//
//文件名ac.h
//
#pragma once
#include <iostream>
#include <queue>
#include <fstream>
#include <stdlib.h>
#include <string.h>
#define BUFSIZE 4096 //读文件缓冲区大小
#define MAX_NUM_OF_PATTERN 32 //模式的最大数量
#define MAX_NUM_OF_GOTO 256 //转向指针数量的最大值
#define MAX_LENGTH_FILE_NAME 128 //文件名最大长度
#define MAX_LENGTH_PATTERN 128 //模式的最大长度
using namespace std;
typedef struct AC_State
{
int state_no; //状态的编号，没有实际的用处，可以用来模拟老师课件上的输出
int depth; //深度
int is_final_state; //判断该节点是否为楼阁终态
int output[MAX_NUM_OF_PATTERN]; //输出函数值，对应模式，可能有多个
int num_of_goto; //有多少个节点
string str; //存储从树根到该节点的字符序列，便于调试
struct AC_State *Goto[MAX_NUM_OF_GOTO]; //转向指针
struct AC_State *failure; //失效指针
} AC_State;
void init(struct AC_State *state); //初始化
int addPattern(struct AC_State *root, const char* pattern, int length); //将一个模式加入并构建转向函数
void getFailFunc(struct AC_State *root); //求失效指针
int acSearch(struct AC_State *root, ifstream *_if, ofstream *out); //执行匹配
void finalAssign(int *t, int *s);
void acFree(struct AC_State *root);
相关阅读 更多 +
