Каков наилучший способ поиска в большом файле?

Question

Я хочу применить поиск KMP (или аналогичный) к большому файлу (> 4 ГБ).

Я ожидаю, что это вызовет у меня проблемы. Я не могу скопировать все это в память, потому что там недостаточно места.

Мой вопрос: каков наилучший способ поиска? Должен ли я просто создать ФАЙЛ * и выполнить поиск непосредственно в файле, следует ли мне скопировать блоки (скажем, 4 КБ) в память и выполнить поиск по ним или что-то еще полностью?

Answer 1

Для доступа к файлу я бы рекомендовал использовать отображенный в памяти файл, чтобы избежать копирования данных. Это тривиально на машинах Unix. Возможно, вам придется разбить отображение файла на более мелкие блоки, если оно не может быть размещено в одном блоке. Я могу предоставить код, если вы заинтересованы.

Для поиска я бы порекомендовал использовать алгоритм поиска Boyer More .

Answer 2

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

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

Answer 3

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

Однако обычно более эффективно попытаться проиндексировать файл каким-либо образом, чтобы вам не приходилось выполнять линейный поиск по всему файлу. Например, KMP - это алгоритм поиска строк - вы просто ищете вхождения слова? Затем вы можете просто создать хеш-таблицу (на диске) слов и их расположения в файле и осуществлять очень эффективный поиск.

Answer 4

Поиск непосредственно в файле будет очень медленным, использование буферизации даст гораздо лучшую производительность. Но обратите внимание, что ваш буфер должен быть больше, чем вы ищете (SearchLength), конечно, и вы должны обновить буфер, когда он составляет SearchLength байт до его конца.