Trovare la differenza tra due stringhe in Java

1. Panoramica

Questo breve tutorial mostrerà come trovare la differenza tra due stringhe utilizzando Java.

Per questo tutorial, utilizzeremo due librerie Java esistenti e confronteremo i loro approcci a questo problema.

2. Il problema

Consideriamo il seguente requisito: vogliamo trovare la differenza tra le stringhe ABCDELMN” e “ABCFGLMN”.

A seconda del formato di cui abbiamo bisogno per l'output e ignorando la possibilità di scrivere il nostro codice personalizzato per farlo, abbiamo trovato due opzioni principali disponibili.

La prima è una libreria scritta da Google chiamata diff-match-patch. Come affermano, la libreria offre algoritmi robusti per la sincronizzazione del testo normale .

L'altra opzione è la classe StringUtils di Apache Commons Lang.

Esploriamo le differenze tra questi due.

3. diff-match-patch

Ai fini di questo articolo, useremo un fork della libreria originale di Google, poiché gli artefatti per quella originale non vengono rilasciati su Maven Central. Inoltre, alcuni nomi di classi sono diversi dalla base di codice originale e sono più aderenti agli standard Java.

Innanzitutto, dovremo includere la sua dipendenza nel nostro file pom.xml :

 org.bitbucket.cowwoc diff-match-patch 1.2 

Quindi, consideriamo questo codice:

String text1 = "ABCDELMN"; String text2 = "ABCFGLMN"; DiffMatchPatch dmp = new DiffMatchPatch(); LinkedList diff = dmp.diffMain(text1, text2, false);

Se eseguiamo il codice precedente, che produce la differenza tra text1 e text2 , la stampa della variabile diff produrrà questo output:

[Diff(EQUAL,"ABC"), Diff(DELETE,"DE"), Diff(INSERT,"FG"), Diff(EQUAL,"LMN")]

In effetti, l'output sarà un elenco di oggetti Diff , ciascuno formato da un tipo di operazione ( INSERT , DELETE o EQUAL ) e dalla porzione di testo associata all'operazione .

Quando si esegue la differenza tra text2 e text1, otterremo questo risultato:

[Diff(EQUAL,"ABC"), Diff(DELETE,"FG"), Diff(INSERT,"DE"), Diff(EQUAL,"LMN")]

4. StringUtils

La classe di Apache Commons ha un approccio più semplicistico .

Innanzitutto, aggiungeremo la dipendenza Apache Commons Lang al nostro file pom.xml :

 org.apache.commons commons-lang3 3.9 

Quindi, per trovare la differenza tra due testi con Apache Commons, chiameremo StringUtils # Difference :

StringUtils.difference(text1, text2)

L'output prodotto sarà una semplice stringa :

FGLMN

Considerando che l'esecuzione del diff tra text2 e text1 restituirà:

DELMN

Questo semplice approccio può essere migliorato utilizzando StringUtils.indexOfDifference () , che restituirà l' indice in cui le due stringhe iniziano a differire (nel nostro caso, il quarto carattere della stringa). Questo indice può essere utilizzato per ottenere una sottostringa della stringa originale , per mostrare ciò che è comune tra i due input , oltre a ciò che è diverso.

5. Prestazioni

Per i nostri benchmark, generiamo un elenco di 10.000 stringhe con una porzione fissa di 10 caratteri , seguita da 20 caratteri alfabetici casuali .

Quindi scorriamo l'elenco ed eseguiamo una differenza tra l' ennesimo elemento e l' n + 1 ° elemento dell'elenco:

@Benchmark public int diffMatchPatch() { for (int i = 0; i < inputs.size() - 1; i++) { diffMatchPatch.diffMain(inputs.get(i), inputs.get(i + 1), false); } return inputs.size(); }
@Benchmark public int stringUtils() { for (int i = 0; i < inputs.size() - 1; i++) { StringUtils.difference(inputs.get(i), inputs.get(i + 1)); } return inputs.size(); }

Infine, eseguiamo i benchmark e confrontiamo le due librerie:

Benchmark Mode Cnt Score Error Units StringDiffBenchmarkUnitTest.diffMatchPatch avgt 50 130.559 ± 1.501 ms/op StringDiffBenchmarkUnitTest.stringUtils avgt 50 0.211 ± 0.003 ms/op

6. Conclusione

In termini di pura velocità di esecuzione, StringUtils è chiaramente più performante , sebbene restituisca solo la sottostringa da cui le due stringhe iniziano a differire.

Allo stesso tempo, Diff-Match-Patch fornisce un risultato di confronto più completo , a scapito delle prestazioni.

L'implementazione di questi esempi e frammenti è disponibile su GitHub.