Binar patch-generație în C #

Are cineva, sau știu, o implementare algoritm de generare a patch-urilor în C #?

Practic, comparați două fișiere (desemnate vechi și noi ) și produceți un fișier de patch-uri care poate fi utilizat pentru a actualiza fișierul vechi același conținut ca și fișierul nou .

Implementarea ar trebui să fie relativ rapidă și să lucreze cu fișiere uriașe. Ar trebui să prezinte ore de funcționare O (n) sau O (logn).

Algoritmii mei tind să fie fie neplacuți (rapizi, dar producând patch-uri imense), fie lent (produc patch-uri mici, dar au O (n ^ 2) runtime).

Orice sfat sau indicii pentru implementare ar fi frumos.

În mod specific, implementarea va fi utilizată pentru a menține serverele în sincronizare pentru diferite fișiere de date mari pe care le avem pentru un server principal. Când se schimba fișierele de date ale serverului principal, trebuie să actualizăm mai multe servere în afara site-ului.

Cel mai naiv algoritm pe care l-am făcut, care funcționează numai pentru fișierele care pot fi păstrate în memorie, este după cum urmează:

1. Grab the first four bytes from the old file, call this the key
2. Add those bytes to a dictionary, where key -> position, where position is the position where I grabbed those 4 bytes, 0 to begin with
3. Skip the first of these four bytes, grab another 4 (3 overlap, 1 one), and add to the dictionary the same way
4. Repeat steps 1-3 for all 4-byte blocks in the old file
5. From the start of the new file, grab 4 bytes, and attempt to look it up in the dictionary
6. If found, find the longest match if there are several, by comparing bytes from the two files
7. Encode a reference to that location in the old file, and skip the matched block in the new file
8. If not found, encode 1 byte from the new file, and skip it
9. Repeat steps 5-8 for the rest of the new file

Aceasta este oarecum compresie, fără ferestre, deci va folosi o mulțime de memorie. Este, totuși, destul de rapid și produce niște patch-uri destul de mici, atâta timp cât încerc să fac codurile rezultate minime.

Un algoritm mai eficient din memorie utilizează ferestre, dar produce fișiere mult mai mari de patch-uri.

Există mai multe nuanțe la algoritmul de mai sus pe care l-am sarit în acest post, dar pot posta mai multe detalii dacă este necesar. Cu toate acestea, simt că am nevoie de un alt algoritm altfel, îmbunătățirea algoritmului de mai sus probabil că nu mă va face suficient de departe.

Edit #1: Here is a more detailed description of the above algorithm.

Mai întâi, combinați cele două fișiere, astfel încât să aveți un fișier mare. Amintiți-vă de punctul de tăiere dintre cele două fișiere.

În al doilea rând, faceți acest pas apucați 4 octeți și adăugați poziția lor în dicționar pas pentru totul din întregul fișier.

În al treilea rând, de unde pornește fișierul nou , faceți buclele cu încercarea de a localiza o combinație existentă de 4 octeți și pentru a găsi cea mai lungă potrivire. Asigurați-vă că luăm în considerare numai pozițiile din fișierul vechi sau din mai devreme în fișierul nou decât în ​​momentul în care suntem în prezent la . Acest lucru asigură faptul că putem reutiliza materialul atât în ​​fișierul vechi, cât și în cel nou în timpul aplicării unui patch.

Edit #2: Source code to the above algorithm

S-ar putea să primiți un avertisment cu privire la faptul că certificatul are unele probleme. Nu știu cum să rezolv asta, așa că deocamdată acceptați certificatul.

Sursa folosește o mulțime de alte tipuri din restul bibliotecii mele, astfel încât fișierul nu este tot ce este necesar, dar asta este implementarea algoritmului.

@lomaxx, am încercat să găsesc o documentație bună pentru algoritmul utilizat în subversiune, numit xdelta, dar dacă nu știți deja cum funcționează algoritmul, documentele pe care le-am găsit nu reușesc să-mi spună ce trebuie să știu.

Sau poate că sunt doar dense ... :)

Am făcut o scurtă privire asupra algoritmului din site-ul pe care l-ați dat și din păcate nu este utilizabil. Un comentariu din fișierul bifal diff spune:

Găsirea unui set optim de diferențe necesită timp quadratic față de dimensiunea de intrare, astfel încât devine inutilizabil foarte repede.

Nevoile mele nu sunt însă optimale, deci caut o soluție mai practică.

Vă mulțumim pentru răspuns, deși, a adăugat un marcaj la utilitățile sale, dacă am nevoie vreodată de ele.

Edit #1: Note, I will look at his code to see if I can find some ideas, and I'll also send him an email later with questions, but I've read that book he references and though the solution is good for finding optimal solutions, it is impractical in use due to the time requirements.

Edit #2: I'll definitely hunt down the python xdelta implementation.