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

一尘不染

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

algorithm

假设有一个文本流（或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：“ overflow ....... xyz”

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

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

阅读 275

2020-07-28

共1个答案

一尘不染

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

我还写了一篇相关文章：在流中搜索子字符串：Haxe中对Knuth-Morris-
Pratt算法的略微修改。文章提到了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"));

    }
}

2020-07-28