如何构建简单的倒排索引？

Question

我想在没有任何API的情况下构建一个简单的搜索引擎索引功能,例如Lucene.在倒排索引中,我只需要记录每个单词的基本信息,例如docID,position和freqence.

现在,我有几个问题:

1. 什么样的数据结构经常用于构建倒排索引？多维列表？

2. 构建索引后,如何将其写入文件？文件中有哪种格式？像一张桌子？就像在纸上画一个索引表一样？

Answer 1

你可以在TinySearchEngine中看到一个非常简单的倒排索引和搜索实现.

对于你的第一个问题,如果你想构建一个简单的(内存中)倒排索引,那么简单的数据结构就像这样的Hash映射:

val invertedIndex = new collection.mutable.HashMap[String, List[Posting]]

或Java-esque:

HashMap<String, List<Posting>> invertedIndex = new HashMap<String, List<Postring>>();

哈希将每个术语/单词/标记映射到过帐列表.A Posting只是一个表示文档中单词出现的对象:

case class Posting(docId:Int, var termFrequency:Int)

索引新文档只需将其标记(用标记/单词分隔),并为每个标记在哈希映射的正确列表中插入新的过帐.当然,如果该特定docId中的该术语已存在,则增加termFrequency.还有其他方法可以做到这一点.对于内存中的反向索引,这是可以的,但是对于磁盘上的索引,您可能希望Postings使用正确的插入一次termFrequency而不是每次都更新它.

关于你的第二个问题,通常有两种情况:

(1)你有一个(几乎)不可变的索引.您可以将所有数据编入索引一次,如果有新数据,则可以重新编制索引.例如,不需要在一小时内多次实时或索引.

(2)新文件一直到达,您需要尽快搜索新到的文件.

对于情况(1),您可以拥有至少2个文件:

1 - 反向索引文件.它列出了每个术语的全部Postings(docId/termFrequency对).这里用纯文本表示,但通常存储为二进制数据.

 Term1<docId1,termFreq><docId2,termFreq><docId3,termFreq><docId4,termFreq><docId5,termFreq><docId6,termFreq><docId7,termFreq>
 Term2<docId3,termFreq><docId5,termFreq><docId9,termFreq><docId10,termFreq><docId11,termFreq>
 Term3<docId1,termFreq><docId3,termFreq><docId10,termFreq>
 Term4<docId5,termFreq><docId7,termFreq><docId10,termFreq><docId12,termFreq>
 ...
 TermN<docId5,termFreq><docId7,termFreq>

2-偏移文件.存储每个术语的偏移量,以在倒排索引文件中查找其反转列表.这里我用字符表示偏移量但你通常会存储二进制数据,因此偏移量将以字节为单位.此文件可以在启动时加载到内存.当您需要查找术语反转列表时,可以查找其偏移量并从文件中读取反转列表.

Term1 -> 0
Term2 -> 126
Term3 -> 222
....

除了这2个文件,你可以(通常会)有文件来存储每个术语的IDF和每个文档的规范.

对于情况(2),我将尝试简要解释Lucene(以及Solr和ElasticSearch)是如何做到的.

文件格式可以与上面解释的相同.主要区别在于,在Lucene等系统中索引新文档而不是从头开始重建索引时,只需创建一个只包含新文档的新文档.因此,每次必须索引某些内容时,都要在新的分离索引中进行索引.

要在此"拆分"索引中执行查询,您可以针对每个不同的索引(并行)运行查询,并在返回给用户之前将结果合并在一起.

Lucene称之为"小"指数segments.

这里显而易见的问题是,你会很快得到很多小段.为避免这种情况,您需要一个合并细分和创建更大细分的策略.例如,如果您有多个N segments可以决定合并所有小于10 KBs一起的段.