Megtalálni a különbséget a Java két húrja között
1. Áttekintés
Ez a gyors bemutató megmutatja, hogyan kell keresse meg a különbséget két húr között Java használatával.
Ehhez az oktatóanyaghoz használni fogjuk két létező Java könyvtár és hasonlítsák össze a probléma megközelítését.
2. A probléma
Vegyük figyelembe a következő követelményt: meg akarjuk találni a különbséget a húrok között “ABCDELMN ”és„ ABCFGLMN ”.
Attól függően, hogy milyen formátumra van szükségünk a kimenetre, és figyelmen kívül hagyva az egyéni kód megírásának lehetőségét, két fő lehetőséget találtunk.
Az első a Google által írt könyvtár diff-match-patch. Mint állítják, a könyvtár kínál robusztus algoritmusok a sima szöveg szinkronizálásához.
A másik lehetőség a StringUtils osztály Apache Commons Lang-tól.
Fedezzük fel a kettő közötti különbségeket.
3. diff-match-patch
E cikk alkalmazásához az eredeti Google könyvtár egy villáját fogjuk használni, mivel az eredeti műtárgyait nem adjuk ki a Maven Centralon. Néhány osztálynév különbözik az eredeti kódbázistól, és jobban megfelel a Java szabványoknak.
Először is be kell építenünk a függőségét a sajátunkba pom.xml fájl:
org.bitbucket.cowwoc diff-match-patch 1.2
Vizsgáljuk meg ezt a kódot:
String text1 = "ABCDELMN"; String text2 = "ABCFGLMN"; DiffMatchPatch dmp = új DiffMatchPatch (); LinkedList diff = dmp.diffMain (text1, text2, false);
Ha a fenti kódot futtatjuk - ami a különbséget eredményezi szöveg1 és szöveg2 - a változó kinyomtatása diff ezt a kimenetet fogja produkálni:
[Diff (EQUAL, "ABC"), Diff (DELETE, "DE"), Diff (INSERT, "FG"), Diff (EQUAL, "LMN")]
Valójában a kimenet a listája Diff tárgyakat, mindegyik lény művelettípus alkotja (INSERT, TÖRÖL vagy EGYENLŐ), és a művelettel társított szövegrész.
A diff futtatásakor szöveg2 és text1, ezt az eredményt kapjuk:
[Diff (EQUAL, "ABC"), Diff (DELETE, "FG"), Diff (INSERT, "DE"), Diff (EQUAL, "LMN")]
4. StringUtils
Az osztály innen: Apache Commons van egy egyszerűbb megközelítés.
Először hozzáadjuk az Apache Commons Lang függőséget pom.xml fájl:
org.apache.commons commons-lang3 3.9
Aztán, hogy megtaláljuk a különbséget két szöveg között az Apache Commons-szal, felhívnánk StringUtils # Különbség:
StringUtils.difference (text1, text2)
Az előállított kimenet egyszerű karakterlánc lesz:
FGLMN
Míg a különbség futtatása szöveg2 és szöveg1 vissza fog térni:
DELMN
Ez az egyszerű megközelítés segítségével fokozhatóStringUtils.indexOfDifference (), melyik visszaadja aindex, amelynél a két húr kezd eltérni (esetünkben a húr negyedik karaktere). Ezt az indexet fel lehet használni szerezzünk egy sztringet az eredeti karakterláncból, megmutatni mi közös a két bemenet között, amellett, hogy mi más.
5. Teljesítmény
A referenciaértékeinkhez létrehozunk egy 10 000 karakterláncot tartalmazó listát 10 karakterből álló fix rész, utána következik 20 véletlenszerű ábécé karakter.
Ezután végignézzük a listát, és végrehajtjuk a különbséget a n elem és a n + 1 a lista eleme:
@Benchmark public int diffMatchPatch () {for (int i = 0; i <bemenetek.méret () - 1; i ++) {diffMatchPatch.diffMain (bemenetek.get (i), bemenetek.get (i + 1), hamis) ; } return inputok.size (); }
@Benchmark public int stringUtils () {for (int i = 0; i <bemenetek.size () - 1; i ++) {StringUtils.difference (bemenetek.get (i), bemenetek.get (i + 1)); } return inputok.size (); }
Végül futtassuk a referenciaértékeket, és hasonlítsuk össze a két könyvtárat:
Benchmark Mode Cnt Score Hibaegységek StringDiffBenchmarkUnitTest.diffMatchPatch avgt 50 130.559 ± 1.501 ms / op StringDiffBenchmarkUnitTest.stringUtils avgt 50 0.211 ± 0.003 ms / op
6. Következtetés
A tiszta végrehajtási sebességet tekintve StringUtils egyértelműen teljesítőbb, bár csak azt az alsztringet adja vissza, amelytől a két karakterlánc eltérni kezd.
Ugyanabban az időben, Diff-Match-Patch biztosítja a alaposabb összehasonlítási eredmény, a teljesítmény rovására.
Ezeknek a példáknak és kivonatoknak a megvalósítása elérhető a GitHubon.