java - 在流中搜索字符串的有效方法

Question

假设有一个文本流(或 Java 中的 Reader)，我想检查一个特定的字符串。文本流可能非常大，所以一旦找到搜索字符串，我想返回 true 并尽量避免将整个输入存储在内存中。

天真地，我可能会尝试做这样的事情(在 Java 中):

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    while((numCharsRead = reader.read(buffer)) > 0) {
        if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
            return true;
    }
    return false;
}

当然，如果给定的搜索字符串出现在 1k 缓冲区的边界上，这将无法检测到它:

搜索文字:“stackoverflow”
流缓冲区 1:“abc............stack”
流缓冲区 2:“溢出.......xyz”

如何修改此代码，以便它正确地找到跨越缓冲区边界的给定搜索字符串，但不将整个流加载到内存中？

编辑:请注意，在流中搜索字符串时，我们会尝试尽量减少从流中读取的次数(以避免网络/磁盘中的延迟) 并保持内存使用量不变，无论流中的数据量如何。 string matching algorithm的实际效率是次要的，但显然，找到使用其中一种更有效算法的解决方案会很好。

Answer 1

这里有三个很好的解决方案:

1. 如果您想要一些简单且相当快速的东西，请不要使用缓冲区，而是实现一个简单的非确定性有限状态机。您的状态将是您正在搜索的字符串的索引列表，您的逻辑看起来像这样(伪代码):

   String needle;
   n = needle.length();
   
   for every input character c do
     add index 0 to the list
     for every index i in the list do
       if c == needle[i] then
         if i + 1 == n then
           return true
         else
           replace i in the list with i + 1
         end
       else
         remove i from the list
       end
     end
   end
   

   如果它存在，这将找到字符串，您将永远不需要缓冲区。

2. 工作量稍大但速度更快:进行 NFA 到 DFA 的转换，提前计算出可能的索引列表，并将每个索引分配给一个小整数。 (如果您在 Wikipedia 上阅读了有关字符串搜索的信息，这称为 powerset 构造。)然后您有一个单一的状态，并且您对每个传入的字符进行状态到状态的转换。您想要的 NFA 只是字符串的 DFA，其前面带有一个不确定地丢弃字符或尝试使用当前字符的状态。您还需要一个明确的错误状态。

3. 如果您想要更快的速度，请创建一个大小至少为 n 两倍的缓冲区，并让用户 Boyer-Moore 从 needle 编译状态机。您会遇到很多额外的麻烦，因为 Boyer-Moore 的实现并非易事(尽管您会在网上找到代码)，而且您必须安排将字符串滑过缓冲区。您必须构建或找到一个可以“滑动”而无需复制的 圆形 缓冲区；否则，您可能会回馈您从 Boyer-Moore 获得的任何性能提升。