1. 作用
词位置倒排索引存在的意义是什么呢?
在web搜索中,绝大多数情况都是*文本搜索。用户期望很简单的输入一些词语串,搜索引擎就能匹配出与之相关的文档。而词项位置信息,在搜索引擎进行匹配和打分的过程中,提供了很重要的信息。
例如,
文档1包含"I promise I will always love you"。
文档2包含"You should promise you will always love me"。
如果建立的索引中没有任何词位置信息,当用户query“I love you”的时候,搜索引擎查询系统恐怕就只能根据"I" , "love","you"三个词分别取倒排,利用向量空间模型来进行对文档的打分,这样就极有可能将文档2也检索出来。
而文档2实际上与用户的搜索意图差别甚远。
问题就出在没有事先对文档词项位置信息进行索引,使得查询系统只能简单根据词项的文档频率,逆文档频率来计算相关度,没有考虑词位置对相关性的影响,失之毫厘谬以千里。
这就可以看出词位置索引的重要性了。
2. .prx文件格式分析
.prx的结构如下图所示,
这里将.frq也放进来了,原因是一个词项的倒排有3部分,词频倒排,词位置倒排和跳表,而跳表是存储在.frq文件当中的。
可以从图中看出,跳表中的ProxSkip就是指向该词项在这个文档中的词位置在.prx文件中的地址。
词位置索引由TermCount个TermPostions结构组成,每个文档一个TermPositions结构。它们是按照Term来排序的,也就是和tis文件中的TermInfo排序是一样的,也即按字典序排序。
每个TermPostions结构由DocFreq个Positions结构组成,DocFreq为词项的文档频率,也即它在多少个文档中出现,就有多少个Positions结构。还记得DocFreq记录在哪吗?在词典文件.tis中TermInfo结构中。Positions是按照文档ID来对Position排序的。
每个Positions结构又由Freq个Position结构组成,Freq是词项在某篇文档中的出现次数,Freq是保存在.frq的TermFreq中的。
而每个Position的结构就很简单了,记录词项位置,PositionDelta和PayloadLength也用了压缩算法,也就是那个所谓的“或然跟随法则”。PayloadData就是附加的Payload,由PayloadLength指定长度。
3. Lucene索引倒排部分总结
前面对Lucene倒排索引(词典,词频倒排,词位置倒排,多级跳表)做了介绍,但是因为倒排索引是Lucene索引中最重要的部分,因此这里还是有必要画一下Lucene倒排索引的完整结构。
其实偶尔看看下面的这张总结图,自己在脑子理理,也都能理出Lucene大致是如何写索引以及如何从索引中取出信息的。毕竟索引文件的格式就摆在那,程序逻辑就要那么来,不取跳表偏移,你就找不到跳表。
所以偶尔对着结构图看看还是挺有好处的,有助于回忆。
蓝色部分是词典。
红色部分是词频倒排。
黄色部分是多级跳表。
紫色部分是词位置倒排。