Schnelle Möglichkeit, Zeilen in einer Datei zu finden, die sich nicht in einer anderen befinden?

241

Ich habe zwei große Dateien (Sätze von Dateinamen). Etwa 30.000 Zeilen in jeder Datei. Ich versuche einen schnellen Weg zu finden, um Zeilen in Datei1 zu finden, die in Datei2 nicht vorhanden sind.

Wenn dies beispielsweise Datei1 ist:

line1
line2
line3

Und das ist Datei2:

line1
line4
line5

Dann sollte mein Ergebnis / meine Ausgabe sein:

line2
line3

Das funktioniert:

grep -v -f file2 file1

Aber es ist sehr, sehr langsam, wenn es für meine großen Dateien verwendet wird.

Ich vermute, dass es einen guten Weg gibt, dies mit diff () zu tun, aber die Ausgabe sollte nur die Zeilen sein, sonst nichts, und ich kann keinen Schalter dafür finden.

Kann mir jemand helfen, einen schnellen Weg zu finden, indem ich Bash- und grundlegende Linux-Binärdateien verwende?

EDIT: Um meine eigene Frage zu beantworten, ist dies der beste Weg, den ich bisher mit diff () gefunden habe:

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

Sicherlich muss es einen besseren Weg geben?

Niels2000
quelle
1
Sie könnten dies versuchen, wenn es schneller ist:awk 'NR==FNR{a[$0];next}!($0 in a)' file2 file1 > out.txt
Kent
ohne schnelle Anforderung: stackoverflow.com/questions/4366533/…
Ciro Santilli 法轮功 冠状 病 六四 事件 27
4
Vielen Dank für erzählen über grep -v -f Datei2 Datei1
Rahul Prasad
Einfacher Weg mit reduziertem Werkzeugsatz: cat file1 file2 file2 | sort | uniq --uniquesiehe meine Antwort unten.
Ondra Žižka

Antworten:

233

Sie können dies erreichen, indem Sie die Formatierung der alten / neuen / unveränderten Zeilen in der GNU- diffAusgabe steuern :

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

Die Eingabedateien sollten sortiert sein, damit dies funktioniert. Mit bash(und zsh) können Sie direkt mit der Prozessersetzung sortieren <( ):

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

In den obigen Abschnitten werden neue und unveränderte Zeilen unterdrückt, sodass nur geänderte (in Ihrem Fall entfernte Zeilen) ausgegeben werden. Sie können auch ein paar verwenden diffOptionen , die anderen Lösungen nicht bieten, wie -iFall zu ignorieren, oder verschiedene Leerzeichen Optionen ( -E, -b, -vusw.) für weniger strenges Matching.


Erläuterung

Die Optionen --new-line-format, --old-line-formatund --unchanged-line-formatlassen Sie die Art und Weise steuern , diffformatiert die Unterschiede ähnlich printfFormatbezeichner. Diese Optionen formatieren neue (hinzugefügte), alte (entfernte) bzw. unveränderte Zeilen. Wenn Sie "leer" setzen, wird die Ausgabe dieser Art von Zeile verhindert.

Wenn Sie mit dem einheitlichen Diff- Format vertraut sind , können Sie es teilweise neu erstellen mit:

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

Der %LBezeichner ist die betreffende Zeile, und wir stellen jeweils "+" "-" oder "" voran diff -u (beachten Sie, dass nur Unterschiede ausgegeben werden --- +++und die @@Zeilen und oben bei jeder gruppierten Änderung fehlen ). Sie können dies auch verwenden, um andere nützliche Dinge zu tun, z. B. die Nummerierung jeder Zeile mit %dn.


Die diffMethode (zusammen mit anderen Vorschlägen commund join) erzeugt nur die erwartete Ausgabe mit sortierter Eingabe, obwohl Sie sie <(sort ...)zum Sortieren verwenden können. Hier ist ein einfaches awk(nawk) Skript (inspiriert von den in Konsoleboxs Antwort verknüpften Skripten), das willkürlich geordnete Eingabedateien akzeptiert und die fehlenden Zeilen in der Reihenfolge ausgibt, in der sie in Datei1 vorkommen.

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

Dies speichert den gesamten Inhalt von Datei1 Zeile für Zeile in einem Zeilennummern-indizierten Array ll1[]und den gesamten Inhalt von Datei2 Zeile für Zeile in einem Zeileninhalt-indizierten assoziativen Array ss2[]. Nachdem beide Dateien gelesen wurden, wiederholen Sie den Vorgang ll1und verwenden Sie den inOperator, um festzustellen, ob die Zeile in Datei1 in Datei2 vorhanden ist. (Dies hat eine andere Ausgabe als die diffMethode, wenn Duplikate vorhanden sind.)

Für den Fall, dass die Dateien so groß sind, dass das Speichern beider Dateien ein Speicherproblem verursacht, können Sie die CPU gegen Speicher tauschen, indem Sie nur Datei1 speichern und Übereinstimmungen während des Lesens von Datei2 löschen.

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

Oben wird der gesamte Inhalt von Datei1 in zwei Arrays gespeichert, von denen eines nach Zeilennummer ll1[]und eines nach Zeileninhalt indiziert ist ss1[]. Beim Lesen von Datei2 wird dann jede übereinstimmende Zeile aus ll1[]und gelöscht ss1[]. Am Ende werden die verbleibenden Zeilen aus Datei1 ausgegeben, wobei die ursprüngliche Reihenfolge beibehalten wird.

In diesem Fall können Sie mit dem angegebenen Problem auch mithilfe von GNU (Filterung ist eine GNU-Erweiterung) teilen und siegensplit , wiederholte Läufe mit Blöcken von Datei1 ausführen und Datei2 jedes Mal vollständig lesen:

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

Beachten Sie die Verwendung und Platzierung der -Bedeutung stdinin der gawkBefehlszeile. Dies wird von splitaus Datei1 in Blöcken von 20000 Zeilen pro Aufruf bereitgestellt .

Für Benutzer auf nicht-GNU - Systemen gibt an Sicherheit grenzender Wahrscheinlichkeit ist ein GNU coreutils Paket , das Sie erhalten, auf OSX auch im Rahmen der Apple - Xcode - Tool , das GNU bietet diff, awkallerdings nur ein POSIX / BSD spliteher als eine GNU - Version.

mr.spuratic
quelle
1
Dies macht genau das, was ich brauche, in einem winzigen Bruchteil der Zeit, die der enorme Grep benötigt. Vielen Dank!
Niels2000
1
Fand diese Gnu Manpage
Juto
einige von uns sind nicht auf gnu [OS X bsd hier ...] :)
Rogerdpack
1
Ich nehme an, Sie meinen für diff: Im Allgemeinen sind die Eingabedateien unterschiedlich, 1 wird diffin diesem Fall von zurückgegeben. Betrachten Sie es als Bonus ;-) Wenn Sie in einem Shell-Skript testen, werden 0 und 1 Exit-Codes erwartet, 2 weist auf ein Problem hin.
mr.spuratic
1
@ mr.spuratic ah yeah, jetzt finde ich es in der man diff. Vielen Dank!
Archeosudoerus
242

Der Befehl comm (kurz für "common") kann nützlich seincomm - 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 

Die manDatei ist dafür eigentlich gut lesbar.

JnBrymn
quelle
6
Funktioniert einwandfrei unter OSX.
Pisaruk
40
Die Anforderung für sortierte Eingaben sollte möglicherweise hervorgehoben werden.
Tripleee
20
commhat auch eine Option, um zu überprüfen, ob die Eingabe sortiert ist --check-order(was anscheinend trotzdem der Fall ist, aber diese Option führt zu einem Fehler, anstatt fortzufahren). Aber um die Dateien zu sortieren, machen Sie einfach: com -23 <(sort file1) <(sort file2)und so weiter
Michael
Ich habe eine in Windows generierte Datei mit einer unter Linux generierten Datei verglichen und es schien, commals würde sie überhaupt nicht funktionieren. Ich habe eine Weile gebraucht, um herauszufinden, dass es um die Zeilenenden geht: Selbst Zeilen, die identisch aussehen, werden als unterschiedlich angesehen, wenn sie unterschiedliche Zeilenenden haben. Der Befehl dos2unixkann verwendet werden, um die CRLF-Zeilenenden nur in LF zu konvertieren.
ZeroOne
23

Wie konsolebox vorgeschlagen hat, ist die Poster-Grep-Lösung

grep -v -f file2 file1

funktioniert wirklich gut (schnell), wenn Sie einfach die -FOption hinzufügen , die Muster als feste Zeichenfolgen anstelle von regulären Ausdrücken zu behandeln. Ich habe dies anhand von ~ 1000 Zeilendateilisten überprüft, die ich vergleichen musste. Mit -Fes dauerte 0,031 s (real), während es ohne 2,278 s (real) dauerte, wenn die grep-Ausgabe auf umgeleitet wurde wc -l.

Diese Tests umfassten auch den -xSchalter, der Teil der Lösung ist, um die vollständige Genauigkeit in Fällen sicherzustellen, in denen Datei2 Zeilen enthält, die mit einem Teil, aber nicht allen einer oder mehreren Zeilen in Datei1 übereinstimmen.

Eine Lösung, bei der die Eingaben nicht sortiert werden müssen, ist schnell und flexibel (Groß- / Kleinschreibung usw.):

grep -F -x -v -f file2 file1

Dies funktioniert nicht mit allen Versionen von grep, z. B. schlägt es unter macOS fehl, wo eine Zeile in Datei 1 als nicht in Datei 2 vorhanden angezeigt wird, obwohl dies der Fall ist, wenn sie mit einer anderen Zeile übereinstimmt, die eine Teilzeichenfolge davon ist . Alternativ können Sie GNU grep unter macOS installieren , um diese Lösung zu verwenden.

pbz
quelle
Ja, es funktioniert, aber selbst -Fdamit lässt sich nicht gut skalieren.
Molomby
das ist nicht so schnell, ich habe 5 Minuten auf 2 Dateien mit ~ 500k Zeilen gewartet, bevor ich aufgegeben habe
cahen
Tatsächlich ist dieser Weg immer noch langsamer als der Kommunikationsweg, da dieser mit unsortierten Dateien umgehen kann, die durch Unsortierung nach unten gezogen werden. Comm nutzt den Vorteil der Sortierung
Workplaylifecycle
@workplaylifecycle Sie müssen die Zeit für das Sortieren hinzufügen, was der Engpass für extrem große sein kann file2.
1.
Grep mit der -xOption verwendet jedoch anscheinend mehr Speicher. Mit file2180M Wörtern von 6-10 Bytes wurde mein Prozess Killedauf einem 32 GB RAM-Computer ausgeführt ...
1.
11

Was ist die Geschwindigkeit als sort und diff?

sort file1 -u > file1.sorted
sort file2 -u > file2.sorted
diff file1.sorted file2.sorted
Puggan Se
quelle
1
Vielen Dank, dass Sie mich daran erinnert haben, dass Sie die Dateien sortieren müssen, bevor Sie diff ausführen. sort + diff ist VIEL schneller.
Niels2000
4
ein Liner ;-) diff <(sort file1 -u) <(sort file2 -u)
steveinatorx
11

Wenn Sie wenig „fancy Werkzeuge“ sind, zB in einem gewissen minimalen Linux - Distribution, gibt es eine Lösung mit nur cat, sortund uniq:

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

Prüfung:

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    

Dies ist auch relativ schnell im Vergleich zu grep.

Ondra Žižka
quelle
1
Hinweis - Einige Implementierungen erkennen die --uniqueOption nicht. Sie sollten in der Lage sein, die standardisierte POSIX-Option für diese zu verwenden:| uniq -u
AndrewF
1
Woher kam im Beispiel die "2"?
Niels2000
1
@ Niels2000, seq 1 1 7erstellt Zahlen von 1 mit Inkrement 1 bis 7, dh 1 2 3 4 5 6 7. Und genau da ist Ihre 2!
Eirik Lygre
5
$ join -v 1 -t '' file1 file2
line2
line3

Das -tstellt sicher, dass die gesamte Zeile verglichen wird, wenn Sie in einigen Zeilen ein Leerzeichen hatten.

Steven Penny
quelle
Wie comm, joinerfordern beide Eingangsleitungen auf dem Feld sortiert werden Sie die auf Join - Operation durchführen.
Tripleee
4

Sie können Python verwenden:

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())
'
Hallo Auf Wiedersehen
quelle
4

Verwenden combinevon moreutilsPaket, ein Dienstprogramm , das Satz Stützen not, and, or, xorOperationen

combine file1 not file2

dh gib mir Zeilen, die in Datei1, aber nicht in Datei2 sind

ODER geben Sie mir Zeilen in Datei1 minus Zeilen in Datei2

Hinweis: combine Sortiert und findet eindeutige Zeilen in beiden Dateien, bevor eine Operation ausgeführt wird, dies diffjedoch nicht. Sie können also Unterschiede zwischen der Ausgabe von diffund feststellen combine.

Tatsächlich sagen Sie also

Suchen Sie unterschiedliche Zeilen in Datei1 und Datei2 und geben Sie mir dann Zeilen in Datei1 minus Zeilen in Datei2

Nach meiner Erfahrung ist es viel schneller als andere Optionen

GypsyCosmonaut
quelle
2

Die Verwendung von fgrep oder das Hinzufügen der Option -F zu grep könnte helfen. Für schnellere Berechnungen können Sie jedoch Awk verwenden.

Sie können eine dieser Awk-Methoden ausprobieren:

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

konsolebox
quelle
2
+1 Dies ist die einzige Antwort, bei der keine Eingaben sortiert werden müssen. Während das OP anscheinend mit dieser Anforderung zufrieden war, ist dies in vielen realen Szenarien eine inakzeptable Einschränkung.
Tripleee
1

Normalerweise verwende ich das --suppress-common-linesFlag. Beachten Sie jedoch, dass dies nur funktioniert, wenn Sie es im Side-by-Side-Format ausführen.

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

BAustin
quelle
0

Ich fand, dass für mich die Verwendung einer normalen if- und for-Schleifenanweisung perfekt funktionierte.

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
Tman
quelle
2
Siehe DontReadLinesWithFor . Außerdem verhält sich dieser Code sehr schlecht, wenn eines Ihrer grepErgebnisse auf mehrere Wörter erweitert wird oder wenn einer Ihrer file2Einträge von der Shell als Glob behandelt werden kann.
Charles Duffy