网站快慢由什么决定,wordpress常用的插件推荐,自助建设wap网站,wordpress发布的文章今天开启一个新篇章——智能搜索与NLP。本篇章将由羸弱菜鸡小Q和大家一同学习与智能搜索相关的知识和技术#xff0c;希望能和大家一同学习与进步#xff0c;冲鸭#xff01;#xff01;这里首先区分两个概念#xff1a;搜索和检索检索#xff1a;数据库时代的概念#… 今天开启一个新篇章——智能搜索与NLP。本篇章将由羸弱菜鸡小Q和大家一同学习与智能搜索相关的知识和技术希望能和大家一同学习与进步冲鸭这里首先区分两个概念搜索和检索检索数据库时代的概念及将数据存入数据库有需要的时候进行查取。对结果的要求绝对精确比如我要在图书馆里找到所有出现“白马”字样的图书这里用到的就是检索。搜索互联网时代的概念人们将信息资源放在网上第三方将互联网的信息搜罗起来建立索引所以搜索更多是指基于问题相关性的信息收集方式。当我想知道“如何骑白马最帅”的时候这里就不能只罗列出现过“白马”字样的图书了毕竟骑白马的不一定是王子还有可能是唐僧 (╯-_-)╯~╩╩。所以这时候就需要真正的搜索了。闻道有先后术业有专攻。那我们就先来讲一讲关于检索的那些事儿。一、倒排索引の初体验让我来先进入一个例子我想要在《莎士比亚全集》中找到所有出现过“Brutus”和“Caesar”的章节一个办法就是从头到尾阅读这本书留意每一个出现“Brutus”和“Caesar”的地方。这种线性扫描就是一种最简单的计算机文档检索方式。那我现在想找出所有出现过“Calpurnia”章节难道还是需要对整本书重新阅读一遍嘛这样时间开销也太大了吧为了解决这个问题我们引入第一个核心概念——倒排索引。一个典型的倒排索引分为两部分词项词典和倒排记录表如下图所示每一个词项对应一个倒排记录一条倒排记录表示该词项所出现过的所有文档列表如“Brutus”在第1、2、4、11...篇文档中出现过文档列表的可以是无序的但是升序更有利于我们之后的高效检索下文会提到。易得建立一个倒排索引的时间复杂度是ON其中N是所有文档中单词的数量。图一 倒排索引的两个部分那么有了倒排索引后我们如何完成上诉检索任务呢先以一个简单的查询为例找到同时出现“Brutus”和“Calpurnia”两个单词的文档。具体步骤如下(1)在词典中定位Brutus;(2)返回其倒排记录表;(3)在词典中定位Calpurnia;(4)返回其倒排记录表;(5)对两个倒排记录表求交集如下图图二 求交集示意图在这里交集interp操作非常关键这是因为我们必须快速将倒排记录表求交集以尽快找到哪些文档同时包括两个词项。该操作有时也称为合并merge。经常刷题的同学一眼就看出来这不就是有序数组求交集嘛leetcode原题实锤了嗷leetcode 1213 原题easy难度⊙﹏⊙|||伪代码如下图三 merge伪代码思路就是用两个指针p1、p2分别指向两个倒排记录倒排记录是按升序排列的的头部如果两个指针指向的文档ID相同则将该文档放入结果集中并同时后移两个指针如果不相同则将指向文档ID较小的指针向后移动。a [1, 2, 3, 6, 9, 11, 45, 67]b [4, 6, 13, 45, 69, 98]
i j 0result []while i len(a) and j len(b): if a[i] b[j]: result.append(a[i]) i i 1 j j 1 elif a[i] b[j]: i i 1 else: j j 1print(result) #[6, 45]
假设两个倒排记录表的大小分别是x和y那么上述求交集的过程需要 O(xy)次操作。更正式的说法是查询的时间复杂度为O(N)。和之前“再读一遍书”的扫描方法相比同样是O(N)的复杂度但是该方法的中的N是文档数而前者的N是单词数假设平均一篇文档有1000个单词那么倒排索引的效率至少也提高了1000倍。二、构建倒排索引为获得检索速度的提升就必须要事先建立索引。建立索引的主要步骤如下。 (1)收集需要建立索引的文档如Doc1: Friends Romans countrymen.Doc2: So let it be with Caesar …(2)将每篇文档转换成一个个词条的列表这个过程通常称为词条化tokenization或者分词如Friends, Romans, countrymen, So, …(3) 进行语言学预处理产生归一化的词条来作为词项如Friends roman countrymen So …(4) 对所有文档按照其中出现的词项来建立倒排索引索引中包括一部词典和一个全体倒排记录表。建立索引最核心的步骤是将这个列表按照词项的字母顺序进行排序其中一个词项在同一文档中的多次出现会合并在一起。词典中同样可以记录一些统计信息比如出现某词项的文档的数目即文档频率这里就是指每个倒排记录表的长度。在最终得到的倒排索引中词项词典和倒排记录表都有存储开销。前者往往放在内存中而后者由于规模大得多通常放在磁盘上。因此两部分的大小都非常重要。那么倒排记录表一般利用哪一种数据结构进行存储呢由于有些词在很多文档中出现而另外一些词出现的文档数目却很少所以如果采用定长数组的方式将会浪费很多空间。对于内存中的一个倒排记录表可以采用两种好的存储方法1单链表singly linked list便于文档的插入和更新比如对更新的网页进行重新采集因此通过增加指针的方式可以很自然地扩展到更高级的索引策略。2变长数组variable length array的存储方式一方面可以节省指针消耗的空间另一方面由于采用连续的内存存储可以充分利用现代计算机的缓存cache技术来提高访问速度。额外的指针在实际中可以编码成偏移地址融入到表中。如果索引更新不是很频繁的话变长数组的存储方式在空间上更紧凑遍历也更快。三、布尔查询及性能优化在第一章中——找到同时出现“Brutus”和“Calpurnia”两个单词的文档这个任务其实就是一个布尔查询。布尔检索模型接受布尔表达式查询即通过AND、OR及NOT等逻辑操作符将词项连接起来的查询。在该模型下每篇文档只被看成是一系列词的集合。例如一个标准的布尔查询可以表示为Brutus OR CalpurniaAND NOT Caesar在很多情况下不论是由于查询语言本身的性质所决定还是仅仅由于这是用户所提交的最普遍的查询类型查询往往是由纯“与”操作构成的。正是因为这种特性的存在我们可以进一步优化查询速度。查询优化指的是如何通过组织查询的处理过程来使处理工作量最小。对布尔查询进行优化要考虑的一个主要因素是倒排记录表的访问顺序。那么哪种访问顺序具有最优性呢一些工程优化策略1对每个词项我们必须取出其对应的倒排记录表然后将它们合并。一个启发式的想法是按照词项的文档频率也就是倒排记录表的长度从小到大依次进行处理如果我们先合并两个最短的倒排记录表那么所有中间结果的大小都不会超过最短的倒排记录表这样处理所需要的工作量很可能最少。2在多个布尔检索合并中不是将倒排记录表合并看成两个输入加一个不同输出的函数而是将每个返回的倒排记录表和当前内存中的中间结果进行合并这样做的效率更高而最初的中间结果中可以调入最小文档频率的词项即该词对应的文档数目最小所对应的倒排记录表。算法如下图所示图四 利用中间结果进行合并3在很多情况下中间结果表可能会短一个甚至多个数量级。这时可以通过在长倒排记录表中对中间结果表中的每个元素进行二分查找也可以实现合并使得时间复杂度下降为O(alogb)其中a、b分别是2个倒排记录的长度。这里就有同学要问了之前的复杂度不是O(ab)这难道是下降嘛—— 因为中间结果表很短意味着a b的情况是可能发生的所以这里的线性复杂度并不一定要优于多项式对数复杂度。或者将长倒排记录表用哈希方式存储这样对中间结果表的每个元素就可以通过常数时间而不是线性或者对数时间来实现查找。4对于中间结果表合并算法可以就地对失效元素进行破坏性修改或只添加标记。破坏性修改更适合单链表结构的倒排记录表而添加标记更适合数组形式。好了通过这篇文章小Q和大家一起对倒排索引在检索中是如何使用的有了一个大体的认识。但搜索引擎之路道阻且长下一篇文章我们将会继续学习词项集合的确定和另外高阶版本的倒排记录表。 参考文献《信息检索导论 修订版》倒排索引优化 - 跳表 —— 博客园 海鸟
