How to find recurring patterns on a hexdump?

I need to find recurring patterns from an hexdump output. Every line in my output file is something like:

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

Where 00 is a byte in hexadecimal.

The patterns aren't of fixed length but they always lie in one line.

I have an idea on how to do this but I'd like to know what would be the most efficent method in your opinion, like if there is some sort of known algorhitm I am unaware of.

Also I'd like to code this in Python.

Any suggestion is grealty appreciated :)

Thanks

EDIT: I need to find partition boot sectors in a disk dump. The problem is that the filesystem is uncommon so I need to scan the hexdump to find pattern frequently used in order to restrict the area of research.

For example I am looking for byte-patter开发者_如何转开发ns like:

00 56 f0 43 d0 

---

It is not apparent whether you know the substrings that you want to search for, or whether you need to discover a set of query substrings first. I think that discovery can be achieved by finding frequently occurring n-grams. One you have your set of query substrings, you can proceed to where they are, and how far apart they are (e.g. if some substring occurs every 1024 bytes, that may be a block size).

Step 1: read your hexdump file and convert it back to a single string. I'll leave the details up to you.

Step 2: for each interesting value of n (say 3, 4, 5 (like your example), 6, etc) use this function:

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

That will give you the most frequent occurring substrings.

Step 3: where those strings occur:

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

Step 4: how far apart those occurrences are:

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