用C语言做模糊搜索

螢火虫007 2018-08-14

展开全文

作者

De掉所有bug

文末「阅读原文」查看原文出处。

如需转载，请联系原作者授权。

绪论：本文所提到的模糊搜索是指输入不完整的关键词即可查询到对应的全部准确结果。

例如：输入“天”即可将所有姓名中带有“天”字的人搜索出来；输入“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<>
    N2+=i;
 
    /*计算连续子串的个数*/
    //i控制子字符串的长度
    //j控制赋值
    //k控制新的线性结构b的下标
    //l控制子数组的首项在原数组中的位置
    //m控制即将用作赋值的str的下标
    Element *b=malloc(sizeof(Element)*N2);
    for(i=1;i<>
    {
        l=0;
        /*while循环内为给一个子字符串数组赋值*/
        while(1)
            {
            m=l;
            for(j=0;j<>
            {
                b[k].son[j]=str[m];
                m++;
            }
            l++;
            k++;
            if(m==N1)
                break;
            }
    }
 
    //挨个比对
    for(i=0;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<>
    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));
}