Как найти повторяющиеся строки во многих больших файлах?

9

У меня есть ~ 30 тыс. Файлов. Каждый файл содержит ~ 100 тыс. Строк. Строка не содержит пробелов. Строки в отдельном файле сортируются и дублируются бесплатно.

Моя цель: я хочу , чтобы найти все все повторяющиеся строки через два или более файлов , а также имена файлов, содержащие дублированные записи.

Простое решение будет следующим:

cat *.words | sort | uniq -c | grep -v -F '1 '

И тогда я бы побежал:

grep 'duplicated entry' *.words

Вы видите более эффективный способ?

Ларс Шнайдер
источник

Ответы:

13

Поскольку все входные файлы уже отсортированы, мы можем пропустить фактический этап сортировки и просто использовать sort -mдля объединения файлов вместе.

В некоторых системах Unix (насколько мне известно только в Linux) этого может быть достаточно

sort -m *.words | uniq -d >dupes.txt

чтобы получить дублированные строки, записанные в файл dupes.txt.

Чтобы найти, из каких файлов были получены эти строки, вы можете сделать

grep -Fx -f dupes.txt *.words

Это будет указывать grepобрабатывать строки в dupes.txt( -f dupes.txt) как фиксированные строковые шаблоны ( -F). grepтакже потребует, чтобы вся строка идеально подходила от начала до конца ( -x). Он напечатает имя файла и строку к терминалу.

Unix Linux Unices (или даже больше файлов)

В некоторых системах Unix 30000 имен файлов будут расширяться до строки, которая слишком длинна, чтобы передать ее одной утилите (что означает sort -m *.wordsсбой Argument list too long, что происходит в моей системе OpenBSD). Даже Linux будет жаловаться на это, если количество файлов намного больше.

Нахождение обманщиков

Это означает, что в общем случае (это также будет работать со многими, более чем 30000 файлами), нужно «разделить» сортировку:

rm -f tmpfile
find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

В качестве альтернативы, создание tmpfileбез xargs:

rm -f tmpfile
find . -type f -name '*.words' -exec sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh {} +

Это найдет все файлы в текущем каталоге (или ниже), чьи имена совпадают *.words. Для соответствующего размера фрагмента этих имен за раз, размер которого определяется xargs/ find, он объединяет их в отсортированный tmpfileфайл. Если он tmpfileуже существует (для всех, кроме первого чанка), этот файл также объединяется с другими файлами в текущем чанке. В зависимости от длины ваших имен файлов и максимально допустимой длины командной строки, для этого может потребоваться более или намного более 10 отдельных запусков внутреннего скрипта ( find/ xargsсделает это автоматически).

«Внутренний» shскрипт,

if [ -f tmpfile ]; then
    sort -o tmpfile -m tmpfile "$@"
else
    sort -o tmpfile -m "$@"
fi

используется sort -o tmpfileдля вывода в tmpfile(это не будет перезаписывать, tmpfileдаже если это также вход sort) и -mдля слияния. В обеих ветвях "$@"развернется список имен файлов, указанных в кавычках, которые передаются в скрипт из findили xargs.

Затем, просто запустите uniq -dна , tmpfileчтобы получить все строки, которые дублировали:

uniq -d tmpfile >dupes.txt

Если вам нравится принцип «СУХОЙ» («Не повторяйте себя»), вы можете написать внутренний скрипт как

if [ -f tmpfile ]; then
    t=tmpfile
else
    t=/dev/null
fi

sort -o tmpfile -m "$t" "$@"

или

t=tmpfile
[ ! -f "$t" ] && t=/dev/null
sort -o tmpfile -m "$t" "$@"

Откуда они пришли?

По тем же причинам, что и выше, мы не можем grep -Fx -f dupes.txt *.wordsопределить, откуда появились эти дубликаты, поэтому вместо этого мы используем findснова:

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt {} +

Поскольку «сложной» обработки не требуется, мы можем вызывать grepнепосредственно из -exec. -execОпция принимает команду утилиты и поместить найденные имена {}. С +в конце, findразместит столько аргументов, {}сколько поддерживает текущая оболочка при каждом вызове утилиты.

Чтобы быть полностью правильным, можно использовать либо

find . -type f -name '*.words' \
    -exec grep -H -Fx -f dupes.txt {} +

или

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt /dev/null {} +

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

Первый вариант используется grep -Hдля всегда вывода совпадающих имен файлов. Последний вариант использует тот факт, что grepбудет включать имя соответствующего файла, если в командной строке указано более одного файла .

Это имеет значение, поскольку последний кусок имен файлов, отправленных grepс, findможет фактически содержать только одно имя файла, и в этом случае grepон не будет упоминаться в его результатах.


Бонусный материал:

Рассекая команду find+ xargs+ sh:

find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

find . -type f -name '*.words'просто сгенерирует список имен путей из текущего каталога (или ниже), где каждое из них совпадает с именем обычного файла ( -type f) и имеет в конце соответствующий компонент имени файла *.words. Если нужно искать только текущий каталог, можно добавить -maxdepth 1после ., перед -type f.

-print0обеспечит вывод всех найденных путей с символом \0( nul) в качестве разделителя. Это символ, который недопустим в пути Unix, и он позволяет нам обрабатывать имена путей, даже если они содержат символы новой строки (или другие странные вещи).

findтрубы его выход на xargs.

xargs -0прочтет \0-delimited список имен путей и будет выполнять данную утилиту несколько раз с кусками этих, гарантируя , что утилита выполняется с достаточно просто аргументы , чтобы не вызвать оболочку жаловаться на слишком длинный список аргументов, пока больше нет ввода от find.

Утилита вызывается xargsэто shс помощью сценария , заданного в командной строке в виде строки , используя свой -cфлаг.

При вызове sh -c '...some script...'с последующими аргументами аргументы будут доступны скрипту $@, за исключением первого аргумента , в который будет помещен $0(это «имя команды», которое вы можете заметить, например, topесли вы достаточно быстры). Вот почему мы вставляем строку shв качестве первого аргумента после конца реального скрипта. Строка shявляется фиктивным аргументом и может быть любым отдельным словом (некоторые предпочитают _или sh-find).

Кусалананда
источник
В конце вашего первого блока сценария оболочки, какая польза fi' sh?
дан
@danielAzuelos Это fiконец ifоператора во "внутреннем" shсценарии оболочки. В 'торцах , что сценарий оболочки (весь сценарий является одиночно строкой в кавычках). shБудет передан на внутренний скрипт в $0(не часть $@, которая будет содержать имена файлов). В этом случае эта shстрока может быть любым словом. Если пропустить shв конце, первое имя файла будет передано $0и не будет частью обработки, выполняемой внутренним сценарием оболочки.
Кусалананда
8

Строки в отдельном файле сортируются и дублируются бесплатно.

Это означает, что вы, вероятно, можете найти какое-то применение для sort -m:

 -m, --merge
        merge already sorted files; do not sort

Другой очевидной альтернативой для этого было бы просто awkсобрать строки в массив и сосчитать их. Но, как прокомментировал @ dave_thompson_085 , эти 3 000 миллионов строк (или сколько угодно уникальных), вероятно, потребовали бы некоторый значительный объем памяти для хранения, так что это может работать не очень хорошо.

ilkkachu
источник
3

С помощью awk вы можете получить все повторяющиеся строки во всех файлах одной короткой командой:

$ awk '_[$0]++' *.words

Но он будет повторять строки, если линия существует 3 или более раз.
Есть решение получить только первый дубликат:

$ awk '_[$0]++==1' *.words

Это должно быть довольно быстро (если повторов мало), но потребляет много памяти, чтобы сохранить все строки в памяти. Возможно, в зависимости от ваших реальных файлов и повторов, попробуйте сначала с 3 или 4 файлами.

$ awk '_[$0]++==1' [123]*.words

В противном случае вы можете сделать:

$ sort -m *.words | uniq -d

Который будет печатать уникальные повторяющиеся строки.

Исаак
источник
2
+1 заsort -m * | uniq -d
Джефф Шаллер
awk может избежать повторов, 'x[$0]++==1'но на самом деле потребуется много памяти; если линии 3G имеют, скажем, отличные значения 1G, и если вашему awk нужно, скажем, 50 байтов для записи хеш-массива, отображающей (предположительно короткую) строку в значение неинициализированного значения, это 50 ГБ. Для сортированного ввода вы можете сделать это uniq -dвручную, awk '$0==p&&n++==1;$0!=p{p=$0;n=1}'но зачем?
dave_thompson_085
@ dave_thompson_085 Спасибо за концепцию ==1, отличная идея.
Исаак
Предполагая 30000 файлов с 100000 строк по 80 символов в каждом и без дубликатов , для этого потребуется awkхранить 2,4E11 байт (223 ГиБ).
Кусалананда
sort -m *.words | uniq -dработает отлично! После процесса я запускаю, grepчтобы найти файлы, которые содержат повторяющиеся записи. Вы видите способ напечатать хотя бы одно имя файла, содержащее дублированную запись?
Ларс Шнайдер
3

Оптимизированное sort+ uniqрешение:

sort --parallel=30000 *.words | uniq -d
  • --parallel=N - изменить количество одновременных сортировок на N
  • -d, --repeated - печатать только дубликаты строк, по одной для каждой группы
RomanPerekhrest
источник