如何加快搜索按字母順序排列的單詞列表領導通配符匹配

我在我的業餘時間字謎毫無價值，所以我花的其它空餘時間很多於輔助程序，允許通配符搜索模式工作。它效果很好。在我的戴爾筆記本電腦（i5,8GB RAM）上搜索一個140,000字的「字典」，用於通配符匹配的單詞具有幾乎不可察覺的且絕對可接受的延遲，僅當返回數以萬計的單詞時纔會發生。 Java規則。其執行regex和match()也是如此。如何加快搜索按字母順序排列的單詞列表領導通配符匹配

我希望將它移植到Android。我整天工作得到一個或多或少的等效應用程序進行編譯。給定的代碼架構沒有機會。

的問題是，導致通配符可以（必須）被允許。例如，???ENE返回15個匹配項 - 從achENE到xylENE和*RAT返回22個匹配項 - 從aristocRAT直到zikuRAT - 即必須搜索所有140,000個單詞（？），這將在大多數（全部？）上執行aaaaaaaaawhiiiiiiiiile Android設備。（我的筆記本電腦每次花費不到一秒鐘。）（這需要我的電腦3秒鐘才能返回所有140,000字，並稍微長一點以便全部觀察它們。）

由於某些字謎允許字數可變的字母，不允許使用領先的通配符將應用程序的內心切割出來以解決這些難題。但是，如果搜索模式必須以字母開頭，那麼執行二分搜索（或更快）會很容易。（它仍然可能會令人無法接受的緩慢）。

無論如何，我想知道是否有人可能知道一些算法，或者可以想到一些可能被應用於加速使用前導通配符進行搜索的方法。

來源

2015-08-30 DSlomer64

我相信，你正在嘗試做的優化版本是衆所周知的的Unix/Linux工具的「grep」，其中，如果我沒有記錯，使用博耶 - 穆爾搜索算法。

在幕後，Java的圖形類使用博耶 - 穆爾。它支持正則表達式，所以如果你可以寫一些東西把通配符搜索模式變成正則表達式，你可以使用模式。

還有的grep在http://www.java2s.com/Code/Java/Regular-Expressions/AnotherGrep.htm

一個有趣的Java實現它使用內存映射文件。我猜你不能將你的整個單詞列表放入內存中，但是你可以將它分成一堆小文件 - 上面的內存實現 - 一次映射一個文件。您必須進行一些測試才能找到文件的最佳大小。

來源

2015-08-30 02:33:12 GreyBeardedGeek

GreyBeardedGeek（從WhiteBeardedNerd）：謝謝。在翻譯「Windows通配符」（'*'和'？'）和我自己的'＃'（比如'？'，但不允許將相同的字母兩次或更多）轉換爲等效的''''後，我使用'regex'和'match正則表達式「語法。 14萬字只佔用1.4MB。我想知道RAM中的列表或文檔很大。'grep'程序看起來很有趣。 – DSlomer64

嗯...在Netbeans中（我的筆記本電腦上，不是Android）我把所有140k的單詞放入'ArrayList'中，這個花費了與之前報告的相同的3秒來返回所有140k。但隨後對所有140k的請求花費了大約一半的時間。這可能有承諾。 – DSlomer64

在Android上，花了很長時間來加載140,000個單詞，但只花費了15秒將全部40個匹配給'xy *'，但花了30秒纔將所有32個匹配賦給'* rat'，但是花了15秒'鼠*'。我不知道這是領先的，但可能有承諾。 – DSlomer64

我剛剛谷歌搜索，發現有第二個列表反向字母化可能是一種方式，然後有一個領先的通配符成爲尾隨，打開方式開始二進制搜索的門。有趣。但*a???ene*也是該程序中的合法搜索模式。然後怎樣呢？（是啊，多久你會需要這樣的搜索。）

我剛剛發現這個關於Apache Lucene的：

Leading wildcards (e.g. *ook) are not supported by the QueryParser by default.作爲Lucene的2.1的，它們可以通過調用QueryParser.setAllowLeadingWildcard(true)啓用。請注意，這可能是一項昂貴的操作：它需要全面掃描索引中的標記列表以查找與該模式匹配的標記列表。

來源

2015-08-30 19:00:44 DSlomer64

一旦我將列表加載到'ArrayList'中，使用'Collections.binarySearch（...）'IMMEDIATELY查找匹配以字母開頭且不是通配符的模式。但是，及時將140,000個單詞放入他們的'ArrayList'中（我的手機需要一分鐘）。我想知道如果第一次運行應用程序，如果設備上的文件會有所幫助。沒有在設備上完成文件。假設我被允許。也許應該做後臺線程來加載'ArrayList'，這種方式或其他。 – DSlomer64

如何加快搜索按字母順序排列的單詞列表領導通配符匹配

回答

相關問題