grep mit Muster aus einer Datei (3,2 GB), das mit einer anderen Datei übereinstimmt (4,8 GB)

7

Ich habe zwei Textdateien. Eine ist eine Textdatei mit Name, E-Mail-Adresse und anderen Feldern. Einige Zeilen aus file1:

John:[email protected]:johnson123:22hey
Erik:[email protected]:johnson133:22hey
Robert:[email protected]:johnson123:21hey
Johnnny:[email protected]:johnson123:22hey

Die andere enthält nur E-Mail-Adressen. Beispiele aus file2:

[email protected]
[email protected]
[email protected]
[email protected]

Ich möchte, dass die Ausgabe in jeder vollständigen Zeile file1eine E-Mail-Adresse enthält file2. Ist zum Beispiel [email protected]in file2, also würde ich gerne die folgende Zeile von sehen file1:

John:[email protected]:johnson123:22hey

Gibt es eine einfache Möglichkeit, file1die Zeilen zu suchen und auszugeben, die mit der "Liste der E-Mail-Adressen" übereinstimmen file2?

Ich habe nach STUNDEN gesucht, aber meine Google-Suche (und StackOverflow-Suche) sowie die Bemühungen in der Befehlszeile waren bisher nicht effektiv.

Befehle, die ich ausprobiert habe und von denen ich denke, dass sie funktionieren würden:

fgrep -f file2.txt file1.txt > matched.txt
grep -F -f ....
grep -F -x -f file1 file2 > common 

usw., aber sie haben alle grep memory exhausted- die Dateien, mit denen ich übereinstimme, sind 4,8 GB ( file1) und 3,2 GB ( file2die nur die E-Mail-Adressen enthalten). Ich gehe davon aus, dass der Speicher mit diesen Befehlen erschöpft ist. Ich habe eine Methode gefunden, mit findder die Befehle reibungsloser ausgeführt werden können, aber sie hat nicht funktioniert.

tldr ; Notwendigkeit übereinstimmen file2mit file1und wenn es eine Zeile aus , file2dass entspricht einer Zeile in die file1Ausgangs es. Die Dateien sind groß und ich brauche einen sicheren Weg, um nicht den gesamten Speicher zu verbrauchen.

Danke, habe den ganzen Tag danach gesucht und experimentiert, wollte nicht aufgeben (5 Stunden +).

Axel Tobieson
quelle
8
Diese Daten sind ein Kandidat für das Einfügen in eine Datenbank.
Kusalananda
Was meinst du?
Axel Tobieson
4
Ich meine, da die Datenmengen so groß sind, kann es effizienter sein, ein Datenbankmodul die Abfrage ausführen zu lassen, als Unix-Befehlszeilentools zu verwenden. Ich habe gerade nach einer Möglichkeit gesucht, die Daten in SQLite oder MySQL einzulesen, um zu sehen, ob ich sie effizient abfragen kann, aber hier wird es spät, sodass ich nicht weiß, ob ich Zeit habe, etwas Reales zu tun. Andere können mit anderen Lösungen einspringen.
Kusalananda
Okay Mann, es ist im TXT-Format.
Axel Tobieson
1
Ja. Ich glaube, ich habe einige großartige Antworten erhalten, aber ich habe costas answer angewendet und es zum Laufen gebracht.! :)
Axel Tobieson

Antworten:

7

Es ist ziemlich schwierig, große Dateien zu bedienen, aber Sie können dies in drei Schritten tun:

  1. Sortieren Sie Datei1 nach dem zweiten Feld

    sort -k2,2 -t: file1 >file1.sorted
    
  2. Sortieren file2

    sort file2 >file2.sorted
    
  3. Verbinden Sie 2 Dateien per E-Mail-Feld

    join -t: -2 2 file2.sorted file1.sorted -o 2.1,0,2.3,2.4 >matched.txt
    
Costas
quelle
Sie berücksichtigen nicht, :was im lokalen Teil einer E-Mail-Adresse auftreten kann.
Anthon
@Anthon Das ist sicherlich eine Schwäche des Formats, in dem die Daten gespeichert wurden
Score_Under
5

Ich sende eine zweite Antwort auf diese Frage (dies ist ein interessantes Problem). Diese Lösung unterscheidet sich grundlegend von meiner SQLite-Lösung und von den vielversprechend aussehenden sort+ joinLösungen, die sich abzeichnen:

Verwenden Sie Ihren anfänglichen Ansatz mit grep -f, aber reduzieren Sie das Problem buchstäblich ein wenig. Teilen wir die "Abfragedatei" file2mithilfe von in verwaltbare Blöcke auf split.

Das splitDienstprogramm kann eine Datei basierend auf der Zeilenanzahl in mehrere kleinere Dateien aufteilen.

Eine 3,2-GB-Datei mit einer durchschnittlichen Zeilenlänge von 20 Zeichen enthält ungefähr 172.000.000 Zeilen (es sei denn, ich habe einen Rechenfehler gemacht). Das Aufteilen in 2000 Dateien mit 85000 Zeilen pro Datei ist möglich.

Damit,

$ mkdir testing
$ cd testing
$ split -l 85000 -a 4 ../file2

Die -a 4Option weist splitan, nach einer Initiale vier Zeichen xzu verwenden, um die Dateinamen für die neuen Dateien zu erstellen. Die Dateien werden aufgerufen werden xaaaa, xaaabusw.

Führen Sie dann das Original grep -fauf diesen aus:

for f in x????; do
  grep -F -f "$f" ../file1
done

Dies kann es ermöglichen grep, den jetzt viel kleineren Satz von Abfragemustern im Speicher zu halten.

UPDATE : Mit 145.526.885 Zeilen können Sie split -l 72000 -a 4ungefähr 2000 Dateien erstellen.

Denken Sie daran, das testingVerzeichnis jedes Mal zu löschen, wenn Sie versuchen, einen neuen Satz geteilter Dateien zu erstellen.

Beachten Sie, dass die geteilten Dateien aus dieser Antwort einzeln als Eingabe für alle anderen Antworten verwendet werden können, die Sie möglicherweise auf diese Frage erhalten.

Kusalananda
quelle
Ich schätze die Hilfe sehr, werde es versuchen - werde Sie wissen lassen, ob es funktioniert. Auch die 3,2-GB-Datei befindet sich bei 145,526,885 Zeilen (145,5 m)
Axel Tobieson
@ AxelTobieson Da, ich glaube, ich habe es jetzt verstanden. Entschuldigung für meine Verwirrung. Keine Garantie, dass es funktioniert. Die Sort + Join-Lösungen sind wahrscheinlich auch gut.
Kusalananda
@AxelTobieson Ich habe ein Feedback bekommen und habe jetzt eine bessere Version der Antwort.
Kusalananda
4

Die Antwort von Costas ist angesichts Ihres genauen Problems wahrscheinlich die beste, da Sie ein Feld haben, das zu 100% übereinstimmt.

Aber wenn Ihr Problem wirklich war für Millionen von regexps in Milliarden von Zeilen greppen, dann hat GNU Parallel eine Beschreibung, wie das zu tun: https://www.gnu.org/software/parallel/man.html#EXAMPLE:-Grepping -n-Zeilen-für-m-reguläre-Ausdrücke

Die einfachste Lösung, um eine große Datei für viele reguläre Ausdrücke zu durchsuchen, ist:

grep -f regexps.txt bigfile

Oder wenn die regulären Ausdrücke feste Zeichenfolgen sind:

grep -F -f regexps.txt bigfile

Es gibt drei einschränkende Faktoren: CPU, RAM und Festplatten-E / A.

RAM ist einfach zu messen: Wenn der grep-Prozess den größten Teil Ihres freien Speichers beansprucht (z. B. wenn Sie oben ausgeführt werden), ist RAM ein begrenzender Faktor.

Die CPU ist auch leicht zu messen: Wenn der grep> 90% der CPU oben einnimmt, ist die CPU ein begrenzender Faktor, und die Parallelisierung beschleunigt dies.

Es ist schwieriger zu erkennen, ob die Festplatten-E / A der begrenzende Faktor ist, und je nach Festplattensystem kann die Parallelisierung schneller oder langsamer sein. Der einzige Weg, um sicher zu wissen, ist zu testen und zu messen.

Begrenzungsfaktor: RAM

Die normale grep -f regexs.txt-Bigfile funktioniert unabhängig von der Größe der Bigfile. Wenn die regexps.txt jedoch so groß ist, dass sie nicht in den Speicher passt, müssen Sie sie aufteilen.

grep -F benötigt ungefähr 100 Bytes RAM und grep ungefähr 500 Bytes RAM pro 1 Byte Regexp. Wenn also regexps.txt 1% Ihres Arbeitsspeichers ausmacht, ist es möglicherweise zu groß.

Wenn Sie Ihre regulären Ausdrücke in feste Zeichenfolgen konvertieren können, tun Sie dies. ZB wenn die Zeilen, nach denen Sie in bigfile suchen, alle so aussehen:

ID1 foo bar baz Identifier1 quux
fubar ID2 foo bar baz Identifier2

dann kann Ihre regexps.txt konvertiert werden von:

ID1.*Identifier1
ID2.*Identifier2

in:

ID1 foo bar baz Identifier1
ID2 foo bar baz Identifier2

Auf diese Weise können Sie grep -F verwenden, das etwa 80% weniger Speicher benötigt und viel schneller ist.

Wenn es immer noch nicht in den Speicher passt, können Sie dies tun:

parallel --pipepart -a regexps.txt --block 1M grep -F -f - -n bigfile |
sort -un | perl -pe 's/^\d+://'

Die 1M sollte Ihr freier Speicher sein, geteilt durch die Anzahl der Kerne und geteilt durch 200 für grep -F und durch 1000 für normales grep. Unter GNU / Linux können Sie Folgendes tun:

free=$(awk '/^((Swap)?Cached|MemFree|Buffers):/ { sum += $2 }
          END { print sum }' /proc/meminfo)
percpu=$((free / 200 / $(parallel --number-of-cores)))k

parallel --pipepart -a regexps.txt --block $percpu --compress grep -F -f - -n bigfile |
sort -un | perl -pe 's/^\d+://'

Wenn Sie mit doppelten Zeilen und falscher Reihenfolge leben können, ist dies schneller:

parallel --pipepart -a regexps.txt --block $percpu --compress grep -F -f - bigfile

Begrenzungsfaktor: CPU

Wenn die CPU der begrenzende Faktor ist, sollte die Parallelisierung auf den regulären Ausdrücken erfolgen:

cat regexp.txt | parallel --pipe -L1000 --round-robin --compress grep -f - -n bigfile |
sort -un | perl -pe 's/^\d+://'

Der Befehl startet einen Grep pro CPU und liest Bigfile einmal pro CPU. Da dies jedoch parallel erfolgt, werden alle Lesevorgänge mit Ausnahme des ersten im RAM zwischengespeichert. Abhängig von der Größe von regexp.txt ist es möglicherweise schneller, --block 10m anstelle von -L1000 zu verwenden.

Einige Speichersysteme bieten eine bessere Leistung, wenn mehrere Blöcke gleichzeitig gelesen werden. Dies gilt für einige RAID-Systeme und für einige Netzwerkdateisysteme. Um das Lesen von Bigfile zu parallelisieren:

parallel --pipepart --block 100M -a bigfile -k --compress grep -f regexp.txt

Dadurch wird bigfile in 100-MB-Blöcke aufgeteilt und grep für jeden dieser Blöcke ausgeführt. Um sowohl das Lesen von bigfile als auch von regexp.txt zu parallelisieren, kombinieren Sie beide mit --fifo:

parallel --pipepart --block 100M -a bigfile --fifo cat regexp.txt \
\| parallel --pipe -L1000 --round-robin grep -f - {}

Wenn eine Zeile mit mehreren regulären Ausdrücken übereinstimmt, wird die Zeile möglicherweise dupliziert.

Größeres Problem

Wenn das Problem zu groß ist, um damit gelöst zu werden, sind Sie wahrscheinlich bereit für Lucene.

Ole Tange
quelle
2

Wichtiger Haftungsausschluss: Ich habe dies anhand der in der Frage angegebenen Daten getestet. Das Laden mehrerer Gigabyte Daten in eine SQLite-Datenbank kann viel Zeit in Anspruch nehmen. Die Abfrage unter Verwendung von zwei Textfeldern kann ineffizient sein. Die Festplattenleistung kann berücksichtigt werden. Usw. usw.

Das folgende shSkript erstellt die SQLlite-Datenbank database.db(diese Datei wird gelöscht, wenn sie bereits vorhanden ist), erstellt die Tabellen qadrund dataund lädt die Daten in die beiden Tabellen ( file1in dataund file2in qadr). Anschließend wird ein Index für erstellt data.adr.

#!/bin/sh

address_file="file2"
data_file="file1"

database="database.db"

rm -f "$database"

sqlite3 "$database" <<END_SQL
CREATE TABLE qadr ( adr TEXT );
CREATE TABLE data ( name TEXT, adr TEXT, tag1 TEXT, tag2 TEXT );
.separator :
.import "$data_file" data
.import "$address_file" qadr
VACUUM;
CREATE UNIQUE INDEX adri ON data(adr);
VACUUM;
END_SQL

Bei der Erstellung des Index wird davon ausgegangen, dass die Adressen in file1eindeutig sind ( :dh , dass das Feld mit der zweiten Begrenzung eindeutig ist). Wenn dies nicht UNIQUEder CREATE INDEXFall ist, entfernen Sie es aus der Anweisung (im Idealfall sind sie eindeutig, und im Idealfall file2sind auch die Zeilen in eindeutig).

Ich habe noch nie mit SQLite und diesen Datenmengen gearbeitet, aber ich weiß, dass Multi-Gigabyte-Importe in MongoDB und MySQL schmerzhaft langsam sein können und dass die Indexerstellung ebenfalls zeitaufwändig sein kann. Ich sage also im Grunde, dass ich das nur für jemanden mit vielen Daten zum Testen rauswerfe.

Dann handelt es sich um eine einfache Abfrage:

$ sqlite3 database.db 'SELECT data.* FROM data JOIN qadr ON (data.adr = qadr.adr)'
John|[email protected]|johnson123|22hey

oder vielleicht sogar nur

$ sqlite3 database.db 'SELECT * FROM data NATURAL JOIN qadr'
John|[email protected]|johnson123|22hey

Jemand mit mehr SQLite-Kenntnissen wird dies sicherlich konstruktiv kommentieren.

Kusalananda
quelle
1
Nur :als Trenner zu verwenden, ist zu simpel. A :kann sich im lokalen Teil einer gültigen E-Mail-Adresse befinden.
Anthon
1
@Anthon Wusste das nicht. Dazu müssen die Daten vor dem Import einer Formatierung unterzogen werden, für die möglicherweise E-Mail-Adressen analysiert und überprüft werden müssen. Ich werde das außerhalb des Rahmens betrachten, den ich bereit bin, für diese spezielle Frage zu tun. Die anderen Antworten sind möglicherweise fruchtbarer, wenn dies der Fall ist (oder sogar unabhängig davon, ob die Liste exotische Adressen enthält).
Kusalananda
1
Der :Separator kann einfach mit awk oder perl befestigt werden. Aufteilen in ein Array mit: als Trennzeichen. Wenn das Array 4 Felder enthält, verwenden Sie es unverändert. Wenn es 5 Felder hat, verbinden Sie die Felder 2 und 3 mit einem :, löschen Sie Feld 3 und verwenden Sie dann. "use" kann so einfach sein wie die Ausgabe mit TAB-Trennzeichen und Pipe in SQLite für den Import. oder richtig zitiert und CSV. oder json oder XML. Übrigens würde ich bei Dateien dieser Größe dazu neigen, postgresql oder mysql anstelle von sqlite zu verwenden.
Cas
2

Wenn Sie eine DB-Lösung vermeiden müssen (nicht sicher, warum, scheint mir die beste Idee zu sein), können Sie dies tun, indem Sie die beiden Dateien nach den E-Mail-Adressen sortieren und dann den joinBefehl verwenden, der ungefähr der Leistung einer DB entspricht.

Folgendes habe ich getan:

sort -t: +1 file1 -o file1
sort file2 -o file2
join -t: -o 1.1,1.2,1.3,1.4 -1 2 file1 file2

Das scheint mit Ihren Beispieldaten das Richtige zu tun. Es sortiert die Dateien an Ort und Stelle . Wenn Sie das nicht möchten, ändern Sie die -oOption auf dem sorts in temporäre Dateinamen und verwenden Sie diese im Join. Wenn Sie tatsächlich andere als 4 Felder in der ersten Datei haben, müssen Sie dies in der -oOption berücksichtigen join.

Weitere Informationen finden Sie in den Manpages.

KARTE
quelle
Sie berücksichtigen nicht, dass: im lokalen Teil einer E-Mail-Adresse auftreten kann.
Anthon
1

So etwas würde funktionieren, aber ich bin mir nicht sicher, ob es eine gute Idee ist, abhängig von Ihrem Anwendungsfall (ungetestet):

while read f2line
do
  f1=$(grep $line file1)

  [[ ! -z $f1 ]] && echo $f1line 
done < file2

Eine weitere mögliche Lösung, wenn Sie mehr von einer Einzeiler-Methode möchten (unten schnell getestet):

grep . file2 | xargs -i^ grep ^ file1

Was ergab:

root@7Z233W1 (/tmp)# cat f1
John:[email protected]:johnson123:22hey
Erik:[email protected]:johnson133:22hey
Robert:[email protected]:johnson123:21hey
Johnnny:[email protected]:johnson123:22hey

root@7Z233W1 (/tmp)# cat f2
[email protected]
[email protected]
[email protected]
[email protected]

root@7Z233W1 (/tmp)# grep . f2 | xargs -i^ grep ^ f1
John:[email protected]:johnson123:22hey
Jim
quelle
1
Die zweite Lösung sieht plausibler aus, da die erste eine Grep pro Zeile in einer 3,2-GB-Datei ausführt.
Kusalananda
0

Hier ist eine Version von Kusalanandas Skript, mit perlder vor dem Einspeisen file1von :getrennt in getrenntes TAB umgewandelt wird sqlite3.

Das eingebettete perlSkript prüft, ob 5 statt 4 Felder vorhanden sind. Wenn dies der Fall ist, hängt es Feld 3 an Feld 2 an (wobei das :vom Autosplit entfernte Feld wiederhergestellt wird ) und löscht dann Feld 3.

#!/bin/sh

address_file="file2"
data_file="file1"

database="database.db"

rm -f "$database"

sqlite3 "$database" <<END_SQL
CREATE TABLE qadr ( adr TEXT );
CREATE TABLE data ( name TEXT, adr TEXT, tag1 TEXT, tag2 TEXT );
.mode line
.import "$address_file" qadr
END_SQL

perl -F: -lane 'if (@F == 5) {
    $F[1] .= ":" . $F[2];  # perl arrays are zero-based
    delete $F[2];
  };
  print join("\t",@F);' $data_file | 
    sqlite3 "$database" -separator $'\t' '.import /dev/stdin data'


sqlite3 "$database" <<END_SQL
VACUUM;
CREATE UNIQUE INDEX adri ON data(adr);
VACUUM;
END_SQL

IMO, SQLite ist nicht für eine so große Datenbank geeignet. Ich würde empfehlen, stattdessen mysqloder zu postgresqlverwenden. Für diese Art von Aufgabe mysqlist es aufgrund der Geschwindigkeit wahrscheinlich eine bessere Wahl - für einfache Dinge wie diese ist es schneller, aber für komplexere Aufgaben ist postgresql viel schneller - meiner Erfahrung nach ist pg "smart fast" (dh es kann massiv erreichen Geschwindigkeitsverbesserungen bei komplexen Aufgaben durch intelligentes Arbeiten anstatt hartes Arbeiten), MySQL ist "dumm schnell" (dh es arbeitet hart, ohne viel Fähigkeit, intelligent zu arbeiten).

Das obige Skript kann leicht angepasst werden, um mit den psqloder mysqlBefehlszeilen-Clients zu arbeiten sqlite3, aber ich würde die CREATE TABLEBefehle so ändern , dass CHARACTER(size)stattdessen eine feste Größe verwendet wird TEXT, wobei sizeeine vernünftige Vermutung vorliegt, wie groß die maximale Größe für jedes Feld ist - z. B. vielleicht 255 Zeichen für das adrFeld und 10-50 Zeichen für die anderen.

Eine mögliche Optimierung besteht darin, die Feldgrößen sorgfältig so auszuwählen, dass jeder Datensatz ein gleichmäßiger Teiler der Blockgröße Ihres Laufwerks ist (unter Berücksichtigung des Overheads von mysql / postgresql pro Datensatz). 512 Bytes sollten für alle gängigen Blockgrößen geeignet sein. Machen Sie die Felder in der gewünschten Größe und fügen Sie ein zusätzliches, nicht verwendetes CHARACTER(size)Feld hinzu, um den Unterschied auszugleichen. Der Grund dafür ist, dass Datensätze niemals eine Blockgrenze überschreiten, sodass die Datenbank-Engine immer nur einen Plattenblock einlesen muss, um alle Daten für einen bestimmten Datensatz abzurufen (tatsächlich werden mehrere Datensätze in einem Block mit gelesen Die meisten aktuellen Blockgrößen, aber das hilft nur der Leistung, kann sie nicht beeinträchtigen.

https://dba.stackexchange.com/ ist wahrscheinlich die beste Website, um nach Informationen zur Optimierung der Datensatzgröße zu suchen oder diese anzufordern.

cas
quelle