23
Desidero implementare il documento Word diverso, quali algoritmi richiede per implementare?Come funzionano gli algoritmi di diff documento?
A
risposta
3
la soluzione più ottimizzare di LCS è O(ND) Myer 's algorithm, e qui è un approccio algoritmico, che Ho usato per implementare documenti diff ufficio 2007. Link to algorithm paper
+4
non funziona. –
+2
Questo sta lavorando per me: http://www.xmailserver.org/diff2.pdf – Zamicol
15
Un diff è essenzialmente solo a solution per il longest common sub-sequence problem.
La soluzione ottimale richiede la conoscenza di dynamic programming quindi è un problema abbastanza complesso da risolvere.
Tuttavia, può anche essere fatto costruendo un suffisso-albero. Entrambi gli algoritmi sono delineati here.
+1
Generalmente si presuppone che il documento sia un flusso di caratteri o byte.Qui la domanda è comunque sul documento word. Prima di implementare un tale algoritmo è necessario porsi una domanda: "Ciao mondo" in blu 8pt Verdana uguale a "Ciao mondo" in rosso 10pt Arial, ecc. – quosoo
+1
Sì, ovviamente gli algoritmi di base richiedono una logica aggiuntiva da analizzare per tale differenze, ma il nucleo dell'algoritmo sarà sempre lo stesso. –
6
2
Come indicato da Ben S, il problema delle differenze può essere risolto in generale risolvendo il problema di sottosquadra più lungo comune. Più specificamente, lo Hunt-McIlroy algorithm è uno dei classici algoritmi che sono stati applicati al problema (ad esempio, nell'implementazione dell'utilità di Unix 'diff).
28
Bene, in generale, diff viene risolto in genere dallo Longest common subsequence problem. Vedere anche il "Algorithm" sezione alle voci di Wikipedia Diff:.
Il funzionamento del diff si basa sulla risolvere il più lungo comune sottosequenza problema
In questo problema, si hanno due sequenze di articoli :
a b c d f g h j q z a b c d e f g i j k r x y ze si desidera trovare la più lunga sequenza di elementi che è presente in Bot h sequenze originali nello stesso ordine . Cioè, si desidera trovare una nuova sequenza che può essere ottenuta da la prima sequenza eliminando alcuni elementi e dalla seconda sequenza da eliminando altri elementi. Si desidera anche questa sequenza fino a possibile. In questo caso è
a b c d f g j zdalla più lunga sottosequenza comune è solo un piccolo passo per ottenere l'output diff-like:
e h i q k r x y + - + - + + + +
Detto questo, tutto questo funziona bene con il testo base documenti. Poiché i documenti di Word sono effettivamente in un formato binario e includono molte informazioni e dati di formattazione, questo sarà molto più complesso. Idealmente, si potrebbe guardare in automazione di Word per sé in quanto ha la capacità di "diff" tra i documenti, come dettagliato qui:
Microsoft Word Tip: How to compare two documents for differences
+0
Ci sono due scopi per avere un'implementazione dell'algoritmo diff: per memorizzare solo le differenze tra le versioni, o per mostrare le differenze tra le versioni. Questi sono molto diversi (nessun gioco di parole). LCS è solitamente utilizzabile solo per mostrare le differenze, ma per una conservazione ottimale sono necessari algoritmi più avanzati. Ad esempio, se si taglia una porzione grande di una sezione del documento e la si incolla in un'altra sezione, un buon algoritmo di archiviazione lo rileva e non lo memorizza come "hey, molti nuovi dati sono appena apparsi qui". –
+2
@Lasse - Concordato. Dal momento che il richiedente la domanda originale stava parlando di documenti di Word, ho pensato che sarebbero stati più interessati al lato "visivo" del lato diffidente, piuttosto che al lato dello storage. Tuttavia, hai ragione sul lato dello storage, dovresti esaminare Codifica/Compressione Delta (http://en.wikipedia.org/wiki/Delta_encoding) ecc. Il link alla carta – CraigTP
Problemi correlati
- 1. algoritmi Diff
- 2. Come funzionano solitamente gli algoritmi di consigli automatici?
- 3. Come funzionano 20 domande sugli algoritmi AI?
- 4. Come posso elencare gli algoritmi Cipher disponibili?
- 5. Come funzionano gli stream bufferizzati?
- 6. Come funzionano gli alberi Suffix?
- 7. Come gli Intenti funzionano internamente?
- 8. Come funzionano gli indici compositi?
- 9. Python: come funzionano gli insiemi
- 10. Come funzionano gli operatori boost?
- 11. Come funzionano gli assassini di attività?
- 12. Come funzionano gli editor di testo in linea?
- 13. Gli "algoritmi" esistono nella programmazione funzionale?
- 14. Come funzionano gli interrupt su Intel 8080?
- 15. Confronta algoritmi di similarità
- 16. Come funzionano gli attributi del metodo Perl?
- 17. Come gli stati astratti funzionano in ionico?
- 18. Come funzionano gli eventi virtuali in C#?
- 19. Come funzionano gli overlay Turbo Pascal?
- 20. Come funzionano gli appunti in Windows?
- 21. Come funzionano gli itinerari in FOSRestBundle?
- 22. Come funzionano gli interpreti/motori JavaScript?
- 23. Come funzionano gli enumeratori in Ruby 1.9.1?
- 24. Come funzionano gli aggiornamenti in tempo reale?
- 25. Scelta di random_state per gli algoritmi di sklearn
- 26. Come riscrivere un ciclo annidato usando gli algoritmi C++ STL?
- 27. Gli skin DevExpress non funzionano
- 28. Gli esempi MATLAB non funzionano
- 29. Come funzionano gli stream di log di Winston?
- 30. Gli script di PowerShell funzionano con Mono?
Lo utilizzerai per mostrare * le differenze o * memorizzare * le differenze in modo ottimale? –