17

我想构建一个没有任何API的搜索引擎的简单索引功能，例如Lucene。在倒排索引中，我只需要记录每个单词的基本信息，例如docID、位置和频率。

现在，我有几个问题：

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

  2. 建立索引后，如何将其写入文件？文件中的格式是什么？像一张桌子？就像在纸上画一个索引表？

4

1 回答 1

34

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

对于您的第一个问题，如果您想构建一个简单的（在内存中）倒排索引，那么直接的数据结构是一个像这样的哈希映射：

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

或Java-esque：

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

哈希将每个术语/单词/标记映射到 Postings 列表。APosting只是一个对象，表示文档中出现的单词：

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

索引一个新文档只是对其进行标记（以标记/单词分隔）的问题，并为每个标记在哈希映射的正确列表中插入一个新的发布。当然，如果在该特定 docId 中已经存在该术语的 Posting，则可以增加 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一起的段合并。

于 2012-09-20T21:29:48.100 回答