數據結構索引整個文檔和算法進行快速搜索任何規模大小子

Question

我試圖找到一個數據結構（和算法），讓我來索引整個文本文檔，並搜索它的子，也不管子字符串的大小。在索引過程中或結束時，數據結構應存儲在磁盤中。

例如，給定下面的句子：

The book is on the table 

算法應該迅速（O(log(n))）找到的出現的任何文本子集。

例如，如果輸入是book它應該找到它的所有實例，但這也應該是book is和The book is。

不幸的是，大多數解決方案通過令牌化的文本，並使用單獨的標記使搜索工作。普通的數據庫也可以索引任何文本，而不用擔心子集搜索（這就是爲什麼SELECT '%foo%'用線性搜索完成並需要很多？）。

我可以嘗試從頭開發的東西（可能是反向指標的變化？），但我很想發現有人這樣做。

最類似的事情，我發現是SQLite3 Full-text search。

謝謝！

Answer 1

一種方法是指數在一個suffix tree您的文檔，然後 - 一些後綴的每個前綴 - 在文檔中的子字符串。

使用這種方法，您只需構建後綴樹，並在查詢子字符串s時，遵循樹中的節點，並且如果您可以按照整個查詢字符串執行操作，則表示有後綴，它的前綴是查詢字符串 - 因此它也是一個子字符串。

---

如果您只查詢完整單詞，則inverted index可能就夠了。倒排索引通常映射某個術語（單詞）到它出現在文檔列表。相反，你會映射到文檔中的位置。

經查詢，你需要找到在查詢詞i每一次出現，它的位置（讓它成爲p），如果你的查詢期限i+1，出現以及在p+1位置。

這可以非常有效地進行，類似於傳統是如何倒排索引做和查詢，而是進行搜索相同的文檔，在增加職位搜索項中的所有條款。