java - 高效搜索字符串中的单词

Question

我有一本包含单词列表的字典，并且有一个字符串 URL。我想在使用分隔符将 URL 分解为标记后找到 URL 中包含的所有单词。现在，我正在针对大于特定数字的每个标记测试字典中的每个单词(使用 java 的 String contains 函数)。例如，我在 wunderground 中搜索“ground”之类的单词 www.wunderground.com

我确信有一种更有效的方法可以做到这一点。有什么想法吗？

Answer 1

如果将字典加载到 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 术语都有 C² 子字符串。如果将其修剪为至少 5 个字符的子字符串，则为 (C - 5)² 个子字符串。 [嗯，从技术上讲，它是 (C - 5) * (C - 4)/2，但我们正在计算渐近复杂度，这是大局近似。] 因此，在字典中查找它们的成本是 (C - 5)² 步骤。同样，这适用于 URL 中的每个单词，并且与字典大小无关。

假设您的字典有 10,000 个条目，平均 URL 术语长度为 10 个字符。那么旧算法每个 URL 术语需要 50,000 步，而哈希算法每个 URL 术语需要 25 步。有道理吗？