Jarak Levenshtein: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k perbaikan pranala untuk "pertidaksamaan segitiga" |
Fitur saranan suntingan: 2 pranala ditambahkan. |
||
| (Satu revisi perantara oleh satu pengguna lainnya tidak ditampilkan) | |||
Baris 32:
* Bernilai setidaknya sebesar perbedaan ukuran kedua string tersebut.
* Maksimum bernilai sebesar panjang dari string yang lebih panjang.
* Bernilai nol [[jika dan hanya jika]] kedua string sama.
* Jika kedua string berukuran sama, [[jarak Hamming]] adalah batas atas bagi jarak Levenshtein.
* Jarak Levenshtein antara dua string tidak pernah lebih besar dari jumlah jarak Levenshtein mereka dengan suatu string lain ([[pertidaksamaan segitiga]]).
Baris 43:
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.{{Butuh rujukan|date=January 2019}}
Dalam [[linguistik]], jarak Levenshtein digunakan sebagai metrik untuk mengukur [[jarak linguistik]], atau seberapa berbedanya dua bahasa satu sama lain.
== Hubungan dengan metrik jarak edit lainnya ==
Baris 53:
* [[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 [[Asam deoksiribonukleat|DNA]] seperti algoritma [[Algoritma Smith-Waterman|Smith-Waterman]], dengan biaya operasi bergantung pada tempat penerapannya.
== Implementasi ==
| |||