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：
-
如果你想要简单快捷的东西，就不要使用缓冲区，而要实现一个简单的非确定性有限状态机。 你的状态将是你正在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，如果它存在，你永远不会需要一个缓冲区。
-
做更多的工作，但也更快：做一个NFA到DFA的转换，事先计算出哪些索引列表是可能的，并将每个索引分配给一个小整数。 （如果你阅读维基百科上的stringsearch，这就是所谓的powerset构build 。）然后你有一个单一的状态，你在每个传入的字符上进行状态到状态的转换。 您需要的NFA只是string的DFA，前面带有一个非确定性的字符，或者尝试使用当前字符。 你也需要明确的错误状态。
-
如果你想要更快一点，创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。
