Jarak Levenshtein

Dalam teori informasi, linguistik, dan ilmu komputer, jarak Levenshtein adalah metrik untuk mengukur perbedaan antara dua barisan. Secara informal, jarak Levenshtein antara dua kata adalah jumlah minimum perubahan karakter yang diperlukan untuk mengubah satu kata menjadi kata lainnya. Jarak ini dinamai dengan nama matematikawan Soviet Vladimir Levenshtein, yang mempertimbangkan jarak ini pada tahun 1965. Jarak levenshtein juga dapat disebut sebagai jarak edit, meskipun istilah tersebuh juga merujuk pada keluarga metrik jarak yang lebih umum yang dikenal secara kolektif sebagai jarak edit.