Bagaimana Cara Menghitung Jarak Levenshtein di Jawa?

1. Perkenalan

Dalam artikel ini, kami menjelaskan jarak Levenshtein, atau dikenal sebagai jarak Edit. Algoritme yang dijelaskan di sini dibuat oleh ilmuwan Rusia, Vladimir Levenshtein, pada tahun 1965.

Kami akan memberikan implementasi Java berulang dan rekursif dari algoritme ini.

2. Berapa Jarak Levenshtein?

Jarak Levenshtein adalah ukuran ketidaksamaan antara dua String. Secara matematis, dengan dua String x dan y , jarak mengukur jumlah minimum pengeditan karakter yang diperlukan untuk mengubah x menjadi y .

Biasanya tiga jenis pengeditan diperbolehkan:

  1. Penyisipan karakter c
  2. Penghapusan karakter c
  3. Substitusi karakter c dengan c '

Contoh: Jika x = 'shot' dan y = 'spot' , jarak edit antara keduanya adalah 1 karena 'shot' dapat diubah menjadi 'spot' dengan mengganti ' h ' menjadi ' p '.

Dalam sub-kelas tertentu dari masalah, biaya yang terkait dengan setiap jenis pengeditan mungkin berbeda.

Misalnya, lebih sedikit biaya untuk substitusi dengan karakter yang terletak di dekat keyboard dan lebih banyak biaya sebaliknya. Untuk kesederhanaan, kami akan mempertimbangkan semua biaya menjadi sama dalam artikel ini.

Beberapa aplikasi edit jarak adalah:

  1. Pemeriksa Ejaan - mendeteksi kesalahan ejaan dalam teks dan menemukan ejaan terdekat yang benar dalam kamus
  2. Deteksi Plagiarisme (lihat - Kertas IEEE)
  3. Analisis DNA - menemukan kesamaan antara dua urutan
  4. Pengenalan Ucapan (lihat - Riset Microsoft)

3. Perumusan Algoritma

Mari kita ambil dua Senar x dan y dengan panjang masing-masing m dan n . Kita dapat menunjukkan setiap String sebagai x [1: m] dan y [1: n].

Kita tahu bahwa pada akhir transformasi, kedua String akan memiliki panjang yang sama dan memiliki karakter yang cocok di setiap posisi. Jadi, jika kita mempertimbangkan karakter pertama dari setiap String, kita punya tiga opsi:

  1. Pengganti:
    1. Tentukan biaya ( D1 ) untuk mengganti x [1] dengan y [1] . Biaya langkah ini akan menjadi nol jika kedua karakter sama. Jika tidak, maka biayanya menjadi satu
    2. Setelah langkah 1.1, kita tahu bahwa kedua String dimulai dengan karakter yang sama. Karenanya total biaya sekarang akan menjadi jumlah dari biaya pada langkah 1.1 dan biaya untuk mengubah sisa String x [2: m] menjadi y [2: n]
  2. Insersi:
    1. Masukkan karakter di x agar cocok dengan karakter pertama di y , biaya langkah ini adalah satu
    2. Setelah 2.1, kami telah memproses satu karakter dari y . Oleh karena itu total biaya sekarang akan menjadi jumlah biaya pada langkah 2.1 (yaitu, 1) dan biaya untuk mengubah x [1: m] penuh menjadi y yang tersisa (y [2: n])
  3. Penghapusan:
    1. Hapus karakter pertama dari x , biaya langkah ini adalah satu
    2. Setelah 3.1, kami telah memproses satu karakter dari x , tetapi y penuh tetap diproses. Total biaya adalah jumlah dari biaya 3.1 (yaitu, 1) dan biaya mengubah sisa x menjadi y penuh

Bagian solusi selanjutnya adalah mencari tahu opsi mana yang harus dipilih dari ketiganya. Karena kita tidak tahu pilihan mana yang akan menghasilkan biaya minimum pada akhirnya, kita harus mencoba semua pilihan dan memilih yang terbaik.

4. Implementasi Rekursif Naif

Kita dapat melihat bahwa langkah kedua dari setiap opsi di bagian # 3 sebagian besar adalah masalah jarak edit yang sama tetapi pada sub-string dari Strings asli . Ini berarti setelah setiap iterasi kita berakhir dengan masalah yang sama tetapi dengan String yang lebih kecil .

Pengamatan ini adalah kunci untuk merumuskan algoritma rekursif. Hubungan perulangan dapat didefinisikan sebagai:

D (x [1: m], y [1: n]) = mnt {

D (x [2: m], y [2: n]) + Biaya Penggantian x [1] ke y [1],

D (x [1: m], y [2: n]) + 1,

D (x [2: m], y [1: n]) + 1

}

Kita juga harus mendefinisikan kasus dasar untuk algoritma rekursif kita, yang dalam kasus kita adalah ketika salah satu atau kedua String menjadi kosong:

  1. Jika kedua String kosong, maka jarak di antara keduanya adalah nol
  2. Ketika salah satu String kosong, maka jarak edit di antara mereka adalah panjang String lainnya , karena kita membutuhkan banyak penyisipan / penghapusan untuk mengubah satu ke yang lain:
    • Contoh: jika satu String adalah "anjing" dan String lainnya adalah "" (kosong), kita memerlukan tiga penyisipan dalam String kosong untuk menjadikannya "anjing" , atau kita perlu tiga penghapusan di "anjing" untuk membuatnya kosong. Oleh karena itu jarak edit di antara mereka adalah 3

Implementasi rekursif yang naif dari algoritma ini:

public class EditDistanceRecursive { static int calculate(String x, String y) { if (x.isEmpty()) { return y.length(); } if (y.isEmpty()) { return x.length(); } int substitution = calculate(x.substring(1), y.substring(1)) + costOfSubstitution(x.charAt(0), y.charAt(0)); int insertion = calculate(x, y.substring(1)) + 1; int deletion = calculate(x.substring(1), y) + 1; return min(substitution, insertion, deletion); } public static int costOfSubstitution(char a, char b) { return a == b ? 0 : 1; } public static int min(int... numbers) { return Arrays.stream(numbers) .min().orElse(Integer.MAX_VALUE); } }

Algoritma ini memiliki kompleksitas eksponensial. Pada setiap langkah, kami bercabang menjadi tiga panggilan rekursif, membangun kompleksitas O (3 ^ n) .

Di bagian selanjutnya, kita akan melihat bagaimana meningkatkannya.

5. Pendekatan Pemrograman Dinamis

Saat menganalisis panggilan rekursif, kami mengamati bahwa argumen untuk sub-masalah adalah sufiks dari Strings asli . Ini berarti hanya dapat ada m * n panggilan rekursif unik (di mana m dan n adalah sejumlah sufiks x dan y ). Oleh karena itu kompleksitas solusi optimal harus kuadrat, O (m * n) .

Mari kita lihat beberapa sub-masalah (menurut relasi pengulangan yang didefinisikan di bagian # 4):

  1. Sub-masalah dari D (x [1: m], y [1: n]) adalah D (x [2: m], y [2: n]), D (x [1: m], y [2 : n]) dan D (x [2: m], y [1: n])
  2. Sub-problems of D(x[1:m], y[2:n]) are D(x[2:m], y[3:n]), D(x[1:m], y[3:n]) and D(x[2:m], y[2:n])
  3. Sub-problems of D(x[2:m], y[1:n]) are D(x[3:m], y[2:n]), D(x[2:m], y[2:n]) and D(x[3:m], y[1:n])

In all three cases, one of the sub-problems is D(x[2:m], y[2:n]). Instead of calculating this three times like we do in the naive implementation, we can calculate this once and reuse the result whenever needed again.

This problem has a lot of overlapping sub-problems, but if we know the solution to the sub-problems, we can easily find the answer to the original problem. Therefore, we have both of the properties needed for formulating a dynamic programming solution, i.e., Overlapping Sub-Problems and Optimal Substructure.

We can optimize the naive implementation by introducing memoization, i.e., store the result of the sub-problems in an array and reuse the cached results.

Alternatively, we can also implement this iteratively by using a table based approach:

static int calculate(String x, String y) { int[][] dp = new int[x.length() + 1][y.length() + 1]; for (int i = 0; i <= x.length(); i++) { for (int j = 0; j <= y.length(); j++) { if (i == 0) { dp[i][j] = j; } else if (j == 0) { dp[i][j] = i; } else { dp[i][j] = min(dp[i - 1][j - 1] + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1, dp[i][j - 1] + 1); } } } return dp[x.length()][y.length()]; } 

This algorithm performs significantly better than the recursive implementation. However, it involves significant memory consumption.

This can further be optimized by observing that we only need the value of three adjacent cells in the table to find the value of the current cell.

6. Conclusion

Pada artikel ini, kami menjelaskan apa itu jarak Levenshtein dan bagaimana jarak itu dapat dihitung menggunakan pendekatan berbasis pemrograman rekursif dan dinamis.

Jarak Levenshtein hanyalah salah satu ukuran kesamaan string, beberapa metrik lainnya adalah Cosine Similarity (yang menggunakan pendekatan berbasis token dan menganggap string sebagai vektor), Koefisien Dadu, dll.

Seperti biasa, implementasi lengkap contoh dapat ditemukan di GitHub.