如何提高關鍵字搜索的性能？

Question

這是一個面試問題。

你必須編寫程序，它會查找包含所有給定關鍵字的所有文件。你將如何預處理文件以改善搜索性能。

我的回答：

我會用Lucene（或任何其他文本的搜索引擎）。如果我需要手動實現它，我將建立一個索引，將文檔字映射到文檔ids。我們可能應該用B-trees來實現該索引。另一種方法是使用RDBMS（mySQL或smth），但它看起來對我來說太過分了。

它有道理嗎？你會如何回答這個問題？

Answer 1

我同意，大部分時間文本的搜索引擎的是要走的路..真的很容易建立可靠。這裏只是一個小細節：大多數引擎默認進行搜索或搜索，因此您必須指定要匹配所有單詞。

如果你必須建立你自己的解決方案，是的，顯然你必須建立映射..我會使用哈希查找而不是樹索引，但你的樹大概不會太大，所以這只是一個性能改善不大。不過，我沒有看到使用樹的時候，你不需要它的穿越功能，你將永遠不會搜索上一個或下一個字..

更多有趣的細節彈出你在實際檢查你將如何使用你的數據結構。我們舉一個例子搜索：The pony he comes。直觀地說，你不會開始查找the，可能所有的文件都包含它（假設它們是英文文本）。 pony是一個不錯的選擇，並且可以輕鬆縮小搜索範圍。大多數文本搜索引擎都包含這樣的指標：有多少文檔包含該特定字詞。因此，根據你從最不頻繁的開始，並按增加的頻率順序檢查單詞。

一旦你設法縮小了搜索範圍，你就開始意識到你的索引不能很好地工作......你仍然有the這個詞來檢查，並且在你的索引中會顯示數十億個文檔，所以在這個指出使用反向映射會更好，從文檔到單詞（再次，哈希查找或trie）。你檢查一些文件，看它們是否包含剩餘的單詞。

注：這裏的許多決定（如何存儲的映射，單一或雙繪圖，B樹/散列/線索/ ...）取決於項目的規模。如果你必須在幾個文件中搜索，建立一些簡單的東西，並建立一些不同的東西，如果你必須索引github上的所有文件，或者用於基因序列搜索，甚至索引可能不適合內存...