Nájdenie rozdielu medzi dvoma reťazcami v Jave

1. Prehľad

Tento rýchly návod ukáže, ako na to nájdi rozdiel medzi dvoma reťazcami pomocou Javy.

Pre tento tutoriál budeme používať dve existujúce knižnice Java a porovnať ich prístupy k tomuto problému.

2. Problém

Uvažujme o nasledujúcej požiadavke: chceme nájsť rozdiel medzi reťazcami ABCDELMN “a„ ABCFGLMN “.

V závislosti od toho, aký formát potrebujeme, aby bol výstup, a ignorujúc možnosť napísania vlastného kódu, aby sme tak mohli urobiť, sme našli dve hlavné možnosti.

Prvou z nich je knižnica napísaná spoločnosťou Google s názvom diff-match-patch. Ako tvrdia, knižnica ponúka robustné algoritmy na synchronizáciu obyčajného textu.

Druhou možnosťou je StringUtils triedy od Apache Commons Lang.

Poďme preskúmať rozdiely medzi týmito dvoma.

3. diff-match-patch

Na účely tohto článku použijeme vidličku pôvodnej knižnice Google, pretože artefakty pôvodnej sa na Maven Central neuvoľňujú. Niektoré názvy tried sa tiež líšia od pôvodnej kódovej základne a viac zodpovedajú štandardom Java.

Najprv budeme musieť zahrnúť jeho závislosť do našej pom.xml spis:

 org.bitbucket.cowwoc diff-match-patch 1.2 

Potom zvážime tento kód:

Reťazec text1 = "ABCDELMN"; Reťazec text2 = "ABCFGLMN"; DiffMatchPatch dmp = nový DiffMatchPatch (); LinkedList diff = dmp.diffMain (text1, text2, false);

Ak spustíme vyššie uvedený kód - ktorý vytvorí rozdiel medzi text1 a text2 - tlač premennej rozdiel vyprodukuje tento výstup:

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

V skutočnosti bude výstupom a zoznam Rozdiel predmety, každá jedna bytosť tvorený typom operácie (VLOŽTE, ODSTRÁNIŤ alebo ROVNAKÝ) a časť textu spojená s operáciou.

Pri spustení rozdielu medzi text2 a text1, dostaneme tento výsledok:

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

4. StringUtils

Trieda z Apache Commonszjednodušenejší prístup.

Najskôr do našej pridáme závislosť Apache Commons Lang pom.xml spis:

 org.apache.commons commons-lang3 3.9 

Potom, aby sme našli rozdiel medzi dvoma textami s Apache Commons, zavolali by sme StringUtils # Rozdiel:

StringUtils.difference (text1, text2)

Produkovaný výstup bude jednoduchý reťazec:

FGLMN

Zatiaľ čo beží rozdiel medzi text2 a text1 vráti sa:

DELMN

Tento jednoduchý prístup je možné vylepšiť pomocouStringUtils.indexOfDifference (), ktoré vrátiindex, pri ktorom sa tieto dva reťazce začnú líšiť (v našom prípade štvrtý znak reťazca). Na tento index sa dá zvyknúť získať podreťazec pôvodného reťazca, ukázať čo je spoločné medzi týmito dvoma vstupmi, okrem toho, čo je iné.

5. Výkon

Pre naše referenčné hodnoty generujeme zoznam 10 000 reťazcov s pevná časť 10 znakov, nasledovaný 20 náhodných abecedných znakov.

Potom prechádzame zoznamom a robíme rozdiel medzi n-té prvok a n + 1 prvok zoznamu:

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

Nakoniec spustíme porovnávacie hodnoty a porovnáme tieto dve knižnice:

Benchmark Mode Cnt Score Error Units StringDiffBenchmarkUnitTest.diffMatchPatch avgt 50 130,559 ± 1,501 ms / op StringDiffBenchmarkUnitTest.stringUtils priem. 50 0,211 ± 0,003 ms / op

6. Záver

Pokiaľ ide o čistú rýchlosť vykonávania, StringUtils je jednoznačne výkonnejšia, hoci vráti iba podreťazec, od ktorého sa tieto dva reťazce začínajú líšiť.

Zároveň, Diff-Match-Patch poskytuje a dôkladnejší výsledok porovnania, na úkor výkonu.

Implementácia týchto príkladov a úryvkov je k dispozícii na serveri GitHub.


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