假设有一个文本流(或者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的实际效率是次要的,但显然,找到一个使用这些算法中更有效的算法之一的解决方案会很好。
发布于 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"));
}
}
发布于 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.
n
两倍的缓冲区,用户Boyer-Moore从needle
编译一个状态机。您将有很多额外的麻烦,因为Boyer-Moore的实现并不容易(尽管您可以在网上找到代码),而且您还必须安排将字符串滑过缓冲区。你必须建立或找到一个循环缓冲区,它可以在不复制的情况下“滑动”;否则,你很可能会放弃从博耶-摩尔那里获得的任何性能收益。发布于 2009-05-11 05:01:26
Knuth-Morris-Pratt search algorithm从不备份;这正是您想要用于流搜索的属性。我以前使用过它来解决这个问题,尽管使用可用的Java库可能有更简单的方法。(当我想到这个问题时,我是在90年代用C语言工作的。)
KMP本质上是一种构建字符串匹配DFA的快速方法,就像Norman Ramsey的建议2一样。
https://stackoverflow.com/questions/846175
复制相似问题