分享
 
 
 

SQL Server中检索语句中Like的算法实现

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

本文主要对字串匹配Like的算法实现,在SQL Server中Like的匹配中主要有表现为对两个通配符的处理,分别为“_”代表一个字符,“%”代表任意个字符。由于“%”在匹配过程中的位置任意性,所以完全匹配、通配符“_”匹配与此不应该一起参与匹配运算,所以我们决定在匹配前先将子串按“%”分段,进行逐段匹配,显然降低了匹配算法的难度,下面讲解一下算法的实现过程:(后附实现源码)

1. 确定第一个“%”的位置,

目的:确定模式匹配的方式

a> 是以“%”开头则不需要左匹配(左匹配即要求子串的第一个字符必须与原串的第一个字符相一致)

b> 不是以“%”开头则需要进行左匹配

2. 进行KMP*算法进行模式匹配

KMP算法不能完全地实现本文提到的匹配算法,我们必须对此加以修正,主要是模式因子不适合,在这里必须认为“_”的因子值为与前一个任意字符一致,所以“_”越多,匹配时的回退的可能性将越少,当然其匹配速度比教课书上的模式查找要快。

3. 继续下一个子串段的匹配工作。

下面提供算法的源码,分为两个函数,

1. _strat

为KMP*模式串查找函数,函数前有其使用说明。

2. _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);

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有