Каков наилучший способ поиска в большом файле?
https://stackoverflow.com/questions/1212255
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хочу применить поиск KMP (или аналогичный) к большому файлу (> 4 ГБ).
Я ожидаю, что это вызовет у меня проблемы. Я не могу скопировать все это в память, потому что там недостаточно места.
Мой вопрос: каков наилучший способ поиска? Должен ли я просто создать ФАЙЛ * и выполнить поиск непосредственно в файле, следует ли мне скопировать блоки (скажем, 4 КБ) в память и выполнить поиск по ним или что-то еще полностью?
Решение
Если вы используете платформу, которая поддерживает ее, вы можете использовать mmap (). Пагинация файла также возможна, но не забудьте сохранить буфер настолько большим, насколько это возможно, чтобы уменьшить накладные расходы ввода-вывода и соблюдать осторожность между границами двух страниц (предположим, что строка совпадает, но разбивается по границе страницы)
В качестве альтернативы я предлагаю вам создать какой-нибудь индекс и использовать индекс для ограничения поиска. KMP поиск не особенно эффективен. Это, конечно, зависит от природы вашего файла, способа его создания, и т. Д.
Другие советы
Для доступа к файлу я бы рекомендовал использовать отображенный в память файл, чтобы избежать копирования данных. Это тривиально на машинах Unix. Возможно, вам придется разбить отображение файла на более мелкие блоки, если оно не может быть размещено в одном блоке. Я могу предоставить код, если вы заинтересованы.
Для поиска я бы рекомендовал использовать алгоритм поиска Boyer More .
Поиск непосредственно в файле будет очень медленным, использование буферизации даст гораздо лучшую производительность. Но обратите внимание, что ваш буфер должен быть больше, чем вы ищете ( SearchLength ), конечно, и вы должны обновить буфер, когда он является SearchLength байтами до его конца.
Лучший подход - читать его по блокам и искать его. Вы должны сделать размер блока параметром, чтобы вы могли поэкспериментировать с тем, что дает наилучшую производительность.
Тем не менее, обычно более эффективно попытаться проиндексировать файл каким-либо образом, чтобы вам не приходилось выполнять линейный поиск по всему файлу. Например, KMP - это алгоритм поиска строк - вы просто ищете вхождения слова? Затем вы можете просто создать хеш-таблицу (на диске) слов и их расположения в файле и осуществлять очень эффективный поиск.
