Jabarkan Aplikasi dari Jarak Levenshtein

Dalam pencocokan string secara samar, tujuan yang ingin dicapai adalah untuk menemukan kecocokan antara sebuah string pendek dengan string lain di dalam sebuah teks yang lebih panjang; dengan anggapan hanya ada sedikit perbedaan diantara mereka. Misalnya, teks yang lebih panjang dapat berupa kamus, dan string yang pendek berasal dari masukan pengguna. Hal Ini memiliki berbagai aplikasi, misalnya untuk pemeriksa ejaan dan sistem koreksi untuk pengenalan karakter optik.

Jarak Levenshtein juga dapat dihitung antara dua string yang lebih panjang, tetapi biaya untuk menghitungnya secara kasar sebanding dengan hasil kali panjang kedua string, membuat hal ini tidak praktis. Jadi, ketika digunakan untuk membantu pencarian string samar dalam aplikasi seperti record linkage, string yang umum dibandingkan berukuran pendek untuk membantu meningkatkan kecepatan perbandingan.

Dalam linguistik, jarak Levenshtein digunakan sebagai metrik untuk mengukur jarak linguistik, atau seberapa berbedanya dua bahasa satu sama lain. Hal ini terkait dengan kejelasan timbal balik, semakin tinggi jarak linguistik, semakin rendah kejelasan timbal balik, dan semakin rendah jarak linguistik, semakin tinggi kejelasan timbal balik tersebut.

Hubungan dengan metrik jarak edit lainnya

Ada beberapa jarak edit lain yang populer, yang dihitung berdasarkan operasi-operasi edit yang diizinkan. Sebagai contoh:

jarak Damerau-Levenshtein memperbolehkan transposisi dua karakter yang bersebelahan, di samping penyisipan, penghapusan, dan substitusi;

jarak subbarisan terpanjang bersama (Inggris: longest common subsequence, LCS) hanya memungkinkan penyisipan dan penghapusan, namun tidak substitusi;

jarak Hamming hanya memungkinkan substitusi, oleh karena itu, ini hanya berlaku untuk string dengan panjang yang sama.

jarak Jaro hanya memungkinkan transposisi .

Jarak edit biasanya didefinisikan sebagai metrik yang dapat diukur parameternya yang dihitung dengan serangkaian operasi edit tertentu yang diizinkan, dan setiap operasi diberi biaya (mungkin tak terbatas). Hal ini selanjutnya digeneralisasikan oleh algoritma penyelarasan urutan DNA seperti algoritma Smith-Waterman, dengan biaya operasi bergantung pada tempat penerapannya.