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.

0
fr hi bn
Acea bucată de cod este post, aici este versiunea curentă, deși nu am întreținut acea bibliotecă în vîrste: lassevk.kilnhg.com/Code/LVK-for-NET/net-40/trunk/Files/… / a>
Legătura codului sursă este mortă. Puteți să-l actualizați, vă rog?
adăugat autor lasseschou, sursa

6 răspunsuri

Dacă aceasta este pentru instalare sau distribuție, ați luat în considerare utilizarea SDK-ului Windows Installer? Are abilitatea de a patch-uri fișiere binare.

http://msdn.microsoft.com/en-us /library/aa370578(VS.85).aspx

0
adăugat

Ar fi bine să verificați ce fac unii dintre ceilalți în acest spațiu și nu neapărat în C# arena.

Aceasta este o bibliotecă scrisă în C#

SVN are de asemenea un algoritm de difuzare binară și știu că există o implementare în Python, deși nu am reușit să o găsesc cu o căutare rapidă. S-ar putea să vă dau câteva idei despre unde să vă îmbunătățiți propriul algoritm

0
adăugat
SVN folosește algoritmul xdelta (cel puțin dintr-o privire la sursă)
adăugat autor Simon Buchan, sursa

Îmi pare rău că nu pot fi mai mult ajutor. M-aș gândi cu siguranță la xdelta pentru că am folosit-o de mai multe ori pentru a produce diferențe de calitate pe 600MB + fișiere ISO pe care le-am generat pentru distribuirea produselor noastre și se comportă foarte bine.

0
adăugat
Da, xdelta este bună. Cu toate acestea, funcționează pe ferestre relativ mici (100kb dacă nu mă înșel), dar cu o punere în practică a acesteia, aș putea modifica cu ușurință acest lucru pentru datele noastre. Mărimea ferestrei a fost aleasă pentru viteza de subversiune, dacă nu mă înșel, dar codul nostru poate rula cu ușurință un pic mai mult, atâta timp cât nu are nevoie să ia toată noaptea (ceea ce face actuala mea implementare).
adăugat autor Lasse Vågsæther Karl, sursa

bsdiff was designed to create very small patches for binary files. As stated on its page, it requires max(17*n,9*n+m)+O(1) bytes of memory and runs in O((n+m) log n) time (where n is the size of the old file and m is the size of the new file).

Implementarea inițială este în C, dar un port C# este descris aici și disponibil aici .

0
adăugat

Ați văzut VCDiff ? Face parte dintr-o bibliotecă Misc care pare a fi destul de activă (ultima versiune r259, 23 aprilie 2008). Nu am folosit-o, dar am crezut că merită menționat.

0
adăugat

Aceasta este o orientare aspră, dar următorul este pentru algoritmul rsync care poate fi folosit pentru a crea patch-urile binare.

http://rsync.samba.org/tech_report/tech_report.html

0
adăugat