Abbiamo un requisito nel progetto che dobbiamo confrontare due testi (update1, update2) e trovare un algoritmo per definire quante parole e quante frasi sono cambiate.Algoritmo di confronto del testo
Esistono algoritmi che posso utilizzare? Non sto nemmeno cercando il codice. Se conosco l'algoritmo, posso codificarlo in java. Grazie.
In genere ciò si ottiene trovando lo Longest Common Subsequence (comunemente chiamato problema LCS). Ecco come funzionano gli strumenti come diff. Naturalmente, diff è uno strumento orientato alla linea e sembra che le tue esigenze siano in qualche modo diverse. Tuttavia, presumo che tu abbia già costruito un modo per confrontare parole e frasi.
Una specie di variante diff potrebbe essere utile, ad esempio, wdiff
Se si decide di inventare il proprio algoritmo, si sta andando ad avere per affrontare la situazione in cui è stata inserita una frase. Per esempio, per i seguenti due documenti:
The men are bad. I hate the men
e
The men are bad. John likes the men. I hate the men
Lo strumento dovrebbe essere in grado di guardare avanti a riconoscere che nella seconda, I hate the men non è stato sostituito da John likes the men ma invece è intatto e una nuova frase inserita prima di esso. cioè dovrebbe riportare l'inserimento di una frase, non il cambio di quattro parole seguito da una nuova frase.
L'algoritmo specifico utilizzato da diff e dalla maggior parte delle utilità di confronto è Eugene Myer's An O(ND) Difference Algorithm and Its Variations. È disponibile un'implementazione Java disponibile nel pacchetto java-diff-utils.
An O(NP) Sequence Comparison Algorithm utilizzato dal motore di diff di subversion.
Per vostra informazione, ci sono implementazioni con vari linguaggi di programmazione da solo nella pagina seguente di github.
La difficoltà viene quando si confrontano file di grandi dimensioni in modo efficiente e con buone prestazioni. Ho quindi implementato una variazione di Myers O (ND) algoritmo diff - che svolge abbastanza bene e preciso (e supporta filtro basato su espressioni regolari):
algoritmo può essere testato qui: becke.ch compare tool web application
e un po ' ulteriori informazioni sulla home page: becke.ch compare tool
Di seguito sono riportati due documenti che descrivono altri algoritmi di confronto testuale che dovrebbero generare in genere "migliore" (ad es.piccole più significative) differenze:
Il primo documento cita il secondo e cita questo circa il suo algoritmo:
Heckel [3] ha sottolineato simile problemi con le tecniche LCS e proposto un algoritmo lineare-lime per rilevare i movimenti del blocco. L'algoritmo esegue adeguatamente se ci sono pochi simboli duplicati nelle stringhe. Tuttavia, l'algoritmo fornisce risultati scadenti altrimenti. Ad esempio, date le due stringhe aabb e bbaa, l'algoritmo di Heckel non riesce a rilevare alcuna sottostringa comune.
Il primo lavoro è stato menzionato in this answer e la seconda nel this answer, sia alla domanda simile SO:
http://stackoverflow.com/questions/65199/ c-sharp-compare-algorithms –
http://neil.fraser.name/software/diff_match_patch/myers.pdf –