如何在文本文件中搜索多个字符串

Question

我正在处理文本文件。我想在Java中实现一个搜索算法。我有一些需要搜索的文本文件。

如果我只想查找一个单词，我可以将所有文本放入哈希表中，并存储每个单词的出现次数。但是，如果我想搜索两个字符串（或更多），是否有任何算法可用？我应该将这些字符串成对哈希吗？

- Arjit

Answer 1

这很大程度上取决于文本文件的大小。通常有几种情况需要考虑：

1. 查询很多非常短的文档（网页，文章长度等）。文本分布类似正常语言。简单的O(n^2)算法就可以了。对于长度为n的查询，只需取长度为n的窗口并滑动它。比较并移动窗口直到找到匹配项。该算法不关心单词，因此您只需将整个搜索视为一个大字符串（包括空格）。这可能是大多数浏览器所做的。KMP或Boyer Moore不值得尝试，因为O(n^2)的情况非常罕见。
2. 在一个大型文档中进行许多查询。预处理文档并存储为预处理。常见的存储选项是后缀树和倒排列表。如果您有多个文档，可以通过连接它们并单独存储文档结尾来构建一个文档。这是文档数据库的最佳选择，其中集合几乎是恒定的。
3. 如果您有多个文档，其中高度冗余且您的集合经常发生变化，请使用KMP或Boyer Moore。例如，如果您想在DNA数据中查找特定序列，并且您经常获得新的序列以及实验中的新DNA，则天真算法的O(n^2)部分会浪费您的时间。

可能还有很多需要不同算法和数据结构的情况，因此您应该确定哪种情况最适合您。

- LiKao

Answer 2

在提出建议之前，需要更多细节：

您是只搜索完整的单词还是任意子字符串？

您是否要在同一个未更改的文件中搜索许多不同的单词？

您是否已经知道要同时搜索哪些单词？

有许多高效（线性）的字符串搜索算法。如果可能，建议使用已经为您编写的算法。

http://en.wikipedia.org/wiki/String_searching_algorithm

一个简单的想法是使用滑动窗口哈希，窗口大小与搜索字符串相同。然后在单次遍历中，您可以快速检查窗口哈希是否与搜索字符串的哈希匹配。如果匹配，则再次检查以确定是否有真正的匹配。

- AutomatedMike

---

我想搜索一个可能不是子字符串的单词（我现在不想处理通配符）。是的，我要在同一个文件中搜索许多不同的单词。不，我不知道我想要搜索的单词，搜索取决于用户。是的，我理解了滑动窗口的概念，但问题在于滑动窗口的大小，因为我可以搜索两个相邻的单词。例如，如果我可以在这个网页上搜索1.许多2.许多不同3.许多不同的单词。那么，滑动窗口的大小应该是多少？ - Arjit

Rabin Karp只有在某些特殊情况下（基本上是同时搜索多个字符串）才能与KMP或Boyer Moore相媲美，否则最好选择其他算法。如果您想一次搜索更大的单词集，则Rabin Karp变得有趣且易于实现。 - Voo

浏览器是如何做到的？比如Chrome？它使用了哪种算法？因为我正在尝试获得浏览器具有的效果。 - Arjit

如果您想同时搜索三个不同长度的单词，可以在同一次操作中维护3个不同的哈希窗口。您需要多快才能完成此操作？文档搜索频率如何？请问自己是否值得预处理文档。如果是用户驱动的搜索（例如浏览器），我认为上述方法就足够了。 - AutomatedMike

这是一个文本文件，所以我想要预处理该文件，因为它不会改变。该文本文件仅用于查看，而不能进行编辑。因此，当我应用其他任何东西时，我发现了这个...我认为这很有趣http://johannburkard.de/software/stringsearch/。 - Arjit

如果文件永远不会改变，并且您期望进行大量搜索，则应将此文件存储为后缀树。在后缀树上搜索子字符串仅需要O(m)的时间，其中m是字符串的长度（而搜索算法至少需要O(n)，n是文本的长度）。但是构建树需要O(n^2)的时间，因此您需要足够的查询来弥补这一点。 - LiKao