поиск последовательности 4-5 байтов в большом файле

Question

у меня есть файл ~ 1,5 ГБ Мне нужно найти в этом файле 3 миллиарда последовательностей байтов. Одна последовательность может быть 4 или 5 байтов. Найти первую позицию или убедиться, что такой последовательности в файле нет. Как это сделать быстрее всего?

ограничение ОЗУ на компьютере - 4 ГБ

Answer 1

Использование grep.Он очень оптимизирован для поиска вещей в больших файлах.
Если это не вариант, прочитайте о алгоритме Бойера-Мура , который он использует, и реализуйте его самостоятельно.Потребуется много настроек, чтобы воспроизвести ту же скорость, что и у grep.

Answer 2

Ознакомьтесь с поисковой системой Searchlight.

Эта программа позволяет хранить в одном файле несколько последовательностей до 10 байтов ASCII.Затем вы указываете на файл, каталог, файл с именами файлов, файл с именами каталогов, массив списков имен файлов или массив списков имен каталогов, и он отправляется !!каждой найденной последовательности.

Answer 3

Использовать предварительную обработку.

Я думаю, вам нужно просто создать Index, выполнить прогон файла, записав первый экземпляр каждой уникальной 4-байтовой последовательности.Сохраните 4-байтовую последовательность и первую встречающуюся позицию в другом файле, отсортированном по байтовой последовательности.

Использование простого двоичного поиска в файле индекса эффективно найдет вашу последовательность.

Вы можетебыть более умным и использовать хеширование, чтобы сократить поиск до O (1).