搜索引擎如何進行「AND」操作？

Question

考慮下面的搜索結果：

• Google for 'David' - 591百萬安打0.28秒
• Google for 'John' - 785百萬安打0.18秒

確定。頁面被編入索引，它只需要查找索引表中的計數和前幾個項目，因此速度是可以理解的。

現在考慮下面的搜索與操作：

• Google for 'David John'（ '大衛' 和 '約翰'） - 173個百萬命中在0.25秒

這讓我打勾;）搜索引擎如何能夠如此快地獲得巨大數據集上的AND運算結果？我看到以下兩種方式來執行任務，兩者都很糟糕：

1. 您進行'大衛'的搜索。拿着巨大的臨時表，並在其上搜索「約翰」。但是，臨時表不是由'John'索引的，因此需要進行強力搜索。不管你有什麼樣的硬件，它在0.25秒內都不會計算。
2. 通過所有可能的詞索引 像'大衛約翰'組合。然後我們面臨一個關鍵數量的組合式爆炸，並且 甚至沒有Google的存儲 容量來處理。

你可以和在一起as many search phrases as you want，你仍然可以在0.5秒內得到答案！怎麼樣？

Answer 1

Markus寫的關於Google在多臺機器上並行處理查詢的問題是正確的。

此外，還有information retrieval算法，使這項工作更容易一些。經典的做法是構建一個inverted index，其中包含過帳列表 - 按順序包含該術語的所有文檔的每個術語的列表。

當查詢包含兩個詞語時，在概念上，您將爲這兩個詞語（'david'和'john'）中的每一個詞彙發佈列表，並沿着它們前進，查找包含這兩個詞條的文檔。如果兩個列表都以相同的方式排序，則可以在O（N）中完成。當然，N仍然很大，這就是爲什麼這將在數百臺機器上並行完成。

此外，還可能有其他技巧。例如，如果列表中排名最高的文檔的排名較高，那麼算法可能會判定它找到了10個最好的結果，而無需遍歷整個列表。然後猜測在其餘數量的結果（基於兩個列表的大小）。

Answer 2

我在一臺16位機器上做了類似於今年的工作。該數據集的上限約爲110,000條記錄（這是一個墓地，因此有限的墓地限制），所以我設置了一系列包含128K位的位圖。

搜索「david」導致我在其中一個位圖上設置相關位以表示記錄中包含單詞「david」。在第二個位圖中，'john'也一樣。

然後你需要做的就是一個二進制的'和'兩個位圖，並且結果位圖告訴你哪些記錄號碼中包含'david'和'john'。對結果位圖進行快速掃描可以讓您找回符合兩個術語的記錄列表。

這種技術不適用於谷歌，所以考慮這個價值0.02美元。

Answer 3

我認爲你是從錯誤的角度接近問題。

Google在單臺機器上沒有表格/索引。相反，他們將數據集大量分佈在服務器上。報告顯示that as many as 1000 physical machines are involved in every single query！利用這種數量的計算能力，它「簡單地」（高度諷刺地使用）確保每臺機器在一秒鐘內完成其工作。

關於Google技術和基礎架構的閱讀非常鼓舞人心且教育程度非常高。我建議您閱讀BigTable,MapReduce和Google File System。

谷歌有一個archive of their publications有很多關於其技術的多汁信息。 This thread on metafilter也提供了一些洞察到運行搜索引擎所需的大量硬件。

Answer 4

我不知道谷歌是怎麼做的，但我可以告訴你我如何做到了，當類似的客戶需要的東西：

它開始倒排索引​​，如阿維描述。這只是一個表格列表，對於每個文檔中的每個單詞，文檔ID，單詞以及單詞在該文檔中的相關性得分。 （另一種方法是將單詞的每個外觀與其位置一一對應起來，但在這種情況下這不是必需的。）

從那裏，它比Avi的描述更簡單 - 不需要單獨搜索爲每個學期。標準數據庫摘要操作可以很容易地做到這一點在單次：

SELECT document_id, sum(score) total_score, count(score) matches FROM rev_index 
WHERE word IN ('david', 'john') GROUP BY document_id HAVING matches = 2 
ORDER BY total_score DESC 

這將返回具有分數都「大衛」和「約翰」（即，這兩個詞的出現）的所有文件的ID，通過有序一些相關性的近似值，無論需要查找多少條或多少條目，都需要大致相同的時間才能執行，因爲IN的性能不受目標集大小的很大影響，並且它使用簡單的count來確定是否所有條款都匹配或不匹配。請注意，這種過於簡單的方法只是將'David'分數和'John'分數相加，以確定總體相關性;它不需要命令/接近/等等。的名字考慮在內。再一次，我確信谷歌確實將這些因素納入他們的分數中，但我的客戶並不需要它。