Tag Archives: Boolean Retrieval

IR笔记(1)

看了一点关于信息检索(Information Retrieval, IR)的东西,随便记录一下,也请路过的大牛指正。发现关于算法的东西我写起来勉强还算有点底气,关于其它的内容就实在是纯献丑了,哈哈。本系列文章大部分内容参考自新书 Introduction to Information Retrieval

信息检索中一种比较简单的形式是所谓Boolean Retrieval,它处理的Query是“roba AND ppmm”这样的形式,它返回的结果是既包含“roba”又包含“ppmm”的文档,当然,可用的逻辑运算符还有“OR”和“NOT”。我们通常在搜索引擎如Google, 百度上所作的搜索称为Web Search,它貌似是叫做Ad-Hoc Retrieval的,在这种搜索里我们很少用运算符,也不一定要求返回的结果精确匹配,这样问题就比较复杂了。

我们需要一种手段表示出文档(doc)和它包含的词(item)之间的关系,一个自然的想法就是邻接矩阵,用行表示单词,列表示文档,如果矩阵的第i行第j列非零,就表示单词i出现在文档j里。当然这样得到的矩阵是相当稀疏的,所以我们可以改用邻接表,这样得到的东西叫做inverted index(反向索引?),注意我们是对每个词拉了一个链表(posting)出来。

对于查询“roba AND ppmm”,我们找到“roba”对应的posting和“ppmm”对应的posting,然后求这两个链表的交即可。如果链表中文档的编号是有序的话,这个操作显然可以在线性时间完成,OR操作也同样。对于多个运算符的连接,只要保留中间结果然后一个个算下去就好了,另外我们还可以加入一些启发式优化。比如查询“roba AND ppmm AND acm”,如果我们知道“roba”和“ppmm”的返回结果都小于“ACM”,那么可以先求“roba”和“ppmm”的交,再与“ACM”求交。

如果我们对线性时间还不满意,可以再加入一些“跳跃”指针,形成所谓的跳跃表(skiplist,印象中某年NOI冬令营论文有大牛分析过此物),基本思想就是当需要大步前进时可以用跳跃的,关于指针的密度为多少合适,这时就需要一个trade-off,太大太小都不好,理论上来说sqrt(N)的间隔是最好的,当然这个东西动态维护起来就比较恶心了。

关于检索返回结果的质量评价,一般有两个指标:Precision(精确度)和Recall(召回率?)。前者是指,返回的结果里面,有多大比例是有用的;后者是指,返回的有用文档占全部有用文档的比例是多少。不同的场合对这两者的偏重可能会有所不同。