LINUX.ORG.RU

Быстрый алгоритм проверки наличия сэмплов в файле

 ,


0

2

Есть список где-то с сотню слов (может вырастет еще), нужно как-то суметь не просто проверить, а очень быстро проверить есть ли они в файле и если есть, то сколько (статистика). Не требуется узнавать их местоположение. Файлы могут быть в разных кодировках. UTF-8, UTF-16, cp1251, может быть и еще какие-то. В идеале бы не тратить время на конвертацию, а как-то так без нее проверять на лету. Ограничений по расходу памяти в разумных пределах нет. Файлы где-то вряд ли больше 10Мб, скорее всего меньше намного.

Прежде чем начать велосипедить хочется узнать, может есть где-то (полу)готовые такие алгоритмы?

★★★★★

Последнее исправление: praseodim (всего исправлений: 1)

может есть где-то (полу)готовые такие алгоритмы?

Есть, регулярные выражения называются.

anonymous
()
Ответ на: комментарий от anonymous

Спасибо, надо будет проверить работу. Даже не знал (не помнил) про -F у грепа.

Правда, что скверно, в разных кодировках оно не ищет и -c выводит количество строк с совпадениями, а не просто число совпадений. Но ничего, для начала сойдет.

praseodim ★★★★★
() автор топика
Ответ на: комментарий от anonymous

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

praseodim ★★★★★
() автор топика
Ответ на: комментарий от praseodim

Я не знаю регулярных выражений, умеющих одновременно разные кодировки

Так переведи сэмплы во все нужные кодировки и потом — ищи их как байтстринги в локали C (если не интересует каноническая эквивалентность юникода, NFD/NFC и прочая фигня, нерелевантная для русского в реальном мире). Быстрее, чем переводить файлы.

x3al ★★★★★
()
Последнее исправление: x3al (всего исправлений: 1)
Ответ на: комментарий от Waterlaz

Мне не нужно как это вообще сделать, с этим проблем нет. Нужно БЫСТРО. iconv - это потеря времени на перекодировку, к тому же ее еще узнать надо, а она заранее неизвестна.

praseodim ★★★★★
() автор топика
Последнее исправление: praseodim (всего исправлений: 1)
Ответ на: комментарий от x3al

Так переведи сэмплы во все нужные кодировки и потом — ищи их как байтстринги в локали C

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

praseodim ★★★★★
() автор топика

попробуй перекодировать не данные, а семплы, и потом искать перекодированные семплы в файлах простым strstr'ом

thesame ★★★★
()
Ответ на: комментарий от thesame

Использовать strstr - значит запускать ее столько раз сколько семплов? Это затормозит поиск, файл будет сканироваться много раз подряд. Или этого не избежать и фактически все равно много сравнений надо?

Как-то хотелось бы исхитриться так, что бы было время O(1) от количества сэмплов, в крайнем случае O(log k) - к число сэмплов и не более O(n) от длины файла.

praseodim ★★★★★
() автор топика
Последнее исправление: praseodim (всего исправлений: 2)
Ответ на: комментарий от praseodim

Эмм. Пробегаешь по файлу через каждые <длину самого короткого сэмпла> байт, если там попался встречающийся в сэмплах байт — смотришь что перед ним (а если сэмпл не самый короткий либо это не последний байт, то ещё и за ним), всё. Вряд ли удастся сделать быстрее.

x3al ★★★★★
()
Ответ на: комментарий от i-rinat

Кажется это примерно оно. Спасибо. Интересно, какой алгоритм в grep -F ? Если он же задача почти решена, максимум немного переписать под себя grep надо будет.

praseodim ★★★★★
() автор топика
Ответ на: комментарий от x3al

Вряд ли удастся сделать быстрее.

Вроде i-rinat подсказал алгоритм побыстрее.

praseodim ★★★★★
() автор топика
Ответ на: комментарий от praseodim

Интересно, какой алгоритм в grep -F ?

В Википедии пишут, что что-то на основе Aho-Corasick. В kwset.c тоже есть на них ссылка.

Есть ещё семейство алгоритмов, описаны в http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.313 Они могут быть ещё быстрее, но сложнее в реализации.

i-rinat ★★★★★
()
Ответ на: комментарий от Waterlaz

Тут еще дело в том, что заранее не известна кодировка.

praseodim ★★★★★
() автор топика

Rabin-Karp-Algorithm.

invy ★★★★★
()
Ответ на: комментарий от i-rinat

О5 местные нули помогают нулю решать выдуманный им план действий вместо реальной задачи, которая тоже высер заказчика-нуля.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.