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

Question

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

如果我想找到一个单词，我可以通过将所有文本放入hashmap并存储每个单词的出现来完成。但是，如果我想搜索两个字符串（或可能更多），是否有任何算法？我应该把这两个字符串散列在一起吗？

你搜索一个全字或任何字符串：

Answer 1

这取决于文本文件的大小。通常有几种情况下，你应该考虑：

1. 地块的查询在很短的文件（网页，文章长度等的文本）的。正常语言的文本分配。一个简单的O（n^2）算法很好。对于长度为n的查询，只需要一个长度为n的窗口并将其滑过。比较并移动窗口，直到找到匹配项。这个算法并不关心单词，所以你只是将整个搜索视为一个大字符串（包括空格）。这可能是大多数浏览器所做的。 KMP或Boyer Moore不值得付出努力，因为O（n^2）的情况非常罕见。

2. 很多的查询在一个大文件上。预处理您的文档并进行预处理。常见的存储选项是后缀树和反转列表。如果您有多个文档，您可以通过连接它们并单独存储文档的末尾来构建一个文档。这是收集几乎不变的文档数据库的方法。

3. 如果您有多个文件，且您的冗余度高且您的馆藏经常更改，请使用KMP或Boyer Moore。例如，如果您想在DNA数据中找到某些序列，并且您经常会从实验中获得新的序列以找到新的DNA，那么天真算法的O（n^2）部分将会浪费您的时间。

可能很多更多的可能性需要不同的算法和数据结构，所以你应该找出哪一个最适合你的情况。

Answer 2

一些细节暗示的方法之前，需要？

你打算在同一个不变的文件中搜索许多不同的单词吗？

您是否知道要一次搜索所有文字？

对于字符串有许多有效的（线性）搜索算法。如果可能的话，我会建议使用一个已经为你写的。

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

一个简单的想法是使用滑动窗口哈希与窗口大小相同的搜索字符串。然后在一次传递中，您可以快速检查以查看窗口哈希与搜索字符串的哈希值匹配的位置。如果匹配，请仔细检查，看看是否有真正的匹配。