searchstring的有效方法

假设有一个文本stream(或Java中的Reader),我想检查一个特定的string。 文本stream可能非常大,所以一旦findsearchstring,我想返回true,并尝试避免将整个input存储在内存中。

天真地,我可能会尝试做这样的事情(在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; } 

当然这不能检测给定的searchstring,如果它发生在1k缓冲区的边界上:

search文本:“stackoverflow”
数据stream缓冲区1:“abc ……… stack”
stream缓冲区2:“溢出……. xyz”

我怎样才能修改这段代码,使它正确地在缓冲区的边界上find给定的searchstring,但没有将整个stream加载到内存中?

编辑:注意当为一个stringsearchstream时,我们试图最小化从stream中读取的数量 (以避免networking/磁盘中的延迟),并保持内存使用恒定,而不pipestream中的数据量如何。 string匹配algorithm的实际效率是次要的,但很明显,find使用这些algorithm中更高效的解决scheme将是很好的。

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

我还写了一篇相关的文章: 在stream中search子串:对Haxe中的Knuth-Morris-Prattalgorithm稍作修改 。 这篇文章提到雅加达RegExp ,现在已经退休,并在阿帕奇阁楼rest。 在RE类中的Jakarta Regexp库“ 匹配 ”方法使用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")); } } 

这里有三个好的解决scheme:

  1. 如果你想要简单快捷的东西,就不要使用缓冲区,而要实现一个简单的非确定性有限状态机。 你的状态将是你正在search的string的索引列表,你的逻辑看起来像这样(伪代码):

     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 

    这将findstring,如果它存在,你永远不会需要一个缓冲区。

  2. 做更多的工作,但也更快:做一个NFA到DFA的转换,事先计算出哪些索引列表是可能的,并将每个索引分配给一个小整数。 (如果你阅读维基百科上的stringsearch,这就是所谓的powerset构build 。)然后你有一个单一的状态,你在每个传入的字符上进行状态到状态的转换。 您需要的NFA只是string的DFA,前面带有一个非确定性的字符,或者尝试使用当前字符。 你也需要明确的错误状态。

  3. 如果你想要更快一点,创build一个大小至less为n的缓冲区,用户Boyer-Moore可以从needle编译状态机。 你会有很多额外的麻烦,因为Boyer-Moore不是微不足道的实现(虽然你会在网上find代码),因为你必须安排通过缓冲区滑动string。 你将不得不build立或find一个循环缓冲区,可以“滑动”,而不需要复制; 否则你可能会回报你可能从Boyer-Moore获得的任何性能提升。

Knuth-Morris-Prattsearchalgorithm从不支持; 这只是你想要的stream媒体search的属性。 我之前用过这个问题,虽然可能有更简单的方法使用可用的Java库。 (当我想起我时,我在90年代在C工作。)

从本质上来说,KMP是一种快速构buildstring匹配DFA的方法,就像Norman Ramsey的build议#2一样。

这个答案适用于问题的初始版本,如果该string存在,那么只有在需要匹配string时才能读取该string。 这个解决scheme不能满足保证固定内存利用率的要求,但是如果你发现了这个问题,并且不受这个约束的约束,那么值得考虑。

如果受到常量内存使用约束的束缚,Java会将任何types的数组存储在堆上,因此null引用不会以任何方式释放内存; 我认为在循环中涉及数组的任何解决scheme都会占用堆上的内存并需要GC。


为了简单的实现,也许可以接受InputStream并使用java.util.regex.Pattern来searchinput的Java 5的Scanner可以节省您担心的实现细节。

以下是一个潜在实现的例子:

 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; } } 

我想正则expression式,因为它听起来像一个有限状态自动机的工作,从初始状态开始,改变状态字符,直到它拒绝string(不匹配)或进入接受状态。

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

这也是正则expression式的工作原理。

而不是让你的缓冲区是一个数组,使用实现一个循环缓冲区的抽象。 您的索引计算将是buf[(next+i) % sizeof(buf)] ,您必须小心一次将缓冲区填满一半。 但只要searchstring适合缓冲区的一半,就可以find它。

我相信解决这个问题的最好办法是尽量保持简单。 请记住,因为我正在读取stream,我想保持从stream中的读取数量最小(因为networking或磁盘延迟可能是一个问题),同时保持使用的内存量不变(因为stream可能是非常大)。 string匹配的实际效率不是第一个目标(因为已经被研究过 )。

基于AlbertoPL的build议,下面是一个简单的解决scheme,它将缓冲区与searchstring按字符进行比较。 关键在于,因为search只能一次完成一个字符,所以不需要回溯,因此不需要循环缓冲区或特定大小的缓冲区。

现在,如果有人能够基于Knuth-Morris-Prattsearchalgorithm提出类似的实现scheme,那么我们将拥有一个很好的高效解决scheme;)

 public boolean streamContainsString(Reader reader, String searchString) throws IOException { char[] buffer = new char[1024]; int numCharsRead; int count = 0; while((numCharsRead = reader.read(buffer)) > 0) { for (int c = 0; c < numCharsRead; c++) { if (buffer[c] == searchString.charAt(count)) count++; else count = 0; if (count == searchString.length()) return true; } } return false; } 

实现一个滑动窗口。 在你的缓冲区周围,向前移动缓冲区中的所有元素,最后在缓冲区中input一个新的字符。 如果缓冲区等于您search到的单词,则包含它。

当然,如果你想提高这个效率,你可以看一下防止移动缓冲区中的所有元素的方法,例如通过循环缓冲区和string的表示来循环缓冲区这样做,所以你只需要检查内容的平等。 这可以节省移动缓冲区中的所有元素。

我认为你需要缓冲区之间的边界缓冲less量。

例如,如果缓冲区大小是1024,SearchString的长度是10,那么除了search每个1024字节的缓冲区之外,还需要search两个缓冲区之间的每个18字节转换(从前一个缓冲区的末尾开始的9个字节从下一个缓冲区开始连接9个字节)。

我会说切换到一个字符的解决scheme,在这种情况下,你会扫描你的目标文本中的第一个字符,然后当你发现该字符递增一个计数器,并寻找下一个字符。 每次你没有find下一个连续的字符重新启动计数器。 它会这样工作:

 public boolean streamContainsString(Reader reader, String searchString) throws IOException { char[] buffer = new char[1024]; int numCharsRead; int count = 0; while((numCharsRead = reader.read(buffer)) > 0) { if (buffer[numCharsRead -1] == searchString.charAt(count)) count++; else count = 0; if (count == searchString.size()) return true; } return false; } 

唯一的问题是当你在查看字符的时候……在这种情况下,需要记住你的countvariables。 除了作为整个class级的私人variables之外,我看不出一个简单的方法。 在这种情况下,您不会在此方法内实例化计数。

如果您不想使用Reader,那么您可以使用Java的NIO API来有效地加载文件。 例如(未经testing,但应接近工作):

 public boolean streamContainsString(File input, String searchString) throws IOException { Pattern pattern = Pattern.compile(Pattern.quote(searchString)); FileInputStream fis = new FileInputStream(input); FileChannel fc = fis.getChannel(); int sz = (int) fc.size(); MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, sz); CharsetDecoder decoder = Charset.forName("UTF-8").newDecoder(); CharBuffer cb = decoder.decode(bb); Matcher matcher = pattern.matcher(cb); return matcher.matches(); } 

这基本上是mmap()的search文件,依靠操作系统来做关于caching和内存使用的正确的事情。 不过要注意的是,只要将文件读入大于10 KiB的文件的大缓冲区,map()就更加昂贵。

在Ujorm框架的RingBuffer类中实现了对stream的快速search。 看样品:

  Reader reader = RingBuffer.createReader("xxx ${abc} ${def} zzz"); String word1 = RingBuffer.findWord(reader, "${", "}"); assertEquals("abc", word1); String word2 = RingBuffer.findWord(reader, "${", "}"); assertEquals("def", word2); String word3 = RingBuffer.findWord(reader, "${", "}"); assertEquals("", word3); 

SourceForge上提供单个类的实现:有关更多信息,请参阅链接 。

您可以使用一些stringsearchalgorithm来提高search超大string的速度

如果你正在寻找一个恒定的子串而不是正则expression式,我推荐Boyer-Moore。 互联网上有很多源代码。

此外,使用循环缓冲区,以避免想太多的缓冲区边界。

麦克风。

我也有类似的问题:从InputStream跳过字节,直到指定的string(或字节数组)。 这是基于循环缓冲区的简单代码。 这不是很有效率,但为我的需要工作:

  private static boolean matches(int[] buffer, int offset, byte[] search) { final int len = buffer.length; for (int i = 0; i < len; ++i) { if (search[i] != buffer[(offset + i) % len]) { return false; } } return true; } public static void skipBytes(InputStream stream, byte[] search) throws IOException { final int[] buffer = new int[search.length]; for (int i = 0; i < search.length; ++i) { buffer[i] = stream.read(); } int offset = 0; while (true) { if (matches(buffer, offset, search)) { break; } buffer[offset] = stream.read(); offset = (offset + 1) % buffer.length; } } 

您可以使用快速傅里叶变换(Fast Fourier Transforms)来实现一个非常快速的解决scheme,如果执行得当,它允许您在时间O(nlog(m))中进行string匹配,其中n是要匹配的较长string的长度, m是较短弦的长度。 例如,您可以在接收到长度为m的streaminput后立即执行FFT,如果匹配,则可以返回,如果不匹配,则可以丢弃streaminput中的第一个字符,等待通过stream显示一个新的字符,然后再次执行FFT。