Поиск шаблона в большом двоичном файле с использованием C или C ++?

Question

У меня бинарный файл ~ 700 МБ (нетекстовые данные);то, что я хотел бы сделать, это искать определенный шаблон байтов, который встречается в случайных местах по всему файлу.например, 0x? 0x? 0x55 0x? 0x? 0x55 0x? 0x? 0x55 0x? 0x? 0x55 и т. д. для 50 или около того байтов в последовательности.Шаблон, который я искал, был бы последовательностью два случайных байта с 0x55, встречающимися каждые два байта.

То есть, поиск таблиц, сохраненных в файле с 0x55, являющимся разделителем, и затем сохранение содержащихся данныхв таблицах или иным образом манипулировать им.

Лучшим вариантом будет просто проходить каждый отдельный байт по одному, а затем смотреть вперед на два байта, чтобы увидеть, равно ли значение 0x55, и если оно есть, тоСнова и снова заглядывая в будущее, чтобы убедиться, что в этом месте есть таблица?

Загрузить все?FSEEK?Буферные порции, ищущие по одному байту за раз?

Как лучше всего просмотреть этот большой файл и найти шаблон, используя C или C ++?

Answer 1

Это звучит как отличная работа для регулярного выражения matcher или детерминированного конечного автомата .Это мощные инструменты, предназначенные для выполнения именно того, о чем вы просите, и если они у вас есть, у вас не должно возникнуть особых проблем при выполнении такого поиска.В C ++ подумайте о библиотеках Boost.Regex , в которых должны быть все функции, необходимые для решения этой проблемы.

Answer 2

То, что в конечном итоге сработало для меня, было гибридом между алгоритмом Бойера-Мура-Хорспула (предложенным Джерри Коффином) и моим собственным алгоритмом, основанным на структуре таблиц и хранимых данных.

По сути,алгоритм BMH уловил большинство вещей, которые я искал.Очевидные вещи.

Но в некоторых таблицах оказалось странное форматирование, и мне пришлось реализовать полуинтеллектуальный поиск, который бы просматривал данные, следующие за каждым 0x55, и выяснял, действительно ли этоесли бы это были, вероятно, хорошие данные или просто случайный мусор.

Как ни странно, я закончил тем, что реализовал их в PHP, а не в C ++, и вывел результаты прямо в базу данных MySQL длявыполнение запроса.Процесс поиска занял всего около 5 минут или меньше, и результаты были в основном хорошими.В итоге у меня было много ненужных данных, но они поймали все, что мне было нужно, и (насколько я знаю) не оставили никаких хороших данных.

Answer 3

Загрузить все это? FSEEK? Буферные порции, ищущие по одному байту за раз?

Если вы можете загрузить все это в память, вам, вероятно, следует использовать функции отображения памяти, предоставляемые вашей платформой. Таким образом, операционная система может решить, следует ли ей хранить большие части файла в физической памяти (т. Е. В данный момент в системе много свободной оперативной памяти) или она должна работать только небольшими порциями.

Конечно, это работает, только если вы можете поместить файл в рабочий набор.