00:00
Hello,大家好,嗯,之前我是讲过一些算法视频啊,宣传数之类的,然后今天给大家讲一下,就是我几个月前参加比赛,然后做了一个小项目,嗯,就是算法应用与实现,嗯,就是呃,我做那个项目名字叫基于串数的搜索引擎自动联想踹,它是一个数据结构啊,同时也个也是一个算法,它的中文名叫前缀数,嗯,这个这个这个东西它是用来干嘛的呢?就是比方说我们搜淘宝,嗯。淘宝。哎,怎么有点慢?算了,直接打王者吧。嗯,然后比方说我在搜。程序,它就会以程序为前缀出来一系列关键字,对吧,比方说我在搜,嗯。
01:03
衣服,它就会以衣服为前缀出来一些关键字,对吧,这个就是我我做的一个项目的实现的功能,然后项目预览的话,在这里,嗯搜索。对搜这个地址,这就是我,因为我给他部署到服务器上去了,所以说大家都可以访问。呃,然后在这里面搜一些我。搜一些指定的关键字,比方说H就hello对吧,Hello my sister,然后点一下可以补全。对吧,它就只有这个了,还有中文也可以比方说嗯,百度。就是这些关键字,然后你点一下就会补全啊,还有淘宝吧,嗯淘米游戏,嗯淘宝网。点一下就可以,对,就是这个功能,嗯,然后我就简要给大家讲述一下,首先我的源源码是放在get上面,然后大家如果有兴趣的话,可以从这上面下载,包括数据库文件我也放在里面了,就是这个search.circleql啊,我用的数据库是MYSQL啊,如果你觉得有用的话,别忘了给我给我个star啊,谢谢。嗯,然后就是下面这些东西,可以看一下效果图之类的,嗯,源码是这,好,那我就讲一下了,首先嗯,串数的话,前置技能肯定是串数嘛,因为你要对串数了解才可以,果对串数不了解的话,也可以看一下我的博客,里面有讲解串数的,在这里搜踹,然后就有下一页,一二,按照这个顺序来看一二,然后三四往上翻,三四先把这个学会了之后,然后才能。
02:54
应用,嗯,这个就是,首先这个算法的背景就是谷歌搜索啊,淘宝搜索的时候都会只要搜一部分关键字,它就会把这个关键字包含的一些关呃词条罗列出来,对,然后这个就是串数,这个就是串数的样子,就是说这个边,这个竖上的边才是纯它的字符节点,是不存字符的,然后以边构成的路径就是你这个关键词,比方说。
03:28
啊。比方说上面这个字符串集合就是in对吧,就是in色节点就表示说这个字符是结束了。你看比方说in,那么这个里面就是in,然后in再往下走,这也是个结束了,所以是in,还有就是int这样的一个路线。这个就是串数,嗯,大概介绍一下,就是串数长这个样子。啊,这些都是插入,这个都就大家自己写,如果不懂的话,可以看一下我这几篇文章,写的很详细,然后我就具体说一下,就是因为我做的是一个类似于外部界面吧,毕竟它对吧展示到外部上面了,嗯,首先肯定要有数据库,因为你没有数据库的话,你没办法做查询,嗯,给大家看一下我的数据库。
04:26
对,就这几个水库,然后我是把中文和英文分开了啊,后来我想了一下,感觉这样的做有点蠢,因为如果说一个词条它既包含英文又包含中文,那我到底是放到英文里面还是放到中文里面呢?嗯哼,所以我就感觉有点蠢,还是还我觉得可以不不分开,其实。其实大家如果改的话,可以把它改成不分开的,我是给它分开了。
05:00
嗯,就这样子,英文的话就放在这里面,然后中文就在这里面,就是你已经插入好的,比方说京就已京开头的有京东商城,京东快递,还有什么京沪好高铁,京东生鲜这些东西,对吧,就先把你的磁条都存到数据库里面去。然后就是在访问页面的时候呢,嗯,这里大家看一下我这个外部源码就是index点。Index JSP。啊,我这个项目是用GSP做的,就是呃,我首先。是访问index这个界面就是你当你输入。当你输入这个项目的时候,它就会自动进入index.jsp。但它会。立马转发到initial这个里面去,这个作用是。把我那个。数据库里面所有的词条。
06:00
都给它实例化成串数,就是这里是连接数据库,然后查询出来,查询出来之后呢。在这里对。就是把这个踹建立好,建立好之后放到里面去。放到塞里面,然后。再转发到四点点JSP。就是这里。然后就是大家看到那个界面就是search JSP,就是说所以你可能会发现,就当我输入RX。它会自动跳转到三级P。我默认的index.jsp,它也会自动跳转到4.sp,因为它经过一个转发的操作,它把数据库里面的所有东西都读取了一遍,然后再转发到你真正的界面来。然后我这里一些用的技术就是呃,GS嘛,GS。来获取你这个输入框当中有的字符,然后去查询。然后再显示出来,就是这样子。
07:02
也是调用了一个set,转发到search set里面去了。然后去查询一下,以这个为前缀。然后就是get try.get这个get方法就是说在这个TRY里面是用一个DFS的方法去获取所有以这个当前输入框为前缀的一些词条,全部都读取出来,然后放到list里面去,List放到list容器里面去,然后返回给。嗯。这里返回给这个list,然后把这个list里面所有的内容一个一个取出来,展示到下面,就是这样的一个流程,嗯。就是这样子的,然后因为这个项目其实重点并不在前端,所以说我一些前端GS我就不给大家讲了,如果大家有兴趣的话,可以直接去我的get上面把这个项目源码下载下来,然后自己自己调试,自己运行。这个项目最主要的是它的算法的部分,所以我就只讲了算法的部分,嗯,然后还有一个就是其实现在有这样的一个。
08:10
插件叫auto,就是嗯,Query插件自动补。就是只要在。在这里面搜这个就可以了,就可以找到。然后他的项目也是中国的差不多的。运行,然后。以这些为前缀,但是我不知道为什么,他这个为什么我搜A他B也出来了,可能是有问题吧。可能是查询的方式不一样之类的。就是都差不多。其实。所以说嗯,但是我这个毕竟是我自己手写的,嗯没有用它的这个方法,所以说还是有参考价值的,而且就是嗯,我做了一下对比,如果说嗯,我们查询词条对吧,我搜W,你可以有两种方法,一种方法就是像我这样子。用一个对象实例化,把它存储到赛里面去,然后读取出来,这就是比较快,但是你还有一种方法,就是说你每搜一个大,你每搜搜一个关键字,你就把它放到数据库里面去做一次查询,JDBC做一次查询,哦,C rud做一次查询,然后再给它显示出来,但如果你次数很多的话,就会非常的慢,因为你访问数据库的话还是要慢,要比我访问session要慢很多的。这里我做了一个测试,就是说你嗯执行1000次的情况下,输入同样内容,然后执行1000次,我踹1000次只花了六毫秒,而数据库模糊查询总共一千四花了这么多毫秒是吧,所以数据库其实是非常慢的,如果用这种方法就很快,嗯,大概就是这样子,但是我想到一个问题,就是我这个项目其实还有一点缺陷,就当我的我现在数据很少的,但是当我数据很多的时候,它直接全部到。
10:00
筛选里面,那筛选或为报呢,这也是一个问题,所以我想嗯,可不可以用一个limit,就是每次查询的时候限制一下,嗯,限制它前几条进行,出现多的,我不我不是全部给大家展现出来,那么这个的话,嗯,到底哪几条呢?就要有个排序的问题了,这个排序的话可以比方说再加一列。这个关键字设为就是查询次数,就是说用户查询多的就排名第一,用户查询少的就排到最后,然后每次展现的时候就让他从多到少来给用户展现,这样的话。嗯,比较感觉会比较好,但是因为我没有那么多时间,就没有写。嗯。嗯,大概就这么多了,看一下就是。这个就是。把我的所有的都insert到我的那个串数里面去,把所有的关键字都insert串数里面去,然后当串建好了之后,这个图就是这样子的,这个数就是这样。
11:13
就是这样,嗯,它中间这个红色节点就是开始节点,比方说淘宝网就是淘宝网,它是一个词条,然后淘宝网天猫又是个词条,因为黑色节点就是终结节点嘛,然后比方说我再走一条就是ha,呃,Hat,哦哦,这是空格,这空格的意思,空格ha对吧,What happened,嗯,它是也是一个词条,然后就是哦,对了,还有一点就是这个关于。数据存储的方法就是TRY的话,我是用什么方法来存呢?我每嗯,我每个节点都是用的map来存的,是一个string对应一个node,就是说这string是它的边,Node是它节点,就是说我当前node经过这个string string到达下一个node,我是用的map来存的,这也是很关键的一点,因为啊,你不可能用数组去存,你速度的话,你不知道开多大对吧,而且你开的话会浪费空间啊,因为你固定你肯定要开固定大小内容,所以你要浪费空间,并且因为我这边中文也有,英文也有,所以你数组。
12:32
呃,肯定要开很大,因为有多少个中文字符,你就要开多大,然后有多少个英文字符,呃,你要把中文字符英文字符的个数全部加起来,英文字符还好,英文字符就26个字母嘛,啊,再加个空格27个对吧,但是中文字符中文就太多了。呃,中中文字不太多了,所以说你用数组的话是不行的,必须要用map。这是一个关键点。嗯,大概就这么多吧。
13:01
好啊,还有一点就是我这个项目确实没什么点赞,我也不知道为什么,就我感觉我做的形式还是挺好的。但是就十八十八个star,但是我我在就是备战考研期间,发现我这个考研高数复习笔记。每一天至少每至少每天都有人点赞,点了已经90多个赞了,这有点我觉得有点那个有点夸张了,怎么好的项目有人点赞,这种笔记就很多人点赞的,嗯,大概就这么多了,然后就是欢迎大家关注我的这个博客,博客地址在这里,然后这里面也有一些我的一些做的项目,比方说点这关于,然后里面有啊,我的一些开源项目啊,比方知识脚本语言和我研究的一个master net,就是说一个剪辑神经网络,用来做图片分类的剪辑神经网络,这个大家有兴趣的话可以看一下,然后并嗯,如果觉得有意思的话,可以给我个star,嗯。
14:02
这是就是自制脚本语言,就是学完编译原理以后做的这个大家有有兴趣的话自己可以看一下。嗯,今天大概就讲这么多了。应该没有忘,好,那就谢谢大家观看。
我来说两句