我有一本包含单词列表的字典,并且有一个字符串 URL。我想在使用分隔符将 URL 分解为标记后找到 URL 中包含的所有单词。现在,我正在针对大于特定数字的每个标记测试字典中的每个单词(使用 java 的 String contains 函数)。例如,我在 wunderground 中搜索“ground”之类的单词 www.wunderground.com
我确信有一种更有效的方法可以做到这一点。有什么想法吗?
最佳答案
如果将字典加载到 HashMap 中,则可以测试每个候选子字符串 ("wunderground", "underground", "nderground", "derground", ..., "wundergroun", ..., "under",...“地面”,...)非常快,特别是在 O(1) 时间内。
衡量效率:计算出它需要执行多少步。我们将估计其大 O 复杂性。
您当前的算法必须循环遍历整个字典:工作量与字典大小(D 条目)成正比。对于每个字典单词,它调用 contains()
:工作量与 URL 单词的大小(C 字符)减去平均字典单词大小(我们称之为 5)成正比。对于 URL 中的每个单词,D * (C - 5) 个步骤的顺序为 O(D * (C - 5))。
构建哈希表后,查找成本与条目数无关。 C 字符的每个 URL 术语都有 C2 子字符串。如果将其修剪为至少 5 个字符的子字符串,则为 (C - 5)2 个子字符串。 [嗯,从技术上讲,它是 (C - 5) * (C - 4)/2,但我们正在计算渐近复杂度,这是大局近似。] 因此,在字典中查找它们的成本是 (C - 5)2 步骤。同样,这适用于 URL 中的每个单词,并且与字典大小无关。
假设您的字典有 10,000 个条目,平均 URL 术语长度为 10 个字符。那么旧算法每个 URL 术语需要 50,000 步,而哈希算法每个 URL 术语需要 25 步。有道理吗?
关于java - 高效搜索字符串中的单词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26005246/