Wie entferne ich doppelte Zeilen in einer Textdatei?

126

Eine riesige (bis zu 2 GiB) Textdatei von mir enthält ungefähr 100 exakte Duplikate jeder Zeile (in meinem Fall nutzlos, da die Datei eine CSV-ähnliche Datentabelle ist).

Was ich brauche, ist, alle Wiederholungen zu entfernen, während (vorzugsweise, aber dies kann für einen signifikanten Leistungsschub geopfert werden) die ursprüngliche Sequenzreihenfolge beibehalten. Im Ergebnis soll jede Zeile eindeutig sein. Wenn es 100 gleiche Zeilen gäbe (normalerweise sind die Duplikate über die Datei verteilt und werden keine Nachbarn sein), wäre nur eine einzige davon übrig.

Ich habe ein Programm in Scala geschrieben (halte es für Java, wenn du nichts über Scala weißt), um dies zu implementieren. Aber vielleicht gibt es schnellere C-geschriebene native Tools, die dies schneller können?

UPDATE: Die awk '!seen[$0]++' filenameLösung schien für mich in Ordnung zu sein, solange die Dateien in der Nähe von 2 GiB oder kleiner waren, aber jetzt, da ich eine 8 GiB-Datei bereinigen möchte, funktioniert sie nicht mehr. Auf einem Mac mit 4 GiB RAM und einem 64-Bit-Windows 7-PC mit 4 GiB RAM und 6 GiB Swap scheint es unendlich zu werden. Und ich bin angesichts dieser Erfahrung nicht begeistert davon, es unter Linux mit 4 GiB RAM zu versuchen.

Ivan
quelle
Dies wird Ihre Bestellung zerstören, aber wenn Sie es mit sort -u versucht haben, habe ich keine Ahnung, wie oder ob es auf solch einer massiven Datei ausgeführt werden kann
0x7c0
5
C ist oft nicht wesentlich schneller als Java. Wenn Sie es jetzt (in der richtigen Reihenfolge) ausführen, besteht eine gute Chance, dass es beendet wird, bevor Sie hier eine Antwort erhalten, es implementieren und es beendet wird. außer Betrieb, sort -uwird wahrscheinlich schneller sein.
Kevin

Antworten:

215

Eine awkLösung von #bash (Freenode):

awk '!seen[$0]++' filename
Enzotib
quelle
1
Habe es gerade mit einer 2G-Datei versucht und es hat drei Minuten auf meinem Notebook gedauert. Nicht schlecht. Ich habe auch versucht, uniq filename | awk '! seen [$ 0] ++', aber es war nicht schneller.
mgjk
Dies ist überraschend schneller als eine ausführlichere awkVersion mit 2 Array-Suchen (als erweiterte Erklärung in Gilles Antwort gezeigt): 0m36.132s vs 0m49.958s .. für 50 Millionen Zeilen .. Ich dachte, der Engpass wäre die E / A, aber die zusätzliche Array-Suche ist ... 1 Million Elemente im Array scheinen eine ziemlich erhebliche
Beeinträchtigung zu verursachen
Aber wie ist das im Vergleich zu sort -u ....?
HashWizard
1
@HashWizard: Dieser Befehl sortiert nicht, sondern beseitigt jedes nächste Vorkommen derselben Zeile
enzotib
1
@MaxWilliams ja, es funktioniert, sie werden zufällig verteilt.
Setholopolus
47

Es gibt eine einfache (was nicht selbstverständlich ist) Methode, bei der Standarddienstprogramme verwendet werden sort, für deren Ausführung nur ein großer Speicher erforderlich ist. In den meisten Implementierungen gibt es spezielle Optimierungen für große Dateien (ein guter externer Sortieralgorithmus). Ein Vorteil dieser Methode besteht darin, dass nur alle Zeilen in Spezialdienstprogrammen durchlaufen werden, nicht jedoch in interpretierten Sprachen.

<input nl -b a -s : |           # number the lines
sort -t : -k 2 -u |             # sort and uniquify ignoring the line numbers
sort -t : -k 1n |               # sort according to the line numbers
cut -d : -f 2- >output          # remove the line numbers

Wenn alle Zeilen mit einem Nicht-Leerzeichen beginnen, können Sie auf einige der Optionen verzichten:

<input nl | sort -k 2 -u | sort -k 1n | cut -f 2- >output

Bei einer großen Anzahl von Duplikaten ist eine Methode, bei der nur eine einzige Kopie jeder Zeile im Speicher gespeichert werden muss, leistungsfähiger. Mit einigem Interpretationsaufwand gibt es dafür ein sehr kurzes awk-Skript (bereits von enzotib gepostet ):

<input awk '!seen[$0]++'

Weniger präzise: !seen[$0] {print} {seen[$0] += 1}ZB die aktuelle Zeile drucken, wenn sie noch nicht gesehen wurde, dann den seenZähler für diese Zeile inkrementieren (nicht initialisierte Variablen oder Array-Elemente haben den numerischen Wert 0).

Bei langen Zeilen können Sie Speicherplatz sparen, indem Sie für jede Zeile nur eine nicht fälschbare Prüfsumme (z. B. einen kryptografischen Auszug) aufbewahren. Bei Verwendung von SHA-1 benötigen Sie beispielsweise nur 20 Byte plus einen konstanten Overhead pro Zeile. Das Berechnen von Digests ist jedoch ziemlich langsam. Diese Methode gewinnt nur, wenn Sie eine schnelle CPU (insbesondere eine mit einem Hardwarebeschleuniger zum Berechnen der Digests) und im Verhältnis zur Dateigröße und den ausreichend langen Zeilen nicht viel Speicher haben. Mit keinem Basisdienstprogramm können Sie eine Prüfsumme für jede Zeile berechnen. Sie müssten den Interpretationsaufwand für Perl / Python / Ruby / ... tragen oder ein spezielles kompiliertes Programm schreiben.

<input perl -MDigest::MD5 -ne '$seen{Digest::MD5::md5($_)}++ or print' >output
Gilles
quelle
@Gilles Bedeutet awk '!seen[$0]++'dies, dass, wenn awk zwei doppelte Zeilen sieht, die immer erste beibehalten und alle nachfolgenden ignoriert werden? (Oder wird es den letzten behalten?)
user779159
1
@ user779159 Es wird die erste Zeile beibehalten: Jede Eingabezeile wird entweder sofort (erstes Vorkommen) oder gar nicht (wiederholtes Vorkommen) gedruckt.
Gilles
Aber wie ist das im Vergleich zu sort -u ...?
HashWizard
@HashWizard Eine Ebene sort -uändert die Reihenfolge. Meine Antwort zeigt Lösungen, bei denen die Reihenfolge erhalten bleibt (die Reihenfolge der ersten Vorkommen, um genau zu sein).
Gilles
@Gilles Würden Sie sagen, dass es schneller ist als sort -u für große Dateien (10G) mit 50% Duplikaten?
HashWizard
25
sort -u big-csv-file.csv > duplicates-removed.csv

Beachten Sie, dass die Ausgabedatei sortiert wird.

Vladislavs Dovgalecs
quelle
1
Nicht so schnell wie der awkBefehl in anderen Antworten, aber konzeptionell einfach!
Johann
@Johann Ich mache das ziemlich oft bei Dateien mit Hunderttausenden (sogar Millionen) von kurzen Zeilen mit Zeilenende. Ich bekomme die Ergebnisse für die Experimente, die ich mache, ziemlich schnell. In Skripten, die immer wieder ausgeführt werden, kann es wichtiger sein, Zeit zu sparen.
Vladislavs Dovgalecs
1
Dient sort -uzum Entfernen von Duplikaten während des Sortierens und nicht danach. (Und spart Speicherbandbreite). Dies ist nur dann besser als die awkVersion, wenn auch Ihre Ausgabe sortiert werden soll. (Das OP zu dieser Frage möchte, dass seine ursprüngliche Bestellung beibehalten wird , daher ist dies eine gute Antwort für einen etwas anderen Anwendungsfall.)
Peter Cordes,
Ich habe ungefähr eine Minute für eine Datei mit 5,5 Millionen Zeilen (insgesamt 1,8 GB) gebraucht. Brillant.
Max Williams
18

Vorausgesetzt, Sie können es sich leisten, so viel wie die nicht duplizierte Datei im Arbeitsspeicher zu behalten (wenn Ihre Daten tatsächlich um den Faktor 100 dupliziert werden, das sollte ungefähr 20 MB + Overhead sein), können Sie dies mit Perl ganz einfach tun.

$ perl -ne 'print unless $dup{$_}++;' input_file > output_file

Dadurch bleibt auch die Reihenfolge erhalten.

Sie können die Anzahl der Vorkommen jeder Zeile aus dem %dupHash extrahieren, wenn Sie dies wünschen, als zusätzlichen Bonus.

Wenn Sie es vorziehen awk, sollte dies auch so sein (dieselbe Logik wie die Perl-Version, dieselbe Reihenfolge, dieselben Daten, die in der dupVariablen gesammelt wurden ):

$ awk '{if (++dup[$0] == 1) print $0;}' input_file > output_file
Matte
quelle
Das ist zu gut @Mat, ich wollte gerade die Datei schlürfen, lol ;-).
Nikhil Mulley
Jetzt warte auf @ManAtWork für seine sed und awk Magic Weaver :-)
Nikhil Mulley
Nochmals super für den awk-Tipp :-)
Nikhil Mulley
1
Ist es möglich, das Perl-Skript so zu ändern, dass nur doppelte benachbarte Zeilen entfernt werden?
Dumbledad
2
@ Dumbledad: uniqmacht das alles von selbst
Mat
3

Da an Ort und Stelle keine andere Antwort zur Verfügung gestellt wurde, ist hier eine:

gawk -i inplace '!a[$0]++' file
Jan Chren - rindeal
quelle
Bewahrt dies die Ordnung? Übrigens hat das bei mir nicht geklappt. Meine Version ist:GNU Awk 4.0.2
Leonid
1
@Leonid ja, das tut es. Es wird das erste Vorkommen einer eindeutigen Zeile gedruckt. Die Inplace-Unterstützung wurde erstmals in Version 4.1 eingeführt, die 2013 veröffentlicht wurde.
Jan Chrenrindeal, 16.
3

Sie können uniq http://www.computerhope.com/unix/uuniq.htm verwenden

uniq meldet oder filtert wiederholte Zeilen in einer Datei heraus.

Mahmoud Zalt
quelle
Wenn Sie eine Antwort geben, ist es vorzuziehen, eine Erklärung zu geben , WARUM Ihre Antwort die richtige ist. Wie unterscheidet sich diese Antwort von einigen der vorherigen Antworten?
Stephen Rauch
1
Auf der Manpage von uniq: Hinweis: 'uniq' does not detect repeated lines unless they are adjacent. Sie müssen sie also zuerst sortieren und die Reihenfolge der nicht doppelten Zeilen verlieren.
Vindolin
2

Python One-Liner:

python -c "import sys; lines = sys.stdin.readlines(); print ''.join(sorted(set(lines)))" < InputFile
Rahul Patil
quelle
Dies führt dazu, dass die gesamte Datei in den Speicher verschoben wird und möglicherweise nicht für das OP-Problem geeignet ist. Auch nicht garantiert, um die Bestellung beizubehalten
iruvar
Vielen Dank für den Vorschlag, ich habe gerade Python gelernt .. habe es nur zu Lernzwecken versucht .. :)
Rahul Patil
Hier ist eine Python 2.7-Version, die nicht einzeilig ist, sondern (kurz und bündig) eindeutige Zeilen mit beibehaltener Reihenfolge zurückgibt, ohne entweder die gesamte Datei in den Speicher zu laden oder eine einzelne gigantische Zeichenfolge zu erstellen, die zum Drucken
eingespeist werden soll
Thanks @ 1_CR Ich habe heute etwas gelernt :)OrderedDict
Rahul Patil
0

Keine der hier aufgeführten Antworten hat auf meinem Mac funktioniert, daher habe ich ein einfaches Python-Skript geschrieben, das für mich funktioniert. Ich ignoriere führende / nachfolgende Leerzeichen und kümmere mich auch nicht um den Speicherverbrauch.

import sys

inputfile = sys.argv[1]
outputfile = sys.argv[2]

with open(inputfile) as f:
    content = f.readlines()

content = [x.strip() for x in content]

my_list = list(set(content))

with open(outputfile, 'w') as output:
    for item in my_list:
        output.write("%s\n" % item)

Speichern Sie das oben auf unique.py und führen Sie es folgendermaßen aus:

python unique.py inputfile.txt outputfile.txt
Jared
quelle
-1

Mit bash 4 kann eine Pure-bash-Lösung verwendet werden, die assoziative Arrays nutzt. Hier ist ein Beispiel

unset llist; declare -A llist;
while read -r line; do
if [[ ${llist[$line]} ]]; then
  continue
else 
  printf '%s\n' "$line"
  llist[$line]="x"
fi
done < file.txt
iruvar
quelle
2
Verwenden Sie keine readSchleifen, um große Textdateien zu verarbeiten. Die Bash muss ein Byte nach dem anderen lesen, um ein Überschießen einer neuen Zeile zu vermeiden. Bash ist auch nicht sehr schnell in der Textverarbeitung im Allgemeinen im Vergleich zu awk. Wenn Sie dies verwenden, read -ravermeiden Sie Backslashes in Ihrer Eingabe. Vergessen Sie auch nicht, unset llist nach der Schleife, wenn Sie dies in eine Shell-Funktion setzen oder interaktiv verwenden.
Peter Cordes
2
@ PeterCordes, oder Sie könnten nur darauf verwiesen haben :-)
iruvar