从模糊搜索 1.0 到 3.0 的算法迭代历程 | 技术头条

作者 | 宋广泽

责编 | 郭 芮

前一段时间在Linux上用C语言做了一个信息管理系统，初始版本的搜索就是直接使用了C语言库文件<string.h>里的库函数strcmp。后来联想到微信/QQ等软件上的搜索就很方便，无需输入全部的信息就能查找到想要的结果，或者给出一堆结果让用户选择。于是我便开始了模糊搜索算法的探索。

模糊搜索Version1.0：

//只有返回1才视为匹配成功
//错误样例：234 1230234
int result_mohu(const char* key,char* str)
{
 int i=0,j=0,f=0;
 while(1)
 {
 //找到第一个相匹配的字符
 if((f==0||f==1)&&str[i]==key[j])
 {
 i++;
 j++;
 f=1;
 }
 //已经有一个字符相匹配了再往后又不相匹配了
 //便认为匹配失败
 else if(f==1&&str[i]!=key[j])
 {
 i++;
 f=2;
 }
 else
 {
 i++;
 }
 //匹配到结尾或出现了匹配失败的结果就退出循环
 if(i==strlen(str)||j==strlen(key)||f==2)
 {
 break;
 }
 }
 return f;
}

该算法确实能够在一定程度上解决模糊搜索的问题，但是在判断匹配成功与否的时候，没有回退机制，只能一股脑地往前匹配，一旦出现有任何不相匹配的迹象就会跳出循环并返回匹配失败。

例如想要搜索的结果是1230234，而输入的关键字是234，从前往后遍历匹配串遍历到第一个23的时候算法机制就认为该匹配串有可能就是想要的结果，然而第一个23再往后一位是0，又与模式串中23之后是4的情况不符，则算法机制认为匹配失败。

以上算法是我自己构想的，没有查阅任何资料，直到最后我才发现，原来我最初构想的这个算法再仔细考虑一下就成为了模式匹配领域的著名算法BF算法，BF算法就是在上述算法的基础上加上了回退机制。然而因为我的一时冲动，直接重构了上述代码，于是便有了下面的模糊搜索Version2.0。

以上算法虽然有一些无法处理的样例，也是可以部署在实际应用中的，如智能停车场。拿出手机在地下停车场里扫描停车缴费的二维码，在输入框中按照系统要求从前往后填入车牌号，输入“鲁”则停车场内所有在山东挂牌的车牌号都显示出来供用户选择，一步一步缩小范围，再输入“A”则所有在济南挂牌的车牌号都显示出来供用户选择。

模糊搜索Version2.0：

int result_mohu(const char* key,char* str)
{
 typedef struct
 {
 char son[11];
 }Element;
 int i,j,k=0,l=0,m=0;
 //f=1为符合筛选条件
 int f=0;
 //N1为str的长度 N2为str连续子串的个数
 int N1=0,N2=0;
 N1=strlen(str);
 /*计算连续子串的个数*/
 for(i=1;i<=N1;i++)
 N2+=i;
 /*计算连续子串的个数*/
 //i控制子字符串的长度
 //j控制赋值
 //k控制新的线性结构b的下标
 //l控制子数组的首项在原数组中的位置
 //m控制即将用作赋值的str的下标
 Element *b=malloc(sizeof(Element)*N2);
 for(i=1;i<=N1;i++)
 {
 l=0;
 /*while循环内为给一个子字符串数组赋值*/
 while(1)
 {
 m=l;
 for(j=0;j<i;j++)
 {
 b[k].son[j]=str[m];
 m++;
 }
 l++;
 k++;
 if(m==N1)
 break;
 }
 }
 //挨个比对
 for(i=0;i<N2;i++)
 if(strcmp(key,b[i].son)==0)
 {
 f=1;
 break;
 }
 free(b);
 return f;
}

以上算法过于暴力，思路是穷举出待匹配字符串的所有子串，然后再将模式串与待匹配字符串的所有子串一个一个匹配，如果存在一个完全一致的子串，则返回true。

那么"abcdef"这个字符串到底有多少个连续子片段呢？我们按照子片段的长度挨个找规律，按长度由大到小进行：长度为6的就只有"abcdef"这1个；长度为5的有2个："abcde"和"bcdef"；长度为4的有3个："abcd"、"bcde"和"cdef"；长度为3的有4个；长度为2的有5个；长度为1的有6个。所以一共有1+2+3+4+5+6=21个。想必看到这里大家已经找到了规律：若关键词的长度为n，则该关键词的连续子字符串的个数就为1+2+3+...+n。

以上算法虽然在理论上可行，但当真正部署在管理系统内的时候就会出现一种不稳定的bug，这个bug我至今都没有找出来，而且时间复杂度和空间复杂度都很高，是一种效率低下的算法。

直到有一天，在一本技术上，看到了BF算法。

模糊搜索Version3.0：

int result_mohu(const char* key,char* str)
{
 int i=0,j=0,k=0;
 int flag=0;
 int len_key=strlen(key);
 int len_str=strlen(str);
 while(i<len_str&&j<len_key)
 {
 //遇到一个相同的字符就继续往后匹配
 if(key[j]==str[i])
 {
 k++;
 j++;
 i++;
 if(k==len_key)
 {
 flag=1;
 break;
 }
 }
 //又回退到最初的起点
 else
 {
 j-=k;
 i=i-k+1;
 k=0;
 }
 }
 return flag;
}

以上算法在模糊搜索Version1.0的基础上加上了回退机制，就避免了234匹配1230234失败这种bug了。

需要注意的是，模式串和匹配串回退的格数不同，模式串是直接回退到第一个元素的位置上，而匹配串则回退到第一个相匹配的字符后一个字符的位置上，因为匹配串需要继续向后检索是否有匹配成功的片段。

查询搜索系统经过了一次一次的迭代升级，变成了最美好的模样。

本文所谈的模糊搜索仅仅是模糊搜索中的一种——模式匹配，还有其他种类的模糊搜索，例如近义词/同义词搜索等。模式匹配算法也不仅仅只有BF算法，还有KMP算法、KMPP算法等，感兴趣的可以多了解一下。

作者：宋广泽，青岛某普通一本大学计算机专业在校生，本科在读，学生开发者。喜欢用C/C++编写有意思的程序，解决实际问题。

声明：本文为CSDN原创投稿，未经允许请勿转载。