倒排索引的简单介绍和实现

在信息检索(Information Retrieval)领域, 有个重要而基础的方法, 倒排索引(Inverted Index), 它被广泛用于各种全文搜索. 在无知的时代, 区区曾经"自创"过一种牛掰的方法, 于是称之为"映射", 小数据集上居然颇有效果, 颇为自得, 后来了解了倒排索引后, 俺才切切实实的了解到 “你以为你的 idea 很牛B, 其实只是你文献看得太少了” 这句话的真谛...

倒排索引的概念其实很简单, 如果我们有一组 int/float 之类的数据要存储, 我们不仅存储一个"id -> val"这样一个 map, 还存储一个"value -> id list"这样一个 map, 当我们需要寻找所有某个 value 为一个特定的值--比如 1024 的时候, 我们只需要在 "value -> id list" 中以特定 value--比如 1024 为 key, 就很容易得到一个 id list, 而不必去 "id -> value"这个 map 里面遍历一遍了. 当数据量很大的时候, 这种用空间换时间的方法很有效.

但是, 实际情况中, 我们并不仅仅需要寻找这么个数字, 很多时候, 我们存储了一段文字到某处, 而查询的时候, 输入只言片语, 期望能得到完整的结果. 这就需要一些更多的处理.

前几天在此处隐去姓名的 Wei Huang 同学突然问起倒排索引的事情,我说这东西概念很容易, 我用 python 给你个 toy level 的 demo, 不过真的实现还需要考虑很多, 比如持久化, 比如线程同步之类, 而且它只是个初步结果, 光靠它显然是不行滴. 折腾了大约半个小时写了个居然可以用的代码, 然后通知那位同学, "大致就这个意思, 若真想做的话, 差不多就长这样了".

python管理起来各种蛋疼菊紧, 效率也实在不敢恭维, 但有个好处, 百来行级别的代码随便拿个 vi 就能写, 然后 terminal 看 debug 信息也还不错, 比之 c++ 夸张的报错, 用 python 来 rush 个 demo 还是个不错的选择. 所以我用 python 做那个 demo, 用 Jiawei Han 老头的 650+ 篇 paper 的 title 建立个索引(当然, 这些输入存储在 data.txt 中, 不爽可以自己换内容, 反正一行一个格式相当粗暴), 然后让人查询个内容, 很是简陋但描述下"咋做索引"这类问题应该够了. 有兴趣可以到 这里 看这个 toy repo.

查询 string, 其实本质上和查询个 int/float 没啥区别, 就是另外建立个 map, key 是原本的 value, value 是 id list 之类的, 不过因为恐怕很少有人能够直接把目标内容完整地写到 query 里面, 所以我们倒排索引的时候, 首先要先把 string 内容切为一些小小的 term, 然后将 term 索引, 当有人 query 的时候, 也将 query 切 term, 然后分别查询, 最后把各个单词 term 的结果合并即可.

现在有个问题了, 现在有个 term, 由 term 查询原来的 doc, 我们往往可以找到一组结果--这组结果数量可能很多. 但不同于 int 的倒排, 你要搜寻值为 1024 的那个 doc, 那就找所有1024 搞定了, 是或者否, 布尔类型而已. 但查询 string, 就有点区别了, 比如你搜索 data mining, 文中反复提到 data mining 的 string 可能比只是偶尔提一次的要更相关, 而如果我们将 is 作为 term, 它在各种文中都被提到, 可能并非是个有意义的 term. 为了解决这个问题, TF-IDF是一个很常见的方法, 所以我们不仅需要已知 term 获取相关 doc id 的 list, 还要将这些 doc id 按照重要性排序. 顺便需要知道的一点是, TF-IDF只是个假设, 我们发现这样很有效(经验), 但凭啥有效, 目前貌似还没啥可靠证明. . .

TF-IDF需要这样四个参数:

• 这个 term 在当前 doc 中出现了多少次?
• 这个 doc 中共有多少 term?
• 数据库中共有多少doc?
• 数据库中有多少拥有本 term 的 doc?

然后公式一代就得到一个 term 在某 doc 中 tf-idf 的 score 了. 它的 score 越高, 相关越高.

知道原理, 实现也就很简单了. 首先, 构造个 class, 用于存放相关数据(这个是为了简化起见, 真要实际应用这些内容还放内存可真不大胶布了)

class Index :
  # a unique doc id && all document size
  max_doc_id = 0 
  doc = {}
  # key : doc id , value : all term size&times
  doc_meta = {}
  index = {}

其中

• doc是存放 id->内容的映射的, doc_meta 用于回答 "这个 doc 中共有多少 term?" 这个问题
• index 是一个二级 dict, key 是 term, value 是一组 id->"这个 term 在当前 doc 中出现了多少次?"的 dict.
• max_doc_id 我把它用在了两个地方, 首先当我们需要增加一个 doc 的时候, 它是作为当前的 doc id 来用(用完后 max_doc_id ++ ), 当我们查询的时候, 它的值正好可以回答"数据库中共有多少 doc?" 这个问题

这样, 四个问题就回答了三个, 而唯一剩下的是"数据库中有多少拥有本 term 的 doc ?", 其实也很容易, index[term] 的 size 就是.

准备好数据结构后, 我们按照数据结构照方抓药即可.

build index的过程很容易.

def build_index(idx):
  print("Building Index .. ")
  f = open('data/data.txt', 'r')
  for line in f:
    idx.doc[idx.max_doc_id] = line.strip()  # store doc
    tokens = analysis(line)
    term_sz = 0
    for k, v in tokens.items():
      idx_term = {}
      if k in idx.index :
        idx_term = idx.index[k]
      else :
        idx_term = {}
      idx_term[idx.max_doc_id] = v
      idx.index[k] = idx_term
      term_sz += v
    idx.doc_meta[idx.max_doc_id] = term_sz
    idx.max_doc_id = idx.max_doc_id + 1
  f.close()

逐行读取doc, 对每个 doc 先保存到 Index. doc 中, 然后将内容分词, 获取每个 term 及其出现次数(也就是 analyzer 的工作). 然后按照数据结构分别保存内容.

查询也一样, 先 analyze 下, 对每个 term 分别查询, 将得到的 score 合并(比如我简单的将同 doc id 的 score 相加), 然后排一下序, 就是个初步的查询结果了.

需要说明的是, 虽然我们假模假样的捯饬出了一堆 doc 和 tf-idf score, 但毕竟还只是初步的结果, 它只是个良好的开端, 还需要更多的处理来让结果成为人需要的结果.

更新: 另外, 最近我又用 c++ 实现了一个用 leveldb 存储的 index. 有兴趣请查看这篇内容.

更新: 添加了 BM25 算法. 如何合并多个 tf-idf 的查询结果? 这是一个常见的解决方案.