0
我有一個包含單詞列表的字典，我有一個字符串URL。我想使用分隔符將URL分解爲令牌後，找到URL中包含的所有單詞。現在，我正在對字典中的每個單詞進行測試，以確定每個大於特定數字的標記（使用java的String contains函數）。例如，我在www.wunderground.com搜索wunderground中的「ground」這樣的詞。高效搜索字符串中的單詞
我確信有一種更有效的方法可以做到這一點。有任何想法嗎？
A
回答
1
如果您將字典加載到HashMap中，您可以測試每個候選子字符串（「wunderground」，「underground」，「nderground」，「derground」，...，「wundergroun」，...，「） 「，......」地「，...）很快，特別是在O（1）時間。
爲了衡量效率：找出它需要做多少步驟。我們會估計它的大O複雜性。
您當前的算法必須遍歷整個字典：工作量與字典大小成正比，D條目）。對於每個字典單詞，它調用：工作與URL字的大小（C字符）的比例減去平均字典字的大小，我們將調用它5.因此，這取決於D *（C - 5）步驟，O（D *（C-5）），爲URL中的每個單詞。
生成哈希表後，查找的開銷與條目數無關。每個C字符的URL項都有C 子字符串。如果將它修剪成至少5個字符的子字符串，那就是（C-5）子字符串。 [從技術上講，它是（C - 5）*（C - 4）/ 2，但我們正在計算漸近複雜度，這是一個大概的近似值。]所以在字典中查看它們的代價是（C - 5）步驟。再次，這是針對URL中的每個單詞並且與字典大小無關。
假設您的字典有10,000個條目，並且平均URL長度爲10個字符。然後，舊算法需要每個URL術語50000步，而哈希算法需要每個URL術語 25步。合理？
但有時這個詞被嵌入到字符串中，如「wunderground」中的「ground」。我不能提前索引「wunderground」。 – user436390 2014-09-23 22:11:29
在運行時，您只需將術語「wunderground」拆分爲所有候選單詞（子字符串），然後測試每個候選單詞以查看它是否在HashMap中。候選名單不會很長（假設條款很短，如「wunderground」），每個測試都會很快。 – Jerry101 2014-09-23 22:15:10
好的，謝謝。這可能確實比循環每個令牌的整個字典更快。 – user436390 2014-09-24 00:11:55