Dateiunterschiede speichern

Hallo,

ich hab da jetzt mal so einen Entwurf, von einem Dateiunterschied-Parser und brauch mal etwas Hilfe dazu.

Erstmal, ich gehe zeilenweise vor. Ist das ok so? Oder soll ich das in Chunks machen? Es geht mir nicht nur um Textdateien, sondern Dateien aller Art. Da kann es doch vorkommen, dass es da eine 1 GiB Zeile gibt, die man nicht komplett auf einmal in den Speicher schreiben sollte? Also lieber Chunks? Wenn ja, ist 4096 Bytes eine gute Buffer-Größe?

Ansonsten, kann mir jemand noch etwas Kritik zum Schnipsel geben?

#include <string>
#include <fstream>
#include <map>

struct difference_type{
    std::string before, after;

    void clear(){
        before.clear();
        after.clear();
    }

    bool differ() const{
        return before != after;
    }
};

std::ostream& operator<< (std::ostream& stream, const difference_type& diff){
    return stream << diff.before << "\n---\n" << diff.after;
}

struct file_difference{
    std::size_t lines_before{}, lines_after{};
    std::map<std::size_t, difference_type> differences;

    void parse(const std::string& fp1, const std::string& fp2){
        std::ifstream stream1{fp1, std::ios::binary},
                      stream2{fp2, std::ios::binary};

        std::string line1, line2;
        difference_type difference;
        std::size_t current;

        while(stream1 || stream2){
            difference.clear();

            if(stream1){
                std::getline(stream1, line1);
                current = lines_before++;
                difference.before = std::move(line1);
            }

            if(stream2){
                std::getline(stream2, line2);
                current = lines_after++;
                difference.after = std::move(line2);
            }

            if(difference.differ())
                differences[current] = std::move(difference);
        }
    }
};

std::ostream& operator<< (std::ostream& stream, const file_difference& fdiff){
    stream << "Lines before : " << fdiff.lines_before << '\n'
           << "Lines after  : " << fdiff.lines_after << "\n\n";

    for(const auto& entry : fdiff.differences)
        stream << "Line: " << entry.first << '\n' << entry.second << "\n\n";

    return stream;
}

#include <iostream>

int main(){
    file_difference diff;
    diff.parse("f", "f2");
    std::cout << diff << '\n';
}

Ich hab mir eigentlich vorgestellt, dass das etwas mehr wird, fehlt da vielleicht noch was? Oder noch irgendwas an der Vorgehensweise zu meckern?

Also eigentlich ist dir schon klar, dass getline nicht funktionieren wird. Warum fängst du dann trotzdem damit an?

manni66 schrieb:

Also eigentlich ist dir schon klar, dass getline nicht funktionieren wird. Warum fängst du dann trotzdem damit an?

Ok. Sind 4KiB eine gute Buffer-Größe?
Gibt es sonst noch was an meiner Vorgehensweise anzumeckern?

Th69

Für einen Textvergleich macht das mit den Zeilen ja Sinn, bei Binärdaten aber bringen dir auch keine alleinigen Blockvergleiche etwas, denn die Änderung kann ja gerade an den Blockgrenzen sein.

Änderungen sind ja Löschen, Einfügen und Ersetzen - und eine Metrik dafür ist z.B. die Levenshtein-Distanz.

Th69 schrieb:

Für einen Textvergleich macht das mit den Zeilen ja Sinn, bei Binärdaten aber bringen dir auch keine alleinigen Blockvergleiche etwas, denn die Änderung kann ja gerade an den Blockgrenzen sein.

Naja, doch, man kann pro Block die Änderungen speichern, oder nicht?
Man hat ne struct difference mit zwei Vektoren std::vector<char> before, after.
Dann muss man sich doch nicht Löschen, Einfügen, Ersetzen merken, oder nicht?

Th69

Wenn du dann aber zwei Dateien hast (welche original identisch sind), wo in der 2. Datei am Anfang ein Zeichen zusätzlich eingefügt ist, dann unterscheiden sich dann in deiner Implementierung alle (folgenden) Blöcke - selbiges natürlich beim Löschen eines Zeichens.

Ok, aber dann verstehe ich nicht mehr so recht, wie ich da anfangen soll.
Könntest du mir ein struct skizieren, damit ich sehe, was da eigentlich genau geparst werden soll?

Th69

Hast du mal den Wiki-Link durchgelesen? Steht dort unter dem Stichwort "Backtrace"...

Th69 schrieb:

Hast du mal den Wiki-Link durchgelesen? Steht dort unter dem Stichwort "Backtrace"...

Klar hab ich mir den mal angekuckt, aber der hilft mir jetzt nicht sonderlich weiter.

Also die Levenshtein-Distanz könnt ich schonmal ausrechnen. Nicht, dass ich sonderlich viel davon verstehe, sondern es gibt einen Code auf Rosetta-Code, den ich abtippen und nach eigenem Ermessen verändern kann. Ich verstehe den Code zwar per se, aber nicht wirklich die mathematische Berechnung dabei. Aber den Algo hab ich schonmal!

Jetzt tauchen bei mir jedoch noch einige Fragen auf: Wenn es weder mit Zeilen, noch mit Chunks funktionieren soll, wie soll es denn dann funktionieren?

Und wie wende ich meinen Levenshtein-Algo darauf an?

Da muss es doch soon struct geben, nennen wirs mal difference_type , wo die Differenzen zweier Chunks(?) drin hausen. Aber ich hab das Problem, mir vorzustellen, wie dieses difference_type aussieht.

→Welche Member brauche ich in meiner Struktur?

hustbaer

Vergiss erstmal wie du die Unterschiede dann abspeicher willst. Ich würde mal damit anfangen wie du ermitteln willst was überhaupt unterschiedlich ist. Das ist nämlich nicht so einfach. Speziell wenn du möchtest dass es auch für grosse Dateien in annehmbarer Zeit funktioniert.

Was ich dir schonmal sagen kann: Es gibt soweit ich weiss keinen Algorithmus der für zwei richtig grosse Files (mehrere GiB) eine "minimale" Lösung in annehmbarer Zeit ausspucken kann. Wobei ich mit "minimal" meine dass es keine andere mögliche Lösung gibt, wo die Summe der Bytes (bzw. allgemein: Symbole) in den Unterschieden geringer ist.

Ein relativ einfacher Algorithmus, der auch halbwegs gut dokumentiert ist, ist z.B. der von rsync. Der ist aber bei richtig grossen Files immer noch ziemlich langsam, und braucht nochdazu richtig viel RAM.