Luí*_*ues 23 algorithm indexing search-engine full-text-indexing inverted-index
我知道全文搜索的一个基本方面是使用倒排索引.因此,使用反向索引,单字查询变得微不足道.假设索引的结构如下:
some-word - > [doc385,doc211,doc39977,...](按等级排序,降序排序)
要回答该单词的查询,解决方案就是在索引中找到正确的条目(需要O(log n)时间)并从索引中指定的列表中显示一些给定数量的文档(例如前10个).
但是那些返回与两个单词相匹配的文档的查询呢？最直接的实现如下:
现在,第三步可能需要O(n log n)时间来执行.对于非常大的A和B,可能使查询缓慢回答.但像谷歌这样的搜索引擎总会在几毫秒内回复他们的答案.所以这不是完整的答案.
一个明显的优化是,由于像谷歌这样的搜索引擎无论如何都没有返回所有匹配的文档,我们不必计算整个交集.我们可以从最小的集合(例如B)开始,并找到足够的条目,这些条目也属于另一个集合(例如A).
但是,我们还不能有以下最糟糕的情况吗？如果我们设置A是与普通单词匹配的文档集,并且集合B是与另一个常用单词匹配的文档集,则可能仍然存在A∩B非常小的情况(即,组合很少).这意味着搜索引擎必须线性地遍历B的所有元素x成员,检查它们是否也是A的元素,以找到符合这两个条件的少数元素.
线性不快.并且您可以使用两个以上的单词进行搜索,因此仅使用并行性肯定不是整个解决方案.那么,这些案例如何优化？大型全文搜索引擎是否使用某种复合索引？布隆过滤器？有任何想法吗？
正如你所说的那样 - > [doc385,doc211,doc39977,...](按排名,降序排序),我认为搜索引擎可能不会这样做,文档列表应按文档ID排序,每个文档都有根据这个词排名.
查询到来时,它包含多个关键字.对于每个单词,您都可以找到一个文档列表.对于所有关键字,您可以执行合并操作,并计算doc与查询的相关性.最后将排名靠前的相关性doc返回给用户.
并且可以分发查询过程以获得更好的性能.
即使没有排名，我想知道谷歌如何如此快地计算两个集合的交集。
\n\n显然，计算某些单词 A、B、C 的交集的最坏情况是它们的索引非常大而交集非常小。典型的情况是搜索不同语言中的一些非常常见（数据库术语中的“流行”）单词。
\n\n让我们尝试一下中文的“具体”和 \xe4\xbd\x8d\xe7\xbd\xae（“站点”、“位置”）和 \xe6\xa5\xb5\xe7\xab\xaf\xe3\x81\日语中的 xaa（“极端”）。
\n\nGoogle 搜索 \xe4\xbd\x8d\xe7\xbd\xae 返回“大约 1,500,000,000 个结果（0.28 秒）” \nGoogle 搜索“concrete”返回“大约 2,020,000,000 个结果（0.46 秒）” \nGoogle 搜索“\xe6\ xa5\xb5\xe7\xab\xaf\xe3\x81\xaa"大约 7,590,000 个结果（0.25 秒）
\n\n这三个术语极不可能出现在同一个文档中，但让我们用 google 搜索它们：\nGoogle 搜索“concrete \xe4\xbd\x8d\xe7\xbd\xae \xe6\xa5\xb5\xe7 \xab\xaf\xe3\x81\xaa" 返回“大约 174,000 个结果（0.13 秒）”
\n\n添加俄语单词“\xd0\xb8\xd0\xb3\xd1\x80\xd0\xb0”（游戏）\n搜索\xd0\xb8\xd0\xb3\xd1\x80\xd0\xb0：约212,000,000个结果（0.37秒） ）
\n\n搜索所有这些： " \xd0\xb8\xd0\xb3\xd1\x80\xd0\xb0 混凝土 \xe4\xbd\x8d\xe7\xbd\xae \xe6\xa5\xb5\xe7\xab\xaf\xe3 \x81\xaa " 返回大约 12,600 个结果（0.33 秒）
\n\n当然，返回的搜索结果是无意义的，它们不包含所有搜索词。
\n\n但是看看组合查询的查询时间，我想知道是否在单词索引上计算了一些交集。即使所有内容都在 RAM 中并且高度分片，计算具有 1,500,000,000 和 2,020,000,000 个条目的两个集合的交集也是 O(n)，并且很难在 <0.5 秒内完成，因为数据位于不同的机器上并且它们必须进行通信。
\n\n肯定有一些连接计算，但至少对于流行词来说，这肯定不是在整个词索引上完成的。再加上结果是模糊的，谷歌显然使用了某种“返回一些排名靠前的结果，并在 0.5 秒后停止”的优化。
\n\n这是如何实现的，我不知道。有任何想法吗？
\n