Het verschil vinden tussen twee strings in Java

1. Overzicht

Deze korte tutorial laat zien hoe zoek het verschil tussen twee snaren met behulp van Java.

Voor deze tutorial gaan we gebruiken twee bestaande Java-bibliotheken en vergelijk hun benaderingen van dit probleem.

2. Het probleem

Laten we eens kijken naar de volgende vereiste: we willen het verschil tussen de strings vinden ABCDELMN ”en“ ABCFGLMN ”.

Afhankelijk van het formaat dat we de uitvoer moeten hebben, en de mogelijkheid negeren om onze aangepaste code hiervoor te schrijven, hebben we twee hoofdopties gevonden.

De eerste is een door Google geschreven bibliotheek genaamd diff-match-patch. Zoals ze beweren, biedt de bibliotheek robuuste algoritmen voor het synchroniseren van platte tekst.

De andere optie is de StringUtils class van Apache Commons Lang.

Laten we de verschillen tussen deze twee onderzoeken.

3. diff-match-patch

Voor de toepassing van dit artikel gebruiken we een splitsing van de originele Google-bibliotheek, aangezien de artefacten voor de originele niet op Maven Central worden vrijgegeven. Ook zijn sommige klassenamen verschillend van de originele codebase en zijn ze meer in overeenstemming met de Java-standaarden.

Ten eerste moeten we de afhankelijkheid ervan opnemen in onze pom.xml het dossier:

 org.bitbucket.cowwoc diff-match-patch 1.2 

Laten we dan eens naar deze code kijken:

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

Als we de bovenstaande code uitvoeren - die produceert het verschil tussen tekst1 en tekst2 - het afdrukken van de variabele diff zal deze output produceren:

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

In feite zal de uitvoer een lijst van Diff voorwerpen, elk wezen gevormd door een bewerkingstype (INVOEGEN, VERWIJDEREN of GELIJK), en het gedeelte van de tekst dat aan de bewerking is gekoppeld.

Bij het uitvoeren van het verschil tussen tekst2 en tekst1, we krijgen dit resultaat:

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

4. StringUtils

De klas van Apache Commons heeft een meer simplistische benadering.

Eerst zullen we de Apache Commons Lang-afhankelijkheid toevoegen aan onze pom.xml het dossier:

 org.apache.commons commons-lang3 3.9 

Om vervolgens het verschil te vinden tussen twee teksten met Apache Commons, zouden we bellen StringUtils # Verschil:

StringUtils.difference (tekst1, tekst2)

De geproduceerde output zal een simpele string zijn:

FGLMN

Terwijl het verschil tussen tekst2 en tekst1 zal terugkeren:

DELMN

Deze eenvoudige aanpak kan worden verbeterd metStringUtils.indexOfDifference (), welke retourneert deindex waarop de twee strings beginnen te verschillen (in ons geval het vierde teken van de string). Deze index kan worden gebruikt om haal een substring op van de originele string, laten zien wat is gemeenschappelijk tussen de twee ingangen, naast wat er anders is.

5. Prestaties

Voor onze benchmarks genereren we een lijst van 10.000 strings met een vast gedeelte van 10 karakters, gevolgd door 20 willekeurige alfabetische tekens.

We doorlopen vervolgens de lijst en voeren een diff uit tussen de n element en de n + 1ste element van de lijst:

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

Laten we tot slot de benchmarks uitvoeren en de twee bibliotheken vergelijken:

Benchmarkmodus Cnt Score Fouteenheden StringDiffBenchmarkUnitTest.diffMatchPatch gemiddelde 50 130.559 ± 1.501 ms / op StringDiffBenchmarkUnitTest.stringUtils gemiddelde 50 0.211 ± 0.003 ms / op

6. Conclusie

In termen van pure uitvoeringssnelheid, StringUtils is duidelijk meer performant, hoewel het alleen de subtekenreeks retourneert waarvan de twee strings beginnen te verschillen.

Tegelijkertijd, Diff-Match-Patch verschaft een grondiger vergelijkingsresultaat, ten koste van de prestaties.

De implementatie van deze voorbeelden en fragmenten is beschikbaar op GitHub.


$config[zx-auto] not found$config[zx-overlay] not found