c++ - 在 C++ 中存储、加载和使用倒排索引的最佳方式 (~500 Mo)

Question

我正在开发一个使用 TF-IDF 和余弦相似度的小型搜索引擎。添加页面时，我会建立一个倒排索引以保持不同页面中的词频。我删除了停用词和更常见的词，以及复数/动词/等等。被阻止。

我的倒排索引是这样的:

map< string, map<int, float> > index

[
    word_a => [ id_doc=>frequency, id_doc2=>frequency2, ... ],
    word_b => [ id_doc->frequency, id_doc2=>frequency2, ... ],
    ...
]

有了这个数据结构，我可以用 word_a.size() 得到 idf 权重。给定一个查询，程序会遍历关键字并对文档进行评分。

我不太了解数据结构，我的问题是:

1. 如何存储 500 Mo 倒排索引以便在搜索时加载它？目前，我使用 boost 来序列化索引:

   ofstream ofs_index("index.sr", ios::binary);
   boost::archive::bynary_oarchive oa(ofs_index);
   oa << index;
   

   然后我在搜索时加载它:

   ifstream ifs_index("index.sr", ios::binary);
   boost::archive::bynary_iarchive ia(ifs_index);
   ia >> index;
   

   但是它非常慢，加载需要 sometines 10 秒。

2. 我不知道 map 对于倒排索引是否足够有效。

3. 为了对文档进行聚类，我从每个文档中获取所有关键字，然后遍历这些关键字以对相似文档进行评分，但我想避免再次阅读每个文档并仅使用这个倒排索引。但我认为这种数据结构的成本很高。

提前感谢您的帮助!

Answer 1

答案在很大程度上取决于您是否需要支持与机器 RAM 相当或更大的数据，以及在您的典型用例中您可能会访问所有索引数据还是只访问其中的一小部分。

如果您确定您的数据适合您的机器内存，您可以尝试优化您现在使用的基于 map 的结构。将数据存储在 map 中应该可以提供相当快的访问，但是当您将数据从磁盘加载到内存中时，总会有一些初始开销。此外，如果您只使用索引的一小部分，这种方法可能会非常浪费，因为您总是读取和写入整个索引，并将所有索引保存在内存中。

下面我列出了一些您可以尝试的建议，但在您花太多时间在其中任何一个之前，请确保您实际测量了哪些改进了负载和运行时间，哪些没有。如果不分析您使用的实际数据的实际工作代码，这些只是可能完全错误的猜测。

• map 被实现为一棵树(通常是黑-红树)。在许多情况下，hash_map 可以为您提供更好的性能以及更好的内存使用(例如更少的分配和更少的碎片)。
• 尝试减小数据的大小 - 数据越少意味着从磁盘读取数据的速度越快，可能分配的内存越少，有时由于更好的局部性，内存中的性能也会更好。例如，您可能会考虑使用 float 来存储频率，但也许您可以仅将出现次数存储为 map 值中的 unsigned short 和单独的 map 存储每个文档的所有单词数(也称为短)。使用这两个数字，您可以重新计算频率，但在将数据保存到磁盘时使用更少的磁盘空间，这可能会导致更快的加载时间。
• 您的 map 有很多条目，有时使用自定义内存分配器有助于在这种情况下提高性能。

如果您的数据可能会增长到超出您机器 RAM 的大小，我建议您使用内存映射文件来存储数据。这种方法可能需要重新建模您的数据结构，并使用自定义 STL 分配器或使用完全自定义的数据结构而不是 std::map，但如果做得好，它可能会将您的性能提高一个数量级。特别是，这种方法使您不必一次将整个结构加载到内存中，因此您的启动时间将显着缩短，但代价是当您第一次接触结构的不同部分时，与随时间分布的磁盘访问相关的轻微延迟时间。这个主题非常广泛，需要对代码进行更深入的更改，而不仅仅是调整 map ，但如果您计划处理大量数据，您当然应该看看 mmap 和 friend 。