Recherche de la différence entre deux chaînes en Java

1. Vue d'ensemble

Ce tutoriel rapide montrera comment trouver la différence entre deux chaînes à l' aide de Java.

Pour ce didacticiel, nous allons utiliser deux bibliothèques Java existantes et comparer leurs approches à ce problème.

2. Le problème

Considérons l'exigence suivante: nous voulons trouver la différence entre les chaînes « ABCDELMN» et «ABCFGLMN».

En fonction du format dont nous avons besoin pour la sortie, et en ignorant la possibilité d'écrire notre code personnalisé pour le faire, nous avons trouvé deux options principales disponibles.

Le premier est une bibliothèque écrite par Google appelée diff-match-patch. Comme ils le prétendent, la bibliothèque propose des algorithmes robustes pour synchroniser du texte brut .

L'autre option est la classe StringUtils d'Apache Commons Lang.

Explorons les différences entre ces deux.

3. diff-match-patch

Pour les besoins de cet article, nous utiliserons un fork de la bibliothèque Google d'origine, car les artefacts de l'original ne sont pas publiés sur Maven Central. En outre, certains noms de classe sont différents de la base de code d'origine et sont plus conformes aux normes Java.

Tout d'abord, nous devrons inclure sa dépendance dans notre fichier pom.xml :

 org.bitbucket.cowwoc diff-match-patch 1.2 

Ensuite, considérons ce code:

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

Si nous exécutons le code ci-dessus - qui produit la différence entre text1 et text2 - l'impression de la variable diff produira cette sortie:

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

En fait, la sortie sera une liste d' objets Diff , chacun étant formé par un type d'opération ( INSERT , DELETE ou EQUAL ), et la partie de texte associée à l'opération .

Lors de l'exécution du diff entre text2 et text1, nous obtiendrons ce résultat:

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

4. StringUtils

La classe d' Apache Commons a une approche plus simpliste .

Tout d'abord, nous allons ajouter la dépendance Apache Commons Lang à notre fichier pom.xml :

 org.apache.commons commons-lang3 3.9 

Ensuite, pour trouver la différence entre deux textes avec Apache Commons, nous appellerions StringUtils # Difference :

StringUtils.difference(text1, text2)

La sortie produite sera une simple chaîne :

FGLMN

Alors que l'exécution du diff entre text2 et text1 retournera:

DELMN

Cette approche simple peut être améliorée en utilisant StringUtils.indexOfDifference () , qui renverra l' index auquel les deux chaînes commencent à différer (dans notre cas, le quatrième caractère de la chaîne). Cet index peut être utilisé pour obtenir une sous-chaîne de la chaîne d'origine , pour montrer ce qui est commun entre les deux entrées , en plus de ce qui est différent.

5. Performance

Pour nos benchmarks, nous générons une liste de 10 000 chaînes avec une partie fixe de 10 caractères , suivie de 20 caractères alphabétiques aléatoires .

Nous parcourons ensuite la liste et effectuons une différence entre le nème élément et le n + 1ème élément de la liste:

@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(); }

Enfin, exécutons les benchmarks et comparons les deux bibliothèques:

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. Conclusion

En termes de vitesse d'exécution pure, StringUtils est clairement plus performant , même s'il ne renvoie que la sous-chaîne à partir de laquelle les deux chaînes commencent à différer.

Dans le même temps, Diff-Match-Patch fournit un résultat de comparaison plus complet , au détriment des performances.

L'implémentation de ces exemples et extraits est disponible à l'adresse over sur GitHub.