Wie werden große Textdateien verglichen?

Nachdem Sie uns nun genauere Informationen gegeben haben, müssen Sie vor dem Partitionieren und optional vor dem Suchen nach Übereinstimmungen vorgehen.

Dies sollte eine beträchtliche Anzahl von Vergleichen eliminieren, die sonst im naiven Brute-Force-Ansatz nicht übereinstimmen würden. Um Argumente zu nennen, lassen Sie beide Dateien mit jeweils 40 Millionen Zeilen verknüpfen.

Partitionierung: Lesen Sie file_1 durch und senden Sie alle Zeilen beginnend mit mat1 nach file_1_mat1 und so weiter. Mach dasselbe für file_2 . Das ist trivial mit ein wenig grep , oder solltest du es programmatisch in Java machen wollen, ist es eine Übung für Anfänger.

Das ist ein Durchlauf durch zwei Dateien für insgesamt 80 Millionen gelesene Zeilen, was zu zwei Sätzen von 50 Dateien mit jeweils 800.000 Zeilen führt.

Sortieren: Sortieren Sie für jede Partition nur nach dem numerischen Wert in der zweiten Spalte (die untere Grenze von file_1 und die tatsächliche Zahl von file_2 ). Selbst wenn 800.000 Zeilen nicht in den Speicher passen, können wir die 2-way externe Zusammenführungs-Sortierung anpassen und diese schneller (weniger allgemeine Lesevorgänge) als eine Art des gesamten unpartitionierten Speicherplatzes ausführen.

Vergleich: Nun müssen Sie einmal durch beide Paare von file_1_mat1 und file_2_mat1 iterieren, ohne etwas im Speicher zu behalten und Übereinstimmungen mit Ihrem ausgeben zu müssen Ausgabedatei. Wiederholen Sie den Vorgang für den Rest der Partitionen. Ein abschließender Zusammenführungsschritt ist nicht erforderlich (es sei denn, Sie bearbeiten Partitionen parallel).

Auch ohne die Sortierstufe sollte der naive Vergleich, den Sie bereits machen, schneller über 50 Dateipaare mit je 800.000 Zeilen statt mit zwei Dateien mit jeweils 40 Millionen Zeilen erfolgen.

Ich denke, dein Weg ist ziemlich vernünftig.

Ich kann mir verschiedene Strategien vorstellen - zum Beispiel können Sie beide Dateien vor dem Vergleich sortieren (wo eine effiziente Implementierung von filesort ist, und unix sort Utility kann mehrere Gbs-Dateien in Minuten sortieren), und während Sie sortiert sind, können Sie Dateien vergleichen nacheinander Zeile für Zeile lesen.

Aber das ist ein ziemlich komplizierter Weg - Sie müssen ein externes Programm (sort) ausführen oder eine vergleichbare effiziente Implementierung von filesort in Java selbst schreiben - was an sich keine leichte Aufgabe ist. Also, aus Gründen der Einfachheit, denke ich, dass Sie Chunked Read sehr vielversprechend ist;

Wie man vernünftigen Block findet - zuallererst mag es nicht richtig sein, "je mehr - desto besser" - ich denke, Zeit aller Arbeit wird asymptotisch, zu einer konstanten Linie wachsen. Also, vielleicht wirst du schneller in der Nähe der Linie sein als du denkst - du brauchst einen Benchmark dafür.

Weiter - Sie können Zeilen lesen, die wie folgt gepuffert sind:

Sie lesen also so viele Zeilen wie Sie können - und den letzten BLOCK_SIZE des freien Speichers lassen. BLOCK_SIZE sollte groß sein, damit das restliche Programm ohne OOM läuft

In einer idealen Welt könnten Sie jede Zeile von file_2 in den Speicher einlesen (wahrscheinlich mit einem schnellen Suchobjekt wie zB HashSet , je nach Ihren Bedürfnissen), dann lesen Sie in jeder Zeile von file_1 eins nach a Zeit und vergleichen Sie es mit Ihrer Datenstruktur, die die Zeilen von file_2 hält.

Wie Sie gesagt haben, haben Sie nicht genug Speicher, aber ich denke, dass eine Strategie vom Typ "Teile und herrsche" am besten wäre. Sie können die gleiche Methode wie oben erwähnt verwenden, aber lesen Sie in einer Hälfte (oder einem Drittel, einem Viertel ... je nachdem wie viel Speicher Sie verwenden können) der Zeilen aus Datei_2 und speichern Sie sie, dann vergleichen Sie alle Zeilen in Datei_1. Dann lese in der nächsten Hälfte / Drittel / Quartal / was auch immer in Speicher (ersetzt die alten Zeilen) und gehen Sie erneut durch Datei_1. Es bedeutet, dass Sie Datei_1 mehr durchgehen müssen, aber Sie müssen mit Ihren Speicherbeschränkungen arbeiten.

BEARBEITEN: Als Reaktion auf die zusätzlichen Details in Ihrer Frage würde ich meine Antwort teilweise ändern. Statt alle Zeile_2 (oder in Chunks) einzulesen und Zeile_1 Zeile für Zeile einzulesen, kehren Sie das Gegenteil um, da Datei_1 die zu überprüfenden Daten enthält.

Auch in Bezug auf die Suche nach den passenden Zeilen. Ich denke, der beste Weg wäre, die Datei 1 zu bearbeiten. Erstellen Sie eine HashMap<List<Range>> , die einen String ("mat1" - "mat50") einer Liste von Range s (nur ein Wrapper für einen startOfRange int und ein endOfRange int ) zuordnet und füllen Sie sie mit den Daten aus Datei_1. Dann schreibe eine Funktion wie (Ignoriere Fehlerprüfung)

und rufen Sie es für jede (geparste) Zeile von file_2 auf.

Es gibt einen Kompromiss: Wenn Sie einen großen Teil der Datei lesen, speichern Sie die Suchzeit , aber Sie haben möglicherweise Informationen gelesen, die Sie nicht benötigen, da die Änderung in den ersten Zeilen aufgetreten ist.

Sie sollten wahrscheinlich einige Experimente [Benchmarks] mit unterschiedlicher Chunk-Größe durchführen, um herauszufinden, welcher optimale Chunk im Durchschnitt zu lesen ist.

Nicht sicher, wie gut eine Antwort das wäre - aber werfen Sie einen Blick auf diese Seite: Ссылка - es fasst zusammen einige diff-Algorithmen. Der Hunt-McIlroy-Algorithmus ist wahrscheinlich die bessere Implementierung. Von dieser Seite gibt es auch einen Link zu einer Java-Implementierung des GNU diff. Ich denke jedoch, eine Implementierung in C / C ++ und in nativen Code kompiliert wird viel schneller. Wenn Sie mit Java festgefahren sind, sollten Sie JNI in Erwägung ziehen.

Tatsächlich könnte das eine Weile dauern. Sie müssen 1.200.000.000 Zeilenvergleiche durchführen. Es gibt mehrere Möglichkeiten, dies um eine Größenordnung zu beschleunigen:

Man würde file2 sortieren und eine Art binäre Suche auf Dateiebene durchführen. Ein anderer Ansatz: Berechne für jede Zeile eine Prüfsumme und suche danach. Abhängig von der durchschnittlichen Zeilenlänge wäre die betreffende Datei viel kleiner und Sie können wirklich eine binäre Suche durchführen, wenn Sie die Prüfsummen in einem festen Format speichern (d. H. Lang)

Die Anzahl der Zeilen, die Sie gleichzeitig aus Datei_1 lesen, ist jedoch nicht . Dies ist eine Mikrooptimierung angesichts der großen Komplexität.

Sie können jede einzelne Datei sortieren. z.B. das UNIX sort oder ähnlich in Java. Sie können die sortierten Dateien Zeile für Zeile lesen, um eine Zusammenführungssortierung durchzuführen.

Wenn Sie genau wissen wollen, ob die Dateien unterschiedlich sind oder nicht, gibt es keine bessere Lösung als Ihre - sequenziell zu vergleichen.

Sie können jedoch einige Heuristiken erstellen, die Ihnen mit einer gewissen Wahrscheinlichkeit sagen können, ob die Dateien identisch sind. 1) Überprüfen Sie die Dateigröße; Das ist am einfachsten. 2) Nimm eine zufällige Dateiposition und vergleiche einen Block von Bytes, der an dieser Position in den zwei Dateien beginnt. 3) Wiederholen Sie Schritt 2), um die erforderliche Wahrscheinlichkeit zu erreichen.

Sie sollten berechnen und testen, wie viele Lesevorgänge (und Blockgröße) für Ihr Programm nützlich sind.

Meine Lösung wäre, zuerst einen Index für eine Datei zu erstellen und dann den Vergleich durchzuführen. Dies ist ähnlich wie bei einigen anderen Antworten, da es Hashing verwendet.

Sie erwähnen, dass die Anzahl der Zeilen bis zu 45 Millionen beträgt. Dies bedeutet, dass Sie (potenziell) einen Index speichern könnten, der 16 Bytes pro Eintrag (128 Bits) verwendet und ungefähr 45.000.000 * 16 = ~ 685 MB RAM verwendet, was auf einem modernen System nicht unangemessen ist. Es gibt Gemeinkosten bei der Verwendung der unten beschriebenen Lösung, so dass Sie möglicherweise immer noch feststellen müssen, dass Sie andere Techniken wie Speicherabbilddateien oder plattenbasierte Tabellen verwenden müssen, um den Index zu erstellen. Siehe Hypertable oder HBase für ein Beispiel, wie der Index in einer schnellen festplattenbasierten Hash-Tabelle gespeichert wird.

Also wäre der Algorithmus in etwa wie folgt:

1. Erstellen Sie eine Hash-Map, die Long einer Liste von Longs (HashMap & lt; Long, List & lt; Long & gt; & gt; & gt;)
zuordnet
2. Erhalte den Hash jeder Zeile in der ersten Datei (Object.hashCode sollte ausreichen)
3. Erhalte den Offset in der Datei der Zeile, damit du ihn später wieder finden kannst
4. Fügen Sie den Versatz zur Liste der Zeilen mit übereinstimmenden hashCodes in der Hash-Map
hinzu
5. Vergleichen Sie jede Zeile der zweiten Datei mit der Menge der Zeilenoffsets im Index
6. Beliebige Zeilen mit übereinstimmenden Einträgen
beibehalten

BEARBEITEN: Als Reaktion auf Ihre bearbeitete Frage würde das nicht wirklich hilfreich sein. Sie könnten einfach den ersten Teil der Zeile hashen, aber es würde nur 50 verschiedene Einträge erzeugen. Sie könnten dann jedoch eine andere Ebene in der Datenstruktur erstellen, die den Anfang jedes Bereichs dem Offset der Zeile zuordnen würde, aus der er stammt.

So etwas wie index.get("mat32") würde eine TreeMap von Bereichen zurückgeben. Sie können nach dem Bereich suchen, der dem gesuchten Wert vorausgeht. Untereintrag () . Zusammen ergibt das eine ziemlich schnelle Überprüfung, ob eine bestimmte MatX- / Zahlenkombination in einem der Bereiche ist, nach denen Sie suchen.

versuchen Sie, Speicherverbrauch zu vermeiden und machen Sie es Disc-konsumieren. Ich meine, jede Datei in ladbare Größen teilen und sie vergleichen, das kann etwas mehr Zeit in Anspruch nehmen, aber Sie werden mit den Speichergrenzen umgehen.

Was ist mit Quellcodeverwaltung wie Mercurial ? Ich weiß nicht, vielleicht ist es nicht genau das, was Sie wollen, aber dies ist ein Werkzeug, das entwickelt wurde, um Änderungen zwischen Revisionen zu verfolgen. Sie können ein Repository erstellen, die erste Datei festschreiben und sie dann mit einer anderen Datei überschreiben und die zweite Datei festschreiben:

Von hier aus können Sie einen Diff erhalten, der Ihnen sagt, welche Zeilen sich unterscheiden. Wenn Sie dieses Diff irgendwie verwenden könnten, um zu bestimmen, welche Zeilen die gleichen waren, würden Sie alles einstellen.

Das ist nur eine Idee, jemand korrigiert mich, wenn ich falsch liege.

Ich würde Folgendes versuchen: Für jede Datei, die Sie vergleichen, erstellen Sie temporäre Dateien (ich beziehe mich später als Teildatei) auf die Festplatte, die jeden Buchstaben und eine zusätzliche Datei für alle anderen Zeichen darstellt. dann lies die ganze Datei Zeile für Zeile. Fügen Sie dabei die Zeile in die entsprechende Datei ein, die dem Anfangsbuchstaben entspricht. Da Sie dies für beide Dateien getan haben, können Sie jetzt den Vergleich zum Laden von zwei kleineren Dateien gleichzeitig einschränken. Eine Zeile, die zum Beispiel mit A beginnt, kann nur in einer Teildatei vorkommen und es wird nicht notwendig sein, jede Teildatei mehr als einmal zu vergleichen. Wenn die resultierenden Dateien immer noch sehr groß sind, können Sie die gleiche Methode auf die resultierenden Teildateien (briefspezifische Dateien) anwenden, die verglichen werden, indem Sie Dateien gemäß dem zweiten Buchstaben in ihnen erstellen. Der Trade-of würde hier die Verwendung von großem Speicherplatz vorübergehend sein, bis der Prozess beendet ist. In diesem Prozess können Ansätze, die in anderen Posts erwähnt werden, dabei helfen, mit den Teildateien effizienter umzugehen.