使用C語言實現模糊搜索功能

2020-01-26 13:39:38

字體：大中小

來源：轉載

供稿：網友

例如：輸入“天”即可將所有姓名中帶有“天”字的人搜索出來；輸入“0809”即可將所有ID中帶有“0809”片段的人搜索出來。

這種搜索技術被廣泛應用于各大有查詢功能的軟件，為用戶提供了極大的方便。在眾多的QQ/微信好友中，輸入想要查找的聯系人的姓名的一部分即可查找到該聯系人，是不是很方便呢？在excel中，即使只記住了查詢對象的幾個字，也能夠通過這種查找方式查詢到對應的對象，是不是彌補了你的健忘癥呢？

實現模糊搜索算法的思路：輸入的關鍵詞即為一個字符數組（字符串），本文將以"abcdef"這個字符串為例。要想完成對片段的查詢，不能僅僅從前往后比對，也不能僅僅從后往前比對，而是要將所有的片段都進行一遍比對。這就要求要將字符串的所有連續子片段都找出來存放到一個新的線性結構中，通過對新線性結構的遍歷并使用字符串比較函數strcmp進行模糊搜索。

那么"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。

以下函數用作判斷是否符合篩選條件，其中key為關鍵詞。

//模糊搜索判斷是否符合篩選條件int result_mohu(const gchar* 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;}

若返回值f=1則表示符合篩選條件，即查詢對象含有包含關鍵詞的片段。最為關鍵的循環就是按照子字符串的長度從1到N1(查詢對象字符串的長度)。

以下片段為遍歷代碼，可看可不看，核心算法都在上面。注：博主實現模糊搜索的環境是linux系統下的gtk開發。

//按學號查找界面的<查找>void on_button_idsearch_clicked(GtkObject* widget,gpointer user_data){ int i; int f=0; GtkTreeIter iter; //獲取搜索關鍵字 const gchar* keywords = gtk_entry_get_text(entry_search_id); gtk_list_store_clear(liststore2); for(i=0;i<size1;i++)  if(result_mohu(keywords,stu1[i].id)==1)   {        gtk_list_store_append(liststore2,&iter);    gtk_list_store_set(liststore2,&iter,0,stu1[i].no,-1);    gtk_list_store_set(liststore2,&iter,1,stu1[i].id,-1);    gtk_list_store_set(liststore2,&iter,2,stu1[i].name,-1);    gtk_list_store_set(liststore2,&iter,3,stu1[i].math,-1);    gtk_list_store_set(liststore2,&iter,4,stu1[i].c_language,-1);    gtk_list_store_set(liststore2,&iter,5,stu1[i].daolun,-1);    gtk_list_store_set(liststore2,&iter,6,stu1[i].english,-1);    gtk_list_store_set(liststore2,&iter,7,stu1[i].pe,-1);    gtk_list_store_set(liststore2,&iter,8,stu1[i].history,-1);    gtk_list_store_set(liststore2,&iter,9,stu1[i].daoyuan,-1);    gtk_list_store_set(liststore2,&iter,10,stu1[i].banzhuren,-1);    gtk_list_store_set(liststore2,&iter,11,stu1[i].score_classmate,-1);    gtk_list_store_set(liststore2,&iter,12,stu1[i].sum,-1);    f=1;   } if(f==0)  gtk_widget_show(GTK_WIDGET(window_noresult));}

最后給大家看一下實驗結果：