streamalism.org

1. Oversigt

Denne hurtige vejledning viser, hvordan man gør det find forskellen mellem to strenge ved hjælp af Java.

Til denne vejledning skal vi bruge to eksisterende Java-biblioteker og sammenligne deres tilgange til dette problem.

2. Problemet

Lad os overveje følgende krav: Vi ønsker at finde forskellen mellem strengene “ABCDELMN ”og“ ABCFGLMN ”.

Afhængigt af hvilket format vi har brug for, at output skal være, og ignorerer muligheden for at skrive vores brugerdefinerede kode for at gøre det, fandt vi to tilgængelige hovedmuligheder.

Den første er et bibliotek skrevet af Google kaldet diff-match-patch. Som de hævder, tilbyder biblioteket robuste algoritmer til synkronisering af almindelig tekst.

Den anden mulighed er StringUtils klasse fra Apache Commons Lang.

Lad os undersøge forskellene mellem disse to.

3. diff-match-patch

Med henblik på denne artikel vil vi bruge en fork af det originale Google-bibliotek, da artefakterne til den originale ikke frigives på Maven Central. Nogle klassenavne adskiller sig også fra den oprindelige kodebase og overholder mere Java-standarderne.

Først skal vi medtage dens afhængighed i vores pom.xml fil:

 org.bitbucket.cowwoc diff-match-patch 1.2 

Lad os så overveje denne kode:

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

Hvis vi kører ovenstående kode - hvilket producerer forskellen mellem tekst1 og tekst2 - udskrivning af variablen diff vil producere dette output:

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

Faktisk vil output være en liste af Diff genstandehvor hver enkelt er dannet af en operationstype (INDSÆT, SLET eller LIGE), og den del af teksten, der er knyttet til operationen.

Når du kører diff mellem tekst2 og tekst1, vi får dette resultat:

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

4. StringUtils

Klassen fra Apache Commons har en mere forenklet tilgang.

Først vil vi tilføje Apache Commons Lang afhængighed til vores pom.xml fil:

 org.apache.commons commons-lang3 3.9 

Derefter, for at finde forskellen mellem to tekster med Apache Commons, ville vi ringe StringUtils # Forskel:

StringUtils.difference (text1, text2)

Den producerede produktion vil være en simpel streng:

FGLMN

Mens kører forskellen mellem tekst2 og tekst1 kommer tilbage:

DELMN

Denne enkle tilgang kan forbedres ved hjælp afStringUtils.indexOfDifference (), hvilken vil returnereindeks, hvor de to strenge begynder at adskille sig (i vores tilfælde strengens fjerde tegn). Dette indeks kan bruges til få et underlag af den originale streng, at vise hvad der er fælles mellem de to indgangeud over hvad der er anderledes.

5. Ydeevne

Til vores benchmarks genererer vi en liste med 10.000 strenge med en fast del på 10 tegn, efterfulgt af 20 tilfældige alfabetiske tegn.

Vi løber derefter gennem listen og udfører en forskel mellem n element og n + 1 element på listen:

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

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

Lad os endelig køre benchmarks og sammenligne de to biblioteker:

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

6. Konklusion

Med hensyn til ren eksekveringshastighed, StringUtils er tydeligvis mere performant, selvom det kun returnerer det substrat, hvorfra de to strenge begynder at adskille sig.

På samme tid, Diff-Match-Patch giver en mere grundigt sammenligningsresultatpå bekostning af ydeevne.

Implementeringen af ​​disse eksempler og uddrag findes på GitHub.