logo标签列表

使用C或C++在大型二进制文件中查找模式？

c++cfilesearchdesign-patterns
5
我有一个大小约为700 MB的二进制文件（非文本数据）；我想要做的是搜索在整个文件中随机位置出现的特定字节模式。例如：0x？0x？0x55 0x？0x？0x55 0x？0x？0x55 0x？0x？0x55 等等，连续出现50多个字节。我要搜索的模式是两个随机字节序列，并且每两个字节都以0x55作为分隔符。
也就是说，搜索存储在文件中的表格，其中0x55是分隔符，然后保存表格中包含的数据或以其他方式操作它。
最好的选择是逐个字节地查找每个字节，然后向前查看两个字节，以查看该值是否为0x55，如果是，则再次向前查看以确认该位置是否存在表格吗？
加载整个文件？fseek？缓冲区块，一次一个字节进行搜索？
使用C或C ++，找到这个大文件中的模式并进行搜索的最佳方法是什么？
@Kyle：如果有重叠的匹配，会发生什么？你会选择哪一个？ - Aryabhatta
对我来说，重要的是：你是否了解你关心的0x55字节的对齐方式？如果它们都将位于偶数（或奇数）位置，那么搜索会更加容易和快速。 - Jerry Coffin
@Moron：基本目标是识别每个表，并将表复制到文本文件或其他类型的文件中。因此，一旦程序找到模式匹配项，它将复制整个表（从第一个0x55之前的两个字节开始，以最后一个表中的最终0x55结束）。由于定界符之间始终有两个字节，因此如果三个字节处的值也为0x55，并且距离该值三个字节的值也为0x55，则知道已找到表。希望这能澄清事情。 - Kyle Lowry
1
@Jerry Coffin：据我所知（目前没有文件在手），并非所有的表格大小都相同。然而，我不记得曾经见过小于50字节左右的表格。换句话说，我不确定最小尺寸是多少，但至少可以肯定没有少于10-20个条目的表格（即10-20对以0x55分隔的字节）。 - Kyle Lowry
3
在这种情况下，我会使用 Boyer-Moore-Horspool 的变种算法。从第 20 个和第 21 个字节开始。如果它们中没有一个是 0x55，则向前移动另外 20 个字节，以此类推。 - Jerry Coffin
显示剩余6条评论
3个回答
3
这似乎是一个很适合使用正则表达式匹配器或确定性有限状态自动机的工作。这些都是高效的工具，专门用于您所需的内容，如果您拥有它们，您应该不会在进行此类搜索时遇到太多麻烦。 在C++中，可以考虑查看Boost.Regex库，它应该具备您需要解决此问题的所有功能。
2
一个字节的搜索字符串使用DFA不是有点过度了吗？这个搜索可以在没有DFA或正则表达式引擎的情况下以线性方式轻松实现。 - Billy ONeal
2
@Billy ONeal-也许我误读了上面的问题，但是它似乎并不只是在寻找一个字节（它要寻找特定的字节模式）。我错了吗？ - templatetypedef
1
@Moron：如果那些问题是致命的，你需要重新审视是否使用C ++是正确的语言。 - Fred Nurk
@Moron：为什么你想要使用正则表达式来做完全无关的事情，比如将匹配的表格写入文件或者处理那些数据？你认为测试和设置所需的工作量（以及你上面提到的“等等”中包含的其他内容）会因为重新发明轮子而显著减少吗？你真的应该研究一下Boost；听起来你因为一些无关紧要的原因错过了一个很棒的工具。 - Fred Nurk
1
@Moron：有时候你真的需要用锤子钉钉子。正则表达式是专门设计用于字符串模式匹配的。你需要某种东西来找到这个模式，唯一的问题是你将使用什么外部库（正则表达式或其他）或者如何自己编写它。 - Fred Nurk
显示剩余3条评论
1

对我最终有效的是 Boyer-Moore-Horspool 算法（由 Jerry Coffin 建议）和基于表结构和存储数据的自己的算法的混合。

基本上，BMH 算法捕获了我正在寻找的大部分内容。显而易见的东西。

但有些表确实具有奇怪的格式，我不得不实现一个半智能搜索，它将查看每个 0x55 后面的数据，并确定它是否可能是好的数据，还是随机垃圾。

奇怪的是，我最终在 PHP 中实现了它，而不是 C++，然后将结果直接转储到 MySQL 数据库中进行查询。搜索过程只需要大约 5 分钟或更短的时间，结果大多是好的。我最终确实得到了很多垃圾数据，但它捕获了我需要的所有内容，并且（据我所知）没有留下任何好的数据。

0
“加载整个文件？使用fseek？缓存块，每次一个字节搜索？”
如果您可以将整个文件加载到内存中，则应该使用平台提供的内存映射功能。这样，操作系统可以决定是保留文件的大部分内容在物理内存中（即系统此时具有大量可用的RAM），还是仅以较小的块来处理。
当然，这仅适用于文件大小不超过工作集的情况。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接