Wie finde ich doppelte Zeilen in vielen großen Dateien?

8

Ich habe ~ 30k Dateien. Jede Datei enthält ~ 100.000 Zeilen. Eine Zeile enthält keine Leerzeichen. Die Zeilen innerhalb einer einzelnen Datei werden sortiert und frei dupliziert.

Mein Ziel: Ich möchte alle doppelten Zeilen in zwei oder mehr Dateien sowie die Namen der Dateien finden, die doppelte Einträge enthalten.

Eine einfache Lösung wäre folgende:

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

Und dann würde ich rennen:

grep 'duplicated entry' *.words

Sehen Sie einen effizienteren Weg?

Lars Schneider
quelle

Antworten:

12

Da alle Eingabedateien bereits sortiert sind, können wir den eigentlichen Sortierschritt umgehen und nur sort -mzum Zusammenführen der Dateien verwenden.

Auf einigen Unix-Systemen (meines Wissens nur unter Linux) kann dies ausreichen

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

um die duplizierten Zeilen in die Datei zu schreiben dupes.txt.

Um herauszufinden, aus welchen Dateien diese Zeilen stammen, können Sie dies tun

grep -Fx -f dupes.txt *.words

Dadurch wird angewiesen grep, die Zeilen in dupes.txt( -f dupes.txt) als feste Zeichenfolgenmuster ( -F) zu behandeln. greperfordert auch, dass die gesamte Linie von Anfang bis Ende perfekt übereinstimmt ( -x). Der Dateiname und die Zeile zum Terminal werden gedruckt.

Nicht-Linux-Unices (oder noch mehr Dateien)

Auf einigen Unix-Systemen werden 30000 Dateinamen zu einer Zeichenfolge erweitert, die zu lang ist, um an ein einzelnes Dienstprogramm übergeben zu werden (was bedeutet , dass dies bei meinem OpenBSD-System sort -m *.wordsfehlschlägt Argument list too long). Sogar Linux wird sich darüber beschweren, wenn die Anzahl der Dateien viel größer ist.

Die Dupes finden

Dies bedeutet, dass im allgemeinen Fall (dies funktioniert auch mit viel mehr als nur 30000 Dateien) die Sortierung "aufgeteilt" werden muss:

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 

Alternativ können Sie erstellen tmpfileohne 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 {} +

Dadurch werden alle Dateien im aktuellen Verzeichnis (oder darunter) gefunden, deren Namen übereinstimmen *.words. Für einen Teil dieser Namen mit angemessener Größe, dessen Größe durch xargs/ bestimmt wird find, werden sie in der sortierten tmpfileDatei zusammengeführt. Wenn tmpfilebereits vorhanden (für alle außer dem ersten Block), wird diese Datei auch mit den anderen Dateien im aktuellen Block zusammengeführt. Abhängig von der Länge Ihrer Dateinamen und der maximal zulässigen Länge einer Befehlszeile sind möglicherweise mehr oder mehr als 10 einzelne Ausführungen des internen Skripts erforderlich ( find/ xargswird dies automatisch tun).

Das "interne" shSkript,

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

wird verwendet, sort -o tmpfileum auszugeben tmpfile(dies wird nicht überschrieben, tmpfileauch wenn dies auch eine Eingabe ist sort) und -mum die Zusammenführung durchzuführen. "$@"Wird in beiden Zweigen zu einer Liste von einzeln zitierten Dateinamen erweitert, die von findoder an das Skript übergeben werden xargs.

Führen Sie dann einfach uniq -dweiter tmpfile, um alle Zeilen zu erhalten, die dupliziert wurden:

uniq -d tmpfile >dupes.txt

Wenn Ihnen das "DRY" -Prinzip ("Don't Repeat Yourself") gefällt, können Sie das interne Skript als schreiben

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

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

oder

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

Wo kommst du her?

Aus den gleichen Gründen wie oben können wir nicht grep -Fx -f dupes.txt *.wordsermitteln, woher diese Duplikate stammen. Stattdessen verwenden wir finderneut:

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

Da keine "komplizierte" Verarbeitung erforderlich ist, können wir grepdirekt von aufrufen -exec. Die -execOption verwendet einen Dienstprogrammbefehl und platziert die gefundenen Namen in {}. Mit +am Ende findwerden {}bei jedem Aufruf des Dienstprogramms so viele Argumente anstelle der aktuellen Shell platziert.

Um ganz richtig zu sein, kann man beides verwenden

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

oder

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

um sicherzugehen, dass Dateinamen immer in der Ausgabe von enthalten sind grep.

Die erste Variante verwendet, grep -Hum immer übereinstimmende Dateinamen auszugeben. Die letzte Variante verwendet die Tatsache, dass grepder Name der übereinstimmenden Datei enthalten ist, wenn mehr als eine Datei in der Befehlszeile angegeben ist.

Dies ist wichtig, da der letzte Teil der Dateinamen, an die grepvon gesendet wird, findmöglicherweise nur einen einzigen Dateinamen enthält. In diesem Fall wird greper in den Ergebnissen nicht erwähnt.


Bonusmaterial:

Zerlegen des find+ xargs+ shBefehls:

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'generiert einfach eine Liste von Pfadnamen aus dem aktuellen Verzeichnis (oder darunter), wobei jeder Pfadname der einer regulären Datei ( -type f) ist und am Ende eine passende Dateinamenkomponente vorhanden ist *.words. Wenn nur das aktuelle Verzeichnis durchsucht werden soll, kann man -maxdepth 1nach dem ., vor hinzufügen -type f.

-print0stellt sicher, dass alle gefundenen Pfadnamen mit einem \0( nul) Zeichen als Trennzeichen ausgegeben werden . Dies ist ein Zeichen, das in einem Unix-Pfad nicht gültig ist, und es ermöglicht uns, Pfadnamen zu verarbeiten, selbst wenn sie Zeilenumbruchzeichen (oder andere seltsame Dinge) enthalten.

findleitet seine Ausgabe an xargs.

xargs -0liest die durch \0-begrenzte Liste von Pfadnamen und führt das angegebene Dienstprogramm wiederholt mit Teilen davon aus, um sicherzustellen, dass das Dienstprogramm mit gerade genug Argumenten ausgeführt wird, damit sich die Shell nicht über eine zu lange Argumentliste beschwert, bis keine Eingabe mehr erfolgt von find.

Das Dienstprogramm aufgerufen , indem xargsist shmit einem Skript in der Befehlszeile als String gegeben unter Verwendung seiner -cFlagge.

Beim Aufrufen sh -c '...some script...'mit folgenden Argumenten stehen die Argumente dem Skript in zur Verfügung $@, mit Ausnahme des ersten Arguments , in das eingefügt wird $0(dies ist der "Befehlsname", den Sie möglicherweise finden, z. B. topwenn Sie schnell genug sind). Aus diesem Grund fügen wir die Zeichenfolge shals erstes Argument nach dem Ende des eigentlichen Skripts ein. Die Zeichenfolge shist ein Dummy-Argument und kann ein einzelnes Wort sein (einige scheinen dies zu bevorzugen _oder sh-find).

Kusalananda
quelle
Wozu dient am Ende Ihres ersten Blocks eines Shell-Skripts fi' sh?
Dan
@danielAzuelos Das fiist das Ende der ifAnweisung im "internen" shShell-Skript. Das 'Ende dieses Shell-Skripts (das gesamte Skript ist eine einfach zitierte Zeichenfolge). Das shwird an das interne Skript in übergeben $0(nicht Teil von $@, das die Dateinamen enthält). In diesem Fall kann diese shZeichenfolge tatsächlich ein beliebiges Wort sein. Wenn sham Ende weggelassen wird, wird der erste Dateiname übergeben $0und ist nicht Teil der Verarbeitung, die das interne Shell-Skript ausführt.
Kusalananda
8

Die Zeilen innerhalb einer einzelnen Datei werden sortiert und frei dupliziert.

Was bedeutet, dass Sie wahrscheinlich eine Verwendung finden für sort -m:

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

Die andere offensichtliche Alternative dazu wäre awk, die Zeilen in einem Array einfach zu sammeln und zu zählen. Aber wie @ dave_thompson_085 kommentierte, würden diese 3 000 Millionen Zeilen (oder wie viele eindeutige es auch gibt) wahrscheinlich eine beträchtliche Menge an Speicher zum Speichern benötigen , so dass dies möglicherweise nicht sehr gut funktioniert.

ilkkachu
quelle
3

Mit awk können Sie alle wiederholten Zeilen in allen Dateien mit einem kurzen Befehl abrufen:

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

Es werden jedoch Zeilen wiederholt, wenn eine Zeile dreimal oder öfter vorhanden ist.
Es gibt eine Lösung, um nur das erste Duplikat zu erhalten:

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

Es sollte ziemlich schnell sein (wenn es nur wenige Wiederholungen gibt), aber es wird viel Speicher verbrauchen, um alle Zeilen im Speicher zu halten. Abhängig von Ihren tatsächlichen Dateien und Wiederholungen versuchen Sie es möglicherweise zuerst mit drei oder vier Dateien.

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

Andernfalls können Sie Folgendes tun:

$ sort -m *.words | uniq -d

Dadurch werden einzelne wiederholte Zeilen gedruckt.

Isaac
quelle
2
+1 fürsort -m * | uniq -d
Jeff Schaller
awk kann die Wiederholungen mit vermeiden, 'x[$0]++==1'benötigt aber tatsächlich viel Speicher; Wenn die 3G-Zeilen unterschiedliche 1G-Werte haben und Ihr awk beispielsweise 50 Byte für einen Hasharray-Eintrag benötigt, der eine (vermutlich kürzere) Zeichenfolge dem uninit-Wert zuordnet, sind das 50 GB. Für sortierte Eingaben können Sie uniq -dmanuell damit arbeiten, awk '$0==p&&n++==1;$0!=p{p=$0;n=1}'aber warum sich die Mühe machen?
Dave_thompson_085
@ dave_thompson_085 Danke für das Konzept ==1, tolle Idee.
Isaac
Unter der Annahme von 30000 Dateien mit 100000 Zeilen mit jeweils 80 Zeichen und ohne Duplikate müssen hierfür awk2,4E11 Bytes (223 GiB) gespeichert werden.
Kusalananda
sort -m *.words | uniq -dfunktioniert super! Nach dem Vorgang suche ich grepnach Dateien, die einen doppelten Eintrag enthalten. Sehen Sie eine Möglichkeit, den mindestens einen Dateinamen zu drucken, der einen doppelten Eintrag enthält?
Lars Schneider
3

Optimierte sort+ uniqLösung:

sort --parallel=30000 *.words | uniq -d
  • --parallel=N - Ändern Sie die Anzahl der gleichzeitig ausgeführten Sortierungen in N
  • -d, --repeated - Drucken Sie nur doppelte Zeilen, eine für jede Gruppe
RomanPerekhrest
quelle