У меня есть большой файл, содержащий одну строку в каждой строке. Я хотел бы иметь возможность быстро определить, есть ли строка в файле. В идеале это должно быть сделано с использованием алгоритма двоичного типа.
Некоторые из Google показали команду look
с флагом -b
, которая обещает найти и вывести все строки, начиная с заданного префикса, с использованием алгоритма двоичного поиска. К сожалению, он не работает должным образом и возвращает нулевые результаты для строк, которые, как я знаю, находятся в файле (они правильно возвращаются при эквивалентном поиске grep
).
Кто-нибудь знает другую утилиту или стратегию для эффективного поиска в этом файле?
Существует существенная разница между grep
и look
:
Если явно не указано иное, grep
найдет паттерны даже где-то в пределах строк. Для look
man-страница заявляет:
look - отображать строки , начинающиеся с заданной строки
Я не использую look
очень часто, но это работало хорошо на тривиальном примере, который я только что попробовал.
Может быть, немного поздний ответ:
Sgrep поможет вам.
Sgrep (сортированный grep) ищет в отсортированных входных файлах строки, соответствующие ключу поиска, и выводит соответствующие строки. При поиске больших файлов sgrep работает намного быстрее, чем традиционный Unix grep, но со значительными ограничениями.
Вы можете скачать источник здесь: https://sourceforge.net/projects/sgrep/?source=typ_redirect
и документы здесь: http: //sgrep.sourceforge.net/
Другой путь:
Я не знаю, насколько велик файл. Возможно, вам стоит попробовать параллельное:
https://stackoverflow.com/questions/9066609/fastest-possible-grep
Я всегда делаю grep с файлами, размер которых> 100 ГБ, это хорошо работает.
Вы можете хешировать файл на части, а затем извлекать только тот фрагмент, который вам нужен:
for line in $(cat /usr/share/dict/american-english | tr '[:upper:]' '[:lower:]' | sort | uniq)
do
prefix=$(echo $line | md5sum - | cut -c 1-2)
mkdir -p $prefix
echo $line | gzip >> $prefix/subwords
done
, тогда поиск будет выглядеть следующим образом:
prefix=$(echo $word | md5sum - | cut -c 1-2)
zgrep -m 1 -w word $prefix/subwords
Это делает две вещи:
sgrep может работать для вас:
sudo apt-get install sgrep
sgrep -l '"needle"' haystack.txt
Страница проекта http://sgrep.sourceforge.net/ гласит:
Sgrep использует алгоритм двоичного поиска, который очень быстрый, но требует сортированного ввода.
Для вставки, однако, я думаю, что нет лучшего решения, чем использование базы данных: https://stackoverflow.com/questions/10658380/shell-one-liner-to-add-a-line -в-а-сортированы-файл / 33859372 # 33859372
Если вы хотите действительно быстро (O (1) быстро), вы можете создать хэш-набор для изучения. Я не смог найти реализацию, которая позволила бы мне сохранить предварительно созданный хэш-набор в файле и проверить его без необходимости считывать весь файл в память, поэтому я свернул свой собственный ].
Создайте хэш-набор (-b
/ --build
):
./hashset.py --build string-list.txt strings.pyhashset
Исследуйте хэш-набор (-p
/ --probe
):
./hashset.py --probe strings.pyhashset \
'Is this string in my string list?' 'What about this one?'
… или со строкой для поиска на стандартном входе:
printf '%s\n' 'Is this string in my string list?' 'What about this one?' |
./hashset.py --probe strings.pyhashset
Вы можете уменьшить вывод --probe
с помощью опции -q
/ --quiet
, если вас интересует только состояние выхода:
if ./hashset.py --quiet --probe strings.pyhashset ...; then
echo 'Found'
else
echo 'Not found'
fi
Дополнительные параметры см. В описании использования, доступном через параметр -h
/ --help
или в прилагаемом файле README
.