Эффективно искать отсортированный файл

У меня есть большой файл, содержащий одну строку в каждой строке. Я хотел бы иметь возможность быстро определить, есть ли строка в файле. В идеале это должно быть сделано с использованием алгоритма двоичного типа.

Некоторые из Google показали команду look с флагом -b, которая обещает найти и вывести все строки, начиная с заданного префикса, с использованием алгоритма двоичного поиска. К сожалению, он не работает должным образом и возвращает нулевые результаты для строк, которые, как я знаю, находятся в файле (они правильно возвращаются при эквивалентном поиске grep).

Кто-нибудь знает другую утилиту или стратегию для эффективного поиска в этом файле?

10
задан 2 July 2018 в 06:56

5 ответов

Существует существенная разница между grep и look:

Если явно не указано иное, grep найдет паттерны даже где-то в пределах строк. Для look man-страница заявляет:

look - отображать строки , начинающиеся с заданной строки

Я не использую look очень часто, но это работало хорошо на тривиальном примере, который я только что попробовал.

0
ответ дан 2 July 2018 в 06:56

Может быть, немного поздний ответ:

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 ГБ, это хорошо работает.

0
ответ дан 2 July 2018 в 06:56

Вы можете хешировать файл на части, а затем извлекать только тот фрагмент, который вам нужен:

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

Это делает две вещи:

  1. чтение и запись сжатых файлов. Обычно быстрее разместить нагрузку на процессор (очень быстро) вместо диска (очень медленно)
  2. , чтобы получить примерно равное распределение, вы можете использовать более короткий или более длинный хэш, как вы хотелось бы, чтобы уменьшить размер каждого куска (но я бы порекомендовал использовать вложенные подкаталоги)
0
ответ дан 2 July 2018 в 06:56

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

0
ответ дан 2 July 2018 в 06:56

Если вы хотите действительно быстро (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.

0
ответ дан 2 July 2018 в 06:56

Другие вопросы по тегам:

Похожие вопросы: