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

string algorithm java search stream

2022-08-31 19:57:18

让我们假设有一个文本流（或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.........堆栈“
流缓冲区 2：”溢出.......xyz”

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

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

答案 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
```
这将找到字符串（如果存在），并且您永远不需要缓冲区。
工作稍微多一点，但也更快：进行NFA到DFA的转换，提前找出哪些索引列表是可能的，并将每个索引分配给一个小整数。（如果你在维基百科上读到字符串搜索，这被称为powerset构造。然后，您有一个状态，并且对每个传入字符进行状态到状态的转换。所需的 NFA 只是字符串的 DFA，其前面带有非确定性删除字符或尝试使用当前字符的状态。您还需要一个显式错误状态。
如果你想要更快的东西，创建一个大小至少是两倍的缓冲区，然后用户Boyer-Moore从编译一个状态机。你会有很多额外的麻烦，因为Boyer-Moore的实现并不容易（尽管你会在网上找到代码），而且你必须安排在缓冲区中滑动字符串。您必须构建或找到一个可以在不复制的情况下“滑动”的圆形缓冲区;否则，你可能会把你可能从Boyer-Moore那里得到的任何性能提升都还给别人。nneedle

答案 2

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

我还写了一篇相关的文章：在流中搜索子字符串：对Haxe中的Knuth-Morris-Pratt算法的轻微修改。文章提到了Jakarta RegExp，现在已经退休，在Apache阁楼休息。RE 类中的 Jakarta 正则表达式库“匹配”方法使用 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"));

    }
}