Я ищу, чтобы применить KMP (или аналогичный) поиск к большому файлу (> 4 ГБ).Каков наилучший способ сделать поиск в большом файле?
Я ожидаю, что это даст мне проблемы. Я не могу скопировать все это в память, потому что там не хватает места.
Мой вопрос: что это лучший способ сделать этот поиск? Должен ли я просто создавать FILE * и выполнять поиск непосредственно в файле, следует ли копировать блоки (скажем, 4k) в память и искать их или что-то еще полностью?
Если вы используете платформу, которая ее поддерживает, вы можете использовать mmap(). Разбиение файла также возможно, но не забудьте сохранить буфер как можно больше, чтобы уменьшить накладные расходы ввода-вывода и быть осторожным между границами двух страниц (предположим, что строка соответствует, но разделена границей страницы)
В качестве альтернативы, я предлагаю вам создать какой-либо индекс и использовать индекс для ограничения поиска. Поиск KMP не особенно эффективен. Это, конечно, зависит от характера вашего файла, от того, как он создается, и т. Д.
Поиск непосредственно в файле будет очень медленным, использование буферизации даст гораздо лучшую производительность. Но учтите, что ваш буфер должен быть больше, чем то, что вы ищете (SearchLength), конечно, и вам нужно обновить буфер, когда он будет SearchLength байт до его окончания.
Лучший подход - прочитать его в блоках и выполнить поиск. Вы должны сделать размер блока параметром, чтобы вы могли поэкспериментировать с тем, что дает лучшую производительность.
Однако, как правило, более эффективно пытаться индексировать файл каким-либо образом, чтобы вам не пришлось линейно искать весь файл. Например, KMP - это алгоритм поиска строк - вы просто ищете случаи слова? Затем вы можете просто создать хеш-таблицу (на диске) слов и их расположение в файле и провести очень эффективный поиск.
Ну, я пытаюсь выполнить поиск всех вхождений шестнадцатеричной строки в предоставленном пользователем файле. Поскольку файл будет отличаться каждый раз, и поскольку я ищу шестнадцатеричные значения, хеш-таблицы выглядят так, как будто они не стоили бы стоимости. – samoz
Правда, вот почему я сказал «обычно» :) Каждая проблема поиска несколько отличается. Я бы защищал только пейджинг, но опять же, всегда использую параметры, чтобы вы могли настраивать настройки для вашей конкретной установки. –
Для доступа к файлам я бы рекомендовал использовать файл с отображением памяти, чтобы избежать копирования данных. Это тривиально на машинах Unix. Возможно, вам придется разбить отображение файла на более мелкие блоки, если он не может быть выделен в одном блоке. Я могу предоставить некоторый код, если вы заинтересованы.
Для поиска я бы рекомендовал использовать Boyer More search algorithm.
+1 для использования mmap. Следует просто отметить, что вам все равно потребуется mmap в блоках на 32-битных машинах, потому что адресного пространства недостаточно. – tsg
Да, mmap (по крайней мере, на OSX, но это стандартная BSD) принимает смещение size_t len и off_t. OP должен проверить, имеют ли эти типы 64-битные значения, иначе он никогда не сможет обратиться за пределом 4 Гигабайта. –