385 Stimmen

Schneller Weg, um Zeilen in einer Datei zu finden, die in einer anderen nicht vorhanden sind?

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

Zum Beispiel, wenn dies Datei1 ist:

Zeile1
Zeile2
Zeile3

Und das ist Datei2:

Zeile1
Zeile4
Zeile5

Dann sollte mein Ergebnis/Ausgabe sein:

Zeile2
Zeile3

Dies funktioniert:

grep -v -f file2 file1

Aber es ist sehr, sehr langsam, wenn es auf meine großen Dateien angewendet wird.

Ich vermute, es gibt eine gute Möglichkeit, dies mit diff() zu tun, aber die Ausgabe sollte nur die Zeilen sein, nichts anderes, und ich kann keinen Schalter dafür finden.

Kann mir jemand helfen, einen schnellen Weg zu finden, dies zu tun, unter Verwendung von Bash und grundlegenden Linux-Binärdateien?

BEARBEITEN: Um auf meine eigene Frage einzugehen, dies ist der beste Weg, den ich bisher gefunden habe, um diff() zu verwenden:

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

Sicherlich muss es einen besseren Weg geben?

442voto

JnBrymn Punkte 22642

Der comm Befehl (kurz für "common") kann nützlich sein comm - zwei sortierte Dateien Zeile für Zeile vergleichen

# Finde Zeilen nur in Datei1
comm -23 Datei1 Datei2 

# Finde Zeilen nur in Datei2
comm -13 Datei1 Datei2 

# Finde Zeilen, die in beiden Dateien gemeinsam sind
comm -12 Datei1 Datei2 

Die man Datei ist tatsächlich recht lesbar dafür.

293voto

mr.spuratic Punkte 9437

Dies ist möglich, indem die Formatierung der alten/neuen/unchanged Zeilen im GNU diff Output kontrolliert wird:

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

Die Eingabedateien müssen sortiert sein, damit dies funktioniert. Mit bash (und zsh) kann man mit Prozess-Substitution <( ) direkt sortieren:

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

In den obigen neuen und unchanged Zeilen werden unterdrückt, so dass nur geänderte (d.h. entfernte Zeilen in Ihrem Fall) ausgegeben werden. Sie können auch ein paar diff Optionen nutzen, die von anderen Lösungen nicht angeboten werden, wie z.B. -i um Groß- und Kleinschreibung zu ignorieren, oder verschiedene Whitespace-Optionen (-E, -b, -v etc) für weniger striktes Matching.


Erklärung

Die Optionen --new-line-format, --old-line-format und --unchanged-line-format ermöglichen es, die Art und Weise zu kontrollieren, wie diff die Unterschiede formatiert, ähnlich wie bei printf Format-Spezifiern. Diese Optionen formatieren jeweils neue (hinzugefügte), alte (entfernte) und unchanged Zeilen. Durch das Setzen auf leer "" wird die Ausgabe dieser Art von Zeile verhindert.

Falls Sie mit dem vereinigten Diff Format vertraut sind, können Sie es teilweise mit folgendem Befehl rekonstruieren:

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

Der %L Spezifizierer ist die Zeile in Frage, und wir ergänzen jedes mit "+" "-" oder " ", wie bei diff -u (beachten Sie, dass es nur Unterschiede ausgibt, es fehlen die ---, +++ und @@ Zeilen oben bei jeder zusammengefassten Änderung). Damit können Sie auch andere nützliche Dinge tun, wie zum Beispiel jede Zeile nummerieren mit %dn.


Die diff Methode (zusammen mit anderen Vorschlägen comm und join) gibt nur die erwartete Ausgabe mit sortierten Eingaben, obwohl Sie <(sort ...) verwenden können um direkt zu sortieren. Hier ist ein einfaches awk (nawk) Skript (inspiriert von den Skripten in Konsolebox's Antwort), das beliebig sortierte Eingabedateien akzeptiert, und die fehlenden Zeilen in der Reihenfolge ausgibt, in der sie in file1 auftreten.

# gib Zeilen in file1 aus, die nicht in file2 sind
BEGIN { FS="" }                         # Erhalte Whitespace
(NR==FNR) { ll1[FNR]=$0; nl1=FNR; }     # Datei1, indiziert nach Zeilennummer
(NR!=FNR) { ss2[$0]++; }                # Datei2, indiziert nach String
END {
    for (ll=1; ll<=nl1; ll++) if (!(ll1[ll] in ss2)) print ll1[ll]
}

Dieses Skript speichert die gesamten Inhalte von file1 zeilenweise in einem Array mit Index der Zeilennummer ll1[], und die gesamten Inhalte von file2 zeilenweise in einem assoziativen Array indiziert nach Zeileninhalt ss2[]. Nachdem beide Dateien eingelesen sind, wird über ll1 iteriert und der in Operator verwendet, um festzustellen, ob die Zeile in file1 in file2 vorhanden ist. (Dies führt zu einem anderen Ergebnis als die diff Methode, wenn es Duplikate gibt.)

Falls die Dateien groß genug sind, dass das Speichern beider Dateien ein Speicherproblem verursacht, können Sie CPU gegen Speicher handeln, indem Sie nur file1 speichern und übereinstimmungen löschen, während file2 eingelesen wird.

BEGIN { FS="" }
(NR==FNR) {  # Datei1, indiziert nach Zeilennummer und String
  ll1[FNR]=$0; ss1[$0]=FNR; nl1=FNR;
}
(NR!=FNR) {  # Datei2
  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]
}

Obiges speichert die gesamten Inhalte von file1 in zwei Arrays, eins indiziert nach Zeilennummer ll1[], eins indiziert nach Zeileninhalt ss1[]. Dann werden beim Einlesen von file2 die übereinstimmenden Zeilen aus ll1[] und ss1[] gelöscht. Am Ende werden die verbleibenden Zeilen aus file1 ausgegeben, wobei die ursprüngliche Reihenfolge beibehalten wird.

In diesem Fall, mit dem genannten Problem, können Sie auch teilen und erobern mit GNU split (Filterung ist eine GNU-Erweiterung), wiederholten Durchläufen mit Dateichunks von file1 und jedes Mal file2 komplett einlesen:

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

Beachten Sie die Verwendung und Platzierung von - was auf stdin auf der gawk Befehlszeile hinweist. Dies wird von split von file1 in Chunks von 20000 Zeilen pro Aufruf bereitgestellt.

Für Benutzer auf nicht-GNU-Systemen gibt es fast sicher ein GNU Coreutils-Paket, das Sie erhalten können, einschließlich auf OSX als Teil der Apple Xcode Tools, die GNU diff und awk bereitstellen, jedoch nur eine POSIX/BSD split Version anstelle einer GNU Version.

49voto

pbz Punkte 699

Wie konsolebox vorgeschlagen hat, die Lösung seines Posters

grep -v -f file2 file1

funktioniert tatsächlich großartig (schneller), wenn Sie einfach die -F Option hinzufügen, um die Muster als feste Zeichenfolgen anstelle von regulären Ausdrücken zu behandeln. Ich habe dies mit einem Paar von ~1000 Zeilen langen Dateilisten überprüft, die ich vergleichen musste. Mit -F dauerte es 0,031 s (real), während es ohne 2,278 s (real) dauerte, als ich die grep-Ausgabe nach wc -l umleitete.

Diese Tests beinhalteten auch den -x Schalter, der ein notwendiger Bestandteil der Lösung ist, um eine völlige Genauigkeit in Fällen sicherzustellen, in denen file2 Zeilen enthält, die Teile von, aber nicht alle von, einer oder mehreren Zeilen in file1 entsprechen.

Also eine Lösung, die keine sortierten Eingaben erfordert, schnell und flexibel (Groß-/Kleinschreibung, usw.) ist:

grep -F -x -v -f file2 file1

Dies funktioniert nicht mit allen Versionen von grep, zum Beispiel scheitert es in macOS, wo eine Zeile in Datei 1 angezeigt wird als nicht in Datei 2 vorhanden, auch wenn sie es ist, wenn sie mit einer anderen Zeile übereinstimmt, die eine Teilzeichenfolge davon ist. Alternativ können Sie GNU grep auf macOS installieren, um diese Lösung zu verwenden.

26voto

Ondra Žižka Punkte 39898

Wenn Ihnen "fancy tools" fehlen, z. B. in einer minimalen Linux-Distribution, gibt es eine Lösung mit nur cat, sort und 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

# Ausgabe:
1
2    

Dies ist auch relativ schnell im Vergleich zu grep.

17voto

GypsyCosmonaut Punkte 499

Verwenden Sie combine aus dem Paket moreutils, ein Sets-Dienstprogramm, das not, and, or, xor Operationen unterstützt

combine datei1 not datei2

d.h. gib mir Zeilen, die in datei1, aber nicht in datei2 sind

ODER gib mir Zeilen in datei1 abzüglich Zeilen in datei2

Hinweis: combine sortiert und findet eindeutige Zeilen in beiden Dateien, bevor es irgendwelche Operationen durchführt, aber diff tut das nicht. Daher können Unterschiede zwischen der Ausgabe von diff und combine auftreten.

Also sagen Sie im Grunde genommen

Finde unterschiedliche Zeilen in datei1 und datei2 und gib mir dann die Zeilen in datei1 abzüglich Zeilen in datei2

In meiner Erfahrung ist es viel schneller als andere Optionen

CodeJaeger.com

CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.

Powered by:

X