索引算法開發一個應用程序，如谷歌桌面搜索？

Question

我想開發像應用程序的Google桌面搜索，我想知道我應該使用哪種索引技術/算法，這樣我可以獲得非常快速的數據檢索。

Answer 1

用於在bzip2中壓縮數據的Burrows-Wheeler變換可用於使文本的子字符串搜索爲恆定時間函數。

http://en.wikipedia.org/wiki/Burrows-Wheeler_transform

我還沒有看到一個簡單的介紹在網上，但這裏是很多的細節：

http://www.ddj.com/architect/184405504

Answer 2

在一般情況下，你要的是一個Inverted Index。您可以自己進行索引編制，但要正確處理很多工作 - 您需要處理stemming,stop words，擴展發佈列表以包含文檔中的位置，以便處理多字查詢等等。然後，您需要將索引存儲在磁盤上的B-Tree中，或者您可以使用磁盤存儲的現有數據庫（如BDB）使您的生活更輕鬆。您還需要編寫一個查詢計劃程序來解釋用戶查詢，執行query expansion並將其轉換爲一系列索引掃描。維基百科有關Search Engine Indexing的文章也很好地概述了所有的挑戰。

或者，您可以利用現有的工作，並使用現成的全文索引解決方案，如Apache Lucene和Compass（它基於Lucene構建）。這些工具幾乎可以處理上面（以及更多）詳細描述的所有內容，這隻會讓您編寫工具來構建和更新索引，方法是將所有文檔都提供到Lucene中，然後使用UI來允許用戶搜索它。