Как найти повторяющиеся шаблоны на hexdump?

Question

Мне нужно найти повторяющиеся шаблоны из вывода hexdump. Каждая строка в моем выходном файле выглядит примерно так:

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

Где 00 - это байт в шестнадцатеричном формате.

Шаблоны не имеют фиксированной длины, но они всегда лежат в одной строке.

У меня есть идея, как это сделать, но я хотел бы знать, какой, по вашему мнению, самый эффективный метод, например, если есть какой-то известный алгоритм, о котором я не знаю.

Также я хотел бы написать это на Python.

Любое предложение приветствуется!)

Спасибо

EDIT: Мне нужно найти загрузочные сектора раздела в дампе диска. Проблема в том, что файловая система необычна, поэтому мне нужно отсканировать hexdump, чтобы найти шаблон, часто используемый для ограничения области исследования.

Например, я ищу байтовые шаблоны, такие как:

00 56 f0 43 d0 

Answer 1

Не ясно, знаете ли вы подстроки, которые вы хотите найти, или вам нужно сначала найти набор подстрок запроса.Я думаю, что открытие может быть достигнуто путем нахождения часто встречающихся n-грамм.Если у вас есть набор подстрок запроса, вы можете перейти к тому, где они находятся и как далеко друг от друга они находятся (например, если некоторая подстрока встречается каждые 1024 байта, что может быть размером блока).

Шаг 1:прочитайте ваш файл hexdump и преобразуйте его обратно в одну строку.Я оставлю детали до вас.

Шаг 2: для каждого интересного значения 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

Это даст вам наиболее часто встречающиеся подстроки.

Шаг 3: где встречаются эти строки:

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

Шаг 4: насколько далеко расположены эти вхождения:

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