新手学做免费网站软件好,网络营销培训班哪家好,工装设计案例网站,天水网站开发技术招聘一只小狐狸带你解锁NLP/ML/DL秘籍作者#xff1a;QvQ老板#xff5e;我会写倒排索引啦#xff01;我要把它放进咱们自研搜索引擎啦#xff01;我呸#xff01;你这种demo级代码#xff0c;都不够当单元测试的#xff01;嘤嘤嘤#xff0c;课本上就是这样讲的呀?!来来QvQ老板我会写倒排索引啦我要把它放进咱们自研搜索引擎啦我呸你这种demo级代码都不够当单元测试的嘤嘤嘤课本上就是这样讲的呀?!来来带你见识一下工业级搜索引擎里的倒排索引是怎么优化的!前言首先回顾一下构建倒排索引的几个主要步骤(1) 收集待建索引的文档(2) 对这些文档中的文本进行词条化(3) 对第2步产生的词条进行语言学预处理得到词项(4) 根据词项对所有文档建立索引。 可以看到上诉过程中非常重要的一步就是获得词项那么词项是什么又是怎么获得的呢词项集合的确定在确定词项前我们需要明确三个概念词条一段文本中有效词的子序列其中每个子序列称为一个词条。词条类相同词条构成的集合。词项一个词项指的是在信息检索系统词典中所包含的某个可能经过归一化处理的词条类。词项集合和词条集合可以完全不同比如可以采用某一个分类体系中的类别标签作为词项。当然在实际的信息检索系统中词项往往和词条密切相关三者关系如下下面让我们一起学习这几者是如何一步步变化得来的。1.1 词条化词条化过程词条化的主要任务就是确定哪些才是正确的词条。比如对于简单的句子将字符串进行拆分并去掉标点符号即可。然而上面的例子仅仅代表的是一种最简单的情况。实际上即使对于单词之间存在空格的英文来说也存在很多难以处理的问题。比如英文中的上撇号“’”既可以代表所有关系也可以代表缩写应当在词条化过程中究竟应该如何对它进行处理?参考下面的例子:对其中的“ O’Neill” 来说词条化的结果可能有如下几种形式可以选择那么到底哪一种才正确 对于可能的各种拆分策略来说最后的选择结果会决定哪些布尔查询会被匹配上、哪些不会被匹配上。给定查询neill AND capital上述五种拆分策略中有3种会被匹配上即第1、4、5种情况。而如果给定查询o’neill AND capital则在没有对查询进行任何预处理的情况下上述策略中只有一种能匹配上。不管是输入布尔查询或者自由文本查询人们总是希望对文档和查询进行同样的词条化处理这往往通过采用相同的词条化工具来实现。这样做能够确保文本与查询中的同一字符串序列的处理结果相一致。在词条化的过程中需要注意以下几个问题1对大多数语言特别是一些特定领域的语言来说往往有一些特定的词条需要被识别成词项如编程语言“C”和“C#”、“B-52”之类的飞行器名字或者叫“M*A*S*H”的电视秀节目等等这时候就不能简单的去掉文本中的符号了这里通常需要建立专有名词字典来解决。2字符序列类型包括邮件地址如jblackmail.yahoo.com、URL如http://stuff.big.com/new/specials.html、IP地址如142.32.48.231和包裹追踪号码1Z9999W99845399981等等。一种做法是不对包括货币量、数字、URL等在内的词条进行索引这是因为如果对这些词条进行索引则会显著扩大索引的词汇量。当然这样做会对用户的搜索产生一些限制。比如人们可能会在程序缺陷bug库中搜索错误发生的行号但是经过上述处理之后的系统显然不能返回正确结果。如果这类数据需要词条化那么利用正则是一个不错的办法。3即使根据空格进行拆分有时也会将概念上本应该看成单个词条的对象分开比如一些名称San FranciscoLos Angeles、外来短语au fait或那些书写时可分可合的复合词white space vs whitespace。其他的例子还包括电话号码[800234-2333]、日期Mar11,1983等。如果在空格处拆分这些对象可能会导致很差的检索结果比如输入York University约克大学时会返回包含New York University纽约大学的文档。连字符和空格甚至会互相影响。这种情况就和中文文本中分词类似了。4对于一些主要的东亚语言如汉语、日语、韩语和泰语等来说由于词之间并不存在空格所以问题更加严重。分词的方法包括基于词典的最大匹配法采用启发式规则来进行未定义词识别和基于机器学习序列模型的方法如隐马尔可夫模型或条件随机场模型等后者需要在手工切分好的语料上进行训练分词作为NLP领域一个非常重要的研究内容我们后面会专门独立一章来介绍分词常用算法ヾ(◍°∇°◍)。由于存在多种切分可能上述分词方法都有可能导致错误的切分结果因此永远不能保证只能得到一个完全一致的唯一切分结果。另一个解决方法则摒弃了基于词的索引策略而采用短字符序列的方法如字符的k-gram方法。这种方法并不关心词项是否会跨越词的边界。该方法之所以能够引起人们的兴趣主要有以下3个原因:第一一个汉字更像是一个音节而不是字符它往往具有语义信息;第二大部分词都很短最常见的汉语词长度是2个字;第三由于缺乏公认的分词标准词的边界有时也很难确定。1.2 去停用词某些情况下一些常见词在文档和用户需求进行匹配时价值并不大需要彻底从词汇表中去除。这些词称为停用词stop word。一个常用的生成停用词表的方法就是将词项按照文档集频率collection frequency每个词项在文档集中出现的频率从高到低排列然后手工选择那些语义内容与文档主题关系不大的高频词作为停用词。停用词表中的每个词将在索引过程中被忽略。 英文常用停用词表不对停用词建立索引一般情况下不会对系统造成太大的影响比如搜索时采用the或by进行查询似乎没有什么意义。但是对于短语查询来说情况并非如此比如短语查询President of the United States中包含两个停用词但是它比查询President AND“United States”更精确。如果忽略掉to那么flights to London因为这里的to并不是以介词的身份出现的意义将会丢失。搜索Vannevar Bush的那篇经典文章As we may think时如果将前3个单词都看作停用词那么搜索将会很困难因为系统只返回包含think的文章。更为严重的是一些特定的查询类型会受到更大的影响。比如一些歌名或者著名的诗歌片段可能全部由常用的停用词组成如To be or not to beLet It BeI don’t want to be等。1.3 词条归一化将文档和查询转换成一个个的词条之后最简单的情况就是查询中的词条正好和文档中的词条相一致。然而在很多情况下即使词条之间并不完全一致但实际上人们希望它们之间能够进行匹配。比如查询USA时我们希望能够返回包含U.S.A.的文档。词条归一化token normalization就是将看起来不完全一致的多个词条归纳成一个等价类以便在它们之间进行匹配的过程。最常规的做法有以下两种1隐式地建立等价类每类可以用其中的某个元素来命名。比如在文档和查询中都把词条anti-discriminatory和antidiscriminatory映射成词项antidiscriminatory,这样对两个词中的任一个进行搜索都会返回包含其中任一词的文档。这种处理方法的优点在于:一方面等价类的建立过程是隐式的不需要事先计算出等价类的全部元素在映射规则下输出相同结果的词项一起构成等价类集合;另一方面仅仅构建“去除字符”这种映射规则也比较容易。2显示建立等价类维护多个非归一化词条之间的关联关系。该方法可以进一步扩展成同义词词表的手工构建比如将car和automobile归成同义词。这些词项之间的关系可以通过两种方式来实现。第一种常用的方式是采用非归一化的词条进行索引并为某个查询词项维护一张由多个词组成的查询扩展词表。当输入一个查询词项时则根据扩展词表进行扩展并将扩展后得到的多个词所对应的倒排记录表合在一块如下图一。另一种方式是在索引构建时就对词进行扩展如下图二。比如对于包含automobile的文档我们同时也用car来索引同样包含car的文档也用automobile来索引。图一图二另一方面由于两个关联词的扩展词表之间可以存在交集但不必完全相同所以上述两种方式相对于隐式建立等价类的方法来说更具灵活性。这也意味着从不同关联词出发可以进行不对称的扩展。下图出了一个例子。该例子中如果用户输入windows那么我们希望返回包含Windows操作系统的文档。但是如果用户输入window虽然此时可以和小写的windows相匹配但是不太可能会和Windows操作系统中的Windows相匹配。隐式建立等价类或查询扩展的使用幅度仍然是个开放的问题。适度使用绝对没错但是过度使用很容易会在无意间造成非预期的扩展结果。例如通过删除U.S.A.中的句点可以把它转化成USA由于在首字母省略用法中存在这种转换模式所以上面的做法乍看上去非常合理。但是如果输入查询C.A.T.返回的很多包含cat的文档却肯定不是我们想要的结果。接下来我们将给出一些在实际当中会遇到的词条归一化问题及其对策1重音及变音符号问题英语中变音符号的使用越来越少见尽管如此人们很可能希望cliche和cliché或者naive和naïve能匹配。这可以通过在词条归一化时去掉变音符号来实现。而在许多其他语言中变音符号属于文字系统的常规部分不同的变音符号表示不同的发音。有时候不同单词之间的区别只是重音不同。比如西班牙语中peña的意思是“悬崖”而pena的意思却是“悲哀”。然而关键并不是规范或者语言学问题而是用户如何构造查询来查找包含这些词的文档。2大小写转换问题大小写转换case-folding问题的一个一般处理策略是将所有的字母都转换成小写。这种做法通常的效果不错比如这样可以允许句首的Automobile和查询automobile匹配。对于Web搜索引擎来说这种做法也很有好处因为大多数用户输入ferrari时实际想找的是Ferrari法拉利车。3英语中的其他问题英语中还存在一些独特的归一化做法。比如用户希望将ne’er和never、英式英语的拼写方式colour和美式英语的拼写方式color等同起来。日期、时间和其他类似的对象往往以多种形式出现这给归一化造成了额外的负担。人们可能希望将3/12/91和Mar.121991统一起来。但是要正确处理这个例子将会十分复杂因为在美国3/12/91指的1991年3月12日Mar.12,1991而在欧洲却指的是1991年12月3日3Dec.19911.4 词干还原和词性归并出于语法上的要求文档中常常会使用词的不同形态比如organize、organizes和organizing。另外语言中也存在大量意义相近的同源词比如democracy、democratic和democratization。在很多情况下如果输入其中一个词能返回包含其同源词的文档那么这样的搜索似乎非常有用。词干还原和词形归并的目的都是为了减少屈折变化的形式并且有时会将派生词转化为基本形式。词干还原通常指的是一个很粗略的去除单词两端词缀的启发式过程并且希望大部分时间它都能达到这个正确目的这个过程也常常包括去除派生词缀。词形归并通常指利用词汇表和词形分析来去除屈折词缀从而返回词的原形或词典中的词的过程返回的结果称为词元。这两个过程的区别还在于:词干还原在一般情况下会将多个派生相关词合并在一起而词形归并通常只将同一词元的不同屈折形式进行合并。词干还原或词形归并往往通过在索引过程中增加插件程序的方式来实现这类插件程序有很多其中既有商业软件也有开源软件。 基于跳表的快速合并算法上一章我们讲解了倒排记录表的基本合并算法:同时在两个表中遍历并且最后算法的时间复杂度为记录表大小的线性函数。假定两个表的大小分别是m和n那么合并过程有Omn次操作。很自然的一个问题就是我们能否做得更好也就是说能否在亚线性时间内完成合并过程下面我们将看到如果索引变化不太频繁的话那么答案是肯定的。如果待合并的两个倒排表数据量很大, 但是交集很少时, 会是什么情况呢?[1, 2, 3, 4, 5, ... 10001, 10005]
[1, 10001, 10008]
如果对这两个做合并操作, 最后的交集结果只有 [1, 10001] 2个元素, 但是却要做10001次移动和比较操作, 所以肯定有什么办法来优化这一点. 可能你已经想到了, 我们做了这么多无用比较, 是因为我们每次指针向前移动的步子太小了点, 如果我们在每次比较后向前多移动一点, 可以忽略很多无用的操作. 这就是跳表的思想.跳表skip list—— 在构建索引的同时在倒排记录表上建立跳表如下图所示。跳表指针能够提供捷径来跳过那些不可能出现在检索结果中的记录项。构建跳表的两个主要问题是:在什么位置设置跳表指针?如何利用跳表指针进行倒排记录表的快速合并?我们以上图为例来先考虑快速合并的问题。假定我们在两个表中遍历一直到发现共同的记录8为止将8放入结果表中之后我们继续移动两个表的指针。假定第一个表的指针移到16处而第二个表的指针移到41处两者中较小项为16。这时候我们并不继续移动上面的表指针而是检查跳表指针的目标项此时为28仍然比41要小因此此时可以直接把上表的表指针移到28处这样就跳过了19和23两项。基于跳表的倒排记录表合并算法有很多变形它们的主要不同可能在于跳表检查的时机不一样。我们再考察另一个问题即在什么位置上放置跳表指针?这里存在一个指针个数和比较次数之间的折中问题。跳表指针越多意味着跳跃的步长越短那么在合并过程中跳跃的可能性也更大但同时这也意味着需要更多的指针比较次数和更多的存储空间。跳表指针越少意味着更少的指针比较次数但同时也意味着更长的跳跃步长也就是说意味着更少的跳跃机会。放置跳表指针位置的一个简单的启发式策略是在每个㏒₂P处均匀放置跳表指针其中P是倒排记录表的长度。这个策略在实际中效果不错但是仍然有提高的余地因为它并没有考虑查询词项的任何分布细节。# 基于跳表的倒排记录表快速合并算法
a range(10008)
b [1, 10001, 10008]i j 0
result []
step 100
count 0
while i len(a) and j len(b):if a[i] b[j]:result.append(a[i])i i 1j j 1count count 1elif a[i] b[j]:while (i step len(a)) and a[i step] b[j]:i i stepcount count 1else:i i 1count count 1else:while (j step len(b)) and b[j step] a[i]:j j stepcount count 1else:j j 1count count 1
print(result) # [1, 10001]
print(count) # 207
上面代码中故意构造了一个很大的集合 [0 ... 10007], 然后用变量count作为计数器来分析两个算法分别执行的操作次数, 可以看到采用跳表算法时(我们模拟了step100)的计算次数是207, 而用之前的方式计算次数是10008, 可见性能提升了很多倍.这里有几点说明下:1. 这里为了简单说明跳表的思路, 全部用了数组表示倒排表, 其实真实的数据结构应该是链表结构(linked list). 这才符合磁盘存储结构. 2. 跳表的原始结构算法比这个复杂, 而且根据场景的不同, 跳表有不同的实现. 这里因为不是利用跳表的快速查询功能, 所以没有多级指针索引概念, 详细跳表实现查考: Skip Lists: A Probabilistic Alternative to Balanced Trees含位置信息的倒排记录表先来看一个问题当用户将“Stanford University”这个查询中的两个词看成一个整体的时候用户是为了查询和Stanford University这所高校相关的信息。但是如果是基于布尔查询详见第一章的话将会被拆解成Stanford AND University进行查询从而一篇含有句子The inventor Stanford Ovshinsky never went to university的文档会推送给用户这并不是我们想要的。那么如何解决这个问题呢这里引入二元词索引。3.1 二元词索引处理短语查询的一个办法就是将文档中每个接续词对看成一个短语。例如文本 Friends,Romans, Countrymen 会产生如下的二元接续词对friends romans
romans countrymen
这种方法将每个接续词对看成词项这样马上就能处理两个词构成的短语查询更长的查询可以分成多个短查询来处理。比如按照上面的方法可以将查询 stanford university palo alto分成如下的布尔查询“stanford university” AND “university palo” AND “palo alto”可以期望该查询在实际中效果会不错但是偶尔也会有错误的返回例子。对于该布尔查询返回的文档我们并不知道其是否真正包含最原始的四词短语。在所有可能的查询中用名词和名词短语来表述用户所查询的概念具有相当特殊的地位。但是相关的名词往往被各种虚词分开比如短语the abolition of slavery或者renegotiation of the constitution。这种情况下可以采用如下方法来建立二元词索引:首先对文本进行词条化然后进行词性标注这样就可以把每个词项归成名词N也包括专有名词、虚词X冠词和介词和其他词。然后将形式为NX*N非词项序列看成一个扩展的二元词。利用上述算法可以将查询cost overruns on a power plant分析成“cost overruns” AND “overruns power” AND “power plant”实际上忽略中间的那个二元词所形成的查询的效果会更好。如果使用更精确的词性模式来定义扩展二元词可能会取得更好的结果。二元词索引的概念可以扩展到更长的词序列三元、四元...如果索引中包含变长的词序列通常就称为短语索引phrase index。实际上利用二元词索引来处理单个词的查询不太方便必须要扫描整个词汇表来发现包含该查询词的二元词因此同时还需要有基于单个词的索引。尽管总有可能得到错误的匹配结果但是在长度为3或者更长的索引短语上发生匹配错误的可能性实际上却很小。然而在另一方面存储更长的短语很可能会大大增加词汇表的大小。穷尽所有长度超过2的短语并维护其索引绝对是一件令人生畏的事情即使只穷尽所有的二元词也会大大增加词汇表的大小。3.2 位置信息索引很显然基于上面谈到的原因二元词索引并非标准的解决方案。实际中更常用的一种方式是采用所谓的位置信息索引positional index简称位置索引。在这种索引中对每个词项以如下方式存储倒排记录单词be的文档频率是178239在文档1中出现2次位置分别是17、25。为处理短语查询仍然需要访问各个词项的倒排记录表。像以往一样这里可以采用最小文档频率优先的策略从而可以限制后续合并的候选词项的数目。在合并操作中同样可以采用前面提到的各种技术来实现但是这里不只是简单地判断两个词项是否出现在同一文档中而且还需要检查它们出现的位置关系和查询短语的一致性。这就需要计算出词之间的偏移距离。举个栗子假如用户输入boy friend进行搜索, 如果只要出现了boy 或者 friend的文档都搜索出来, 那么下面三篇文档都满足要求:the boy and the girl are good friendsyou are my boy friendthe boy has many friends.现在用户应该只想搜出文档 2 出来. 基于位置信息索引方式, 我们可以做到这一点.这种搜索方法类似于k词近邻搜索 —— a /k b这里/k 意味着“ 从左边或右边相距在 k 个词之内若k1则意味着a、b相邻” 。很显然位置索引能够用于邻近搜索而二元词索引则不能。有了这个索引存储结构, 要找出不同的短语就比较容易了, 比如用户想搜索boy friend, 就可以转化成 boy /1 friend 即可以完成要求。只要找出在文档中, boy出现的位置刚好在friend前一个位置的所有文档. 所以文档2满足我们的要求被搜索出来. 下面用python简单实现下这个算法:# p1, p2是两个上述结构的倒排记录表, k是两个词项的位置在k以内
def positional_interset(p1, p2, k):result [] # 最终的搜索结果, 以(文档id, 词项1的位置, 词项2的位置)形式存储while p1 is not None and p2 is not None: # 当p1, 和 p2 都没有达到最尾部时if p1.docId p2.docId: # 如果两个词项出现在同一个文档中l [] # 临时变量, 用来存储计算过程中满足位置距离的位置对信息pp1 p1.positionpp2 p2.positionwhile pp1 is not None: # 先固定pp1的位置, 循环移动pp2的位置进行检查while pp2 is not None:if abs(pp1.pos - pp2.pos) k: # 如果pp1和pp2的距离小于k, 则满足要求l.append(pp2.pos) # 添加到临时变量pp2 pp2.next # pp2向后移一个位置elif pp2.pos pp1.pos: # 如果pp2当前的位置相对pp1已经超过给定的范围(构不成短语要求), 则停止移动pp2, 后续后把pp1再往前移动一个位置breakwhile not l and abs(l[0] - pp1.pos) k: # 当每次移动一次pp1时, l里面会存储上一次计算所得的pp2的一些位置, 这里要过滤那些相对于当前pp1最新位置, 那些不再满足要求的pp2的位置del l[0]for p in l:result.append[(p1.docId, pp1.pos, p)] # 把最终的结果加入到结果集中pp1 pp1.next # pp1向前移动一个位置, 重复上次逻辑计算p1 p1.nextp2 p2.nextelif p1.docId p2.docId:p1 p1.nextelse:p2 p2.next毋庸置疑采用位置索引会加深倒排记录表合并操作的渐进复杂性这是因为需要检查的项的个数不再受限于文档数目而是文档集中出现的所有的词条的个数 T。也就是说布尔查询的复杂度为Θ (T)而不是Θ (N)。然而由于用户往往期望能够进行短语搜索和邻近搜索所以实际中的大部分应用并没有其他选择而不得不采用这种做法。3.3 混合索引机制二元词索引和位置索引这两种策略可以进行有效的合并。假如用户通常只查询特定的短语如Michael Jackson那么基于位置索引的倒排记录表合并方式效率很低。一个混合策略是:对某些查询使用短语索引或只使用二元词索引而对其他短语查询则采用位置索引。短语索引所收录的那些较好的查询可以根据用户最近的访问行为日志统计得到也就是说它们往往是那些高频常见的查询。当然这并不是唯一的准则。处理开销最大的短语查询往往是这样一些短语它们中的每个词都非常常见但是组合起来却相对很少见。Williams等人(2004)评估了一个更复杂的混合索引机制其中除了包含上面两种形式的索引外还在它们之间引入了一个部分后续词索引next word index即对每个词项有个后续词索引记录了它在文档中的下一个词项。论文的结论是虽然比仅仅使用位置索引增加了26%的空间但是面对典型的Web短语混合查询其完成时间大概是只使用位置索引的1/4。本章节主要对词项的形成和倒排索引的两个升级版算法做了一个粗略的介绍。虽然这是搜索引擎中最基础的东西但值得细细挖掘的地方还有很多毕竟每一个小点的改善都可以极大的提高用户体验搜索引擎学习之路道阻且长呀~加油(・ω・´)可能喜欢跨平台NLP/ML文章索引倒排索引初体验让搜索推荐更聪明的篇章标签自动化生产神经网络调参指南DFS、BFS与A*搜索算法求关注 求投喂 拉你进高端群哦~参考文献《信息检索导论 修订版》倒排索引优化 - 跳表 —— 博客园 海鸟
