Tag Archives: indexing

IR笔记(3) – Indexing

这次来说一下Inverted Index的构建,即所谓Indexing。

首先考虑一下规模比较小的情况。这时候一个比较简单的方法是,我们扫描所有的文档,把所有的(TermID,DocID)对列成一个表(这里TermID指单词在词典中的编号,DocID指文档的编号),然后对这个表排序,比如先按TermID递增排序,TermID相同时再按DocID递增排序,这样TermID相同的对就排在一起了,再从头线性扫描一下就可以把整个反向索引表建立起来。

容易发现,这种方法要求全部的(TermID,DocID)对可以在一台机器的内存里放下,在实际应用中这通常是不可能的。于是我们把全部文档分成大致相等的K份,使得每一份处理得到的中间结果(即部分(TermID,DocID)对)都可以在内存中放下,然后我们把这些中间结果写入磁盘文件中(一般情况磁盘空间相对内存来说大得多),等K份都处理完以后就得到了K份中间文件。然后再同时打开这K份文件,用堆实现一个多路归并过程即可。这样做的话,每份的排序复杂度是O((N/K)*log(N/K)),最后合并是O(NlogK),所以总的复杂度还是O(NlogN)量级,当然因为涉及到外部文件,速度变慢是肯定的。另外可以发现这K份排序可以分散到多台机器上并行处理,最后再把结果合并即可。

上面的方法隐含了一个条件,就是有某种方法可以使我们从实际的单词快速得到对应的TermID,这可以通常在内存中保留一个Hash表或是Trie之类的东西来实现。但在数据规模非常大的情况下,即使是这个对应表也不可能在一台机器的内存中放下。这时候我们只好再退一步,不要求计算出TermID,而是直接用实际的Term串作为key。这样如果我们仍然记录所有(Term,DocID)对的话会带来两个新问题:首先是耗费内存太大,因为第一项变成了字符串;另外,对字符串的排序也会变慢。所以我们改用动态维护的链表来实现:依次对每篇文档进行线性扫描,每扫描一个单词,如果它未出现过,就把它记录在Hash表里,然后对它新开一个链表(posting),并把当前文档的DocID添加到里面;如果它已出现过,就找到它所对应的链表,把DocID加进去。等内存即将耗尽之时,对现有的所有posting按照所属的Term排序,之后写入磁盘文件,清空内存继续。等所有文档都处理完毕,再把所有磁盘文件归并。这个方法在Introducion to IR这本书上叫做Single-pass in-memory indexing。

另外扯一句,针对这种任务及类似情况,Google搞了一个非常nb的技术叫做MapReduce,以后可能还会详细提到。

再扯一句,发现这些东西貌似不应该放在“所谓学术”分类下面,还是民工成分多些……

IR笔记(2)

我们可以对简单的Boolean Retrieval进行一些扩展,比如常见的phrase query,例如我们要查询“Tianjin University”,按照一般的方法会得到很多Tianjin和university并不连在一起的结果,但这并不是我们想要的。在现在流行的搜索引擎中,大都是用引号括起要查询的词来表示这种要求。对于这样的查询,可以用所谓biword index,即把相邻的两个词当作一个单位来作索引,这样对于两个相邻单词的查询就可以直接解决了。对于多个相邻单词的情况,可以把它拆成两两组合,得到结果后再检验是否符合要求。比如“Happy St.Valentine’s day”可以拆成“Happy St.Valentines”和“St.Valentines Day”。当然,我们也可以把连续三个词看作一个单位,对于三个相邻词的查询就可以直接得出结果而无需像上面一样需要在最后检验,但这样的话通常词组就稀疏得太厉害了,浪费很多空间和时间,往往得不偿失,这里就又是一个trade-off。

另一种的扩展是所谓positional posting,也就是把单词在每篇文档中出现的位置也记录在posting表里面。因为一个词在一篇文档中可能出现多次,所以现在posting表的每个结点处又包含一个表。这样做的好处是可以处理所谓proximity query,就是类似于这样“roba /3 ppmm”,表示要求“roba”和“ppmm”在文档中相隔不超过三个单词,显然上面的phrase query是它的一种特殊情况。这种查询我想平时大家用得很少,但是据说在某些专业方面的信息检索中是很有用的。可以发现如果记录下位置信息的话,就能较容易地处理此类查询了,当然这样的话时空复杂度都有所增加。

还有一个问题是如何进行单词的提取,这通常是和具体语言相关的。即使对英语来说其实也并不像看上去的那么显然,一般情况下不应该简单地把空格或是标点符号隔开的部分一股脑塞进去。比如,“PPMM”和复数形式“PPMMs”(呃…这好像不是英语-_-)显然应该看作同一个词。因此我们需要对单词进行一些处理,处理的方法可分为stemming和lemmatization:前者指比较简单粗暴地用一些规则硬砍去前缀后缀之类的东西,比如这个Porter Stemmer;后者指利用自然语言处理中相对复杂的方法对单词进行分析,可能得到更准确的结果,当然,我们要为此付出效率的代价。另外对于中文,单词之间并不用空格隔开,因此还需要一个额外的过程就是所谓的“分词”。

另外还要提一下就是所谓stop list(停用词?),这个是指那些出现频率超级高的词,它们几乎在每篇文档中都出现,以至于检索它们变得没有意义且非常耗费时间,这时一个简单的方法就是直接无视它们。我们在用搜索引擎的时候有时会得到提示,说你输入的某某词被忽略,就是因为这个原因。常见的此类词有“of”,“the”以及中文的“的”等。当然简单无视并不是唯一的办法,比如利用TF/IDF加权就可以自动解决这个问题,这个后文应该还会提到。另外扯淡一下,据说在专门针对计算机科学的学术论文检索系统中,“Algorithm”这个本来应属生僻词的术语是在stop list里的,这是我不知从哪里听来的,真假未知。