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

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

   <

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