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

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 缓冲区的边界上，则无法检测到它：

搜索文本：“计算器”

流缓冲区 1：“abc …….stack”

流缓冲区 2：“溢出…….xyz”

我如何修改这段代码，以便它在缓冲区边界正确地找到给定的搜索字符串，而不会将整个流加载到内存中？

编辑： 请注意，当在流中搜索字符串时，我们试图 尽量减少从流中读取的次数（以避免网络/磁盘中的延迟）并 保持内存使用不变，而不管流中的数据量如何。 字符串匹配算法 的实际效率是次要的，但显然，找到一种使用这些算法中效率更高的算法的解决方案会很好。

原文由 Alex Spurling 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我对部分搜索的 Knuth Morris Pratt 算法做了一些更改。由于实际的比较位置总是小于或等于下一个，因此不需要额外的内存。带有 Makefile 的代码也可以在 github 上找到，它是用 Haxe 编写的，可以同时针对多种编程语言，包括 Java。

我还写了一篇相关的文章： searching for substrings in streams: a small modification of the Knuth-Morris-Pratt algorithm in Haxe 。这篇文章提到了 Jakarta RegExp ，现在已经退休并在 Apache Attic 中休息。 RE 类中的 Jakarta Regexp 库“ match ”方法使用 CharacterIterator 作为参数。

 class StreamOrientedKnuthMorrisPratt {
    var m: Int;
    var i: Int;
    var ss:
    var table: Array<Int>;

    public function new(ss: String) {
        this.ss = ss;
        this.buildTable(this.ss);
    }

    public function begin() : Void {
        this.m = 0;
        this.i = 0;
    }

    public function partialSearch(s: String) : Int {
        var offset = this.m + this.i;

        while(this.m + this.i - offset < s.length) {
            if(this.ss.substr(this.i, 1) == s.substr(this.m + this.i - offset,1)) {
                if(this.i == this.ss.length - 1) {
                    return this.m;
                }
                this.i += 1;
            } else {
                this.m += this.i - this.table[this.i];
                if(this.table[this.i] > -1)
                    this.i = this.table[this.i];
                else
                    this.i = 0;
            }
        }

        return -1;
    }

    private function buildTable(ss: String) : Void {
        var pos = 2;
        var cnd = 0;

        this.table = new Array<Int>();
        if(ss.length > 2)
            this.table.insert(ss.length, 0);
        else
            this.table.insert(2, 0);

        this.table[0] = -1;
        this.table[1] = 0;

        while(pos < ss.length) {
            if(ss.substr(pos-1,1) == ss.substr(cnd, 1))
            {
                cnd += 1;
                this.table[pos] = cnd;
                pos += 1;
            } else if(cnd > 0) {
                cnd = this.table[cnd];
            } else {
                this.table[pos] = 0;
                pos += 1;
            }
        }
    }

    public static function main() {
        var KMP = new StreamOrientedKnuthMorrisPratt("aa");
        KMP.begin();
        trace(KMP.partialSearch("ccaabb"));

        KMP.begin();
        trace(KMP.partialSearch("ccarbb"));
        trace(KMP.partialSearch("fgaabb"));

    }
}

原文由 sw. 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

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

这将找到该字符串（如果它存在）并且您将永远不需要缓冲区。

1. 稍微多一些工作但也更快：进行 NFA 到 DFA 的转换，提前计算出可能的索引列表，并将每个索引分配给一个小整数。 （如果您在维基百科上阅读过有关字符串搜索的内容，这称为 _幂集构造_。）然后您将拥有一个状态，并对每个传入字符进行状态到状态的转换。您想要的 NFA 只是字符串的 DFA，其前面有一个不确定地丢弃字符或尝试使用当前字符的状态。您还需要一个明确的错误状态。

2. 如果你想要更快的东西，创建一个缓冲区，其大小至少是 n 的两倍，并且用户 Boyer-Moore 从 needle 编译状态机。你会遇到很多额外的麻烦，因为 Boyer-Moore 实现起来并不简单（尽管你会在网上找到代码），而且你必须安排让字符串滑过缓冲区。您必须构建或找到一个无需复制即可“滑动”的 循环 缓冲区；否则，您可能会放弃从 Boyer-Moore 获得的任何性能提升。

原文由 Norman Ramsey 发布，翻译遵循 CC BY-SA 2.5 许可协议