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

12

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

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

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

command-line text-processing grep Matt
источник
В верхнем ответе указывается неправильная сортировка: на самом деле вам нужно выполнить сортировку с помощью: LC_COLLATE = C sort -d, чтобы lookкоманда работала правильно, потому что внешний вид, похоже, игнорирует локаль и просто использует C, как сортировку жестко, я также открыл ошибку из-за этого запутанного поведения: bugzilla.kernel.org/show_bug.cgi?id=198011
Sur3
look -bне удалось для меня с ошибкой File too large. Я думаю, что он пытается прочитать все это в памяти.
Брайан Минтон

Ответы:

9

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

Если явно не указано иное, grepшаблоны будут найдены даже где-то внутри строк. Для lookman-страницы говорится:

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

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

Клаус-Дитер Варцеха
источник
1
Файл, который мне нужен для поиска, содержит около 110 000 000 строк. Если я это сделаю, egrep "^TEST" sortedlist.txt | wc -l я получу 41 289 результатов. Однако эквивалентные lookкоманды, look -b TEST sortedlist.txt | wc -lдают только результаты 1995 года. Мне почти интересно, есть ли ошибка в look.
Мэтт
1
@Matt Возможно lookиспользует другие параметры сортировки, чем программа, которую вы использовали для сортировки файла.
kasperd
4

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

Сгреп вам поможет.

Sgrep (сортированный grep) ищет в отсортированных входных файлах строки, соответствующие ключу поиска, и выводит соответствующие строки. При поиске больших файлов sgrep работает намного быстрее, чем традиционный Unix grep, но со значительными ограничениями.

  • Все входные файлы должны быть отсортированы обычными файлами.
  • Ключ сортировки должен начинаться с начала строки.
  • Ключ поиска совпадает только в начале строки.
  • Нет поддержки регулярных выражений.

Вы можете скачать источник здесь: https://sourceforge.net/projects/sgrep/?source=typ_redirect

и документы здесь: http://sgrep.sourceforge.net/

Другой путь:

Я не знаю, насколько большой файл. Может быть, вы должны попробовать параллельно:

/programming/9066609/fastest-possible-grep

Я всегда делаю grep с файлами, размер которых> 100 ГБ, это работает хорошо.

memorybox
источник
2
Разве это уже не в askubuntu.com/a/701237/158442 ?
Муру,
да, я заполняю ссылку для скачивания ...
memorybox
Если это все, вы должны отредактировать это сообщение вместо публикации нового ответа.
Муру
этот пост рекомендуется: sudo apt-get install sgrep чтобы получить sgrep, sgrep в репозиториях Buntu на самом деле не является этим sgrep, я не уверен, что это то же самое.
память
0

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

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

sgrep может работать на вас:

sudo apt-get install sgrep
sgrep -l '"needle"' haystack.txt

На странице проекта http://sgrep.sourceforge.net/ написано:

Sgrep использует алгоритм двоичного поиска, который очень быстр, но требует сортированного ввода.

Однако для вставки, я думаю, нет лучшего решения, чем использование базы данных: /programming/10658380/shell-one-liner-to-add-a-line-to-a-sorted-file/ 33859372 # 33859372

Сиро Сантилли 冠状 病毒 审查 六四 事件 法轮功
источник
3
На sgrepсамом деле в репозиториях Ubuntu есть этот sgrep , который предназначен для «поиска файла по структурированному шаблону» и не имеет ничего общего с бинарным поиском.
ingomueller.net
0

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

Дэвид Фёрстер
источник