從模糊搜索 1.0 到 3.0 的演算法迭代歷程 | 技術頭條

知識 03-15

打開今日頭條，查看更多圖片

作者 | 宋廣澤

責編 | 郭芮

前一段時間在Linux上用C語言做了一個信息管理系統，初始版本的搜索就是直接使用了C語言庫文件<string.h>里的庫函數strcmp。後來聯想到微信/QQ等軟體上的搜索就很方便，無需輸入全部的信息就能查找到想要的結果，或者給出一堆結果讓用戶選擇。於是我便開始了模糊搜索演算法的探索。

從模糊搜索 1.0 到 3.0 的演算法迭代歷程 | 技術頭條

模糊搜索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」則所有在濟南掛牌的車牌號都顯示出來供用戶選擇。

從模糊搜索 1.0 到 3.0 的演算法迭代歷程 | 技術頭條

模糊搜索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;
}