假设我的 couchdb 文档看起来像这样：

我想要的是从标签创建一个倒排索引，所以我最终得到的是：

根据我的阅读和尝试，couchdb 可能不会让我这样做。我无法在地图阶段完成它，而且我似乎无法在沙发缩减阶段完成它。这是我需要在应用程序的另一层完成的事情吗？

我的输出是：

word , file ----- ------ wordx Doc2, Doc1, Doc1, Doc1, Doc1, Doc1, Doc1, Doc1

我想要的是：

word , file ----- ------ wordx Doc2, Doc1

为了获得最佳性能 - 我应该在哪里跳过重复出现的文件名？映射，减少或两者兼而有之？ps：我是编写MR任务的初学者，也试图用我的问题弄清楚编程逻辑。

I read the paper by Doug Cutting; "Space optimizations for total ranking".

Since it was written a long time ago, I wonder what algorithms lucene uses (regarding postings list traversal and score calculation, ranking).

Particularly, the total ranking algorithm described there involves traversing down the entire postings list for each query term, so in case of very common query terms like "yellow dog", either of the 2 terms may have a very very long postings list in case of web search. Are they all really traversed in the current Lucene/Solr? Or are there any heuristics to truncate the list employed?

In the case when only the top k results are returned, I can understand that distributing the postings list across multiple machines, and then combining the top-k from each would work, but if we are required to return "the 100th result page", i.e. results ranked from 990--1000th, then each partition would still have to find out the top 1000, so partitioning would not help much.

Overall, is there any up-to-date detailed documentation on the internal algorithms used by Lucene?

我目前正在使用 MongoDB 来看看它有哪些不错的功能。我创建了一个小型测试套件，代表一个简单的博客系统，其中包含帖子、作者和评论，非常基本。

我尝试了一个使用 MongoRegEx 类（PHP 驱动程序）的搜索功能，我只是在“/I”上区分大小写的句子“lorem ipsum”之后搜索所有帖子内容和帖子标题。

我的代码如下所示：

但我对发生的事情感到困惑和震惊。我检查每个查询的运行时间（在查询之前和之后设置微时间并获得 15 位小数的时间）。

对于我的第一个测试，我添加了 110.000 个博客文档和 5000 个作者，所有内容都是随机生成的。当我进行搜索时，它会找到 6824 个带有“lorem ipsum”句子的帖子，搜索需要 0.000057935714722 秒。这是在我重置 MongoDB 服务（使用 Windows）之后，除了 _id 上的默认值之外没有任何索引。

MongoDB 使用 B-tree 索引，这对于全文搜索肯定不是很有效。如果我在我的帖子内容属性上创建一个索引，与上面相同的查询在 0.000150918960571 中运行，这很有趣，这比没有任何索引时要慢（慢，系数为 0.000092983245849）。现在发生这种情况有几个原因，因为它使用了 B 树游标。

但我试图寻找关于它如何如此快速地查询它的解释。我想它可能会将所有内容都保存在我的 RAM 中（我有 4GB，数据库大约 500MB）。这就是为什么我尝试重新启动 mongodb 服务以获得完整结果的原因。

任何有 MongoDB 经验的人都可以帮助我了解这种带或不带索引且绝对没有倒排索引的全文搜索发生了什么吗？

真诚的 - Mestika

2020-02-18 更新

我再次遇到了这个问题，虽然接受的答案保持不变，但我想分享我现在如何优化它（再次不使用第三方库或工具 - 即从头开始重新发明轮子，就像原始问题中提到的那样） .

为了简化和优化这个系统，我将在域逻辑层上使用Trie（前缀树）而不是“倒排索引映射”，并完全摒弃“表查询” SQL 表的不良做法。我将举例说明：

• 假设该应用程序的一些用户已经在数据库中添加了几个对象：w、wo、woo、wood 和 woodx。
• 这些对象（字符串/标签）将由内存中的 Trie 表示，每个 Trie 节点将包含该对象在树中所在级别的数据库发布 ID（Think Associative Array）。
• 当用户查询一个词时，我们在 Trie 中搜索该词并在途中累积所有相关的 ID，从搜索的词开始向下移动（即按顺序从那里遍历）。我们从这些 ID 中检索所有需要的对象数据（无论是来自缓存还是数据库）。

这是一张图片来说明：

• 接下来，如果用户向数据库中添加一个新词，例如“ woodxe ”，则 Trie 会相应更新。
• 当用户查询“ woodx ”时，会发生与之前相同的过程，并且会累积一个新的ID（“ woodxe ”的发布ID）
• 英语词典中有一个以特定字母序列开头的有限单词列表，因此向下移动并获取所有子节点仍然是一个 O(1) 复杂度的有限过程。例如，如果您在 Trie 上以“wood”开头，则在英语词典中以“wood”为前缀的子节点列表是一个有限常数。无论您将所有这些子节点返回给用户、定义限制（延迟加载/分页）还是仅显示前 10 个点击，都是个人架构偏好。

这是一张图片来说明（检查绿色添加的内容）

• 当用户的查询是多字串时，例如：“木家具”，每个字都被单独解析/添加到 Trie 中，并且每个字都有相应的匹配 ID 列表。

*Trie* 如何改进以前的架构？

• “表查询”很麻烦、不好的做法，而且开销很大，而且与数据库成正比增长；现在已删除。
• 我们拥有的“倒排索引映射”产生了额外的内存开销，并且无法通过新词轻松扩展（如上面的“woodx”示例）。有人可能会争辩说，查询一个 Hashmap 是 O(1)，但是在内存中有几个大的 hashmap 实际上会在一定程度上减慢速度，并且被认为是糟糕的工程设计。
• trie 的搜索复杂度为 O(m)，其中 m 是提供的字母表中的字符数。由于用户查询的是纯粹使用英文字母的单词，因此最大的子树将等于可用的最大英文单词（常数，即 O(1)）。此外，如前所述，英语词典中以定义的单词前缀开头的子节点的数量也是一个常数，因此遍历所有组合是 O(1)。所以总的来说这是一个 O(1) 操作。
  • 所以查询 Trie = Get key from Hashmap = O(1) 一样快。
  • 最重要的是，在这个系统中尝试的好处是：
    • 比在内存中运行多个倒排索引哈希映射的内存开销更小
    • 集中查询树
    • 易于扩展，添加到数据库的新词只需要在内存中的现有 Trie 中添加几个新节点。即，不再有数据库增长和搜索查询数量增加的问题（可扩展性噩梦）。

2015-10-15 更新

早在 2012 年，我正在构建一个个人在线应用程序，实际上我想重新发明轮子，因为我天生好奇，为了学习目的并提高我的算法和架构技能。我本可以使用 apache lucene 和其他的，但是正如我所提到的，我决定构建自己的迷你搜索引擎。

问题：那么，除了使用可用的服务（如 elasticsearch、lucene 等）之外，真的没有办法增强这种架构吗？

原始问题

我正在开发一个 Web 应用程序，用户在其中搜索特定的标题（例如：book x、book y 等），这些数据位于关系数据库 (MySQL) 中。

我遵循的原则是，从数据库中获取的每条记录都缓存在内存中，这样应用程序对数据库的调用就更少了。

我开发了自己的迷你搜索引擎，具有以下架构：

这是它的工作原理：

• a) 用户搜索记录名称
• b）系统检查查询以什么字符开头，检查是否有查询：获取记录。如果不存在，则添加它并使用两种方式从数据库中获取所有匹配记录：
  • 表“查询”（这是一种历史表）中已经存在的任一查询，因此根据 ID 获取记录（快速性能）
    
  • 或者，否则使用Mysql LIKE %% 语句来获取记录/ID（然后将用户使用的查询连同它映射到的 ID 一起保存在历史表查询中）。
    -->然后它将记录及其ID添加到 缓存中，并且仅将ID添加到倒排索引映射中。
• c) 结果返回到 UI

该系统工作正常，但是我有两个主要问题，我找不到一个好的解决方案（过去一个月一直在尝试）：

第一个问题：
如果您检查点 (b) ，没有找到查询“历史”并且它必须使用Like %%语句的情况：当查询匹配数据库中的大量记录（而不是一个或二）：

• 从 Mysql 获取记录需要一些时间（这就是我在特定列上使用 INDEXES 的原因）
• 然后是时候保存查询历史了
• 然后是时候向缓存和倒排索引图添加记录/ID

第二个问题：
应用程序允许用户自己添加新记录，其他登录到应用程序的用户可以立即使用这些记录。
然而，为了实现这一点，必须更新倒排索引映射和表“查询”，以便在任何旧查询与新词匹配的情况下。例如，如果要添加新记录“woodX”，旧查询“wood”仍然会映射到它。因此，为了将查询“wood”重新连接到这个新记录，这就是我现在正在做的事情：

• 新记录“woodX”被添加到“记录”表中
• 然后我运行一个Like %%语句来查看表“查询”中哪个已经存在的查询映射到该记录（例如“wood”），然后将此查询与新记录 id 添加为新行： [ wood, new ID]。
• 然后在内存中，更新倒排索引 Map 的“wood”键的值（即列表），将新的记录 ID 添加到这个列表中

--> 因此，现在如果远程用户搜索“wood”，它将从内存中获取：wood 和 woodX

这里的问题也是时间消耗。将所有查询历史（在表查询中）与新添加的单词匹配需要很长时间（匹配的查询越多，时间越长）。那么内存中的更新也需要很多时间。

我正在考虑解决这个时间问题，首先将所需的结果返回给用户，然后让应用程序使用所需的数据发布一个ajax调用以实现所有这些更新任务。但我不确定这是一种不好的做法还是一种不专业的做事方式？
所以在过去的一个月里（再多一点），我试图为这个架构考虑最好的优化/修改/更新，但我不是文档检索领域的专家（实际上它是我构建的第一个迷你搜索引擎）。

对于我应该做些什么来实现这种架构，我将不胜感激任何反馈或指导。
提前致谢。

PS：

• 它是一个使用 servlet 的 j2ee 应用程序。
• 我正在使用 MySQL innodb（因此我不能使用全文搜索选项）

因为我想测试一些inverted index压缩算法，所以我需要一些标准数据集，比如我上面提到的那些。

这些数据集可以免费下载吗？

据我所知，这些数据集由格拉斯哥大学分发，并且与大多数其他TREC测试数据集一样，不是免费的。

给定n字符串S1, S2, ..., Sn和字母集A={a_1,a_2,....,a_m}。假设每个字符串中的字母都是不同的。现在我想为每个a_i (i=1,2...,m). 我的倒排索引也有一些特别之处：其中的字母A是按顺序排列的，如果倒排索引中 a_i 包含一个字符串（例如S_2），则a_j (j=i+1,i+2,...,m)不需要再包含S_2任何内容。简而言之，每个字符串只在倒排列表中出现一次。我的问题是如何以快速有效的方式建立这样的列表？任何时间复杂度都是有界的？

例如，A={a,b,e,g}, S1={abg}, S2={bg}, S3={gae}, S4={g}。那么我的倒排列表应该是：

我有一个问题，其中有大量的字符串或短语，它可能从 100,000 扩展到 100Million。当我搜索一个短语时，如果找到它会给我 ID 或数据库索引以供进一步操作。我知道哈希表可以用于此，但我正在寻找其他算法，它可以为我提供基于字符串生成索引的服务，也可以在自动完成等其他一些功能中有用。

我根据一些 SO 线程读取后缀树/数组，它们服务于目的，但消耗的内存超出了我的承受能力。有什么替代方法吗？

因为我的搜索只在数百万个字符串的巨大列表中。没有文档，没有对 lucene 等搜索引擎不感兴趣的网页。

还阅读倒排索引听起来很有帮助，但我需要学习哪种算法？

我正在努力创建一个非常大的倒排索引术语。你会建议什么方法？

第一的

第二

ps Lucene 不是一个选项

默认情况下 SOLR 接受 XML 文件，我想对数百万个已抓取的 URL（html）执行搜索。