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

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) 部分会浪费您的时间。

可能还有更多的可能性需要不同的算法和数据结构，因此您应该找出最适合您的情况的一种。