如何在十六进制转储中查找重复模式？

Question

我需要从十六进制转储的输出中找出重复的模式。

我的输出文件中的每一行看起来像这样：

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

其中 00 是一个十六进制的字节。

这些模式的长度不固定，但它们总是在同一行中。

我有一个想法来实现这个，但我想知道在你看来，最有效的方法是什么，是否有我不知道的已知算法。

另外，我想用Python来编写这个程序。

任何建议都非常感谢 :)

谢谢

编辑： 我需要在磁盘转储中找到分区引导扇区。问题是文件系统不常见，所以我需要扫描十六进制转储，以找到常用的模式，从而缩小研究范围。

例如，我在寻找像这样的字节模式：

00 56 f0 43 d0 

Answer 1

不太清楚你是否已经知道想要搜索的子字符串，或者你是否需要先找出一组查询子字符串。我认为可以通过找到经常出现的n-grams来实现这个发现。一旦你有了查询子字符串的集合，就可以继续查找它们出现的位置，以及它们之间的距离（例如，如果某个子字符串每1024字节出现一次，那可能就是一个块大小）。

第一步：读取你的十六进制转储文件，并将其转换回一个完整的字符串。具体细节就留给你自己去处理吧。

第二步：对于每一个有趣的n值（比如3、4、5（就像你的例子）、6等等），使用这个函数：

from collections import Counter # needs 2.7
from operator import itemgetter
def get_ngrams(strg, n, top=10, min_count=2):
    counter = Counter()
    for i in xrange(len(strg) - n + 1):
        gram = strg[i:i+n]
        counter[gram] += 1
    sort_these = [(gram, count) for gram, count in counter.iteritems() if count >= min_count]
    best = sorted(sort_these, key=itemgetter(1), reverse=True)[:top]
    return best

这样你就能得到出现频率最高的子字符串。

第三步：找出这些字符串出现的位置：

def multifind(strg, gram):
    positions = []
    end = len(strg)
    pos = 0
    while pos < end:
        pos = strg.find(gram, pos)
        if pos == -1:
            break
        positions.append(pos)
        pos += 1
    return positions

第四步：计算这些出现之间的距离：

deltas = [b - a for a, b in zip(positions, positions[1:])]