Быстрый способ поиска строк в одном файле, которых нет в другом?
У меня есть два больших файла (наборы имен файлов). Примерно 30.000 строк в каждом файле. Я пытаюсь найти быстрый способ найти строки в file1, которых нет в file2.
Например, если это файл1:
line1
line2
line3
И это файл2:
line1
line4
line5
Тогда мой результат / вывод должен быть:
line2
line3
Это работает:
grep -v -f file2 file1
Но это очень, очень медленно, когда используется на моих больших файлах.
Я подозреваю, что есть хороший способ сделать это с помощью diff(), но на выходе должны быть только строки, ничего больше, и я не могу найти переключатель для этого.
Может кто-нибудь помочь мне найти быстрый способ сделать это, используя bash и базовые бинарные файлы Linux?
РЕДАКТИРОВАТЬ: Чтобы продолжить мой вопрос, это лучший способ, который я нашел до сих пор с использованием diff():
diff file2 file1 | grep '^>' | sed 's/^>\ //'
Конечно, должен быть лучший способ?
10 ответов
Вы можете достичь этого, управляя форматированием старых / новых / неизмененных строк в GNU diff выход:
diff --new-line-format="" --unchanged-line-format="" file1 file2
Входные файлы должны быть отсортированы, чтобы это работало. С bash (а также zsh) вы можете отсортировать на месте с заменой процесса <( ):
diff --new-line-format="" --unchanged-line-format="" <(sort file1) <(sort file2)
В вышеупомянутых новые и неизмененные строки подавляются, поэтому выводятся только измененные (т.е. удаленные строки в вашем случае). Вы также можете использовать несколько diff варианты, которые не предлагают другие решения, такие как -i игнорировать регистр или различные варианты пробелов (-E, -b, -v и т. д.) для менее строгого соответствия.
объяснение
Варианты --new-line-format, --old-line-format а также --unchanged-line-format позволить вам контролировать путь diff форматирует различия, похожие на printf спецификаторы формата. Эти параметры форматируют новые (добавленные), старые (удаленные) и неизмененные строки соответственно. Установка одного в "" предотвращает вывод строки такого типа.
Если вы знакомы с унифицированным форматом diff, вы можете частично восстановить его с помощью:
diff --old-line-format="-%L" --unchanged-line-format=" %L" \
--new-line-format="+%L" file1 file2
%L спецификатор - это строка, о которой идет речь, и мы добавляем к каждому префикс "+", "-" или " ", например diff -u (обратите внимание, что он выводит только различия, ему не хватает ---+++ а также @@ линии в верхней части каждого сгруппированного изменения). Вы также можете использовать это, чтобы делать другие полезные вещи, такие как нумерация каждой строки %dn,
diff метод (наряду с другими предложениями comm а также join) производить только ожидаемый вывод с отсортированным вводом, хотя вы можете использовать <(sort ...) сортировать на месте. Вот простой awk Сценарий (nawk) (на основе сценариев, связанных в ответе Konsolebox), который принимает произвольно упорядоченные входные файлы и выводит пропущенные строки в порядке их появления в файле1.
# output lines in file1 that are not in file2
BEGIN { FS="" } # preserve whitespace
(NR==FNR) { ll1[FNR]=$0; nl1=FNR; } # file1, index by lineno
(NR!=FNR) { ss2[$0]++; } # file2, index by string
END {
for (ll=1; ll<=nl1; ll++) if (!(ll1[ll] in ss2)) print ll1[ll]
}
Это хранит все содержимое файла1 построчно в индексированном массиве с номером строки ll1[] и все содержимое файла file2 строка за строкой в индексированном ассоциативном массиве содержимого строки ss2[], После того, как оба файла прочитаны, выполните итерацию ll1 и использовать in оператор, чтобы определить, присутствует ли строка в file1 в file2. (Это будет иметь другой выход к diff метод, если есть дубликаты.)
В случае, если файлы достаточно велики, и их хранение вызывает проблемы с памятью, вы можете обменять ЦП на память, сохранив только файл1 и удалив совпадения по ходу чтения файла2.
BEGIN { FS="" }
(NR==FNR) { # file1, index by lineno and string
ll1[FNR]=$0; ss1[$0]=FNR; nl1=FNR;
}
(NR!=FNR) { # file2
if ($0 in ss1) { delete ll1[ss1[$0]]; delete ss1[$0]; }
}
END {
for (ll=1; ll<=nl1; ll++) if (ll in ll1) print ll1[ll]
}
Выше хранится все содержимое файла file1 в двух массивах, один из которых проиндексирован по номеру строки ll1[] индексируется по содержанию строки ss1[], Затем, когда file2 читается, каждая совпадающая строка удаляется из ll1[] а также ss1[], В конце выводятся оставшиеся строки из file1, сохраняя исходный порядок.
В этом случае, с указанной выше проблемой, вы также можете разделить и победить, используя GNU split (фильтрация является расширением GNU), повторяющиеся прогоны с кусками файла file1 и чтением файла file2 каждый раз:
split -l 20000 --filter='gawk -f linesnotin.awk - file2' < file1
Обратите внимание на использование и размещение - имея в виду stdin на gawk командная строка. Это обеспечивается split из файла1 кусками по 20000 строк на вызов.
Для пользователей не-GNU систем почти наверняка есть пакет GNU coreutils, который вы можете получить, в том числе для OSX как часть инструментов Apple Xcode, предоставляющих GNU. diff, awk хотя только POSIX/BSD split а не версия GNU.
Команда comm (сокращение от "common") может быть полезной comm - compare two sorted files line by line
#find lines only in file1
comm -23 file1 file2
#find lines only in file2
comm -13 file1 file2
#find lines common to both files
comm -12 file1 file2
man файл на самом деле вполне читабелен для этого.
Как предложено konsolebox, решение grep для постеров
grep -v -f file2 file1
на самом деле работает отлично (быстро), если вы просто добавляете -F возможность рассматривать шаблоны как фиксированные строки вместо регулярных выражений. Я проверил это на паре списков файлов по ~1000 строк, которые мне пришлось сравнить. С -F это заняло 0,031 с (реальное), в то время как без этого - 2,278 с (реальное) при перенаправлении вывода grep на wc -l,
Эти тесты также включали -x switch, которые являются необходимой частью решения для обеспечения полной точности в случаях, когда file2 содержит строки, которые соответствуют части, но не всем, одной или нескольким строкам в file1.
Таким образом, решение, которое не требует сортировки входных данных, является быстрым, гибким (чувствительность к регистру и т. Д.), А также (я думаю) работает на любой системе POSIX:
grep -F -x -v -f file2 file1
Если вам не хватает "модных инструментов", например, в каком-то минимальном дистрибутиве Linux, есть решение с cat, sort а также uniq:
cat includes.txt excludes.txt excludes.txt | sort | uniq --unique
Тестовое задание:
seq 1 1 7 | sort --random-sort > includes.txt
seq 3 1 9 | sort --random-sort > excludes.txt
cat includes.txt excludes.txt excludes.txt | sort | uniq --unique
# Output:
1
2
Это также относительно быстро, по сравнению с grep,
Использовать combine от moreutils пакет, утилита наборов, поддерживающая not, and, or, xor операции
combine file1 not file2
т.е. дайте мне строки, которые находятся в файле1, но не в файле2
ИЛИ дайте мне строки в файле1 минус строки в файле2
Примечание: combine сортирует и находит уникальные строки в обоих файлах перед выполнением любой операции, кроме diffне. Таким образом, вы можете найти различия между выводомdiff а также combine.
По сути, вы говорите
Найдите отдельные строки в file1 и file2, а затем дайте мне строки в file1 минус строки в file2
По моему опыту, это намного быстрее, чем другие варианты
Какова скорость сортировки и сравнения?
sort file1 -u > file1.sorted
sort file2 -u > file2.sorted
diff file1.sorted file2.sorted
Мне это кажется быстрым:
comm -1 -3 <(sort file1.txt) <(sort file2.txt) > output.txt
$ join -v 1 -t '' file1 file2
line2
line3
-t удостоверяется, что он сравнивает всю строку, если у вас есть пробел в некоторых строках.
Вы можете использовать Python:
python -c '
lines_to_remove = set()
with open("file2", "r") as f:
for line in f.readlines():
lines_to_remove.add(line.strip())
with open("f1", "r") as f:
for line in f.readlines():
if line.strip() not in lines_to_remove:
print(line.strip())
'
Я обычно делаю это, используя --suppress-common-lines Отметьте, хотя обратите внимание, что это работает, только если вы делаете это в формате бок о бок.
diff -y --suppress-common-lines file1.txt file2.txt
Может помочь использование fgrep или добавление опции -F в grep. Но для более быстрых вычислений вы можете использовать Awk.
Вы можете попробовать один из этих методов Awk:
http://www.linuxquestions.org/questions/programming-9/grep-for-huge-files-826030/
Я обнаружил, что для меня использование нормального оператора цикла if и for работает отлично.
for i in $(cat file2);do if [ $(grep -i $i file1) ];then echo "$i found" >>Matching_lines.txt;else echo "$i missing" >>missing_lines.txt ;fi;done