问题标签 [inverted-index]

我试图了解背景中到底发生了什么。

给定倒排索引的简化模型（忘记位置和分数）：对于每个单词，都有一个文档 ID 的排序列表。多个单词查询与这些排序列表相交以产生另一个这样的列表。（最后有排名）

例如

以下对字段的理解是否正确？

不同的字段意味着不同的索引空间或至少不同的列表。例如，拥有 abstract 和 body 字段可能最终会出现这样的场景：

这种理解正确吗？如果不是，就底层倒排索引而言，这些字段是什么？我找不到任何明确说明它是如何在内部完成的文档。

除此之外，我想知道是否支持在所有/任何字段中搜索等功能。如果像我假设的那样实现，这应该很麻烦，或者需要通过保留上面的列表来实现冗余。通过完整单词列表的子范围实现字段当然可以更好地执行。

很高兴知道 Lucene 实际上做了什么。

这是我关于 SO 的第一篇文章，如果我的问题有点琐碎，我提前道歉，我对编程世界比较陌生，我选择 python 作为我的第一个“严肃”OOP 语言。我通过 SO 档案进行了搜索，但我找不到任何与我的完全相关的问题。好的，长话短说，问题是：

我正在研究倒排索引。我在网上找到了一些教程和提示，我做了以下事情：

• 类 Document 用于词干词干并通过 finditer 函数返回它们的开始和结束位置。

• 类 Inverted_Index 获取文档集合（列表中的列表），对它们进行标记并将它们以如下形式放入倒排索引中

{'word':{document_id:(start_pos, end_pos)}}

喜欢 {'cloud': {0: [(5, 10)]}, 'document': {1: [(11, 19)], 2: [(22, 30)]} ...}。（我在 SO 主题的帮助下做了 document_id，遍历了文档的枚举集合。关于嵌套字典，我很业余地制作了它们，例如：

当我阅读堆栈 owerflow 时，我注意到“defaultdict”数据类型是非常好的方法，但我还没有想出“集合”模块。）。

回到正轨：在 Inverted_Index 内部，我做了一个 Query 方法（只是 OR 运算符的一个版本），它将字符串作为查询，如果该字符串与我的倒排索引中的键/术语匹配，则返回 document_id 的起点和终点一个术语，例如：

在那之后，我……卡住了。我想做一个查询输出，打印出文档中找到的单词及其环境，但我不知道如何连接查询方法的结果（带有开始和结束位置的 document_id）和倒排索引，我不知道不知道如何在她的环境中突出显示匹配的查询。正因为如此，我做了起点和终点，但我不知道如何在 python 中强调它？大胆吗？

我想到了类似的结果：

###################
您的查询：'chocolate pudding'
结果：
########
在具有 id 的文档中：1
yaddi yaddi yadda Chocolate bla bla bla布丁
巧克力 bla bla bla 布丁 yaddi yaddi yadda bla

我的意思是，我正在阅读http://docs.python.org/2/library/string.html#string.center并认为在同一列中对齐找到的单词/查询会起到欺骗作用。但我不知道如何到达那里，所以任何类型的提示都会很棒，因为我没有被困在我的程序中，因为我被困在理解 python 背后的逻辑，在这种情况下，教程不会做正义。（是的，我有一些 python 书籍，但是他们对这种事情有扩展的方法，可能考虑到它不适合初学者，但我不知道从哪里开始，我可以使用什么程序。问题是，我们在大学里学习语言理论和国际关系理论，但我们在实践中做了一些事情。）。

谢谢！

对这个我生命中的故事结束感到抱歉：D

我忘了，一个不使这个话题含糊不清的代码：

我从文件中读取单词并将其放入双链表中我使用 .equals() 方法来检查单词是否在双链表中并且该方法工作正常但是当我使用 compareto() 方法对单词进行排序时它显示了这些异常：-

方法 ：-

双链表中的插入方法：-

我对双链表的实现：

在一些博客和 lucene 网站中，我知道 lucene 在倒排索引中使用数据结构“跳过列表”。但我对此有些疑惑。

1：一般情况下，skip list可能用在内存中，倒排索引存储在磁盘中。那么 lucene 在索引上搜索时是如何使用它的呢？只是在磁盘上扫描或将其加载到内存中？

2：skip list的insert操作符经常使用random(0,1)来决定是否插入到下一级，但是在luncene的介绍中，似乎每一项都是固定的区间，那么lucene如何创建不同的“skip list”呢？

如果我错了，请纠正我。

我有大型 postgresql 数据库，包含文档。每个文档都表示为表中的一行。当新文档添加到数据库中时，我需要检查重复项。但我不能只select用来找到完全匹配。两个文档可能略有不同，但仍然可以被视为重复，例如，如果一些次要字段不同而所有其他字段都相同。

我研究这个问题并找到解决这个问题的方法。可以MinHash为每个文档计算签名并构建倒排索引，从数据库中查询相似的文档。但我不明白如何映射MinHash到关系数据库。

据我了解，MinHash签名是 N 个哈希的列表，其中 N 是许多属性。相似度计算如下：

如果您已经有两个签名，这很简单，问题是在数据库中找到相似度小于或等于某个值的所有文档（具有相应签名）。

例如，我可以创建具有多个列的表，如下所示：

每minhashX列对应于文档属性之一的 minhash，并且docid是文档的标识符。我可以这样查询类似的记录：

其中minhash2searchX是新文档的 minhashes，而 THRESHOLD 是最小相似性。但是这种方法需要全扫描。有什么方法可以加速这个算法吗？

我有一个任务：加快倒排索引的当前实施。在我看来，最好的方法是在云中运行它：

1. 将输入文本划分为几个部分（或者只是抓取几个不同的文本文件）
2. 向节点发送文本
3. 针对不同的输入数据在每个节点上运行算法
4. 收集结果并合并它们

我的问题是：实现它的最简单方法是什么？

我目前的想法是：

• 具有工作角色的 Windows Azure - 是否可以将不同的数据发送到节点并稍后合并它们？
• Windows Azure 和 HPC 调度程序 - 对于这样的任务来说是不是太强大了？我害怕配置和成本（新节点 = 新工人角色？）
• 使用任何其他云，例如 Amazon 或 Google - 我想用 c# 编写代码，并且我熟悉 Microsoft 技术，所以我有点害怕它们

请给我任何建议你将如何实现这个目标，我是云计算的新手（虽然我有一些基础知识，比如 mpi、soa、cuda、azure 基础知识）

我需要将大量数据存储在 Invert Index 的地图中，但我的数据非常庞大，我看到随着 Map 变得越来越大，它变得越来越慢。我们正在谈论一个具有非常稀疏索引的 Map 容器，涵盖 1 到数十亿。

在我的程序的一次迭代中，将计算一些数字，以获取许多要存储的键值（可能是数千个） -这意味着 Map 的大小在每次迭代中都会增加大约数千个左右。我看到在最初的几次迭代中，需要 20 秒左右，但在第 70 次左右的迭代中，需要 100 秒左右。我有大约 5000 组数据——也就是说，我需要对所有这些数据进行 5000 次迭代。随着每次迭代的时间呈指数增长，这将需要数天的时间来计算，这是不可接受的。

那么在这种情况下我能做些什么吗？

我有一个搜索引擎，它通过在倒排索引中查看搜索到的文本来搜索文本并编写相应的网页集，并抛出相应的网页。

现在我想再添加一个功能，就是它会根据颜色进行搜索。

例如，当我搜索“ RED SHOES ”时，它会显示所有倒排索引数据结构中的红鞋。

我对相同算法的看法，

1. 在不同的地方制作图像的数据结构。
2. 每当找到图像时，就像夹克的图像一样，因此使用一些颜色查找算法计算其所有颜色。
3. 将该图像放入所有颜色索引中。

所以这是我的爬行方法，当任何像“红鞋”这样的搜索出现时。它通过查看红色索引找到相应的红色项目。

这是我的算法构建阶段，这就是为什么我没有为上述算法编写任何代码。一旦我得到了正确的方法，我就开始了我的编码阶段。

所以请给我一个建议，

这是一个好的算法吗？或者

是否需要任何优化或更改，如果是，请与我分享/讨论这些更改。

提前致谢。寻找您的善意回应。

从我之前的问题：Data structure for storage large number of indices, each pointing to a set中，我得到了关于反转索引实现的合适数据结构的答案。但是，问题是，我们的 Linux 服务器可能很快就会达到 128 GB RAM 的限制，所以我想做好准备，以防我们再次用完它的内存。

现在，我们在 invert 索引中的索引总数高达 39 亿，这需要大约 50 GB 的 RAM。请注意，虽然有些人可能会建议使用数据库系统等，但这是用于实验研究，我们希望管理自己的数据，我们不会使用任何类型的数据库系统。

我也被指出什么时候应该使用 mmap 进行文件访问？虽然这看起来很有希望，但我四处搜索，发现我需要先为 mmap 分配一个固定空间，然后开始放入数据。然而，我的第一个问题 (1) 是因为我们有更大的数据，我知道我的反转索引会更大，但在我构建它之前我不知道确切的数字。（在将这些数据推送到反向索引之前需要先处理一些数据）我可以为它分配很多内存，但是嘿，我们已经获得了 50 GB 的 RAM 和当前的反向索引。这导致了第二个问题（2），我们的服务器有很多人在使用，并且有 50 GB 或更多的空间，我们的数据将在硬盘中四处分散。

或者，如果我使用文件 I/O 来管理它并制作一个像分层目录一样的 B 树呢？事情可能会变得丑陋...

所以这一次，我想征求一些建议，就像我之前的问题一样，但这一次，我需要在 RAM 和硬盘之间交换一些数据，我们的 128 GB RAM 可能无法容纳这个。

我想用 Prolog 做一些信息检索任务。目前，我有一组（大量）不同的 Prolog 理论，它们表示句子中的依赖关系（顺便说一下，我将这些 Prolog 代码存储在一个文本文件中）——我只想找到那些与用户定义的目标子句匹配的理论。

例如，我有这样的 Prolog 代码：

我想搜索这样的目标子句：

如果我对理论进行简单的类似foreach循环，搜索时间会随着理论数量的增加而变慢，所以我必须引入一些优化。

我的想法是创建一个倒排索引，我可以在其中维护每个术语的频率，以及它们发生的理论的 ID。然后在搜索时，我会首先过滤掉那些不会包含在结果中的不必要的理论。

信息检索领域有没有其他行之有效的方法或好的模式和算法可以很好地处理这个问题？