Ich habe zwei sehr große Dateien (und keiner davon würde in den Speicher passen ). Jede Datei hat eine Zeichenfolge (die keine Leerzeichen enthält und entweder 99/100/101 Zeichen lang ist) in jeder Zeile.
Update: Die Strings sind nicht in einer sortierten Reihenfolge.
Update2: Ich arbeite mit Java unter Windows.
Nun möchte ich den besten Weg finden, alle Strings herauszufinden, die in beiden Dateien vorkommen.
Ich habe darüber nachgedacht, externe merge sort zu verwenden, um beide Dateien zu sortieren und dann einen Vergleich durchzuführen, aber ich bin mir nicht sicher, ob das der beste Weg wäre, dies zu tun. Da die Strings meist ungefähr gleich lang sind, habe ich mich immer gefragt, ob es sinnvoll wäre, für jede Saite eine Art Hash zu berechnen, da dies die Vergleiche zwischen Strings erleichtern würde, aber das würde bedeuten, dass ich die Hashes speichern muss berechnet für die Strings, die ich bisher aus den Dateien gefunden habe, damit sie später beim Vergleich mit anderen Strings verwendet werden können. Ich kann nicht genau sagen, was genau der beste Weg wäre. Ich bin auf der Suche nach Ihren Vorschlägen.
Wenn Sie eine Lösung vorschlagen, geben Sie bitte auch an, ob die Lösung funktionieren würde, wenn mehr als 2 Dateien vorhanden wären und Strings, die in allen vorkommen, herausgefunden werden müssen.
Ich würde es wie folgt machen (für beliebig viele Dateien):
Abhängig davon, wie ähnlich die Einträge in einer Datei sind, könnte es möglich sein, eine Trie zu erstellen (nicht Baum) von ihm. Mit diesem Trie können Sie die andere Datei iterieren und jeden Eintrag überprüfen, wenn er sich im Trie befindet.
Wenn Sie mehr als zwei Dateien haben, durchlaufen Sie eine Datei und erstellen Sie einen neuen Trie aus den Übereinstimmungen. Auf diese Weise enthält der letzte Trie, den Sie haben, alle Übereinstimmungen, die in allen Dateien enthalten sind.
Gibt es eine Reihenfolge für die Daten in den Dateien? Der Grund, warum ich frage, ist, dass, obwohl ein Zeilenvergleich eine Ewigkeit dauern würde, eine Datei Zeile für Zeile durchlaufen würde, während eine binäre Suche in der anderen viel schneller wäre. Dies funktioniert jedoch nur, wenn die Daten auf eine bestimmte Art und Weise sortiert sind.
Eine hashbasierte Lösung könnte so aussehen (in python pseudocode):
%Vor%Wiederholen Sie den Vorgang und drucken Sie die übereinstimmenden Zeilen:
%Vor%Es gibt zwei mögliche Probleme.
Das ist O (Zeilen * Kosten (md5)).
(wenn Leute eine vollere Python-Implementierung haben, ist es ziemlich einfach zu schreiben, ich kenne Java allerdings nicht!).
Um es in Windows zu tun, ist es ziemlich einfach .. Nehmen wir an, Sie haben zwei Dateien A und B. 'A' Dateien enthält die Zeichenfolgen, die Sie in Datei B suchen möchten. Öffnen Sie einfach die Eingabeaufforderung und verwenden Sie den folgenden Befehl
%Vor%Dieser Befehl ist ziemlich schnell und kann zwei Dateien sehr effizient vergleichen. Die Datei OUTPUT enthält die in A und B üblichen Zeichenfolgen.
Wenn Sie die ODER-Operationen (Strings in B außer A) ausführen möchten, verwenden Sie
%Vor%