Бинарный файл с самыми быстрыми строками | grep

Предисловие

Прежде всего, у вашей команды есть несколько недостатков, которые могут привести к сбою в определенных ситуациях:

• Он не будет работать со словами, состоящими из символов, отличных от ASCII, таких как буквы с диакритическими знаками, поскольку они фильтруются strings. Хотя, возможно, вы не ищете таких слов.

• Он будет пропускать слова, содержащие менее 4 символов, если они изолированы. Вы должны использовать strings -n1 для общего решения.

• Он будет пропускать слова, если несколько слов принадлежат одной строке текста, потому что grep -c считает строки, а не слова.

Проблемы с реализацией grep в Android (начиная с Android 8.1):

• На Android вы должны использовать grep -E 'word1|word2|...|wordN' вместо grep -F -e word1 -e word2 .. -e wordN, что эквивалентно, но обычно значительно быстрее. Это связано с тем, что в Android 8 есть ошибка, из-за которой последний не учитывается должным образом.

• На Android я буду использовать не только grep -a, но и grep -za. В Linux GNU grep обрабатывает символы NUL (0) в двоичном файле как конец строк, а опция -z не только бесполезна, но и нежелательна, так как выходные строки также будут заканчиваться NUL вместо новой строки. Но версия для Android ведет себя иначе: символы NUL необходимо явно обрабатывать как символы новой строки, в противном случае то, что следует за ними, игнорируется; случайно строки по-прежнему выводятся с традиционным символом новой строки.

Ограничение вывода strings

Вы, вероятно, получите небольшое увеличение скорости, установив для параметра -n значение strings, равное наименьшему размеру искомого слова. Например, если ни одно из искомых слов не короче 7 символов, используйте strings -n7. Таким образом, вы снизите межпроцессное взаимодействие, и ваш grep не будет беспокоить поиск строк, которые, очевидно, не соответствуют шаблону.

Избавляемся от strings

strings немного дороже и может принести мало пользы (это зависит от количества двоичных символов, которые отфильтрованы - YMMV, см. Мой комментарий в следующем разделе), или даже быть вредным (см. Мои предисловия). Вы можете избавиться от него с помощью:

grep -F -a -o -e word1 -e word 2 ... -e wordN /path/to/binary_file \
| wc -l

Из-за вышеупомянутых проблем с Android grep вот версия Android:

grep -z -a -o -E 'word1|word2|...|wordN' /path/to/binary_file \
| wc -l

Помните, что использование grep | wc обязательно, поскольку grep -c считает не слова, а строки. Вот почему grep -c выглядит быстрее для вас, потому что, как только он нашел слово, grep считает +1 и переходит к следующей строке ввода, возможно, пропуская другие слова в текущей строке.

Распараллеливание

В зависимости от количества ядер вы также можете добиться хорошего ускорения за счет распараллеливания grep:

( grep -F -a -o -e word1 -e word2 /path/to/binary_file &
  grep -F -a -o -e word3 -e word4 /path/to/binary_file
) | wc -l

Из-за вышеупомянутых проблем с Android grep вот версия Android:

( grep -z -a -o -E 'word1|word2' /path/to/binary_file &
  grep -z -a -o -E 'word3|word4' /path/to/binary_file
) | wc -l

Здесь я предполагаю, что наиболее интенсивная обработка выполняется strings и grep, и из-за их фильтрации работа wc незначительна. Это может быть не так, в зависимости от схемы поиска. Точно так же, если strings отлично справляется с фильтрацией двоичного файла, вероятно, предпочтительнее оставить его в качестве первой инструкции. YMMV.

Использование tr вместо strings

strings может отфильтровать много ненужных (не ASCII) символов, и это действительно может помочь grep обрабатывать меньше данных. Вы можете пойти еще дальше, отфильтровав каждый символ, не принадлежащий к словам, которые вы ищете. Например, если вы ищете «word1», «word2» и «word3», вы можете отфильтровать все символы, которые не являются w, o, r, d, 1, 2, 3.

Если у вас есть доступ к инструменту командной строки tr, вы получите преимущества, используя его вместо strings:

tr -c -s 'word123' '\n' < /path/to/binary_file \
| grep -F -o -e word1 -e word2 -e word3 \
| wc -l

Из-за вышеупомянутых проблем с Android grep вот версия Android:

tr -c -s 'word123' '\n' < /path/to/binary_file \
| grep -E -o 'word1|word2|word3' \
| wc -l

(имейте в виду, что tr не работает с многобайтовыми символами, отличными от ASCII, но, поскольку вы используете strings в режиме ASCII, вам это уже не важно)

Бенчмаркинг

Вот несколько тестов, выполненных на звуковом файле размером 24 МБ; Платформа - это мой мобильный телефон с восьмиядерным процессором Android 8.1. В зависимости от вашего входного файла, строк поиска и количества ядер вы, очевидно, получите другие результаты, но это даст вам представление о возможных улучшениях скорости.

# Your original command (fixed)
$ time strings -n1 test | grep -E 'A|B|C|D' -o | wc -l
403380
    0m18.93s real     0m10.05s user     0m13.77s system

# grep alone
$ time grep -z -a -E 'A|B|C|D' -o test | wc -l
403380
    0m07.03s real     0m05.26s user     0m00.04s system

# Parallelized grep (x2)
$ time ( grep -z -a -E 'A|B' -o test &
         grep -z -a -E 'C|D' -o test
       ) | wc -l
403380
    0m03.56s real     0m03.12s user     0m00.03s system

# Parallelized grep -F (x4 - one per string to search)
$ time ( grep -z -a -F A -o test &
         grep -z -a -F B -o test &  
         grep -z -a -F C -o test &
         grep -z -a -F D -o test
       ) | wc -l 
403380
    0m01.04s real     0m01.88s user     0m00.05s system

# tr instead of string
$ time tr -c -s 'ABCD' '\n' < test | grep -E 'A|B|C|D' -o | wc -l
403380
    0m01.60s real     0m01.27s user     0m01.41s system

# Parallelized tr + grep (x2)
$ time ( tr -c -s 'AB' '\n' < test | grep -E 'A|B' -o &
         tr -c -s 'CD' '\n' < test | grep -E 'C|D' -o
       ) | wc -l
403380
    0m00.95s real     0m01.23s user     0m02.20s system

Как видите, в этих условиях тестирования скорость между версией с strings и последней (с tr и распараллеливанием) увеличивается примерно в 20 раз.