多模式匹配

技术宅 rainforest 8年前 (2012-03-25) 4076次浏览 2个评论

最近工作上要用到多模式匹配的算法,所以就搜索一些资料,写篇博客分享一下。今天开始用word来写博客了,也试试效果。

之前在百度实习的时候,也用到过多模式匹配,但是别的部门提供的一个公共库dictmatch。我搜了看到百度互联网技术官方博客上面还有几篇介绍dictmatch的几篇博客,链接如下:

但是这个对于我来说,略显有点复杂了,我也不想去搞一个这么大的工程。我找了一圈,我们的公共库里面也没有提供这样的算法。另外,我依稀记得这个东西因为是用树的结构来存的,还是比较费内存的。我记得,我当时将这个东西改成hash_map这样的东东来实现的,而且效率也完全可以达到要求的。

记得当时是把模式串(要查找的串)放到hashmap中,然后把被查询串切词,切完词后进行相邻组合然后到hash_map中查询是否存在,对于比较短的被查询串来说这个方法还是比较快的,但是对于长的查询串来说可能就不行了,复杂度是O(n^2),其中n为被查询串切词后的长度。

目前我的做法是对于任意一个模式串,用字符串查找算法来判定是否包含该模式串,复杂度为O(m+n)*k(m表示模式串的长度,n为查询串的长度,k为模式串的数量),这种复杂度已经不能满足我的需求了。

我去网上找了找,多模式匹配算法大概有以下几种:

clip_image002

当然最近几年也会有一些改进的算法。网上找了以下最好一种算法的源码,感觉挺复杂的,要学习这个方法也很费劲。找到了一个比较好的实现,代码如下:

/***************************************************
*	Original Filename: 		wm.h
*	Created/Modified: 		Andy_guo								
*	Date:					2009/11/22			
*	Main Purpose:			WM算法
*	Comments:	
****************************************************/
#pragma once

//哈希表大小
#define HASHTABLESIZE (256*256)
//哈希表类型
#define HASH_TYPE short
//移动表大小
#define SHIFTTABLESIZE (256*256)
//模式串的最大长度MAXN - 1
#define MAXPATTERN 10001	
//单词最大长度为MAXM - 1
#define WORDMAX 51	

#include "winsock2.h"
#include "atlstr.h"

//=================================//
//模式结构体
//=================================//
typedef struct WMPATTERNSTRUCT
{
	char*				psPat;	//模式内容
	unsigned			psLen;	//模式的长度
	WMPATTERNSTRUCT*	next;	//下一个模式指针
}WMPATTERNSTRUCT;

//=================================//
//已经匹配模式结构体
//=================================//
typedef struct matchedPattern
{
	char	matchedPtn[20];	//模式内容
	int		matchedSum;		//模式的长度

}MATCHEDPATTERN;

//=================================//
//wm综合结构体
//=================================//
typedef struct WMSTRUCT
{
	WMPATTERNSTRUCT*	plist;				//模式指针链表
	WMPATTERNSTRUCT*	msPatArray;			//模式数组,用来存放模式内容
	unsigned short*		msNumArray;			//模式数组中有相同哈希值的个数
	int					msNumPatterns;		//模式数量
	unsigned			msNumHashEntries;	//哈希表条目的数量
	HASH_TYPE*			msHash;				//last 2 characters pattern hash table
	unsigned char*		msShift;			//bad word shift table
	HASH_TYPE*			msPrefix;			//first 2 characters prefix table
	int					msSmallest;			//模式的最小长度
}WMSTRUCT;

/****************************************************/
class CWM
{
public:
	CWM(void);

	~CWM(void);

	//WM综合结构体
	WMSTRUCT* m_pWmStruct;

	//已经匹配模式结构体
	MATCHEDPATTERN* m_pMatchedPtn;

	//获取指定文件名路径
	/*void GetFilePath(const char* strFileName, char* strFilePath);*/

	/**	
	*	建立shift移动表
	*	@pWmStruct		WM结构体指针
	*	@return void
	**/
	void CreateShiftTable(WMSTRUCT* pWmStruct);

	/**	
	*	建立prefix前缀表
	*	@pWmStruct		WM结构体指针
	*	@return void
	**/
	void CreatePrefixTable(WMSTRUCT* pWmStruct);

	/**	
	*	Hash哈希表的建立
	*	@pWmStruct		WM结构体指针
	*	@return int
	**/
	int CreateHashTable(WMSTRUCT* pWmStruct);

	/**	
	*	从配置文件中加载关键词
	*	@pWmStruct		WM结构体指针
	*	@return int
	**/
	int LoadPatternToArray(WMSTRUCT* pWmStruct);

	/**	
	*	字符串哈希值从小到大排列
	*	@pWmStruct		WM结构体指针
	*	@return void
	**/
	void Sort(WMSTRUCT* pWmStruct);

	/**
	*	WM算法模式匹配
	*	@pchSrcText		要过滤的文本内容
	*	@nTextLen		原文本内容长度
	*	@pList			返回匹配的链表指针
	*	@return	int
	**/
	int WMPatternMatch(unsigned char* pchSrcText, int nTextLen, WMPATTERNSTRUCT** pList);

	/**
	*	后缀哈希值相同,比较前缀以及整个字符匹配
	*	@nIndex			散列值
	*	@pchDestText	文本内容
	*	@windowBgn	    匹配模式窗口头
	*	@return	int
	**/
	int WMPrefixMatch(int nIndex, unsigned char* pchDestText, unsigned char* T,WMPATTERNSTRUCT**);

	/**
	*	用指定的字符串替换文本中出现的要替换的字符串
	*	@pchInput	 	含特殊字符的字符串
	*	@pchOutput		转换后的字符串
	*	@pSrc			要转换的特殊字符	
	*	@pDst			要转换的目的字符
	*	@return	char*	转换后的字符串指针
	**/
	char* Substitute(char* pInput, char* pOutput, char* pSrc, char* pDst);

	/*************************内联、静态函数***************************/

	/**
	*	哈希映射函数
	*	@T			哈希函数键值
	*	@return		unsigned short
	**/
	static unsigned short HASH16(unsigned char* T)
	{
		//每个字节放一位字符,前一个字符左移8位与后面的字符
		return (unsigned short) ((*T) << 4 | *(T + 2));
	}

	/**
	*	判断是否是单字符
	*	@chChar
	*	@return	bool
	**/
	inline bool IsSingleChar(char chChar)
	{
		return chChar > 0;
	}

	/**
	*	判断是否是有效的单字符
	*	@chChar
	*	@return	bool
	**/
	inline bool IsValidSingleChar(char chChar)
	{
		return (chChar >= '0' && chChar <= '9')
			|| (chChar >= 'A' && chChar <= 'Z')
			|| (chChar >= 'a' && chChar <= 'z')
			|| (chChar == ' ');
	}

	/**	
	*	判断是否是有效的双字符(中文)
	*	0xA3B0-0xA3B9,全角数字
	*	0xA3C1-0xA3DA,全角大写字母
	*	0xA3E1-0xA3FA,全角小写字母
	*	GBK/2:OxBOA1-F7FE, 收录 GB2312 汉字 6763 个,按原序排列
	*	GBK/3:Ox8140-AOFE,收录 CJK 汉字 6080 个
	*	GBK/4:OxAA40-FEAO,收录 CJK 汉字和增补的汉字 8160 个
	*	@ushChar
	*	@return bool
	**/
	inline bool IsValidDoubleChar(unsigned short ushChar)
	{
		return (ushChar >= 0xA3B0 && ushChar <= 0xA3B9)
			|| (ushChar >= 0xA3C1 && ushChar <= 0xA3DA)
			|| (ushChar >= 0xA3E1 && ushChar <= 0xA3FA)
			|| (ushChar >= 0xB0A0 && ushChar <= 0xF7FF)
			|| (ushChar >= 0x8140 && ushChar <= 0xA0FF)
			|| (ushChar >= 0xAA40 && ushChar <= 0xFEAF);
	}

	/**	
	*	半角字符转换成全角字符
	*	@chChar
	*	@return unsigned short
	**/
	inline unsigned short ToDoubleChar(char chChar)
	{
		//全角字符 - 半角字符 = 0xA380 
		return 0xA380 + chChar;
	}

	/**	
	*	全角字符转换成半角字符
	*	@ushChar
	*	@return char
	**/
	inline char ToSingleChar(unsigned short ushChar)
	{
		//全角字符 - 半角字符 = 0xA380 
		return ushChar - 0xA380;
	}

	/**	
	*	全角字符从小写字母转换成大写字母:两者差0x0020(32)
	*	@ushChar
	*	@return unsigned short
	**/
	inline unsigned short ToUpperChar(unsigned short ushChar)
	{
		if (ushChar >= 0xA3E1 && ushChar <= 0xA3FA)
			return ushChar - 0x0020;

		return ushChar;
	}

	/**	
	*	全角字符从大写字母转换成小写字母,两者差0x0020(32)
	*	@ushChar
	*	@return unsigned short
	**/
	inline unsigned short ToSmallChar(unsigned short ushChar)
	{
		if (ushChar >= 0xA3C1 && ushChar <= 0xA3DA)
			return ushChar + 0x0020;

		return ushChar;
	}

	/**
	*	把文本字符串转换成全角字符中的预处理
	*	@pchSrc			原文本字符串
	*	@pchDest		目的字符串
	*	@szLength		原文本字符串长度
	*	@return	size_t
	**/
	inline size_t PreProcess(const char* pchSrc, char* pchDest, size_t szLength)
	{
		const char* pchSrcPos = pchSrc;
		char* pchDestPos = pchDest;

		//判断字符串是否越界
		while(pchSrcPos < pchSrc + szLength)
		{
			//判断是单字符
			if (IsSingleChar(*pchSrcPos))
			{
				//判断是否是字母与数字
				if (IsValidSingleChar(*pchSrcPos))
				{
					unsigned short ushChar = ToDoubleChar(*pchSrcPos);
					ushChar = ntohs(ToUpperChar(ushChar));
					memcpy(pchDestPos, &ushChar, 2);
					pchDestPos += 2;
				}

				pchSrcPos++;
			}
			//判断是双字符
			else
			{
				//只有一个单字符(最后-最前)
				if (pchSrc + szLength - pchSrcPos < 2)
					break;

				//用无符号的短整型存储一个中文字符或宽字符
				unsigned short ushChar;
				memcpy(&ushChar, pchSrcPos, 2);

				//将一个无符号短整型数从主机字节顺序转换为网络字节顺序
				ushChar = htons(ToUpperChar(ushChar));

				if (IsValidDoubleChar(ushChar))
				{
					//将一个无符号短整型数从网络字节顺序转换为主机字节顺序
					ushChar = ntohs(ToUpperChar(ushChar));
					memcpy(pchDestPos, &ushChar, 2);
					pchDestPos += 2;
				}

				pchSrcPos += 2;
			}
		}

		return pchDestPos - pchDest;
	}

	/**
	*	把全角字符串转换成半角字符串的预处理
	*	@pchSrc			原文本字符串
	*	@pchDest		目的字符串
	*	@szLength		原文本字符串长度
	*	@return	size_t
	**/
	inline size_t ToHalfPreProcess(const char* pchSrc, char* pchDest, size_t szLength)
	{
		const char* pchSrcPos = pchSrc;
		char* pchDestPos = pchDest;

		//判断字符串是否越界
		while(pchSrcPos < pchSrc + szLength)
		{
			//用无符号的短整型存储一个中文字符或宽字符
			unsigned short ushChar = 0;
			//中文转换成无符号的短整型的好方法
			memcpy(&ushChar, pchSrcPos, 2);
			ushChar = htons(ushChar);

			//判断是否是大写的英文和数字
			if ((ushChar >= 0xA3C1 && ushChar <= 0xA3DA) || 
				(ushChar >= 0xA3B0 && ushChar <= 0xA3B9) ||
				(ushChar == 0xA3A0))
			{
				ushChar = ToSmallChar(ushChar);
				char chChar = ToSingleChar(ushChar);
				memcpy(pchDestPos, &chChar, 1);
				pchDestPos += 1;
			} 
			else
			{
				//只有一个单字符(最后-最前)
				if (pchSrc + szLength - pchSrcPos < 2)
					break;

				//用无符号的短整型存储一个中文字符
				ushChar = ntohs(ushChar);
				memcpy(pchDestPos, &ushChar, 2);
				pchDestPos += 2;
			}

			pchSrcPos += 2;
		}

		return pchDestPos - pchDest;
	}

};


/***************************************************
*	Original Filename: 		wm.cpp
*	Created/Modified: 		Andy_guo
*	Date:					2009/11/22	
*	Main Purpose:			WM算法
*	Comments:	
****************************************************/
#include "WM.h"

/****************************************************/
CWM::CWM(void)
{
	//从配置文件中加载关键词
	m_pWmStruct = new WMSTRUCT;
	memset(m_pWmStruct, 0, sizeof(WMSTRUCT));

	m_pWmStruct->plist = NULL;
	m_pWmStruct->msPatArray = NULL;
	m_pWmStruct->msNumArray = NULL;
	m_pWmStruct->msHash = NULL;
	m_pWmStruct->msShift = NULL;
	m_pWmStruct->msPrefix = NULL;
	m_pWmStruct->msSmallest = MAXPATTERN - 1;

	//加载模式
	LoadPatternToArray(m_pWmStruct);

	//字符串哈希值从小到大排列
	Sort(m_pWmStruct);

	//建立shift移动表
	CreateShiftTable(m_pWmStruct);

	//Hash哈希表的建立
	CreateHashTable(m_pWmStruct);

	//建立prefix前缀表
	CreatePrefixTable(m_pWmStruct);
}

CWM::~CWM(void)
{
	//释放WM综合结构体
	delete m_pWmStruct;
	m_pWmStruct = NULL;
}

/**********************************************
*功  能: 获取指定文件名路径
*参  数: const char*	strFileName		文件名
*	     char*			strFilePath		文件名路径
*返回值:								空
***********************************************/
#if 0
void CWM::GetFilePath(const char* strFileName, char* strFilePath)
{
	//文件路径
	CString pathFile;

	//取当前运行模块全路径
	GetModuleFileName(NULL, pathFile.GetBuffer(MAX_PATH), MAX_PATH);
	pathFile.ReleaseBuffer(MAX_PATH);

	//返回最后匹配字符序号
	int nIndex = pathFile.ReverseFind('\\');

	//取部分路径
	pathFile = pathFile.Left(nIndex);

	//取目的文件路径
	pathFile = pathFile + _T("\\") + _T(strFileName);

	//拷贝目的文件路径
	memcpy(strFilePath, pathFile.GetBuffer(pathFile.GetLength()), pathFile.GetLength());
	pathFile.ReleaseBuffer();

	return;
}
#endif

/****************************************************/
//从配置文件中加载关键词
int CWM::LoadPatternToArray(WMSTRUCT* pWmStruct)
{
	//分配WM内存空间
	if (pWmStruct == NULL)
	{
		pWmStruct = new WMSTRUCT;
		memset(pWmStruct, 0, sizeof(WMSTRUCT));
	}

#if 1
	int ch = 0; 
	char pchDest[64] = {0};
	//打开文件<关键词.txt>
	FILE* pFile = fopen(".\\关键词.txt","r");

	int i = 0;
	//读取文件
	while(!feof(pFile))
	{
		//读入一个数据
		ch = fgetc(pFile);
		if(ch != '\n')
		{
			pchDest[i++] = (char)ch; 
			continue;
		}
		else
			i = 0;

		//对关键词预处理
		char pchTemp[64] = {0};
		int size = CWM::PreProcess(pchDest, pchTemp, strlen(pchDest) + 1);
		strcpy_s(pchDest, pchTemp);

		//分配模式内存空间
		WMPATTERNSTRUCT* pPatternStruct = new WMPATTERNSTRUCT;
		if (!pPatternStruct) return -1;
		memset(pPatternStruct, 0, sizeof(WMPATTERNSTRUCT));

		//给节点赋值
		pPatternStruct->psPat = new char[strlen(pchDest) + 1];
		memset(pPatternStruct->psPat, 0, strlen(pchDest) + 1);
		strcpy_s(pPatternStruct->psPat, strlen(pchDest) + 1, pchDest);
		pPatternStruct->psLen = strlen(pchDest);

		//并把此模式加入链表
		pPatternStruct->next = pWmStruct->plist;
		pWmStruct->plist = pPatternStruct;

		//更新WM结构体值
		pWmStruct->msNumPatterns++;
		if (pPatternStruct->psLen < (unsigned)pWmStruct->msSmallest)
		{
			pWmStruct->msSmallest = pPatternStruct->psLen;
		}

		//清空数组
		memset(pchDest, 0, 64);
	} 
#else
	int ch = 0; 
	char pchDest[32] = {0};
	//打开文件<关键词.txt>
	FILE* pFile = fopen(".\\关键词.txt","r");

	//读取文件
	while(fgets(pchDest, 32, pFile) != NULL)
	{
		//分配模式内存空间
		WMPATTERNSTRUCT* pPatternStruct = new WMPATTERNSTRUCT;
		if (!pPatternStruct) return -1;
		memset(pPatternStruct, 0, sizeof(WMPATTERNSTRUCT));

		//给节点赋值
		pPatternStruct->psPat = new char[strlen(pchDest) + 1];
		memset(pPatternStruct->psPat, 0, strlen(pchDest) + 1);
		strcpy_s(pPatternStruct->psPat, strlen(pchDest) + 1, pchDest);
		pPatternStruct->psLen = strlen(pchDest);
		printf("%s\n", pPatternStruct->psPat);
		printf("%d\n", pPatternStruct->psLen);

		//并把此模式加入链表
		pPatternStruct->next = pWmStruct->plist;
		pWmStruct->plist = pPatternStruct;

		//更新WM结构体值
		pWmStruct->msNumPatterns++;
		if (pPatternStruct->psLen < (unsigned)pWmStruct->msSmallest)
		{
			pWmStruct->msSmallest = pPatternStruct->psLen;
		}

		//清空数组
		memset(pchDest, 0, 32);
	} 
#endif

	//分配模式数组内存空间
	pWmStruct->msPatArray = new WMPATTERNSTRUCT[sizeof(WMPATTERNSTRUCT) * pWmStruct->msNumPatterns];
	if (!pWmStruct->msPatArray)
	{
		printf("ERROR:分配内存空间失败!\n");
		return -1;
	}

	//有相同哈希散列值数组空间
	pWmStruct->msNumArray = new unsigned short[sizeof(short) * pWmStruct->msNumPatterns];
	if(!pWmStruct->msNumArray)
	{
		printf("ERROR:分配内存空间失败!\n");
		return -1;
	}

	//遍历模式链表,并拷贝到模式数组
	WMPATTERNSTRUCT* pList = NULL;
	int kk;
	for(kk = 0, pList = pWmStruct->plist; 
		pList != NULL && kk < pWmStruct->msNumPatterns; 
		pList = pList->next)
	{
		memcpy(&pWmStruct->msPatArray[kk++], pList, sizeof(WMPATTERNSTRUCT));
	}

	return 0;
}

/****************************************************/
//字符串哈希值从小到大排列
void CWM::Sort(WMSTRUCT* pWmStruct)
{
	//取所有模式的最小值
	int m = pWmStruct->msSmallest, B = 4;
	unsigned char* temp;

	for(int i = pWmStruct->msNumPatterns - 1, flag = 1; i > 0 && flag; i--)
	{
		flag = 0;
		for(int j = 0; j < i; j++)
		{
			//后面的比前面还要小,则交换两者
			if(CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[j + 1].psPat[m - B]) 
				< CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[j].psPat[m - B]))
			{
				flag = 1;
				temp = (unsigned char*)pWmStruct->msPatArray[j + 1].psPat;
				pWmStruct->msPatArray[j + 1].psPat = pWmStruct->msPatArray[j].psPat;
				pWmStruct->msPatArray[j].psPat = (char*)temp;
			}
		}
	}
}

/****************************************************/
//建立shift移动表
void CWM::CreateShiftTable(WMSTRUCT* pWmStruct)
{
	//要考虑的一块字符串的大小
	int B = 4;
	//所有模式的最小长度
	int m = pWmStruct->msSmallest;

	//建立移动表空间
	pWmStruct->msShift = new unsigned char[SHIFTTABLESIZE * sizeof(char)];
	if(!pWmStruct->msShift) return;
	memset(pWmStruct->msShift, 0, SHIFTTABLESIZE * sizeof(char));

	//当模式数量少时,取(B = 2),移动表所有初始值为(m - B + 1)
	//显然,与任何模式都不匹配时值为(m - B + 2)
	for(int i = 0; i < SHIFTTABLESIZE; i++)
		pWmStruct->msShift[i] = (unsigned)(m - B + 2);

	//为每个大小为B的字符串映射一个入口
	for(int i = 0; i < pWmStruct->msNumPatterns; i++)
	{
		for(int k = 0; k < m - 2; k++)
		{
			//大小为B的字符串与模式相比,要移动的位数
			//如:(中国)与(中国人)相比,移动2位;(国人)与(中国人)相比,移动0位
			unsigned short nShift = (unsigned short)(m - B - k);

#if 1
			//为每个大小为B的字符串匹配一个整数作为移动表的索引
			//匹配时,移动表索引值与哈希表的索引值相同
			unsigned short nIndex = CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[i].psPat[k]);
#else
			//为每个大小为B的字符串匹配一个整数作为移动表的索引
			//匹配时,移动表索引值与哈希表的索引值相同
			unsigned short nIndex = pWmStruct->msPatArray[i].psPat[k] << 4
				| pWmStruct->msPatArray[i].psPat[k + 2];
#endif

			//与模式匹配时值shift[i]为(m - q),即到q时要移动的距离
			//如:文本ca与模式cat匹配时,要移动1个距离;at与模式cat匹配时,要移动0个距离
			if(nShift < pWmStruct->msShift[nIndex])
				pWmStruct->msShift[nIndex] = nShift;

			k++;
		}
	}

	return;
}

/****************************************************/
//建立prefix前缀表
void CWM::CreatePrefixTable(WMSTRUCT* pWmStruct)
{
	//建立前缀表空间
	pWmStruct->msPrefix = new HASH_TYPE[sizeof(HASH_TYPE) * (pWmStruct->msNumPatterns)];
	if(!pWmStruct->msPrefix) return;

	for(int i = 0; i < pWmStruct->msNumPatterns; i++)
	{
		pWmStruct->msPrefix[i] = CWM::HASH16((unsigned char*)pWmStruct->msPatArray[i].psPat);
	}

	return;
}

/****************************************************/
//哈希表的建立,计算有多少个不同哈希值,且从小到大
int CWM::CreateHashTable(WMSTRUCT* pWmStruct)
{
	unsigned sindex, hindex, nInGroup;
	int m = pWmStruct->msSmallest;
	int B = 4;

	//分配内存空间
	pWmStruct->msNumHashEntries = HASHTABLESIZE;
	pWmStruct->msHash = new HASH_TYPE[sizeof(HASH_TYPE) * pWmStruct->msNumHashEntries];
	if(!pWmStruct->msHash)
	{
		printf("ERROR:分配内存空间出错!\n");
		return -1;
	}

	//给哈希表的条目初始化为-1
	for(int i = 0; i < (int)pWmStruct->msNumHashEntries; i++)
	{
		pWmStruct->msHash[i] = (HASH_TYPE) - 1;
	}

	//遍历模式列表
	for(int i = 0; i < pWmStruct->msNumPatterns; i++)
	{
		//计算最后B(在这B=4)个字符的哈希值为i
		hindex = CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[i].psPat[m - B]);
		sindex = pWmStruct->msHash[hindex] = i;

		//计算最后B个字符的哈希值相等的个数
		nInGroup = 1;
		while(++i < pWmStruct->msNumPatterns && 
			hindex == CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[i].psPat[m - B]))
			nInGroup++;

		//把有相同哈希值的个数放入模式数组中
		pWmStruct->msNumArray[sindex] = nInGroup;
		i--;
	}

	return 0;
}

/********************************************************
* 功 能: WM算法模式匹配
* 参 数: unsigned char*		pchSrcText		要过滤的文本内容
*		 int				nTextLen		原文本内容长度
*		 WMPATTERNSTRUCT*	pList			返回匹配的字符
*返回值:									无
*********************************************************/
int CWM::WMPatternMatch(unsigned char* pchSrcText, int nTextLen, WMPATTERNSTRUCT** pList)
{
	//预处理后的文本缓存
	char pchDestText[1024] = {0};
	memset(pchDestText, 0, 1024);
	nTextLen = strlen((char*)pchSrcText) + 2;

	//预处理文本,减少循环次数
	int nDestTextLen = PreProcess((char*)pchSrcText, pchDestText, nTextLen);

	//取WM综合结构体
	WMSTRUCT* pWmStruct = m_pWmStruct;

	//文本的右边界(尾)
	unsigned char* TextEnd = (unsigned char*)(pchDestText + nDestTextLen);

	//若文本比最小的模式的长度还小,退出
	if(nDestTextLen < pWmStruct->msSmallest)
		return -1;

	//模式块窗口尾
	unsigned char* windowEnd = (unsigned char*)(pchDestText + pWmStruct->msSmallest);

	//1.计算文本当前被扫描的B个字符的哈希值h(从t[m-B+1]...t[m])
	for(unsigned char* windowBgn = (unsigned char*)pchDestText; windowEnd <= TextEnd; windowBgn++, windowEnd++)
	{
		//取移动表shift[i]的值(nShift),若为0,则有匹配
		int nShift = pWmStruct->msShift[*windowBgn << 4 | *(windowEnd - 2)];

		//2.检查shift[i]的值nShift,不为0,没有匹配
		while(nShift)
		{
			windowBgn += nShift;
			windowEnd += nShift;

			//窗口的边界超出文本尾
			if(windowEnd > TextEnd)
				return -1;

			//寻找下一个匹配
			nShift = pWmStruct->msShift[*windowBgn << 4 | *(windowEnd - 2)];
		} 

		//移动值为0,找到匹配,取对应的散列值(nIndex)
		int nIndex = pWmStruct->msHash[*windowBgn << 4 | *(windowEnd - 2)];
		if(nIndex  == (HASH_TYPE) - 1) 
			continue;

		WMPrefixMatch(nIndex, (unsigned char*)pchDestText, windowBgn, pList);

		windowBgn++;
		windowEnd++;
	}

	return 0;
}

/**********************************************
*功  能: 后缀哈希值相同,比较前缀以及整个字符匹配
*参  数: int			nIndex		散列值
*	     unsigned char* pchDestText	文本初始内容
*	     unsigned char* windowBgn	有匹配的文本头
*返回值:							无
***********************************************/
int CWM::WMPrefixMatch(int nIndex, unsigned char* pchDestText, unsigned char* windowBgn,WMPATTERNSTRUCT** pList)
{
	//取WM综合结构体
	WMSTRUCT* pWmStruct = m_pWmStruct;

	//取有相同哈希值头与尾
	WMPATTERNSTRUCT* pPatternBegin = &pWmStruct->msPatArray[nIndex];
	WMPATTERNSTRUCT* pPatternEnd = pPatternBegin + pWmStruct->msNumArray[nIndex];

	//3.计算文本前缀哈希值
	int text_prefix = CWM::HASH16(windowBgn);

	//4.检查每个满足(HASH[h] <= P < HASH[h+1])的模式P
	for( ; pPatternBegin < pPatternEnd; pPatternBegin++)
	{
		if(pWmStruct->msPrefix[nIndex++] != text_prefix)
			continue;
		else
			//5.当PREFIX[P]=text_prefix,与原文本比较
		{
			unsigned char* pPatternTxt = (unsigned char*)pPatternBegin->psPat;
			unsigned char* pTxt = windowBgn;

			//对文本和模式进行直接检查
			while(*(pPatternTxt++) == *(pTxt++) && *(pTxt - 1) != '\0');

			//取到匹配的模式
			if(*(pPatternTxt - 1) == '\0')
			{
				printf("Matched pattern is:%s\n", pPatternBegin->psPat);
				//保存已经匹配的模式内容
				WMPATTERNSTRUCT* pMatchedPtn = new WMPATTERNSTRUCT;
				memset(pMatchedPtn, 0, sizeof(WMPATTERNSTRUCT));

				pMatchedPtn->psPat = new char[strlen(pPatternBegin->psPat) + 1];
				memset(pMatchedPtn->psPat, 0, strlen(pPatternBegin->psPat) + 1);
				strcpy_s(pMatchedPtn->psPat, strlen(pPatternBegin->psPat) + 1, pPatternBegin->psPat);
				pMatchedPtn->next = *pList;
				*pList = pMatchedPtn;
			}

		}

	}

	return 0;
}

/***************************************************
*功  能: 用指定的字符串替换文本中出现的要替换的字符串
*参  数: char* pchInput	 	含特殊字符的字符串
*		 char* pchOutput	转换后的字符串
*		 char* pSrc			要转换的特殊字符	
*		 char* pDst			要转换的目的字符
*返回值:					转换后的字符串
****************************************************/
char* CWM::Substitute(char* pchInput, char* pchOutput, char* pSrc, char* pDst)
{
	char *pchSrc, *pchDst, *pCursor;
	int nSrcLen, nDstLen, nLen;

	// 指向输入字符串的游动指针.
	pchSrc = pchInput;
	// 指向输出字符串的游动指针.
	pchDst = pchOutput;
	// 计算被替换串和替换串的长度.
	nSrcLen = strlen(pSrc);
	nDstLen = strlen(pDst);

	//查找pchSrc,返回指向字符串中第一次出现替换串的位置指针(找不到则返回null).
	pCursor = strstr(pchSrc, pSrc);
	if(pCursor)
	{
		// 找到
		while(pCursor) 
		{
			// 计算被替换串前边字符串的长度.
			nLen = (int)(pCursor - pchSrc);
			// 复制游标指针前的字符串
			memcpy(pchDst, pchSrc, nLen);
			// 复制替换字符
			memcpy(pchDst + nLen, pDst, nSrcLen/2 + nSrcLen%2);
			// 指针跳过被替换串
			pchSrc = pCursor + nSrcLen;
			// 调整指向输出串的指针位置
			pchDst = pchDst + nLen + nSrcLen/2 + nSrcLen%2;
			// 继续查找
			pCursor = strstr(pchSrc, pSrc);
		}
		// 复制剩余字符串.
		strcpy(pchDst, pchSrc);
	}
	else
	{
		// 没有找到则原样复制.
		strcpy(pchDst, pchSrc);
	}

	return pchDst;
}

越看这个代码越觉得复杂。这说明直接上来就代码还是比较困难的,应该先了解清楚了算法,然后才能去看代码或者说是自己来实现代码。

后来我就觉得这样来搞不是很靠谱,自己写一个这样的算法还是比较困难的,所以就想在网络上找个更好的代码,先凑合着用。

网上翻了几个帖子之后,我发现其实我可以用正则表达式来实现我的这个功能,正则表达式中的|(或)直接就可以满足我的需求。就是将所有的模式串或起来,然后搞成一个正则表达式,然后直接用这个正则表达式进行搜索就Ok了,正好能满足我的需求,明天去公司了就准备这么干了。


乐趣公园 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:多模式匹配
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(2)个小伙伴在吐槽
  1. AC自动机是做这个的,就是列出来的第一个算法,之前写敏感词过滤用的是这个
    TroyCheng2012-03-25 17:54 回复
    • 好像正则表达式也是自动机,试了一下正则,速度已经差不多能满足要求了
      小桥流水2012-03-27 19:05 回复