当前位置:首页 > 短网址资讯 > 正文内容

从词典查词到文本检索

www.ft12.com8年前 (2017-07-23)短网址资讯2356

十一假期大家过的还好吗?时间过得真快,距离上一次跟大家聊技术已经过了快三周了。老王很开心今天又能跟大家一起扯淡了,用一句通俗的话讲就是:老王想死你们了!今天准备跟大家聊的,乃是大名鼎鼎的文本检索技术。也就是大家天天都在用的“百度一下”。

 

为了简单,我们先从单词搜索开始,也就是类似于百词斩的查词功能。

 



想必大家或多或少都用过类似的功能,就是我们在查词框里输入几个字母或者中文,然后就能查找出我们想要的单词。那这个算法是如何实现的呢?其实有很多中方法,我们接下来一一介绍。这里为了更方便描述,我们就只介绍搜索英文的情况,中文含义的搜索其实类似,就不混着讲了~

 

在开始之前,我们先设定一个全局变量:假定有一个词典DICT,含有的单词:[good, bad, god, sad]

 

方法一:暴力法

 

最容易让人想到的方法,就是写一个for循环,然后一个个的比较,看是否匹配,伪代码大概就是这样:

 



我们遍历词典中所有的单词,让每一个单词和我们待搜索的单词进行比较,看看他们之间的相似度,比较完了以后,就按照相似度排序,越像的排的越靠前。最后,我们将TOP-N的数据返回给用户。

 

这里面最关键的一个函数,就是compare。我们怎么比较两个单词的相似度呢?一般采用LCSLongest Common Subsequence,最长公共子序列)算法。这个算法用来比较两个字符串含有的最多的相同字符,比如,samesome最长的公共子序列就是sme(same,some)。这个算法是一个动态规划算法,挺有意思,以后有时间可以专门跟大家做一个分享。

 

上述的查找算法虽然很精确,但是却有一个致命的问题,就是算法复杂度太高。如果我们有几万个单词,那么每次用户查询都要做一个几万次的for循环,然后循环里面还要做一次相似度比较,效率实在太低。

 

那有没有更好的方法呢?我们接着往下看。

 

方法二:Trie树(字典树)

 

想必好多朋友都听说过这个大名鼎鼎的字典树。老王模模糊糊的记得,当年去百度的时候,自己写了一个反作弊的匹配算法就用到了这个数据结构。那这个东东是怎么工作的呢?

 



初始化的时候,我们构建一个根节点为空的树,然后我们将字典DICT中的单词,一个个的加入到这棵树中,单词的每一个字母挂接到对应的层次下,比如:good,就将g挂在root结点下,o挂接到g下…… 如此重复。便形成我们上面看到的这棵树。从root结点延任意一条路劲走到叶结点,都能形成我们字典中的单词。

 

那我们搜索的时候怎么做呢?

 

比如当用户输入go的时候,我们就从root结点开始,沿着这棵树一直往下走。依次走过root->g->o这三个结点。接下来他有两个子节点,我们就将这两个子节点对应的单词返回给用户,即:godgood

 

大家看看,这种算法的复杂度一下就下降了,不用再做遍历。但是这个算法有一定的局限性:就是他只能做前缀匹配,也就是说他只能从开始做匹配,如果我们要匹配单词中间的一部分或者是模糊匹配,就很难实现。

 

不过,这种算法也可以做一些简单的改进,从而满足我们更多的需求。

 

我们在建树的时候,可以可以把每个单词做一下拆分,将每一个字符都作为起始字符进行建树。比如:good可以拆成4个单词:good, ood, od, d。然后分别将这些所谓的单词构建成Trie树。这样,我们即使搜索单词中间一部分,也能出对应的结果,就不需要强制用户从第一个字母开始输入。

 

那有朋友一定会问,这个规模会膨胀多少啊?我们只需要简单计算一下就能得出。比方说,我们平均每个单词的长度为10(老王大概统计了几万个单词,平均长度大概是8.4左右),那么我们所有需要构建的单词数就是DICT中单词数的10倍。如果我们常用单词约3万个,那么就只需要构建一棵大约30万个单词的树(这个数量级还是可以接受的)。

 

不过,即使通过上面的改进,我们还是比较难以实现模糊匹配的功能。比如,我们输入gd,字典树就不能检索出good或者god

 

那还有没有其他的方法呢?

 

方法三:倒排索引

 

想必好多朋友对这个词都耳熟能详了吧。没错,这个算法就是我们现在检索用的最多的工业界方法。这个算法用了一个很简单的思想,解决了海量文本的索引问题。也就是百度、google做的事情。那具体怎么做的呢?跟着老王一起往下看吧。

 

我们之前讲的第一种方法(暴力法),对于单词没有任何预处理,数据的组织完全是按照单词本身去组织的,而没有按照用户的输入去组织,所以每次查询来了,都要重复的计算。而第二种方法(Trie树),则是做了一定的预处理,将单词拆分成字母,一定程度上按照用户输入的顺序来组织。所以,每次用户输入请求的时候,只需要做很小一部分计算,就可以得到结果。

 

那根据以上两种方式的启发,我们如果要很好的满足用户的需求,就应该将我们已有的数据按照用户的输入来组织,经过这样的预处理以后,等用户查询来的时候,我们就不会重复的去做计算了,对吧~

 

那倒排索引的思想也基本是这样:我们将每个单词都拆解成字母,然后根据用户输入的字母,将含有这些字母的单词都列举出来,然后看谁更符合用户的输入,就将谁返回。来看下图:

 



我们将每一个单词都拆解成单个单个的字母,然后将含有相同字母的单词挂接到对应的字母链上。如上图:bad就可以拆解成bad三个字母,然后我们将bad这个单词分别挂接到字母bad所在的链上。同理,对于其他单词也是。

 

这样,当用户输入b的时候,我们一下就能找到bad。如果用户输入bd,我们就可以将b链和d链的数据进行合并,将最符合条件的bad先输出,然后再输出其他几个有可能是结果的备选单词。

 

怎么样,是不是很简单啊。是的,这就是传说中的倒排索引。之所以称做倒排,是相对于bad->b-a-d这样的正排索引而言。

 

有了上述这个基本的逻辑以后,我们剩下的工作就是需要做结果优化。

 

1、多路归并计数。

 

比如,我们输入bd,那对于用户预期而言,结果bad肯定要比god要好,因为bad含有bd两个关键字母,而god只有一个d。所以,我们要将检索的结果进行合并,看谁含有的关键字母更多,就应该往前面排。

 

这里用到了一个关键技术,就是多路归并。在算法和数据结构的课上,大家应该至少听说过这个算法。老王就不详细的来讲了。(记得当年刚到百度的时候,就参加了一个内部搞的一个算法优化大赛,做的就是多路归并算法优化,老王还得了前几名,哈哈哈~

 

2、增加偏序关系。

 

上面讲了多路归并,那是不是出现字母越多,就应该排在越前面呢?我们看一个例子:当我们字典里有[god, dog, dot]这三个单词的时候,如果用户输入dog这三个字母的时候,根据上面多路归并的结果,god匹配3次,dog3次,dot2次,按道理说,我们就应该按照字典里的顺序输出god-dog-dot。但是,实际上比较好的一个结果可能是:dog-dot-god。为什么呢?因为用户输入的顺序很!重!要!

 

因此,我们除了要检查字母个数,还需要增加偏序关系,用于记录字母出现在单词中的位置。匹配结果的时候,要根据用户的输入顺序进行排序。具体实现的时候,我们可以在倒排拉链的时候,记录一下位置,最后归并的时候,对位置做一个打分,排序的时候,加入位置因素。

 

好了,以上讲了两种优化结果的方法。其实,还有很多地方要根据实际业务去优化,我们这里就不细讲了(不然这篇文章的字数真的就要过万了)。

 

那上面这个倒排索引的方法,是不是真的就很好了呢?如果你真的去写写代码,就会发现,还有一个巨大的坑儿在等着你!

 

对于a,e,i,o,u这几个元音字母而言,因为绝大多数单词都含有他们,所以他们的拉链会非常的长。如果有用户搜索a,那可能你的程序在很长时间内都没办法出结果。那怎么办呢?

 

这个时候,我们就需要用到分布式了。我们可以将所有单词,随机的拆分成多个组。比如我们有1万个单词,拆分成10组。这样每一组单词,就只有大概1000个。比方说,原来含有字母a的单词大概有7000个,这样拆分以后,每个组里面就只有700个左右的单词含有字母a。因此每个组里面,字母a的拉链就只有700个左右的元素。

 

接下来,我们将每个组的单词放到一台服务器上,搜索的时候,每台服务器都进行检索。完成后,将TOP_N的结果上报给一个合并服务器,由他再做一次合并。这样,我们是不是就可以规避元音字母拉链过长的问题了呢。

 



好了,以上就是我们关于单词检索的算法。大家觉得怎么样呢?

 

除了单词搜索,我们在现实中还经常用到搜索好友、搜索文本内容等东东,对应的就是微信的好友搜索和百度的文本搜索。那这些东东在基础方法上都是上述的一个思想:元素拆分 + 倒排索引 + 合并优化。只不过,在每一个维度上都做了很多优化。比如:文本搜索中,整篇文章就像是一个单词,而文章中的词组就像是单词的字母,用词组作为倒排拉链的基础元素。那最难的就是分词,特别是中文分词,就是一个专门的课题。如果分词分的不好,那么检索的结果就会很差。以后找机会,老王也可以跟大家一起聊聊分词这个话题。

 

而倒排索引和结果合并,也是有很多地方需要优化的。比如,实时性强的文本(比如新闻),就需要按时间顺序来建立排序的索引。对于广告而言,可能价格就更重要。

 

好了,今天的内容大家都看懂了嘛?如果对老王的文章感兴趣,就请继续听老王扯淡吧。老王将文章做了分类,放到了自己搭的网站上,大家可以去上面看看www.ft12.com

扫描二维码推送至手机访问。

版权声明:本文由短链接发布,如需转载请注明出处。

本文链接:https://www.ft12.com/article_336.html

分享给朋友:

相关文章

网站防御cc攻击的方法和突破技巧!

最近FT12短网址经常遭到CC攻击,早在前两个月的时间,我的短链接遭到CC攻击,大概流量在7G左右,7G的CC流量攻击算是非常大的了,那么我们如何防御CC攻击呢,另外CC攻击又是怎么一回事呢?CC攻击是什么CC攻击是通过大量的IP同时访问一...

三江购物再设子公司 或阿里加码新零售布局

【FT12短网址资讯】7月18日消息,据亿邦动力网获悉,7月17日晚间,三江购物发布公告称,为满足业务发展需要,三江购物全资子公司浙江浙海华地网络科技有限公司(以下简称“浙江浙海华地”)拟以自有3000万元人民币投资设立全资子公司杭州浙海华...

短网址数据库InnoDB的快照读,到底和什么相关?

InnoDB是非常适合短网址业务的存储引擎,其多版本并发控制(Multi Version Concurrency Control, MVCC),快照读(Snapshot Read)机制,能够通过读取回滚段(rollback segment)...

FT12短网址详解亚马逊、美团点评和京东的业绩

FT12短网址详解亚马逊、美团点评和京东的业绩

巴菲特曾经坦言看不懂亚马逊,招致错失如今市值已高达4610亿美金的亚马逊(截止2017年5月16日)。认真看亚马逊的收入和净利润,能够看出从2007年开端的表现逐步开端呈现分化。收入增长势不可当,2014-2016年,连续打破800、100...

开着市值2000亿的公司,却跑去卖猪肉,他说赚钱只是顺便的事情…

但凡接触过互联网行业的,无人不识网易和短网址。作为一个优秀的互联网公司,它的作品也向来让人满意。率先推出了中文全文检索、免费邮件系统、网上虚拟社区等,还研发了一款史诗级的国产网络网游。十多年经久不衰的《梦幻西游》,《大话西游》,《短链接》等...

百度:我们不造车,Apollo只是人工智能的搬运工

百度:我们不造车,Apollo只是人工智能的搬运工

[ FT12短网址 ] 百度在Apollo生态中承担的角色更像是供应商,但是与传统零部件供应商不同的是,百度将不主要依赖于车企采购产品或技术的方式盈利,百度的盈利模式还有进一步的想象空间,而且在百度内部也还没完全考虑成熟...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。