Java算法：如何在大型二进制文件中查找字符串模式？

Question

我正在尝试编写一个程序，它将读取一个非常大的二进制文件，并尝试查找两个不同字符串的出现点，然后打印与模式匹配的索引。为了示例起见，让我们假设字符序列是[H,e,l,l,o]和[H,e,l,l,o, ,W,o,r,l,d]

我能够为小型二进制文件编写此代码，因为我将每个字符作为字节读取，然后将其保存在Arraylist中。然后从Arraylist开始，我比较了byte arraylist(byte[] data)和byte[] pattern

我需要找到一种方法来做同样的事情，但不需要将整个二进制文件写入内存进行比较。这意味着我应该能够在读取每个字符时进行比较（我不应该将整个二进制文件保存在内存中）。假设二进制文件只包含字符

对如何实现这一目标有何建议？提前谢谢大家

Answer 1

谷歌“有限状态机”

或者，一次读取一个字节，如果该字节与搜索词的第一个字符不匹配，则转到下一个字节。如果匹配，现在您正在寻找序列中的下一个角色。也就是说，你的状态从0变为1。如果你的状态等于（或超过）搜索字符串的长度，你就找到了

实现/调试留给读者

Answer 2

有专门的算法，但让我们先试试一个简单的算法

您可以从动态比较开始，总是在读取下一个字节之后。一旦这样做了，就很容易发现，不需要保留任何早于最长模式的字节

所以你可以使用一个和你的最长模式一样长的缓冲区，在一端放入新字节，在另一端丢弃它们

正如我所说，有比这更有效的算法，但这是一个良好的开端

Answer 3

看来你真的在找Aho-Corasick string matching algorithm

该算法根据您拥有的给定词典构建一个自动机，然后允许您使用输入字符串的一次扫描来查找匹配项

维基百科的文章链接到this java implementation

Answer 4

使用FileInputStream包装在BufferedInputStream中的FileInputStream并比较每个字节。保留一个缓冲区，与你要寻找的序列长度保持一致，这样如果在某个点不匹配，你就可以回溯。如果要查找的序列太大，可以保存偏移量并重新打开文件进行读取

• 使用流：http://docs.oracle.com/javase/tutorial/essential/io/
• 字符串匹配算法：http://en.wikipedia.org/wiki/String_searching_algorithm

或者，如果你只是想复制和粘贴一些东西，你可以看看this SO question