Führen Sie eine Menge Ersatz in einer Textdatei eine riesige Liste von Ersatzpaaren

Question

Gegeben:

• Datei a.txt viele Millionen Zeilen (sagen wir, einem Satz pro Zeile) (2,6 GB
• Datei enthalten! b.txt 830k Linien mit Paaren [word1] [word2]

Frage enthält:

Wie die effizienteste Austausch von auszuführen jedes Wort1 nach Wort2 für jedes der 830k Tupel (w1, w2) in der riesigen Textdatei?

Naive Methoden wie Sed, Perl, Python usw. würden Wochen brauchen, um dies zu tun. Gibt es (möglicherweise parallelisierungsbasierte) Möglichkeiten, diese Ersatzlast zu bewältigen?

Answer 1

Ich würde es in SQL tun.

Erstellen einer Tabelle mit zwei Spalten (Datenleitung, Sequenz), und setzen a.txt hinein (eine Zeile pro Tabellenzeile)

Dann wird eine zweite Tabelle erstellen, wiederum mit zwei Spalten (word1 und word2) und lesen b.txt in sie (wieder eine Zeile pro Tabellenzeile)

eine Update-Anweisung generiert tabelle1 Aktualisierung basierend auf table2

laufen die sQL-Anweisung

, wenn es abgeschlossen ist, wieder aus der ersten Tabelle lesen in eine Datei

Answer 2

Teilen Sie die Datei in kleinere Stücke. Sie verbrauchen wahrscheinlich viel Speicherplatz, indem Sie nur Bits im Speicher oder auf der Festplatte verschieben.

Dies ist ähnlich, wie es viel schneller zu verketten/ersetzen auf einem Array von Zeichenfolgen anstelle einer einzelnen Zeichenfolge ist.

Der einzige Trick ist es, sicherzustellen, wo Sie die Pause in der Datei ist keine gute Übereinstimmung, die relativ trivial ist. In der Tat, wenn Sie es durch Linien tun können, ist das noch besser, keine Notwendigkeit, gegen Übereinstimmungen zu überprüfen.

Ich finde es auch seltsam, dass es PERL Wochen dauern würde. Es gibt einige anekdotische Hinweise darauf, dass es, dass in weniger als einer Stunde verarbeiten kann:

• http://www.wellho.net/forum/Perl-Programming/replace-text-in-a-large-text-file.html
• http://muharem.wordpress.com/2008/04/30/text-filtering-with-erlang/

In der Tat, sie über 1gb Dateien unter 2 Minuten in der zweiten Verbindung sprechen .

Und ich würde nicht vermuten, dass eine Ersetzung Vorgang dauert deutlich länger als ein Kopiervorgang für eine Datei, schließlich, es nur Teile der Datei abholen und einige der Bits ersetzen, wie Sie sie verschieben.Es sollte sich schnell in der Nähe der Geschwindigkeit der Lage sein, sie zu ersetzen, kopieren (wie sie bereits im Speicher ist)

Answer 3

Sortieren Sie die Liste der Suchen/Ersetzen-Paare durch das Wort [word1]

dann finden lesen durch die Datei, jede Zeile in Wörter aufteilen, und suchen Sie nach jedem Wort in Ihrer Liste von Wörtern zu ersetzen (mit etwas effizienter als eine binäre Suche).

Es sollte erreichbar sein.

Answer 4

Ich würde es in Python tun, aber jede andere Sprache würde die Arbeit tun, wenn Sie den richtigen Algorithmus erhalten. Der ganze Trick besteht darin, die Wortpaare (Datei b.txt) im Speicher zu behalten und die große Datei in einem Durchgang zu durchlaufen. Da I ​​/ O ist viel langsamer Betrieb als aus dem RAM zu lesen, die Leistung dieses Ansatzes würde O (file1) + O (file2)

In Pseudo-Code sein:

myMap = {} 
for line in fileB: 
    myMap[1st word of line] = 2nd word of line 

for line in fileA 
    for word in line 
    if myMap contains word 
     replace word with myMap[word] 

ich dies vorstellen, die am schnellsten ist, können Sie bekommen.

Answer 5

Ich stimme mit idroid Antwort nur das Laden der Paare in den Speicher und dann Streaming über die Datei. Wenn Sie wirklich viele Daten haben (viele GB) und Sie nicht über die Maschinenressourcen verfügen, um dies so schnell zu erledigen, wie Sie möchten, wäre der neue Elastic Hadoop-Service von Amazon eine gute Lösung. Sobald Sie eine einfache ausführbare Datei für kleine Dateien erstellt haben, wäre es ziemlich einfach, diese Menge an Daten mithilfe des Map Reduce-Frameworks von Hadoop zu skalieren.