Verbinden von Textdateien mit mehr als 600 Millionen Zeilen

7

Ich habe zwei Dateien huge.txtund small.txt. huge.txthat rund 600 Millionen Zeilen und es ist 14 GB. Jede Zeile enthält vier durch Leerzeichen getrennte Wörter (Token) und schließlich eine weitere durch Leerzeichen getrennte Spalte mit einer Nummer. small.txthat 150K Zeilen mit einer Größe von ~ 3M, einem durch Leerzeichen getrennten Wort und einer Zahl.

Beide Dateien werden mit dem Befehl sort ohne zusätzliche Optionen sortiert. Die Wörter in beiden Dateien können Apostrophe (') und Bindestriche (-) enthalten.

Die gewünschte Ausgabe würde alle Spalten aus der huge.txtDatei und die zweite Spalte (die Nummer) enthalten, aus der small.txtdas erste Wort huge.txtund das erste small.txtübereinstimmende Wort stammen .

Meine Versuche unten scheiterten kläglich mit folgendem Fehler:

cat huge.txt|join -o 1.1 1.2 1.3 1.4 2.2 - small.txt > output.txt

join: memory exhausted  

Was ich vermute ist, dass die Sortierreihenfolge irgendwie nicht stimmt, obwohl die Dateien vorsortiert sind mit:

sort -k1 huge.unsorted.txt > huge.txt
sort -k1 small.unsorted.txt > small.txt

Die Probleme scheinen bei Wörtern mit Apostrophen (') oder Bindestrichen (-) aufzutreten. Ich habe auch versucht, das Wörterbuch mit der -dOption zu sortieren, die am Ende auf denselben Fehler stößt.

Ich habe versucht, die Dateien in MySQL zu laden, Indizes zu erstellen und sie zu verbinden, aber auf meinem Laptop scheint es Wochen zu dauern. (Ich habe keinen Computer mit mehr Speicher oder schneller Festplatte / SSD für diese Aufgabe)

Ich sehe zwei Möglichkeiten, weiß aber nicht, wie ich eine davon implementieren soll.

  1. Wie sortiere ich die Dateien so, dass der Befehl join sie für richtig sortiert hält?

  2. Ich dachte daran, MD5 oder andere Hashes der Strings zu berechnen , um die Apostrophe und Bindestriche zu entfernen, aber die Zahlen am Ende der Zeilen intakt zu lassen. Führen Sie das Sortieren und Verbinden mit den Hashes anstelle der Zeichenfolgen selbst durch und "übersetzen" Sie die Hashes schließlich wieder in Zeichenfolgen. Da es nur 150K Hashes geben würde, ist es nicht so schlimm. Was wäre ein guter Weg, um einzelne Hashes für jede der Zeichenfolgen zu berechnen? Etwas AWK-Magie?

Siehe Dateibeispiele am Ende.

Beispiel von vast.txt

had stirred me to 46 
had stirred my corruption 57 
had stirred old emotions 55 
had stirred something in 69 
had stirred something within 40 

Beispiel für small.txt

caley 114881 
calf 2757974 
calfed 137861 
calfee 71143 
calflora 154624 
calfskin 148347 
calgary 9416465 
calgon's 94846 
had 987654

Gewünschte Ausgabe:

had stirred me to 46 987654
had stirred my corruption 57 987654
had stirred old emotions 55 987654
had stirred something in 69 987654
had stirred something within 40 987654
dnkb
quelle
1
ok, Sie haben Riesen.txt und Klein.txt angegeben. Können Sie bitte die gewünschte Ausgabe / das gewünschte Ergebnis liefern?
Akira
1
bitte siehe oben
dnkb
Hier neugierig zu sein, aber ich muss fragen. Welche Art von Analyse machen Sie mit all diesen Daten?
Nifle
1
@Nifle: Masterplan, um die Welt zu übernehmen :)
Akira
1
@Nifle, @akira: fast :) eigentlich geht es darum, den berühmten Google Web Corpus zu verarbeiten, um Reize für ein psycholinguistisches Experiment zusammenzustellen. Die Zahlen sind die Häufigkeit der Zeichenfolgen in der englischen Sprache www, wie Google es 2006 gesehen hat. Es tut mir leid, wenn dies ein lahmer Grund ist, all diese Daten
durchzuarbeiten

Antworten:

9

IMO der beste Weg, dies zu tun, wäre die Verwendung der Programmier- / Skriptsprache, die Sie am besten kennen und:

  1. Laden Sie small.txt in ein speicherinternes Hash- / Map- / assoziatives Array, das mit den Wörtern versehen ist
  2. Verarbeiten Sie die Datei vast.txt zeilenweise, fügen Sie die vom Hash nachgeschlagene Spalte hinzu und schreiben Sie das Ergebnis in eine Ausgabedatei
  3. Puffereingabe und -ausgabe so, dass sie in Blöcken von mindestens 4 KB erfolgt
Michael Borgwardt
quelle
1
Danke Michael. Das Problem ist, dass das, was ich oben dargelegt habe, das einfachste Szenario ist. Ich muss den obigen Vorgang auch für zwei große Dateien (10+ GB) ausführen, wobei das Laden einer in den Speicher keine Option ist. Deshalb möchte ich vorsortierte Dateien verwenden und beitreten.
dnkb
@dnkb: Vorsortierte Dateien sind keine Hilfe, wenn beide Dateien zu groß sind, um in den Speicher zu passen, da Sie immer noch wahlfreien Zugriff auf eine von ihnen benötigen, was endloses HD-Thrashing bedeutet. Sie benötigen einen Grace- oder Hybrid-Hash-Join en.wikipedia.org/wiki/Hash_join - aber jedes remote professionelle RDBMS wird dies implementieren. Ihre Zeit wird wahrscheinlich am besten damit verbracht, die MySQL-basierte Lösung zum Laufen zu bringen.
Michael Borgwardt
4
Ich bin anderer Meinung: Wenn die Dateien vorsortiert sind, können sie wie in meiner Antwort nur mit sequentiellem Zugriff zusammengeführt werden.
David Z
@ David: Du hast recht. Ich sollte zu dieser Zeit keine Fragen beantworten ...
Michael Borgwardt
7

Um auf Michael Borgwardts Antwort aufzubauen: Solange beide Dateien sortiert sind, können Sie sie zusammenfügen, indem Sie im Grunde einen Schritt eines Mergesorts ausführen. Es unterscheidet sich ein wenig von Standard-Mergesort, da Sie nur eine der Dateien behalten möchten. Dies muss natürlich in Ihrer bevorzugten Programmiersprache implementiert werden.

Hier ist eine Skizze des Algorithmus:

line1 = read a line from file 1
line2 = read a line from file 2
start of loop:
if (first word of line1 == first word of line2) {
    write all fields of line1
      and second field of line2 to output
    line1 = read a line from file 1
    go to start of loop
}
else if (first word of line1 < first word of line2) {
    write line1 to output
    line1 = read a line from file 1
    go to start of loop
}
else (first word of line1 > first word of line2) {
    line2 = read a line from file 2
    go to start of loop
}

Hier ist eine Python-Version (da Python genau das ist, was ich am besten kenne, nicht unbedingt die beste Sprache für den Job):

file1 = open('file1', 'r')
file2 = open('file2', 'r')
w2, n2 = file2.readline().split()
for line1 in file1:
  w11, w12, w13, w14, n15 = line1.split()
  if w11 == w2:
    print w11, w12, w13, w14, n15, n2
    continue
  elif w11 < w2:
    print w11, w12, w13, w14, n15
    continue
  else:
    while w11 > w2:
      w2, n2 = file2.readline().split()
    if w11 == w2:
      print w11, w12, w13, w14, n15, n2
    elif w11 < w2:
      print w11, w12, w13, w14, n15

und der Vollständigkeit halber habe ich mir nach einigem Graben Folgendes für Awk ausgedacht:

BEGIN {
  getline line2 <"file2";
  split(line2, a);
}
{
  if (a[1] == $1) print $0,a[2];
  else if (a[1] < $1) print $0;
  else { getline line2 <"file2"; split(line2, a); }
}

Rufen Sie als auf awk -f program.awk <file1.

David Z.
quelle
Vielen Dank. Der Teufel ist in der Sortierung und in den <und> Vergleichen. Die GNU-Sorte scheint Apostrophe irgendwie zu ignorieren / zu misshandeln, daher glaube ich, dass meine Probleme darauf zurückzuführen sind. Wenn ich die Dateien gemäß den Implementierungen des Operators <,>, lt, gt "richtig" sortieren könnte, gäbe es überhaupt kein Problem. Tatsächlich habe ich versucht, die obige Logik in Perl zu codieren, aber es ist b / c von Unterschieden fehlgeschlagen, was Perl und Sortierung als "größere" oder "kleinere" Zeichenfolge betrachten.
dnkb
Hmm, nun, Sie könnten beim Zusammenführen eine benutzerdefinierte Vergleichsfunktion verwenden, die der Art und Weise entspricht, wie GNU sort die Dateien behandelt.
David Z
Ja. Irgendwelche Tipps, wie das geht? Oder wie kann man herausfinden, welche Art das tut?
dnkb
Ausgezeichnete Post. Am längsten habe ich je gesehen. + 1 + 1 + 1 + 1
Jamesbtate
2

Meine Antwort ähnelt der von Michael Borgwardt, aber Sie müssen nicht alle Dateien in den Speicher laden. Wenn beide Dateien sortiert sind, gehen Sie zeilenweise durch die erste Datei und durchsuchen die zweite Datei binär, um die betreffende Zielzeile zu finden. Das ist viel HD-Zugriff, aber es ist ein geringer Speicherverbrauch.

Michael H.
quelle
Ich unterstütze diese Antwort. Wenn ich das Problem angehen würde, würde ich wahrscheinlich Folgendes tun: Erstellen Sie so viele .cdb-Dateien aus small.txt wie nötig, um eine sehr schnelle Suche zu ermöglichen, und gehen Sie dann Zeile für Zeile über large.txt und fragen Sie den Begriff in allen .cdb-Dateien ab. Wenn Sie die binäre Suche selbst in Dateien implementieren möchten, ist dies ebenfalls in Ordnung.
Akira
1

Ich weiß, dass es peinlich einfach ist, aber es funktioniert.
Ausgehend von der Annahme, dass meine Originaldateien nur Kleinbuchstaben enthalten, habe ich einfach die problematischen Apostrophe und Bindestriche durch zwei Großbuchstaben ersetzt, die neu sortiert und dann zusammengefügt wurden, und schließlich die Buchstaben wieder in die Zeichen geändert. Das ist es.

Nochmals vielen Dank für alle, die eine Antwort oder einen aufschlussreichen Kommentar beigesteuert haben.

Das Sortieren dauerte für riesig.txt (14Gig) ungefähr 2 Stunden, die Verbindung dauerte weniger als eine Stunde.

cat small.txt | tr "\'-" "AD" | sort -k1 > small.AD
cat huge.txt | tr "\'-" "AD" | sort -k1 | cat huge.txt | join -o 1.1 1.2 1.3 1.4 2.2 - small.AD | tr "AD" "\'-" > output.txt
dnkb
quelle
Ich bin immer noch an der Geschwindigkeit meines Ansatzes interessiert. Kann ich die Dateien irgendwo herunterladen? oder erstellen Sie sie hier mit .. was auch immer?
Akira
@akira: Es ist nur auf 6 DVDs von UPenn erhältlich und kann leider nicht heruntergeladen werden. ldc.upenn.edu/Catalog/CatalogEntry.jsp?catalogId=LDC2006T13 Ich wäre auch sehr interessiert zu sehen. Mein Bauchgefühl ist, dass mit einer herkömmlichen 2,5-Zoll-Laptop-Festplatte der nicht sequentielle Festplattenzugriff, der zum Durchlaufen des Index erforderlich ist, wahrscheinlich die Dinge verlangsamen würde. Mit einer anständigen SSD kann es schneller sein.
dnkb
@akira: Sie können es jedoch testen, indem Sie beispielsweise 5 Millionen eindeutige Zufallszeichenfolgen und entsprechende Ganzzahlen (Frequenzen) generieren und dann die 150K häufigsten Stücke auswählen. Dies wird small.txt sein. Wenn Sie dieselben 5M-Zufallszeichenfolgen verwenden, konstruieren Sie erneut zufällig vier Gramm und geben Sie anschließend eine weitere Ganzzahl ein. Generieren Sie 600 Millionen Zeilen, um die Datei large.txt zu erstellen. ZB asdf wert dfw werhhyr 345345 frtko de serrte flxee 423443 Versuchen Sie schließlich (innen), sie auf einer beliebigen Säule zu verbinden. Dies sollte die Komplexität ziemlich gut reproduzieren.
dnkb
1

OK, dieser Ansatz verwendet http://cr.yp.to/cdb.html , um den Inhalt von 'small.txt' schneller nachzuschlagen:

  • Gehen Sie und installieren Sie cdbmake(Teil des 'freecdb'-Pakets in Ubuntu, aber es sind viele Implementierungen verfügbar.
  • Verwenden Sie awk, um small.txt an zu leiten cdbmake.

    % awk '    { printf "+%d,%d:%s->%s\n", \
                    length($1),length($2),$1,$2 } \
           END { print "" }' | cdbmake small.cdb small.cdbtmp
    

(Dies transformiert eine Zeile von 'small.txt' von etwas wie "Schlüsselwert" in "+ ks, vs: Schlüssel-> Wert".)

  • Jetzt gehen Sie Zeile für Zeile über 'vast.txt' und drucken es aus, wobei Sie das erste Wort in 'small.cdb' nachschlagen:

    #!/bin/python
    import cdb
    import fileinput
    
    c = cdb.init("small.cdb")
    for l in fileinput.input(['huge.txt']):
        print l.strip(),
        v = c.get(l.split()[0])
        print "" if v == None else v
    

Sie müssten natürlich python-cdb installieren, damit dieses winzige Snippet funktioniert (und es funktioniert aufgrund des ' bedingten Ausdrucks ' nur für Python 2.5. Auf jeden Fall gibt es viele Bindungen für jede Sprache, die Sie mögen. Sie können sie auch verwenden cdbget(ein Befehlszeilen-Tool) und rufen Sie es immer wieder auf, aber das Erstellen eines neuen Prozesses für Millionen von Zeilen ist etwas ineffektiv.

Wie auch immer, denken Sie daran:

  • Jede CDB-Datei darf nicht größer als 4 GB sein. Wenn Sie also 'small.txt' mit einer Größe von 10 GB verarbeiten müssen, müssen Sie dies offensichtlich in mehrere Dateien aufteilen und 'small1.cdb', 'small2.cdb', 'small3.cbd' usw. erstellen. Es sollte eine leichte Aufgabe sein.
  • Sie müssen 'small.txt' nicht sortieren, eine Suche in einer CDB-Datei ist sowieso ziemlich schnell.
  • Ich habe meinen kleinen Testfall hier nicht zeitlich festgelegt, er basiert auf dem, was Sie angegeben haben. :) :)
Akira
quelle
0

Anstelle von MySQL können Sie auch PostgreSQL ausprobieren, das diese Aufgabe wahrscheinlich besser bewältigen kann. Lesen Sie den Leitfaden zum effizienten Auffüllen einer Datenbank.

Hanf
quelle
Ein RDBMS ist nicht der richtige Hammer für diese Art von Nagel
Akira