Если это ваш первый визит, рекомендуем почитать справку по форуму. Для размещения своих сообщений необходимо зарегистрироваться. Для просмотра сообщений выберите раздел. |
Поиск строки в файле |
Философия, технологии, алгоритмы! |
|
Опции темы |
15.12.2005, 10:51 | #1 |
Модератор
Сообщений: 665
Регистрация: 09.01.2002
Не в сети |
Поиск строки в файле
Есть задача проверять наличие данной строки в файле.
Нюанс в том, что надо проверить присутствуют ли в файле 20-30 тысяч данных строк. Всё это работает, но занимает довольно долгое время, так как необходимо проверить большое кол-во файлов. Файл 300 Кб проверяется 10-15 секунд. Есть ли идеи, как ускорить это? Язык программирования не важен. |
15.12.2005, 14:16 | #3 |
Registered User
Сообщений: 1,905
Регистрация: 25.03.2003
Не в сети |
стырить, наконец, из clamav сигнатурный поиск,а через год попасть на страницы газет "беспринципные воронежские программисты за решеткой" ).
а еще лучше начать выпускать на основе clamav какой-нибудь полукоммерческий продукт. |
15.12.2005, 14:38 | #4 |
Registered User
Сообщений: 1,905
Регистрация: 25.03.2003
Не в сети |
ниразу не приходилось реализовывать, но алгоритм представляется мне так:
двигаясь по файлу вперед, вычисляем контрольные суммы фрагментов C1,C2, ..CN, где N-максимальная длина фрагмента (сигнатуры). при загрузке из контрольных сумм сигнатур, строится хеш. дальше каждое C[i] нужно проверить на нахождение в хеше, если нашлась в хеше, найти сигнатуру и сверить на фактическое побайтное совпадение. Наверное у кнута есть что-нибудь по теме. |
15.12.2005, 14:48 | #6 |
Форумец
Сообщений: 2,045
Регистрация: 27.08.2003
Не в сети |
Ну, гениальных мыслей у меня нет - их думать надо - а есть простые принцыпы, как я бы действовал для начала.
1. Файлы, по-возможности, грузить в память, потому что считывание целого файла в память довольно быстрая операция по сравнению с поиском по файлу (на кешь не всегда можно полагаться). 2. Искать не текст (строку), а бинарный код, потому что бинарное сравнение работает быстрее (если, конечно, это возможно). 3. Если возможно, для модуля (процедуры, функции и т.д.) сравнения применять оптимизацию компилятора по скорости. Или, если задача сравнения будет решаться побайтовым сравнением, использовать машинную команду сравнения блоков данных - она самая быстрая. 4. Если возможно, придумать хеш-функцию, которая бы отвергала на 100% неодинаковые значения, оставляя только "похоже, что одно и то же". А уж ее результат сравнивать побайтно. |
19.12.2005, 10:14 | #11 |
Форумец
Сообщений: 2,159
Регистрация: 15.01.2003
Не в сети |
Kerish Если поиск бинарный, то можно с кэшем попробывать поиграться. Т.е. искать за раз по 10-20 строк в небольших отрезках файла. И если проц двуядерный, то про распараллеливание тоже не забыть.
Если поиск по тексту - переводим вверхний регистр и делаем бинарный поиск. Про интеловский компилятор тоже не надо забывать. Вообще 300 кб пройти 30000 раз за 15 секунд - это как-то странно... Ты не на яве писал? |
19.12.2005, 11:17 | #14 |
Registered User
Сообщений: 1,905
Регистрация: 25.03.2003
Не в сети |
Калинин Дмитрий наверное, неправильно понял,
там всего за 1 просмотр файла проверяются сразу все сигнатуры. ну и контрольные суммы можно тоже вычислять циклически не суммируя все подряд, а на основе предыдущих значений. Приличных библиотек с реализациями хешей тоже должно быть много. Профессиональные антивирусы ведь работают очень быстро, значит быстрый алгоримт поиска сигнатур есть. И, скорее всего, похож на описанный. |