超快速「開始」從磁盤查詢

Question

我有一個40MB（在這種情況下內存太大）我想要做的字符串列表「開始」查詢來提取匹配。任何人都知道這個數據結構很好？現有os操作系統實現的獎勵點數。如果事物已經存在，我會願意犧牲「開始於」完全匹配。基於磁盤的刻錄機聽起來很理想。

Answer 1

它看起來像你需要像這樣：http://en.wikipedia.org/wiki/Trie

在Java中的實現可以發現here，雖然它不是基於磁盤的。我會繼續尋找：/

有用的論文：Trie methods for text and spatial data on secondary storage，B-tries for disk-based string management

編輯：我碰到這也許可能是有用的：MG4J: Managing Gigabytes for Java™

Answer 2

不能提出任何現有的庫，但我處理類似問題之前。如果您不打算動態修改列表，並且可以對文件中的字符串進行排序（用於二進制搜索），這很容易。

讓我們將您的40Mb分成幾乎相同大小的1000個塊，並保留內存中每個塊的第一個字符串。這將是一個包含1000個字符串的數組。他們是有序的，因爲原始列表是有序的。
當您需要執行查詢時，可以在該數組上使用二進制搜索。這會告訴你哪個塊結果字符串在哪裏。然後，您可以從磁盤讀取該塊（大約40kb）並搜索其內容。例如，如果數組的值爲["andrew", "brian", "donald", "john"]，並且您搜索前綴"cris"，那麼您知道所有的Cristophers和Cristians都在第二個塊中。