Szybki sposób znajdowania wierszy w jednym pliku, których nie ma w innym?


241

Mam dwa duże pliki (zestawy nazw plików). Około 30 000 linii w każdym pliku. Próbuję znaleźć szybki sposób znajdowania wierszy w pliku 1, które nie występują w pliku 2.

Na przykład, jeśli jest to plik1:

line1
line2
line3

A to jest plik2:

line1
line4
line5

Zatem mój wynik / wynik powinien wynosić:

line2
line3

To działa:

grep -v -f file2 file1

Ale jest bardzo, bardzo wolny, gdy jest używany na moich dużych plikach.

Podejrzewam, że jest dobry sposób na wykonanie tego za pomocą diff (), ale dane wyjściowe powinny być tylko liniami, niczym więcej, i nie mogę znaleźć przełącznika do tego.

Czy ktoś może mi pomóc znaleźć szybki sposób na zrobienie tego, używając bash i podstawowych plików binarnych z linuksem?

EDYCJA: Aby odpowiedzieć na moje pytanie, jest to najlepszy sposób, jaki do tej pory znalazłem za pomocą diff ():

diff file2 file1 | grep '^>' | sed 's/^>\ //'

Z pewnością musi być lepszy sposób?


1
możesz spróbować, jeśli jest szybszy:awk 'NR==FNR{a[$0];next}!($0 in a)' file2 file1 > out.txt
Kent


4
Dzięki za informację o grep -v -f plik2 plik1
Rahul Prasad


Prosty sposób ze zredukowanym zestawem narzędzi: cat file1 file2 file2 | sort | uniq --uniquepatrz moja odpowiedź poniżej.
Ondra Žižka,

Odpowiedzi:


233

Możesz to osiągnąć kontrolując formatowanie starych / nowych / niezmienionych linii w diffdanych wyjściowych GNU :

diff --new-line-format="" --unchanged-line-format=""  file1 file2

Pliki wejściowe należy posortować, aby to zadziałało. Za pomocą bash(i zsh) możesz sortować na miejscu z podstawieniem procesu <( ):

diff --new-line-format="" --unchanged-line-format="" <(sort file1) <(sort file2)

W powyższym nowym i niezmienionym wierszu są pomijane, więc wyprowadzane są tylko zmienione (tj. Usunięte linie w twoim przypadku). Można również skorzystać z kilku diffopcji, że inne rozwiązania nie oferują, takie jak -iignorowanie wielkości liter lub różne opcje whitespace ( -E, -b, -vetc) dla mniej ścisłe dopasowanie.


Wyjaśnienie

Opcje --new-line-format, --old-line-formati --unchanged-line-formatpozwalają kontrolować sposób diffformatuje różnice, podobne do printfformatu specyfikatorami. Te opcje formatują odpowiednio nowe (dodane), stare (usunięte) i niezmienione linie. Ustawienie pustego „” zapobiega wyjściu tego rodzaju linii.

Jeśli znasz zunifikowany format różnic , możesz go częściowo odtworzyć za pomocą:

diff --old-line-format="-%L" --unchanged-line-format=" %L" \
     --new-line-format="+%L" file1 file2

Specyfikatorem %Ljest linia, o której mowa, i każdy z nich poprzedza „+” „-” lub „”, podobnie jak diff -u (zauważ, że wyświetla tylko różnice, brakuje linii --- +++i @@na górze każdej zgrupowanej zmiany). Można również użyć tego robić inne przydatne rzeczy jak liczba każdej linii z %dn.


diffMetoda (wraz z innymi sugestiami commi join) produkują tylko oczekiwane wyjście z posortowanej wejścia, choć można użyć <(sort ...)do sortowania w miejscu. Oto prosty awk(nawk) skrypt (zainspirowany skryptami połączonymi w odpowiedzi Konsolebox), który akceptuje arbitralnie uporządkowane pliki wejściowe i wyświetla brakujące wiersze w kolejności, w jakiej występują w pliku1.

# 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]
}

To przechowuje całą zawartość pliku1 linia po linii w tablicy indeksowanej numerem wiersza ll1[]oraz całą zawartość pliku2 linia po linii w tablicy asocjacyjnej indeksowanej treści linii ss2[]. Po odczytaniu obu plików, iteruj ll1i użyj inoperatora, aby ustalić, czy wiersz w pliku 1 jest obecny w pliku 2. (Będzie to miało inny wynik niż diffmetoda, jeśli istnieją duplikaty).

W przypadku, gdy pliki są wystarczająco duże, aby ich przechowanie powodowało problem z pamięcią, możesz wymienić procesor na pamięć, przechowując tylko plik 1 i usuwając dopasowania podczas odczytu pliku 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]
}

Powyżej przechowuje całą zawartość pliku1 w dwóch tablicach, jedna indeksowana według numeru linii ll1[], druga indeksowana według zawartości linii ss1[]. Następnie, gdy plik2 jest czytany, każda pasująca linia jest usuwana z ll1[]i ss1[]. Na koniec wyprowadzane są pozostałe wiersze z pliku1, zachowując pierwotną kolejność.

W tym przypadku, przy opisanym problemie, możesz także dzielić i podbijać za pomocą GNU split(filtrowanie jest rozszerzeniem GNU), powtarzane przebiegi z fragmentami pliku 1 i całkowite czytanie pliku 2 za każdym razem:

split -l 20000 --filter='gawk -f linesnotin.awk - file2' < file1

Zwróć uwagę na użycie i umiejscowienie -znaczenia stdinw gawkwierszu poleceń. Zapewnia to splitplik file1 w porcjach po 20000 linii na wywołanie.

Dla użytkowników systemów innych niż GNU, to prawie na pewno coreutils GNU pakiet można uzyskać, w tym na OSX jako część firmy Apple Xcode narzędzi GNU, która przewiduje diff, awkchoć tylko POSIX / BSD splitzamiast wersji GNU.


1
To robi dokładnie to, czego potrzebuję, w niewielkim ułamku czasu ogromnego grepa. Dzięki!
Niels2000,

1
Znaleziono tę stronę gnu
Juto

niektórzy z nas nie są na GNU [OS X bsd tutaj ...] :)
rogerdpack

1
Zakładam, że masz na myśli diff: ogólnie pliki wejściowe będą inne, diffw tym przypadku zwracane jest 1 . Rozważ to jako bonus ;-) Jeśli testujesz w skrypcie powłoki 0 i 1 są oczekiwanymi kodami wyjścia, 2 oznacza problem.
mr.spuratic

1
@ mr.spuratic ah tak, teraz znajduję to w man diff. Dzięki!
Archeosudoerus

246

Polecenie comm (skrót od „common”) może być przydatnecomm - 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 

manPlik jest całkiem czytelny dla tego produktu.


6
Działa bezbłędnie na OSX.
pisaruk

41
Konieczne może być podkreślenie wymogu sortowania danych wejściowych.
tripleee

21
commma również opcję sprawdzenia, czy dane wejściowe są posortowane --check-order(co wydaje się tak czynić, ale ta opcja spowoduje błąd zamiast kontynuować). Ale aby posortować pliki, po prostu zrób: com -23 <(sort file1) <(sort file2)i tak dalej
Michael

Porównywałem plik wygenerowany w systemie Windows z plikiem wygenerowanym w systemie Linux i wydawało się, że commw ogóle nie działa. Dopiero po chwili zrozumiałem, że chodzi o zakończenia linii: nawet linie wyglądające identycznie są uważane za różne, jeśli mają różne zakończenia linii. Polecenia dos2unixmożna użyć do konwersji zakończeń linii CRLF tylko na LF.
ZeroOne

23

Jak sugeruje konsolebox, rozwiązanie grep dla plakatów

grep -v -f file2 file1

faktycznie działa świetnie (szybko), jeśli po prostu dodasz -Fopcję, aby traktować wzorce jako stałe ciągi zamiast wyrażeń regularnych. Sprawdziłem to na parze ~ 1000 list plików linii, które musiałem porównać. Z -Ftym zajęło 0,031 s (rzeczywiste), podczas gdy bez zabrało 2,278 s (rzeczywiste), gdy przekierowanie wyjścia grep do wc -l.

Testy te obejmowały także -xprzełącznik, który jest niezbędną częścią rozwiązania w celu zapewnienia całkowitej dokładności w przypadkach, gdy plik2 zawiera wiersze, które pasują do części, ale nie wszystkich, jednego lub więcej wierszy w pliku1.

Tak więc rozwiązaniem, które nie wymaga sortowania danych wejściowych, jest szybkie, elastyczne (rozróżnianie wielkości liter itp.) To:

grep -F -x -v -f file2 file1

Nie działa to ze wszystkimi wersjami grep, na przykład nie działa w systemie macOS, gdzie linia w pliku 1 będzie pokazana jako nieobecna w pliku 2, nawet jeśli tak jest, jeśli pasuje do innej linii, która jest jego podciągiem . Alternatywnie możesz zainstalować GNU grep na macOS , aby skorzystać z tego rozwiązania.


Tak, działa, ale nawet przy -Ftym nie skaluje się dobrze.
Molomby

to nie jest tak szybkie, czekałem 5 minut na 2 pliki ~ 500 tys. linii, zanim się
poddałem

w rzeczywistości ta droga jest nadal wolniejsza niż komunikacja, ponieważ można obsługiwać nieposortowane pliki, dlatego przeciągnięto ją w dół przez sortowanie, comm korzysta z sortowania
workplaylifecycle

@workplaylifecycle Musisz dodać czas na sortowanie, co może być wąskim gardłem w przypadku bardzo dużych file2.
rwst

Jednak grep z -xopcją najwyraźniej zużywa więcej pamięci. Z file2zawierających 180M słów 6-10 bajtów mój proces dostał Killedna maszynie RAM 32GB ...
rwst

11

jaka jest prędkość sortowania i porównywania?

sort file1 -u > file1.sorted
sort file2 -u > file2.sorted
diff file1.sorted file2.sorted

1
Dzięki za przypomnienie mi o potrzebie sortowania plików przed zrobieniem różnic. sort + diff jest DUŻO szybszy.
Niels2000,

4
one liner ;-) diff <(sort file1 -u) <(sort file2 -u)
steveinatorx 13.09.16

11

Jeśli masz mało „narzędzi fantazyjnych”, na przykład w pewnym minimalnym dystrybucji Linuksa, istnieje rozwiązanie z właśnie cat, sorti uniq:

cat includes.txt excludes.txt excludes.txt | sort | uniq --unique

Test:

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    

Jest to również stosunkowo szybkie w porównaniu do grep.


1
Uwaga - niektóre implementacje nie rozpoznają tej --uniqueopcji. Powinieneś być w stanie użyć standardowej opcji POSIX do tego:| uniq -u
AndrewF

1
W tym przykładzie, skąd pochodzi „2”?
Niels2000,

1
@ Niels2000, seq 1 1 7tworzy liczby od 1, z przyrostem 1, do 7, tj. 1 2 3 4 5 6 7. I właśnie są twoje 2!
Eirik Lygre

5
$ join -v 1 -t '' file1 file2
line2
line3

-tPilnuje, że porównuje całą linię, jeśli miał miejsce w niektórych liniach.


Podobnie comm, joinwymaga posortowania obu linii wejściowych w polu, w którym wykonuje się operację łączenia.
tripleee

4

Możesz użyć Pythona:

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())
'

4

Korzystać combinez moreutilspakietu, narzędzie, które obsługuje zestawy not, and, or, xoroperacje

combine file1 not file2

tzn. podaj mi wiersze, które są w pliku 1, ale nie w pliku 2

LUB podaj mi linie w pliku 1 minus linie w pliku 2

Uwaga: combine sortuje i wyszukuje unikalne linie w obu plikach przed wykonaniem jakiejkolwiek operacji, ale diffnie robi tego. Więc możesz znaleźć różnice między danymi wyjściowymi diffa combine.

Więc w rzeczywistości mówisz

Znajdź różne linie w pliku 1 i 2, a następnie podaj mi linie w pliku 1 minus linie w pliku 2

Z mojego doświadczenia wynika, że ​​jest znacznie szybszy niż inne opcje


2

Pomocne może być użycie fgrep lub dodanie opcji -F do grep. Ale do szybszych obliczeń możesz użyć Awk.

Możesz wypróbować jedną z następujących metod Awk:

http://www.linuxquestions.org/questions/programming-9/grep-for-huge-files-826030/#post4066219


2
+1 To jedyna odpowiedź, która nie wymaga sortowania danych wejściowych. Chociaż najwyraźniej OP był zadowolony z tego wymogu, jest to niedopuszczalne ograniczenie w wielu rzeczywistych scenariuszach.
tripleee

1

Zwykle robię to przy użyciu --suppress-common-linesflagi, ale pamiętaj, że działa to tylko wtedy, gdy robisz to w formacie side-by-side.

diff -y --suppress-common-lines file1.txt file2.txt


0

Przekonałem się, że użycie normalnej instrukcji if i for loop działało idealnie.

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

2
Zobacz DontReadLinesWithFor . Ponadto ten kod będzie zachowywał się bardzo źle, jeśli którykolwiek z grepwyników zostanie rozwinięty do wielu słów lub jeśli którykolwiek z twoich file2wpisów może być traktowany przez powłokę jako glob.
Charles Duffy,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.