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

Question

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

文件中包含的数据示例可以是: b0 82 91 a2 c3 89 b0 82 4a e3.(更多字节).虽然我在这里只使用了很少的字节，但是我们可以找到上面两次出现的模式"b0 82“。因此，输出应该显示模式和它即将到来的时间。类似地，我们可以有3个字节模式，甚至更多字节模式。

还有其他例子可以是: aa 00 a7 2f 7b4c.(更多字节).....aa 01 a7.(更多字节)......aa 05 a7.我认为即使这样也可以被认为是一个3字节的模式，其中两个字节(aa和a7)是固定的，中间的字节从00到05不等。

这是两个我可以想到的例子，尽管可能会有更多的模式。甚至可能有一些隐藏的模式，无法立即可视化。整个想法是，任何模式都可以做到，只要这有助于在稍后阶段区分两个流。我想我现在更清楚地说明了我的问题。请告诉我以下几点：

1. 我们如何才能进行这种模式发现？
2. 是否有任何工具或库可以帮助实现这一目的？
3. 另外，为了高效和更快的开发，应该使用哪种语言或工具？
4. 为此目的，数据挖掘领域能有所帮助吗？如果是的话，怎么做呢？

Answer 1

这似乎是一个典型的问题。下面是一些ngram解决方案的链接。

用更快的方法检测字符串中的n克？

你应该像对待其他绳子一样对待你的巫术。

Answer 2

您可以在流上训练马尔可夫模型甚至隐藏的马尔可夫模型，并使用这些模型来决定新数据最可能属于哪个流。据推测，有几十个库可以用您所选择的编程语言来实现这一点。

也许从读书开始。我推荐C.毕晓普的http://research.microsoft.com/en-us/um/people/cmbishop/prml/。

Answer 3

这是另一个想法。它是否适用于您，取决于您正在处理的数据数量、可以使用多少内存以及它检测到的模式类型最终是否对您的目的有用。

考虑到所有这些限制，您可能需要尝试使用后缀树或后缀数组。特别是对于后缀树，有一些算法可以使您在将字符附加到文本(所谓的在线后缀树构造)时不断更新树，最显著的是Ukkonen算法。对于数据流的使用(相对于固定长度、完全定义的输入文本)，这可能特别有效。

后缀树(以类似的方式，后缀数组)表示文本的所有后缀(在字符串结束的意义上，而不是语言后缀)。因此，它特别适合于(a)检查任何给定字符串是否为文本的子字符串，以及(b)用于检测文本中的重复子字符串。只要在正确的位置做一些修改，它就可以用来检测重复的子字符串，并对进行轻微的修改(就像在中间交换一个字符重复的模式示例)。

关于这些数据结构的详细介绍，如果您能够访问大学图书馆或有钱，Dan Gusfield对字符串、树和序列算法的介绍将非常有用。但也有许多与此相关的问题和答案。

如果经过进一步的阅读，您认为值得一试，我可以进一步详细说明我认为如何使用后缀树来实现您的目的，这是对一个新问题的回答，具体是关于如何将这些算法用于重复模式检测。