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

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"

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

编辑:注意在搜索字符串的流时,我们尝试最小化从流中读取的数量(以避免网络/磁盘中的延迟)并保持内存使用不变,无论流中的数据量如何.字符串匹配算法的实际效率是次要的,但很明显,找到使用这些算法中更有效的算法之一的解决方案会很好.

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的转换,提前确定哪些索引列表是可能的,并将每个索引分配给一个小整数.(如果你阅读维基百科上的字符串搜索,这称为powerset构造.)然后你有一个状态,你在每个传入的字符上进行状态到状态的转换.您想要的NFA只是字符串的DFA,其前面的状态是非确定性地删除字符或尝试使用当前字符.您还需要一个明确的错误状态.

3. 如果你想要更快的东西,创建一个大小至少两倍的缓冲区n,用户Boyer-Moore从中编译一个状态机needle.你会有很多额外的麻烦,因为Boyer-Moore实现起来并不容易(尽管你会在网上找到代码),因为你必须安排将字符串滑过缓冲区.你必须建立或找到一个可以"滑动"而不需要复制的循环缓冲区; 否则你可能会给Boyer-Moore带来的任何性能提升.

Answer 2

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

我还写了一篇相关的文章:在溪流中搜索子串:在Haxe中略微修改了Knuth-Morris-Pratt算法.文章提到雅加达RegExp,现已退休并在Apache阁楼休息.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"));

    }
}

Answer 3

该克努特莫里斯普拉特搜索算法从未备份; 这只是您想要进行流搜索的属性.我以前使用它来解决这个问题,尽管使用可用的Java库可能有更简单的方法.(当这对我来说,我在90年代在C工作.)

KMP本质上是构建字符串匹配DFA的快速方法,如Norman Ramsey的建议#2.

Answer 4

这个答案适用于问题的初始版本,其中关键是只在必要时读取流以匹配String,如果该String存在.此解决方案不符合保证固定内存利用率的要求,但如果您发现此问题并且不受该约束约束,则可能值得考虑.

如果您受常量内存使用约束的约束,Java会在堆上存储任何类型的数组,因此对引用进行归零不会以任何方式释放内存; 我认为任何涉及循环中的数组的解决方案都会占用堆上的内存并需要GC.

对于简单的实现,也许Java 5的Scanner可以接受InputStream并使用java.util.regex.Pattern来搜索输入,这可能会让您担心实现细节.

以下是潜在实施的示例:

public boolean streamContainsString(Reader reader, String searchString)
            throws IOException {
      Scanner streamScanner = new Scanner(reader);
      if (streamScanner.findWithinHorizon(searchString, 0) != null) {
        return true;
      } else {
        return false;
      }
}

我正在考虑正则表达式,因为它听起来像是一个有限状态自动机的工作,它在初始状态下开始,逐个字符地改变状态,直到它拒绝字符串(不匹配)或进入接受状态.

我认为这可能是您可以使用的最有效的匹配逻辑,并且您如何组织信息的读取可以与用于性能调整的匹配逻辑分开.

这也是正则表达式的工作方式.