stringmatch.h

经曲的字符串匹配模糊搜索算法 思想不是本人的

#include<fstream.h>

const float CAP_MISMATCH_VAL = 0.9f;

/*---------------------------------------------------------
**函数功能：检测两个字符串的匹配相似度
**函数参数：*left和*right为两个比较的字符串
**返 回 值：bool型   true读取成功, false读取失败
**编 写 人：qidajiang
**时    间：2008-7-20
---------------------------------------------------------*/
//本函数会返回一个介于0到1之间的浮点值，表示两个字符串
//之间匹配度的一个近似百分比

float stringMatch(char const *left, char const *right)
{
    // 获取左右两个字符串，能最长串的长度
    int  leftSize = strlen(left);
    int  rightSize = strlen(right);
    int largerSize = (leftSize > rightSize) ? 
	    leftSize : rightSize;
    char const *leftPtr = left;
    char const *rightPtr = right;
    float matchVal = 0.0f;
	// 对左侧的字符串进行迭代操作，直到字符串的最后一个字符
    while(leftPtr != (left + leftSize) && 
	    rightPtr != (right + rightSize))
    {
        // 首先，我们进行一个简单的左右匹配检测
        if(*leftPtr == *rightPtr)
        {
            // 如果匹配，就向匹配总值加上这个字符的百分比值
            matchVal += 1.0f / largerSize;
            ++leftPtr; 
			++rightPtr;
        }
        // 如果匹配失败，进行一次忽略大小写的匹配检测
        else if(::tolower(*leftPtr) == ::tolower(*rightPtr))
        {
            matchVal += CAP_MISMATCH_VAL / largerSize;
            ++leftPtr; 
			++rightPtr;
        }
        else
        {
            char const *lpbest = left + leftSize;
            char const *rpbest = right + rightSize;
            int totalCount = 0;
            int bestCount = INT_MAX;
            int leftCount = 0;
            int rightCount = 0;
            // 这里我们在外层循环中遍历整个左字串
            // 但是为了确保不越过我们当前的最佳数量(bestCount)
            // 会进行提前退出循环的条件检测
            for(char const *lp = leftPtr; (lp != (left + leftSize) 
                && ((leftCount + rightCount) < bestCount)); ++lp)
            {
       
                for(char const *rp = rightPtr; (rp != (right + 
                    rightSize) && ((leftCount + rightCount) < 
                    bestCount)); ++rp)
                {
                    // 在这里，我们不考虑大小写
                    if(::tolower(*lp) == ::tolower(*rp))
                    {
                        totalCount = leftCount + rightCount;
                        if(totalCount < bestCount)
                        {
                            bestCount = totalCount;
                            lpbest = lp;
                            rpbest = rp;
                        }
                    }
                    ++rightCount;
                }
                ++leftCount;
                rightCount = 0;
            }
            leftPtr = lpbest;
            rightPtr = rpbest;
        }
    }
    // 为了防止浮点出错，作数值范围限定
    if(matchVal > 0.99f)
        matchVal = 1.0f;
    else if(matchVal < 0.01f)
        matchVal = 0.0f;
    return matchVal;
}

/*---------------------------------------------------------
**函数功能：从指定文件中读取字符串，存入data数组
**函数参数：data存放字符串的数组，fileName读取的文件名(可含路径)
**返 回 值：bool型   true读取成功, false读取失败
**编 写 人：qidajiang
**时    间：2008-7-20
---------------------------------------------------------*/
bool readFileDatalie(char str[1000][1000], char *fileName,int *pNum) 
{
	bool result;
	ifstream fis;
	fis.open(fileName,ios::in,0);
	if( !fis )
	{
		cout<<"Error:Can't open file!";
		result = false;
	}
	else
	{
		*pNum = 0;
		char textline[1000];
		while(!fis.eof())
		{
			//memset (textline,0,sizeof(textline));
			fis.getline(textline,sizeof(textline));	
			//cout<<"textline="<<textline<<endl;
			strcpy(str[(*pNum)++],textline);
		}
		fis.close();
		result = true;
	}
	return result;
}

/*---------------------------------------------------------
**函数功能：把单个字符串写入文件
**函数参数：fileName读取的文件名(可含路径),strtmp写入的字符串
**返 回 值：bool型   true读取成功, false读取失败
**编 写 人：qidajiang
**时    间：2008-7-20
---------------------------------------------------------*/
bool writeSigleData(char *fileName, char *strtmp) 
{
	bool result;
	fstream fos;
	fos.open(fileName,ios::app,0);
	if( !fos )
	{
		cout<<"Error:Can't open file!";
		result = false;
	}
	else
	{
		//fseek(fp, SEEK_END, SEEK_CUR);
		fos<<strtmp<<endl;
		fos.close();
		result = true;
	}
	return result;
}

/*---------------------------------------------------------
**函数功能：匹配函数，检测符合条件的字符串
**函数参数：instr输入待查询的字符串，str文本中的字符串，s文本中字符串的个数，limit限制比较参数
**返 回 值：bool型   true读取成功, false读取失败
**编 写 人：qidajiang
**时    间：2008-7-20
---------------------------------------------------------*/
void tryMatch(char instr[1000],char str[1000][1000],int s,float limit)
{
	float reslult=0.0f;
	int coumt=0;
	for (int i=0;i<s;i++)
	{
		reslult=stringMatch(instr,str[i]);
		cout<<"i = "<<i<<"时"<<"result = "<<reslult<<endl;
		if(reslult>limit)
		{
			//cout<<"The two String match!"<<endl;
			//cout<<"reslult= "<<reslult<<endl;
			cout<<"the string "<< instr <<" maching is "<< str[i]<<endl;
			writeSigleData("test1.txt",str[i]);
			coumt++;
		}
		else
		{
			//cout<<"The two String don't match!"<<endl;
		}
	}
	if(coumt==0)
	{
		cout<<"the string "<< instr <<" isn't string maching! "<<endl;
	}
}