查找十六进制文件中的模式

Question

我有两个不同的文件，每个文件的内容来自不同的数据流。我从两个不同的文件中收集了来自这些流的一些数据。然后，我想搜索文件以查找任何类型的模式，以便在稍后阶段如果我从流中收集更多数据，我应该能够区分哪些数据属于哪个流（基于我发现的模式更早）。

该文件中包含的数据的一个示例可以是：b0 82 91 a2 c3 89 b0 82 4a e3 ....（更多字节）... 虽然我在这里占用了很少的字节，但我们可以找到上面两次出现的模式“b0 82”。所以输出结果应该显示模式和它未来的时间。类似的，我们可以有3字节模式或甚至更多的字节模式。

其他示例可以是：aa 00 a7 2f 7b 4c ....（更多字节）..... aa 01 a7 .........（更多字节）..... .aa 05 A7 ..... 我认为，即使这可以被认为是3个字节，其中两个字节（AA & A7）是固定的，中间的一个从00到05。

变化的图案这些两个例子我可以想到，虽然可能会有更多的图案。即使可能有一些隐藏的模式不能立即可视化。只要有助于在稍后阶段区分两股流股，整个想法是可行的。我想我现在更清楚地说明我的问题。请让我知道以下几件事：

1. 我们该如何做这种类型的模式查找？

2. 是否有任何工具或库可以帮助实现此目的？

3. 还有哪种语言或工具可用于高效快速的开发？

4. 数据挖掘领域可以为此目的提供帮助吗？如果是的话，如何继续？

Answer 1

你的问题没有完全确定，但我会尽量给你几个指针：

1. 你的模式很可能表达为正则表达式。如果你不知道这些是什么 - 我会试着用你最喜欢的编程语言寻找一个具体的例子。 Python是一个很好的选择（re模块包含在核心语言中）。对于C++，使用boost :: regex和其他语言，请使用google :)

2. 现在 - 使用正则表达式来搜索二进制文件（十六进制）而不是文本，请尝试查看诸如this之类的内容。

祝你好运:)

Answer 2

这是另一种思路。它是否适用于您取决于您​​正在处理的数据量，可以使用多少内存，以及它检测到的模式种类是否最终可用于您的目的。

考虑到所有这些资格，则可能需要使用后缀树或后缀数组尝试。特别是对于后缀树，有一些算法使您能够在将字符附加到文本（所谓的在线后缀树构造）（最值得注意的是Ukkonen算法）时不断更新树。这可能对数据流的使用特别有效（与固定长度，完全定义的输入文本相反）。

后缀树（以及类似的方式，后缀数组）表示文本的所有后缀（在字符串结尾，而不是语言后缀）。因此，它特别适用于（a）检查任何给定的字符串是否为文本的子字符串，以及（b）用于检测文本中的子字符串。通过在正确位置进行一些修改，它可以用来检测重复的子字符串，并稍做修改（就像您在中间交换一个字符时重复的模式示例）。

要全面了解这些数据结构，并且如果您有权访问大学图书馆或有钱，Dan Gusfield's introduction to algorithms on strings, trees and sequences将非常有帮助。但是也有一些与此相关的问题和答案。

如果在进一步阅读之后，您认为值得一试，我可以进一步详细阐述我如何认为后缀树可以用于您的目的，以及针对使用这些算法的新问题的答案重复模式检测。

Answer 3

您可以在您的流上训练Markov Models甚至隐藏马尔可夫模型，并使用这些模型来确定最可能属于哪个新数据流。据说有几十个库可以在你选择的编程语言中做到这一点。

也许从读一本书开始。我建议C. Bishop的Pattern Recognition。

Answer 4

这似乎是一个非常典型的ngram发现问题。这里是一些ngram解决方案的链接。

quicker way to detect n-grams in a string?

你应该把你的十六进制就像任何其他字符串。