3

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

我的倒排索引看起来像：

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

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

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

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

  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;

    但它很慢，加载需要大约 10 秒。

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

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

预先感谢您的任何帮助！

4

1 回答 1

3

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

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

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

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

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

于 2014-03-23T13:46:07.557 回答