Algoritmo per sistema di controllo sorgente?

Question

Ho bisogno di scrivere un semplice sistema di controllo del codice sorgente e mi chiedo quale algoritmo utilizzerei per le differenze tra i file?

Non voglio esaminare il codice sorgente esistente a causa di problemi di licenza. Ho bisogno di avere la licenza sotto MPL, quindi non posso guardare nessuno dei sistemi esistenti come CVS o Mercurial in quanto sono tutti con licenza GPL.

Solo per dare un po 'di background, ho solo bisogno di alcune funzioni davvero semplici - file binari in una cartella. nessuna sottocartella e ogni file si comporta come se fosse il proprio repository. Nessun metadato tranne alcune autorizzazioni.

Complessivamente cose davvero semplici, la mia unica preoccupazione è davvero come memorizzare solo le differenze di un file da revisione a revisione senza sprecare troppo spazio ma anche senza essere troppo inefficiente (Forse memorizzare una versione completa ogni X cambia, un po ' come i fotogrammi chiave nei video?)

Answer 1

Gli algoritmi Common Subsequence più lunghi sono il meccanismo principale utilizzato dagli strumenti diff-like e possono essere sfruttati da un sistema di controllo del codice sorgente.

"Delta inversi" sono un approccio comune all'archiviazione, poiché in primo luogo è necessario tornare indietro nel tempo dalla revisione più recente.

Answer 2

mi è stato effettivamente pensando a qualcosa di simile a questo l'altro giorno ... (strano, eh?)

Non ho una grande risposta per voi, ma io sono venuto alla conclusione che se fossi scrivere uno strumento diff file, che lo farei con un algoritmo (per trovare diff) che funzioni un po 'come il funzionamento di REGEXes con la loro golosità.

Come per la memorizzazione dei DIFF ... Se fossi in voi, invece di memorizzare i DIFF rivolti in avanti (cioè si inizia con il file originale e poi il computer 150 si diffonde contro di esso quando si lavora con la versione 151), utilizzare memorizzato DIFF per la cronologia, ma il tuo ultimo file è archiviato come versione completa. Se lo fai in questo modo, ogni volta che lavori con il file più recente (che è probabilmente il 99% delle volte), otterrai le migliori prestazioni.

Answer 3

Come cercare il codice sorgente di Subversion? la sua rilasciato sotto licenza Apache 2.0

Answer 4

Anche se fossile è GPL, l'algoritmo delta è basato su rsync e descritto here

Answer 5

Patience Diff è un buon algoritmo per trovare delta tra due file che possono avere un senso per le persone. Questo spesso dà risultati migliori rispetto all'algoritmo "longness common sequenceence" ingenuo, ma i risultati sono soggettivi.

Detto questo, molti sistemi di controllo di revisione moderni archiviano file completi in ogni fase e calcolano le differenze effettive in seguito, solo quando necessario. Per i file binari (che probabilmente non sono terribilmente comprimibili), è possibile che la memorizzazione dei delta inversi potrebbe essere in definitiva più efficiente.

Answer 6

Gene Myers ha scritto un buon documento An O(ND) Difference Algorithm and its Variations. Quando si tratta di confrontare le sequenze, Myers è l'uomo. Probabilmente dovresti anche leggere il lavoro di Walter Tichy su RCS; spiega come memorizzare un set di file memorizzando la versione più recente e le differenze.

Answer 7

L'idea di memorizzare dei delta (avanti o indietro) è classica rispetto al controllo della versione. Il problema è sempre stato, "quale delta immagazzini?"

Un sacco di sistemi di controllo sorgente memorizzano i delta come calcolati essenzialmente da" diff ", ad esempio il complemento a linee delle sequenze più lunghe comuni, ma è possibile calcolare i delta per tipi specifici di documenti in un modo specifico per tali documenti , per ottenere dei delta più piccoli (e spesso più comprensibili)

Per il codice sorgente dei linguaggi di programmazione, è possibile calcolare le distanze di Levenshtein rispetto alle strutture del programma.Un set di strumenti per fare essenzialmente questo per una varietà di linguaggi di programmazione popolari può essere trovato a Smart Differencer

Se si memorizzano file non di testo, è possibile trarre vantaggio dalla loro struttura per calcolare s delta maller.

Ovviamente, se ciò che si desidera è un'implementazione minima, è sufficiente archiviare l'immagine completa di ciascuna versione del file. I dischi di terabyte rendono questa soluzione praticabile se non carina. (Il file system PDP10 usato per farlo implicitamente).