Menemukan Perbedaan Antara Dua Senar di Jawa

1. Ikhtisar

Tutorial singkat ini akan menunjukkan bagaimana menemukan perbedaan antara dua string menggunakan Java.

Untuk tutorial ini, kami akan menggunakan dua library Java yang ada dan membandingkan pendekatan mereka untuk masalah ini.

2. Masalah

Mari pertimbangkan persyaratan berikut: kami ingin mencari perbedaan antara string " ABCDELMN" dan "ABCFGLMN".

Bergantung pada format apa yang kita perlukan keluarannya, dan mengabaikan kemungkinan untuk menulis kode khusus kita untuk melakukannya, kami menemukan dua opsi utama yang tersedia.

Yang pertama adalah pustaka yang ditulis oleh Google yang disebut diff-match-patch. Seperti yang mereka klaim, pustaka tersebut menawarkan algoritme yang kuat untuk menyinkronkan teks biasa .

Pilihan lainnya adalah kelas StringUtils dari Apache Commons Lang.

Mari jelajahi perbedaan antara keduanya.

3. diff-match-patch

Untuk keperluan artikel ini, kami akan menggunakan garpu perpustakaan Google asli, karena artefak untuk yang asli tidak dirilis di Maven Central. Selain itu, beberapa nama kelas berbeda dari basis kode asli dan lebih mematuhi standar Java.

Pertama, kita perlu memasukkan ketergantungannya di file pom.xml kita :

 org.bitbucket.cowwoc diff-match-patch 1.2 

Kemudian, mari pertimbangkan kode ini:

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

Jika kita menjalankan kode di atas - yang menghasilkan perbedaan antara teks1 dan teks2 - mencetak variabel diff akan menghasilkan keluaran ini:

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

Faktanya, outputnya adalah daftar objek Diff , masing-masing dibentuk oleh jenis operasi ( INSERT , DELETE atau EQUAL ), dan bagian teks yang terkait dengan operasi tersebut .

Saat menjalankan perbedaan antara teks2 dan teks1, kita akan mendapatkan hasil ini:

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

4. StringUtils

Kelas dari Apache Commons memiliki pendekatan yang lebih sederhana .

Pertama, kami akan menambahkan dependensi Apache Commons Lang ke file pom.xml kami :

 org.apache.commons commons-lang3 3.9 

Kemudian, untuk menemukan perbedaan antara dua teks dengan Apache Commons, kami akan memanggil StringUtils # Difference :

StringUtils.difference(text1, text2)

Output yang dihasilkan berupa string sederhana :

FGLMN

Sedangkan menjalankan diff antara text2 dan text1 akan menghasilkan :

DELMN

Pendekatan sederhana ini dapat ditingkatkan menggunakan StringUtils.indexOfDifference () , yang akan mengembalikan indeks di mana dua string mulai berbeda (dalam kasus kami, karakter keempat dari string). Indeks ini dapat digunakan untuk mendapatkan substring dari string asli , untuk menunjukkan kesamaan antara dua input , selain apa yang berbeda.

5. Kinerja

Untuk tolok ukur kami, kami menghasilkan daftar 10.000 string dengan porsi tetap 10 karakter , diikuti oleh 20 karakter alfabet acak .

Kami kemudian melakukan perulangan melalui daftar dan melakukan perbedaan antara elemen ke - n dan elemen ke - n + ke-1 dari daftar:

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

Terakhir, mari kita jalankan tolok ukur dan bandingkan kedua pustaka:

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

Dalam hal kecepatan eksekusi murni, StringUtils jelas lebih berkinerja , meskipun hanya mengembalikan substring tempat kedua string mulai berbeda.

Pada saat yang sama, Diff-Match-Patch memberikan hasil perbandingan yang lebih menyeluruh , dengan mengorbankan kinerja.

Penerapan contoh dan cuplikan ini tersedia di GitHub.