Generazione di patch binarie in C#

https://stackoverflow.com/questions/5831

08-06-2019
|

Domanda

Qualcuno ha, o è a conoscenza, di un'implementazione dell'algoritmo di generazione di patch binarie in C#?

Fondamentalmente, confronta due file (designati vecchio E nuovo) e produrre un file di patch che può essere utilizzato per aggiornare il file vecchio file in modo che abbia lo stesso contenuto del file nuovo file.

L'implementazione dovrebbe essere relativamente veloce e funzionare con file di grandi dimensioni.Dovrebbe mostrare tempi di esecuzione O(n) o O(logn).

I miei algoritmi tendono ad essere scadenti (veloci ma producono patch enormi) o lenti (producono patch piccole ma hanno un runtime O (n ^ 2)).

Qualsiasi consiglio o indicazione per l'implementazione sarebbe gradito.

Nello specifico, l'implementazione verrà utilizzata per mantenere sincronizzati i server per vari file di dati di grandi dimensioni per i quali disponiamo di un server master.Quando i file di dati del server principale cambiano, dobbiamo aggiornare anche diversi server fuori sede.

L'algoritmo più ingenuo che ho realizzato, che funziona solo per i file che possono essere conservati in memoria, è il seguente:

Prendi i primi quattro byte da vecchio file, chiamalo il chiave
Aggiungi quei byte a un dizionario, dove chiave -> posizione, Dove posizione è la posizione in cui ho preso quei 4 byte, 0 per cominciare
Salta il primo di questi quattro byte, prendine altri 4 (3 sovrapposti, 1 uno) e aggiungili al dizionario allo stesso modo
Ripetere i passaggi 1-3 per tutti i blocchi da 4 byte nel file vecchio file
Dall'inizio del nuovo file, prendi 4 byte e prova a cercarlo nel dizionario
Se trovato, trova la corrispondenza più lunga se ce ne sono diverse, confrontando i byte dei due file
Codifica un riferimento a quella posizione nel file vecchio file e salta il blocco corrispondente nel file nuovo file
Se non lo trova, codifica 1 byte dal file nuovo file e saltalo
Ripetere i passaggi 5-8 per il resto nuovo file

È un po' come la compressione, senza finestre, quindi utilizzerà molta memoria.È, tuttavia, abbastanza veloce e produce patch piuttosto piccole, purché si provi a ridurre al minimo l'output dei codici.

Un algoritmo più efficiente in termini di memoria utilizza le finestre, ma produce file di patch molto più grandi.

Ci sono più sfumature nell'algoritmo di cui sopra che ho saltato in questo post, ma posso pubblicare maggiori dettagli se necessario.Tuttavia, sento di aver bisogno di un algoritmo completamente diverso, quindi migliorare l'algoritmo di cui sopra probabilmente non mi porterà abbastanza lontano.

Modifica n. 1:Ecco una descrizione più dettagliata dell'algoritmo di cui sopra.

Innanzitutto, combina i due file in modo da avere un file grande.Ricorda il punto di taglio tra i due file.

In secondo luogo, fallo prendi 4 byte e aggiungi la loro posizione al dizionario passo per tutto nell'intero file.

In terzo luogo, da dove nuovo inizia il file, esegui il ciclo tentando di individuare una combinazione esistente di 4 byte e trova la corrispondenza più lunga.Assicurati di considerare solo le posizioni del vecchio file o di prima nel nuovo file rispetto a quanto ci troviamo attualmente.Ciò garantisce che possiamo riutilizzare il materiale sia nel vecchio che nel nuovo file durante l'applicazione della patch.

Modifica n. 2: Codice sorgente dell'algoritmo di cui sopra

Potresti ricevere un avviso relativo ai problemi del certificato.Non so come risolverlo, quindi per il momento accetta semplicemente il certificato.

Il sorgente utilizza molti altri tipi dal resto della mia libreria, quindi quel file non è tutto ciò che serve, ma questa è l'implementazione dell'algoritmo.

@lomaxx, ho provato a trovare una buona documentazione per l'algoritmo utilizzato in subversion, chiamato xdelta, ma a meno che tu non sappia già come funziona l'algoritmo, i documenti che ho trovato non riescono a dirmi cosa devo sapere.

O forse sono solo ottuso...:)

Ho dato una rapida occhiata all'algoritmo dal sito che hai fornito e sfortunatamente non è utilizzabile.Un commento dal file diff binario dice:

Trovare un insieme ottimale di differenze richiede tempo quadratico relativo alla dimensione dell'input, quindi diventa inutilizzabile molto rapidamente.

Le mie esigenze però non sono ottimali, quindi sto cercando una soluzione più pratica.

Grazie comunque per la risposta, ho aggiunto un segnalibro alle sue utilità se mai ne avessi bisogno.

Modifica n. 1:Nota, esaminerò il suo codice per vedere se riesco a trovare qualche idea e in seguito gli invierò anche un'e-mail con delle domande, ma ho letto il libro a cui fa riferimento e sebbene la soluzione sia buona per trovare soluzioni ottimali, è poco pratico nell'uso a causa dei requisiti di tempo.

Modifica n. 2:Darò sicuramente la caccia all'implementazione di Python xdelta.

Soluzione

Mi spiace, non potrei essere più d'aiuto.Continuerei sicuramente a guardare xdelta perché l'ho usato diverse volte per produrre differenze di qualità su file ISO da 600 MB+ che abbiamo generato per la distribuzione dei nostri prodotti e funziona molto bene.

Altri suggerimenti

bsdiff è stato progettato per creare patch molto piccole per file binari.Come indicato sulla sua pagina, richiede max(17*n,9*n+m)+O(1) byte di memoria e viene eseguito O((n+m) log n) tempo (dove n è la dimensione del vecchio file e m è la dimensione del nuovo file).

L'implementazione originale è in C, ma viene descritta una conversione in C# Qui e disponibile Qui.

Hai visto VCDiff?Fa parte di una libreria Misc che sembra essere abbastanza attiva (ultima versione r259, 23 aprile 2008).Non l'ho usato, ma ho pensato che valesse la pena menzionarlo.

Potrebbe valere la pena controllare cosa stanno facendo alcuni degli altri ragazzi in questo spazio e non necessariamente nemmeno nell'arena C#.

Questa è una libreria scritta in C#

SVN ha anche un algoritmo di confronto binario e so che esiste un'implementazione in Python anche se non sono riuscito a trovarlo con una ricerca rapida.Potrebbero darti alcune idee su dove migliorare il tuo algoritmo

Se si tratta di installazione o distribuzione, hai considerato l'utilizzo di Windows Installer SDK?Ha la capacità di applicare patch ai file binari.

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

Questa è una linea guida approssimativa, ma quella che segue riguarda l'algoritmo rsync che può essere utilizzato per creare le tue patch binarie.

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow