问题标签 [inverted-index]

我有一个嵌套 python 字典形式的完整倒排索引。它的结构是：

例如让字典被称为索引，那么对于一个单词“垃圾邮件”，条目将如下所示：

我使用了这种结构，因为 python dict 非常优化，它使编程更容易。

对于任何单词“垃圾邮件”，包含它的文档可以通过以下方式给出：

并通过以下方式发布文档 doc1 的列表：

目前我正在使用 cPickle 来存储和加载这个字典。但是腌制文件大约 380 MB 并且需要很长时间才能加载 - 112 秒（大约我使用time.time()对其进行计时）并且内存使用量达到 1.2 GB（Gnome 系统监视器）。一旦它加载，它的罚款。我有 4GB 内存。

len(index.keys())给 229758

代码

我怎样才能让它加载得更快？我只需要在应用程序启动时加载一次。之后，访问时间对于响应查询很重要。

我应该切换到像 SQLite 这样的数据库并在其键上创建索引吗？如果是，我如何存储值以具有等效的模式，这使得检索变得容易。还有什么我应该调查的吗？

附录

使用蒂姆的回答pickle.dump(index, file, -1)，腌制文件要小得多 - 大约 237 MB（转储需要 300 秒）......现在加载时间的一半（61 秒......而不是之前的 112 秒...... time.time () )

但是我应该迁移到数据库以获得可扩展性吗？

至于现在，我将蒂姆的回答标记为已接受。

PS：我不想使用 Lucene 或 Xapian ...这个问题是指存储倒排索引。我不得不问一个新问题，因为我无法删除前一个问题。

我目前正在开发一个网站，允许用户上传演示文稿、文档和电子书（例如 scribd 和 slideshare），所以我需要能够搜索文件的内容。我目前正在从 txt 文件中的文件中提取文本。当我使用 MySQL 时，我正在考虑 2 个选项：

1. 将纯文本存储在单独的表中，并使用 mysql 的全文索引对其进行搜索。
2. 使用倒排索引来存储单词并通过它们进行搜索。（2 个新表 - 单词和多对多与文档表）。现在在这种情况下，我可以做些什么来处理与结果更相关的重复词。

该文本将仅用于搜索。(1) 的问题是电子书的文本可能很大，因此我考虑将其限制为（例如）50kb 或更少。(2) 电子书也有很多单词的问题，同样可以限制。

那么，您能否指导我找到索引文本并能够进行快速全文搜索的最佳方法。在这种情况下，我需要充分利用 mysql。

I consider using Sphinx search in one of my projects so I have a few questions related to it.

1. When using SphinxSE and RT index, every UPDATE or INSERT in the SphinxSE table will update the index, right? No need to call indexer or anything?
2. Can I search on both tags (user entered keywords for a document) and the content and give more relevance to the tag matches? And if it's possible how do I implement the tag search (now I have them in separate tables like an inverted index)
3. For the fillter attributes is it better to stick duplicates of them in the SphinxSE table or fillter using mysql from the regular documents table I have?

Thanks in advance!

我正在为文档集合上的搜索引擎编写倒排索引。现在，我将索引存储为字典字典。也就是说，每个关键字都映射到 docIDs-> 出现位置的字典。

数据模型类似于： {word : { doc_name : [location_list] } }

在内存中构建索引工作正常，但是当我尝试序列化到磁盘时，我遇到了 MemoryError。这是我的代码：

在序列化之前，我的程序使用了大约 50% 的内存（1.6 Gb）。当我调用 cPickle 时，我的内存使用量在崩溃前飙升至 80%。

为什么 cPickle 使用这么多内存进行序列化？有没有更好的方法来解决这个问题？

问题：您需要什么解决方案或技巧来处理一个非常大（数 TB）的数据库，该数据库以高冗余的强哈希为索引？

某种倒置存储？

Postgres有什么可以做的吗？

如果需要，我准备推出自己的存储空间。

（提示：必须是开源的，没有Java，必须在Linux上运行，必须是基于磁盘的，C/C++/Python优先）

细节：

我需要创建一个非常大的数据库，其中每条记录都有：

• 一些任意元数据（一些文本字段），包括一些主键
• 一个哈希（128 位哈希，类似 MD5 的强）

记录的数量是我认为相当大的：几十到上百亿）。跨行的散列存在显着冗余（超过 40% 的记录的散列至少与另一条记录共享，一些散列存在于 100K 记录中）

主要用途是通过哈希查找，然后检索元数据。次要用途是通过主键查找，然后检索元数据。

这是一个分析型数据库，因此整体负载中等，主要是读取，很少写入，主要是批量写入。

当前的方法是使用 Postgres，在主键上有一个索引，在哈希列上有一个索引。该表是在关闭散列索引的情况下批量加载的。

所有索引都是 btree。哈希列上的索引越来越大，与表本身一样大或更大。在一个 120 GB 的表上，重新创建索引大约需要一天时间。虽然查询性能相当不错。

问题在于，根据测试，目标数据库的预计大小将超过 4TB，其中 400GB 的较小数据集约占总目标的 10%。一旦加载到 Postgres 中，不幸的是超过 50% 的存储被散列列上的 SQL 索引使用。

这太大了。而且我觉得散列中的冗余是一个减少存储的机会。

另请注意，虽然这描述了问题，但需要创建其中一些表。

我在某处读到，当你有一个倒排索引时（例如，你有一个 brutus 页面的排序列表、一个 caesar 页面的排序列表和一个 calpurnia 页面的排序列表），当你做 caesar AND brutus AND calpurnia , 如果 calpurnia 和 brutus 的页数少于 caesar 的页数，那么你应该做 caesar AND (brutus and calpurnia)，这意味着你应该先评估后者。通常，每当您有一系列 AND 时，您总是首先评估具有最少页数的对。这背后的原因是什么？为什么这样有效？

我想知道Lucene中的哪个类生成倒排索引？

谢谢

我知道全文搜索的一个基本方面是使用倒排索引。因此，使用倒排索引，一个单词的查询变得很容易回答。假设索引的结构如下：

some-word -> [doc385, doc211, doc39977, ...]（按排名降序排列）

要回答对该词的查询，解决方案只是在索引中找到正确的条目（这需要 O(log n) 时间）并从索引中指定的列表中显示一些给定数量的文档（例如前 10 个）。

但是返回匹配两个单词的文档的查询呢？最直接的实现如下：

1. 将 A 设置为具有单词 1 的文档集（通过搜索索引）。
2. 将 B 设置为具有单词 2 的文档集（同上）。
3. 计算 A 和 B 的交集。

现在，第三步可能需要 O(n log n) 时间来执行。对于可能使查询响应缓慢的非常大的 A 和 B。但是像谷歌这样的搜索引擎总是在几毫秒内返回他们的答案。所以这不能是完整的答案。

一个明显的优化是，由于像 Google 这样的搜索引擎无论如何都不会返回所有匹配的文档，所以我们不必计算整个交集。我们可以从最小的集合（例如 B）开始，并找到足够的条目也属于另一个集合（例如 A）。

但是我们不能还有以下最坏的情况吗？如果我们将 A 设置为匹配一个常用词的文档集，并将 B 设置为匹配另一个常用词的文档集，那么可能仍然存在 A ∩ B 非常小的情况（即这种组合很少见）。这意味着搜索引擎必须线性地遍历 B 的所有元素 x 成员，检查它们是否也是 A 的元素，以找到符合这两个条件的少数元素。

线性并不快。而且您可以搜索两个以上的单词，因此仅使用并行性肯定不是整个解决方案。那么，这些案例是如何优化的呢？大型全文搜索引擎是否使用某种复合索引？布隆过滤器？有任何想法吗？

搜索引擎（或类似的 Web 服务）使用平面文件和 nosql 数据库。倒排索引的结构比多对多关系更简单，但使用后者处理它应该更有效。几十亿的网页和数百万的关键字应该有两个表。我已经测试了一个 5000 万行的表；mysql的速度可以和BerkeleyDB媲美。

我认为在处理 ALTER TABLE 之类的东西时会出现使用大型 mysql 数据库的问题（这里不是这种情况）。这种性能是读取密集型的，其中mysql相当不错。通过 SELECT 读取一行时，我没有发现几行或几百万行的表之间存在显着差异；有数十亿行时有什么不同吗？

注意：我不是指 Google 或 Bing（或全文搜索等高级功能），我是在讨论这个概念。

我目前正在编写一个基于视觉词的图像检索系统，它类似于文本检索中的向量空间模型。在这个框架下，每个图像都由一个向量表示（或者在文献中有时也称为直方图）。基本上，向量中的每个数字都会计算每个“视觉词”在该图像中出现的次数。如果 2 个图像的向量“接近”在一起，这意味着它们具有许多共同的图像特征，因此是相似的。

我基本上是在尝试为一组这样的向量创建倒排文件索引。我想要一些可以从数千（在试用阶段）扩展到数十万或数百万+图像的东西，这样自制的数据结构黑客将无法工作。

我看过 Lucene，但显然它只索引文本（如果我错了，请纠正我），而在我的情况下，我希望它索引数字（即向量本身）。我见过人们通过以下方式将矢量转换为文本文档的情况：

<3, 6, ..., 5> --> “w1 w2...wn”。基本上，任何非零组件都被文本单词“w[n]”替换，其中 n 是该数字的索引。然后将此“文档”传递给 Lucene 以进行索引。

使用这种方法的问题是向量的文本表示不编码特定“单词”出现的频率，因此检索到的图像的排名不会很好。

有谁知道可以处理向量的成熟索引 API，或者可能为我的向量建议不同的编码方案，以便我可以继续使用 Lucene？我还查看了 Lucene for Image Retrieval (LIRE) 项目并尝试了它附带的演示，但是运行该演示时生成的异常数量让我不确定是否使用它。

至于 API 的语言，我对 C++ 或 Java 持开放态度。

提前感谢您的任何回复。