Verbinden von Textdateien mit mehr als 600 Millionen Zeilen

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

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

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.

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.

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

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. :) :)

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.