在流中搜索字符串的有效方法
假设有一个文本流(或者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“
如何修改这段代码，使其在不将整个流加载到内存中的情况下，正确地找到跨越缓冲区边界的给定搜索字符串？
编辑：注意当在一个流中搜索一个字符串时，我们试图最小化从流中读取的次数(以避免网络/磁盘中的延迟)，并保持内存使用量恒定，而不管流中的数据量是多少。string matching algorithm的实际效率是次要的，但显然，找到一个使用这些算法中更有效的算法之一的解决方案会很好。
回答 16
Stack Overflow用户
发布于 2013-01-22 05:55:33
我对用于部分搜索的Knuth Morris Pratt算法做了一些更改。由于实际的比较位置总是小于或等于下一个位置，因此不需要额外的内存。带有Makefile的代码也可以在github上获得，它是用Haxe编写的，可以同时针对多种编程语言，包括Java。
我还写了一篇相关的文章：searching for substrings in streams: a slight modification of the Knuth-Morris-Pratt algorithm in Haxe。这篇文章提到了现已退休并在阿帕奇阁楼休息的Jakarta RegExp。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"));
}
}Stack Overflow用户
发布于 2009-05-11 04:43:13
这里有三个很好的解决方案：
- 如果您想要一些简单且相当快的东西，那么就不使用缓冲区，而是实现一个简单的非确定性有限状态机。你的状态将是你正在搜索的字符串的索引列表，你的逻辑看起来像这样(伪代码)：
字符串针；n= needle.length()；对于每个输入字符c，为列表中的每个索引i添加索引0。do if c == == else if i+1 end n则返回true否则将列表中的i替换为i+1 end否则将i从列表end中移除
这将找到字符串，如果它存在，您将永远不需要buffer.
- Slightly更多的工作，但也更快:做一个NFA到DFA的转换，提前计算出哪些索引列表是可能的，并将每个索引分配给一个小整数。(如果你在Wikipedia上读到关于字符串搜索的内容，这叫做powerset结构。)然后你有一个单一的状态，你在每个传入的字符上进行状态到状态的转换。您需要的NFA只是字符串的DFA，前面的状态不确定地要么丢弃一个字符，要么尝试使用当前字符。你也需要一个显式的错误状态。
- 如果你想要更快的东西，创建一个大小至少是
n两倍的缓冲区，用户Boyer-Moore从needle编译一个状态机。您将有很多额外的麻烦，因为Boyer-Moore的实现并不容易(尽管您可以在网上找到代码)，而且您还必须安排将字符串滑过缓冲区。你必须建立或找到一个循环缓冲区，它可以在不复制的情况下“滑动”；否则，你很可能会放弃从博耶-摩尔那里获得的任何性能收益。
Stack Overflow用户
发布于 2009-05-11 05:01:26
Knuth-Morris-Pratt search algorithm从不备份；这正是您想要用于流搜索的属性。我以前使用过它来解决这个问题，尽管使用可用的Java库可能有更简单的方法。(当我想到这个问题时，我是在90年代用C语言工作的。)
KMP本质上是一种构建字符串匹配DFA的快速方法，就像Norman Ramsey的建议2一样。
https://stackoverflow.com/questions/846175
复制相似问题