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

减小字体 增大字体 作者:佚名  来源:本站整理  发布时间:2009-03-16 14:01:54

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

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);

}

Tags:

作者:佚名
分享到: 微信 更多