|
本文主要对字串匹配Like的算法实现，在SQL Server中Like的匹配中主要有表现为对两个通配符的处理，分别为“_”代表一个字符，“%”代表任意个字符。由于“%”在匹配过程中的位置任意性，所以完全匹配、通配符“_”匹配与此不应该一起参与匹配运算，所以我们决定在匹配前先将子串按“%”分段，进行逐段匹配，显然降低了匹配算法的难度，下面讲解一下算法的实现过程：（后附实现源码）
１. 确定第一个“%”的位置，
目的：确定模式匹配的方式
a> 是以“%”开头则不需要左匹配（左匹配即要求子串的第一个字符必须与原串的第一个字符相一致）
b> 不是以“%”开头则需要进行左匹配
２. 进行ＫＭＰ*算法进行模式匹配
ＫＭＰ算法不能完全地实现本文提到的匹配算法，我们必须对此加以修正，主要是模式因子不适合，在这里必须认为“_”的因子值为与前一个任意字符一致，所以“_”越多，匹配时的回退的可能性将越少，当然其匹配速度比教课书上的模式查找要快。
３. 继续下一个子串段的匹配工作。
下面提供算法的源码，分为两个函数，
１. _strat
为ＫＭＰ*模式串查找函数，函数前有其使用说明。
２. _strlike
为Like的实现过程，内部用到_strat模式串匹配函数，实现的关键是对模式串的分段，来降低匹配的难度。
////////////////////////////////////////////////////////////////////////////////
// 函数名称：int _strat(
// char * chText,
// char * chPattern,
// int nbegpos,
// int nlen
// bool bleft )
// 实现功能：模式串搜索
// 对全局变量的影响：无
// 参数说明：
// chText 原串
// chPattern 模式串
// nbegpos 起始位置
// nlen 原串相对长度
// bleft 是否左对齐(即第一个字符必须一致)
// 返回结果说明：实际位置
// 待优化一：回退数不得大于nlen - len(chPattern)，即回退后无法导致完全匹配
// 待优化二：计算模式串与字串搜索代码合并，减少计算量
////////////////////////////////////////////////////////////////////////////////
int _strat(char * chText , char * chPattern , int nbegpos /* = 0 */ , int nlen /* = -1 */ , bool bleft /* = false */)
{
int nPatternLen = _tcslen(chPattern);
int nTextLen = _tcslen(chText);
if(nlen >= 0)
{
if(nbegpos + nlen < nTextLen)
nTextLen = nbegpos + nlen;
}
if(nbegpos + nPatternLen > nTextLen || nPatternLen > MAXLEN_PATTERN)
return -1;
if(nPatternLen == 0)
return nbegpos;
else
{
int nGeneralLen = 0;
short chNext[MAXLEN_PATTERN] = { -1 };
int nPattPos = 0 , nNext = -1;
if(!bleft)
{
//生成模式回退值
while(nPattPos < nPatternLen)
{
if( nNext == -1 || chPattern[nPattPos] == '_' || chPattern[nPattPos] == chPattern[nNext])
{
nPattPos ++;
nNext ++;
chNext[nPattPos] = nNext;
}
else
nNext = chNext[nNext];
}
}
int nTextPos = nbegpos;
nPattPos = 0;
//进行模式匹配
while(nPattPos < nPatternLen && nTextPos < nTextLen)
{
if(nPattPos == -1 || chPattern[nPattPos] == '_' || chPattern[nPattPos] == chText[nTextPos])
{
nPattPos ++;
nTextPos ++;
}
else
{
//要求左对齐时，不允许回退（回退时肯定不是左对齐的）
if(bleft)
return -1;
else
nPattPos = chNext[nPattPos];
}
}
//判断模式串是否已经完全被匹配，否则返回-1
if(nPattPos == nPatternLen)
return nTextPos - nPattPos;
else
return -1;
}
}
////////////////////////////////////////////////////////////////////////////////
// 函数名称：bool _strlike(
// char * chText,
// char * chPattern,
// int nbegpos )
// 实现功能：两个字符串的匹配算法，带通配符
// 对全局变量的影响：无
// 参数说明：
// chText 原字符串
// chPattern 模式串
// nbegpos 起始位置
// 返回结果说明：
// =true 表示相似或一致
// =false 表示不相似或不一致
////////////////////////////////////////////////////////////////////////////////
bool _strlike(char * chText , char * chPattern , int nbegpos /* = 0 */)
{
bool bLeftMatch = true , bLast = false;
int nTextLen = _tcslen(chText);
//作最基础的匹配，即存在模式串的情况下再作比较
if(_tcslen(chPattern) == 0)
if(_tcslen(chText) == 0)
return true;
else
return false;
do
{
char * chFirstPattern , * chSecondPattern;
if(chPattern[0] == '%')
{
do
{
chPattern ++;
}while(chPattern[0] == '%');
if(chPattern == NULL || _tcslen(chPattern) == 0)
return true;
bLeftMatch = false;
}
else
bLeftMatch = true;
//初始化模式串
chSecondPattern = _tcschr(chPattern , '%');
int nPatternLen;
if(chSecondPattern == NULL)
{
bLast = true;
nPatternLen = _tcslen(chPattern);
if(!bLeftMatch)
{
//若以%开头，并且没有剩余模式串时，只要考虑右对齐匹配的方式即可(实际上也是左对齐)
if(nbegpos + nPatternLen <= nTextLen)
{
nbegpos = nTextLen - nPatternLen;
bLeftMatch = true;
}
else
return false;
}
else
if(nbegpos + nPatternLen != nTextLen)
return false;
}
else
{
//模式串不得长于原串
nPatternLen = chSecondPattern - chPattern;
if(nbegpos + nPatternLen > nTextLen)
return false;
}
//初始化模式串与修改剩余串
chFirstPattern = new char[nPatternLen + 1];
memcpy(chFirstPattern , chPattern , nPatternLen);
chFirstPattern[nPatternLen] = 0;
chPattern = chSecondPattern;
int npos = _strat(chText , chFirstPattern , nbegpos , bLeftMatch ? nPatternLen : nTextLen - nbegpos , bLeftMatch);
delete chFirstPattern;
if(npos < 0)
{
return false;
}
else
{
//定下一查找位置的起点
if(bLeftMatch)
{
if(npos != nbegpos)
return false;
}
else
nbegpos = npos;
if(bLast)
{
if(nPatternLen + npos == nTextLen)
return true;
else
return false;
}
else
nbegpos += nPatternLen;
}
}while(true);
}
|
