快速字符串搜索像startsWith（）不等於（）

我有一個有序的列表（一本字典 - 100K字）和許多單詞頻繁地在這個列表上。所以性能是一個問題。我知道HashSet.contains（theWord）或Collections.binarySearch（sortedList，theWord）非常快。但我實際上並沒有在尋找整個詞彙。快速字符串搜索像startsWith（）不等於（）

我想要的是讓我們說搜索「se」並獲取所有的單詞以「se」開頭。那麼在Java或任何庫中是否有可用的解決方案？

一個更好的例子：在排序的列表以下操作

List.subList（字符串的beginIndex，字符串endIndex的）//返回的間隔

myWordList.subList（「AB」一個快速解決方案，「公元前」）;

注意：這是一個非常類似的問題，但接受的答案並不令人滿意。 Overriding HashSet's Contains Method

來源

2010-07-28 hrzafer

什麼你正在尋找在這裏是一種數據結構commanly稱爲「線索」：

http://en.wikipedia.org/wiki/Trie

它存儲的字符串由前綴，在樹的第一級包含索引樹字符串的第一個字符，第二個字符的第二個字符等等。結果是，它允許您非常快速地通過前綴提取非常大的字符串集合的子集。

來源

2010-07-28 16:10:41

是否有任何流行的庫提供的實現？ – 2011-11-24 16:26:42

這一個？聲稱它已被貢獻給Apache Commons Collections和Google Collections，但快速查看ACC並未在Javadoc中顯示它。 http://code.google.com/p/patricia-trie/ – 2011-11-24 23:19:23

是的確切..我也無法弄清楚這就是爲什麼問你。 – 2011-11-25 05:58:08

該Trie結構非常適合字典和找到具有共同前綴的單詞。 Google Collections/Guava中有一個Trie implementation的貢獻。

來源

2010-07-28 16:10:09 mdma

我檢查了一下。它看起來很好。但是我無法編譯代碼。它依賴於其他一些使事情更復雜的軟件包。我只是修改字符串的二分查找實現。 – hrzafer 2010-07-29 09:22:10

我無法弄清Guava庫或Apache commons集合中的Trie實現。它有其他名字嗎？ – 2011-11-25 06:00:39

真的沒有什麼大的新結構需求：問題可以通過你的清單上的二進制搜索來解決。特別是，您可以修改二進制搜索以返回第一個匹配元素（具有指定前綴的第一個元素）。

List.subList（字符串的beginIndex，endIndex的字符串）//返回的時間間隔
我可能是愚蠢的，但什麼樣的指數具有字符串類型？你能澄清這部分嗎？

來源

2010-07-28 16:21:58

我只是想用已知方法解釋問題，例如List.subList（int beginIndex，int endIndex） – hrzafer 2010-07-28 16:37:08

@hrzafer那麼，這些參數有什麼意義？它是字符串前綴和後綴？ – 2010-07-28 16:42:48

是的，字符串前綴。 – hrzafer 2010-07-29 09:18:48

您的搜索結果將從您訂購的單詞列表中進行選擇。要做到這一點，您需要範圍的第一個和最後一個元素的索引。

要獲得第一個，請使用原始搜索字符串（「se」）運行二進制搜索，並將其與每次迭代中的當前位置進行比較。停止當前位置的單詞大於搜索字符串，但當前的第1個單詞較低。

要獲得最後一個索引，請在搜索項+「z」（「sez」）上運行另一個二進制搜索，但現在只在當前索引處的單詞小於「sez」但當前+1更大時停止。

最後，以您的編程語言中提供的任何方式返回第一個和最後一個索引標記的範圍。

這種方法是建立在兩個假設：

字符串比較看「B」大於「AZ」
「Z」是單詞的列表中最高的char值

我在JavaScript數據操作庫（jOrder.net）中實現了此算法。

來源

2010-07-28 16:31:15

你真的應該使用Character.MAX_VALUE而不是「z」，但除此之外，這篇文章幾乎總結了它。根據你正在做的事情，當我遇到這樣的問題時，我通常在前綴上進行二分搜索，然後使用「while（value.get（x）.startsWith（prefix））」進行處理，而不是嘗試返回一個範圍。 – Jay 2010-07-28 16:40:08

我完全同意你在Character.MAX_VALUE部分，但是考慮到100k的幅度，考慮執行log（N）（N =字典長度）附加字符串比較而不是K（K =結果集長度）？ – 2010-07-28 16:53:32

快速字符串搜索像startsWith（）不等於（）

回答

相關問題