搜索在字典中的字 - 數據結構和方法

我正在寫一個應用程序，我面臨的任務是尋找可能的話基於一個輸入字符串字典和一個什麼樣的描述到搜索。字典是一個文本文件（每行一個字），包含大約220,000個字。搜索在字典中的字 - 數據結構和方法

的輸入字符串可以由四件事情：

普通字符 A-Z
小丑 *。這可以是任何字符A-Z
元音 @。字符必須是元音
輔音＃。字符必須是輔音

例如，輸入字符串* AT @＃應該返回類似「rated」，「satin」，「later」等的單詞，但不包含單詞「ratio」，因爲它不會「 t以輔音結束。

A description用於說明輸入字符串應該如何出現在單詞中。它可以是：

單詞以開頭。 * AT @＃作爲輸入返回像「材料」這樣的詞。
單詞以結尾。 * AT @＃作爲輸入返回像「冰箱」這樣的詞。
單詞包含。 * AT @＃作爲輸入返回類似「照顧」的文字
單詞符合。 * AT @＃作爲輸入返回像「hater」這樣的詞。

首先要弄清楚的是字典的最佳數據結構。由於我有要考慮的描述，所以我不確定樹結構是否是最好的選擇。這對於前綴搜索似乎很好，我可以創建另一棵倒轉詞來處理後綴搜索。我不確定包含一系列字符的單詞。一棵樹感覺不對。另一方面，我想不出別的什麼。我的每個描述應使用哪些數據結構？

我也想創建一個基於輸入字符串和描述的正則表達式，然後將它與字典中的每個字符串進行匹配。不過，我之前沒有使用正則表達式，所以我不知道這是多麼昂貴。

在此先感謝！

來源

2015-02-10 Richard Silvertass

只要他們已經在內存中（因此你不會在每次搜索時加載文件），搜索220,000個單詞的「啞」方式，可能會少於0.1秒。 – immibis 2015-02-10 23:21:49

這可能是你要求的輕微重複，但是... [字典實現的最佳數據結構]（http://stackoverflow.com/questions/10017808/best-data-structure-for-dictionary-implementation ） – Ascalonian 2015-02-10 23:25:12

@immibis感謝您的意見。我的字典雖然不是很好。我的願望是讓我的手接近一百萬字。我希望學習新的東西，而不是隻堅持一個醜陋的解決方案！ – 2015-02-10 23:44:58

在我的一個類中，我們使用了trie數據結構來存儲字典。樹狀結構的每個節點都有一個字符串，它只是它的字母，它的子代表可以根據字典中的單詞跟隨它的任何字母。例如，如果第一個trie節點的字母是'a'並且apple，abraham和acorn在字典中，則該節點將具有'p'，'b'和'c'的子節點。每個節點還有一個布爾值，表示它是否是字典包含的任何單詞的最後一個字母。然後，通過將輸入詞中的第一個和後續字母與可用的子節點進行比較，檢查字典中的詞存在。優點是您可能遇到的最糟糕的表現是您正在搜索的單詞中的字母數量的26倍。

來源

2015-02-11 00:29:20 richtarj

搜索在字典中的字 - 數據結構和方法

回答

相關問題