Binêre pleister-generasie in C #

StackOverflow https://stackoverflow.com/questions/5831

  •  08-06-2019
  •  | 
  •  

Vra

Is daar iemand het, of weet van 'n binêre pleister generasie algoritme implementering in C #?

In beginsel, vergelyk twee lêers (aangewys oud en nuwe ), en 'n pleister lêer wat gebruik kan word om die oud lêer op te gradeer produseer om dieselfde inhoud het as die nuwe lêer.

Die implementering sal relatief vinnig te wees, en werk met 'n groot lêers. Dit moet O (n) of O (logn) Runtimes uitstal.

My eie algoritmes is geneig om óf slegte (vinnig, maar produseer groot kolle) of stadig (produseer klein kolle maar het O (n ^ 2) runtime).

Enige raad of wenke vir implementering sal lekker wees.

Spesifiek, sal die implementering gebruik word om bedieners in sync te hou vir verskeie groot gegevensbestanden dat ons 'n meester-bediener vir. Wanneer die meester bediener gegevensbestanden verander, moet ons 'n paar off-site bedieners werk as goed.

Die mees naïewe algoritme ek gemaak het, wat net werk vir lêers wat in die geheue gehou kan word, is soos volg:

  1. Gryp die eerste vier grepe uit die oud lêer, noem dit die sleutel
  2. Voeg diegene grepe om 'n woordeboek, waar sleutel -> posisie , waar posisie is die posisie waar ek gegryp diegene 4 grepe, 0 te begin met
  3. Slaan die eerste van hierdie vier grepe, gryp 'n ander 4 (3 oorvleuel, 1 een), en by die woordeboek op dieselfde manier
  4. Herhaal stappe 1-3 vir al 4-byte blokke in die oud lêer
  5. Van die begin van die nuwe lêer, gryp 4 grepe, en poging om dit te kyk in die woordeboek
  6. As bevind, vind die langste wedstryd as daar is verskeie, deur dit te vergelyk grepe uit die twee lêers
  7. enkodeer 'n verwysing na daardie plek in die oud lêer, en slaan die pas blok in die nuwe lêer
  8. Indien nie gevind, enkodeer 1 byte van die nuwe lêer, en slaan dit
  9. Herhaal stappe 5-8 vir die res van die nuwe lêer

Dit is 'n bietjie soos kompressie, sonder windows, so dit sal 'n baie van die geheue gebruik. Dit is egter redelik vinnig, en produseer baie klein kolle, so lank as ek probeer om die kodes uitset minimale maak.

'n meer geheue-doeltreffende algoritme gebruik windows, maar produseer baie groter kol lêers.

Daar is meer nuanses aan die bokant algoritme wat ek oorgeslaan in hierdie post, maar ek kan meer besonderhede plaas indien nodig. Ek het egter voel dat ek 'n ander algoritme heeltemal nodig, so die verbetering van die bogenoemde algoritme is waarskynlik nie van plan my ver genoeg te kry.

Edit # 1 :. Hier is 'n meer gedetailleerde beskrywing van die bogenoemde algoritme

In die eerste plek kombineer die twee lêers, sodat jy 'n groot lêer. Onthou die cut-punt tussen die twee lêers.

In die tweede plek doen wat gryp 4 grepe en voeg hul posisie om die woordeboek stap vir alles in die hele lêer.

In die derde plek, vanwaar die nuwe lêer begin, doen die lus met 'n poging om 'n bestaande kombinasie van 4 grepe op te spoor, en vind die langste wedstryd. Maak seker dat ons net kyk na posisies van die ou lêer, of van vroeër in die nuwe lêer as ons tans by . Dit verseker dat ons materiaal kan onthou in beide die ou en die nuwe lêer tydens kol aansoek.

Edit # 2 : Bronkode om die bogenoemde algoritme

Jy kan 'n waarskuwing oor die sertifikaat met 'n paar probleme kry. Ek weet nie hoe om op te los wat so vir die oomblik net die sertifikaat aanvaar.

Die bron gebruik baie van die ander vorme van die res van my biblioteek sodat lêer is nie al wat dit neem, maar dit is die algoritme implementering.

@lomaxx, het ek probeer om 'n goeie dokumentasie vir die algoritme gebruik in ondermyning, genoem xdelta vind, maar tensy jy reeds weet hoe die algoritme werk, tHy dokumenteer Ek het gevind versuim om my te vertel wat ek nodig het om te weet.

Of miskien is ek net digte ...:)

Ek het 'n vinnige blik op die algoritme van die webwerf wat jy het, en dit is ongelukkig nie bruikbaar. A kommentaar van die binêre diff lêer sê:

  

Dit vind van 'n optimale stel verskille vereis kwadratiese tyd relatief tot die insette grootte, so dit raak onbruikbaar baie vinnig.

My behoeftes is nie optimaal al is, so ek is op soek na 'n meer praktiese oplossing.

Dankie vir die antwoord egter bygevoeg 'n boekmerk na sy utilities as ek hulle ooit nodig.

Edit # 1 : Let ek sal kyk na sy kode om te sien of ek 'n paar idees kan vind, en ek sal ook 'n e-pos stuur hom later met vrae, maar ek het gelees dat boek verwys hy en al die oplossing is goed vir die vind van optimale oplossings, is dit onprakties in gebruik as gevolg van die tyd vereistes.

Edit # 2 :. Ek sal beslis jag af die luislang xdelta implementering

Was dit nuttig?

Oplossing

Jammer ek kon nie meer hulp wees. Ek sou beslis hou op soek na xdelta omdat ek dit 'n paar keer gebruik het om gehalte ewenaars op 600MB + ISO lêers ons gegenereer vir die verspreiding van ons produkte te produseer en dit verrig baie goed.

Ander wenke

bsdiff is ontwerp om baie klein kolle vir binêre lêers te skep. Soos uiteengesit op sy bladsy, dit vereis max(17*n,9*n+m)+O(1) grepe van die geheue en loop in O((n+m) log n) tyd (waar n is die grootte van die ou lêer en m is die grootte van die nuwe lêer).

Die oorspronklike implementering is in C, maar 'n C # port beskryf hier en beskikbaar rel="nofollow">.

Het jy al gesien VCDiff ? Dit is deel van 'n Verskeidenheid biblioteek wat blyk te wees redelik aktief wees (laaste release R259, 23 April 2008). Ek het nie gebruik nie, maar het gedink dit was die moeite werd.

Dit mag dalk die moeite werd wees uitcheck wat sommige van die ander ouens doen in hierdie ruimte en nie noodwendig in die C # arena nie.

Dit is 'n biblioteek geskryf in C #

SVN het ook 'n binêre verskil algoritme en ek weet daar is 'n implementering in python hoewel ek dit nie kon kry met 'n vinnige soektog. Hulle kan gee jou 'n paar idees oor waar om jou eie algoritme te verbeter

As dit vir die installasie of verspreiding, het jy al oorweeg die gebruik van die Windows Installer SDK? Dit het die vermoë om binêre lêers te lap.

http://msdn.microsoft.com/ en-ons / library / aa370578 (VS.85) Aspx

Dit is 'n rowwe riglyn, maar die volgende is vir die rsync algoritme wat gebruik kan word om jou binêre kolle te skep.

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

Gelisensieer onder: CC-BY-SA met toeskrywing
Nie verbonde aan StackOverflow
scroll top