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

发布:科技 时间:2019-03-15 08:51

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

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

作者 | 宋广泽

责编| 郭 芮

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

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

模糊搜索Version1.0:

//只有返回1才视为匹配成功

//错误样例:234 1230234

intresult_mohu(constchar* key,char* str)

{

inti= 0,j= 0,f= 0;

while( 1)

{

//找到第一个相匹配的字符

if((f== 0||f== 1)&&str[i]==key[j])

{

i++;

j++;

f= 1;

}

//已经有一个字符相匹配了再往后又不相匹配了

//便认为匹配失败

elseif(f== 1&&str[i]!=key[j])

{

i++;

f= 2;

}

else

{

i++;

}

//匹配到结尾或出现了匹配失败的结果就退出循环

if(i== strlen(str)||j== strlen(key)||f== 2)

{

break;

}

}

returnf;

}

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

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

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

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

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

模糊搜索Version2.0:

intresult_mohu(constchar* key,char* str)

{

typedefstruct

{

charson[ 11];

}Element;

inti,j,k= 0,l= 0,m= 0;

//f=1为符合筛选条件

intf= 0;

//N1为str的长度 N2为str连续子串的个数

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

returnf;

}

以上算法过于暴力,思路是穷举出待匹配字符串的所有子串,然后再将模式串与待匹配字符串的所有子串一个一个匹配,如果存在一个完全一致的子串,则返回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:

intresult_mohu(constchar* key,char* str)

{

inti= 0,j= 0,k= 0;

intflag= 0;

intlen_key= strlen(key);

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

}

}

returnflag;

}

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

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

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

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

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

网站地图