Das erste Problem ist das Diff, der theoretische Ansatz ist:
Code:
(die Endzeilen seinen jeweils exklusive)
Gegeben sind
1. z1von ... z1bis: der zu betrachtende Bereich aus Datei 1
2. z2von ... z2bis: der zu betrachtende Bereich aus Datei 2
Vorgehen:
3. Finde den längsten übereinstimmenden Block innerhalb des Bereichs:
z1fund ... z1fund+zlaenge
z2fund ... z2fund+zlaenge
4. Wenn zlaenge < Mindestlänge (z.B. 3)
-> markiere den Bereich als nicht übereinstimmend
5. sonst
-> Rufe die Funktion rekursiv auf mit den Blöcken davor und danach
z1von ... z1fund und z2von ... z2fund
z1fund+zlaenge ... z1bis und z2fund+zlaenge ... z2bis
Zur Beschleunigung der Geschwindigkeit arbeitet man dann mit Hashcodes, so dass man relativ schnell passende Zeilen findet und nicht alle immer wieder miteinander vergleichen muss.
Ich habe mir Anno '93 mal ein Diff-Programm selbst geschrieben (damals noch für DOS
), das auch große Dateien relativ schnell vergleichen konnte.