当前位置：首页 > 编程日记 > 正文

一文看懂模糊搜索1.0到3.0的算法迭代历程

编程日记 2025-01-09 17:40:00

640?wx_fmt=jpeg

参加 2019 Python开发者日，请扫码咨询 ↑↑↑

作者 | 宋广泽

责编 | 郭芮

来源 | CSDN（ID：CSDNnews）

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

640?wx_fmt=png

模糊搜索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”则所有在济南挂牌的车牌号都显示出来供用户选择。

640?wx_fmt=jpeg

640?wx_fmt=png

模糊搜索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了。

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

640?wx_fmt=png

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

640?wx_fmt=png

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

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

（本文为 AI科技大本营转载文章，转载请微信联系 1092722531）

推荐阅读：

Google首页玩起小游戏，AI作曲让你变身巴赫
特斯拉起诉小鹏汽车员工窃取商业机密，何小鹏回应
提升效率，这十个Pandas技巧必不可少！
超常用的Python代码片段 | 备忘单
小米“祭出” AIoT 神器！| 技术头条
工作量不断增加的微软Azure，正缩小与亚马逊AWS的差距
硬核接亲！程序员被新娘要求现场写代码，结果万万没想到……
理工男的网红生意, 6000万月活50万条日更的背后, 内容链还能这样操作？
曝光！月薪 5 万的程序员面试题：73% 人都做错，你敢试吗?

640?wx_fmt=png

❤点击“阅读原文”，查看历史精彩文章。

https://www.dkcj.cn/info/35562.html

一文看懂模糊搜索1.0到3.0的算法迭代历程

相关文章：

【linux】shell中浮点数运算的加、减、乘、除

页面加载和解析流程

作为程序员应有10项权利

【Qt】QtCreator中自动补全注释

Java内存模型与线程

Google用更少标签生成图像，还提出一个用于训练评估GAN的库

视频用户行为及推荐系统评价KPI-部分

【linux】用户和组的管理：添加、修改、删除（useradd usermod userdel groupadd groupdel）

ping命令工具：同时ping多个IP

顶会论文9篇，又斩获百度奖学金！哈工大NLP“新生代”正崭露头角

医院数据中心机房建设资料汇总（31篇）

【linux】CentOS启动后网络自动配置过程

web存储中cookie、session区别

李沐团队新作Gluon，复现CV经典模型到BERT，简单好用 | 强烈推荐

中国科学技术大学中科大(USTC)UBUNTU源Linux镜像站IPV4/IPV6

深度分析蔡徐坤的百万流量数据，揭底哪些是假的！

【Linux】延时函数sleep、usleep、nanosleep、select、pselect的比较

特斯拉解锁对汽车电池容量的软件限制，以帮助用户逃离飓风危险

nginx安装问题 1

【Qt】使用QPalette设置按钮颜色时，不生效

Swagger 生成 PHP restful API 接口文档

FPGA技术的未来发展：谁与AI平分秋色

一体化设计让容灾变简单

深度研究自然梯度优化，从入门到放弃 | Deep Reading

【Qt】QtCreator中关于Style Plugin Example没有效果的修改方法

最大公约数和最小公倍数的欧几里得算法

如何查看CISCO FWSM上ACL分区的空闲资源

强烈推荐一款Python可视化神器！

【Qt】QIcon::fromTheme：从系统主题中获取图标

检验EIGRP