У меня есть большое количество фиксированных строк (~ 5 миллионов), которые я хочу найти во многих файлах.
Я видел, что два наиболее часто используемых алгоритма поиска строк с использованием конечного набора шаблонов: Aho-Corasick и Commentz-Walter .
Моя цель - найти точное совпадение , а не шаблоны (это означает, что список строк содержит , а не регулярные выражения).
После некоторых исследований я обнаружил множество статей, в которых говорится, что Commentz-Walter в реальных сценариях имеет тенденцию быть быстрее, чем Aho-Corasick ( Article1 , Article2 ), и это также алгоритм за GNU-grep .
Я пытался использовать grep -F также параллельно (взято из здесь ):
free=$(awk '/^((Swap)?Cached|MemFree|Buffers):/ { sum += $2 }
END { print sum }' /proc/meminfo)
percpu=$((free / 200 / $(parallel --number-of-cores)))k
parallel --pipepart -a regexps.txt --block $percpu --compress \
grep -F -f - -n bigfile
и кажется, что проблема слишком большая. Я получаю эту ошибку:
grep: memory exhausted
- Я думал о попытке разбить список шаблонов на несколько файлов и запустить grep несколько раз для одного и того же файла - но это кажется неуклюжим. Есть ли другое решение? или я неправильно запускаю grep?
- Запустив алгоритм Commentz-Walter, grep должен выполнить некоторую предварительную обработку. Я предполагаю, что запуск grep с одним и тем же файлом шаблона в двух разных файлах приведет к тому, что grep выполнит один и тот же этап предварительной обработки дважды. Есть ли способ запустить grep для списка файлов и заставить его запускать предварительную обработку шаблонов только один раз?
- Есть ли хорошая реализация Commentz-Walter в c \ c ++? я только нашел код в Python ( здесь )?
--- Обновление ---
Согласно некоторым комментариям, я пытался протестировать различные реализации Aho-Corasick c \ c ++ ( Komodia , Cjgdev , chasan ), но ни один из них не смог справились с примером из 5 миллионов наборов шаблонов (у всех были проблемы с памятью (ошибка сегментации / переполнение стека)) - они работают на небольших наборах.
Файл примера был сгенерирован этим кодом:
with open(r"C:\very_large_pattern", 'w') as out:
for _ in range(0, 5000000):
out.write(str(uuid.uuid4()) + '\n')
У кого-нибудь есть предложения по реализации, которая может обрабатывать эти числа?