Jarak Levenshtein: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Konten dalam edit ini adalah alih bahasa dari artikel Wikipedia Bahasa Inggris en:Levenshtein distance; Lihat sejarahnya untuk atribusi. |
Fitur saranan suntingan: 2 pranala ditambahkan. |
||
| (3 revisi perantara oleh 2 pengguna tidak ditampilkan) | |||
Baris 20:
=== Contoh ===
[[
Sebagai contoh, jarak Levenshtein antara kata "kartun" dan kata "gantung" adalah 3, karena tiga pengeditan berikut mengubah satu kata ke kata yang lain, dan tidak ada cara untuk melakukannya dengan kurang dari tiga pengeditan:
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 ([[
Sebuh contoh bagi jarak Levenshtein antara dua string dengan panjang yang sama, bernilai lebih kecil dari jarak Hamming, adalah pasangan kata "makan" dan "akang". Di sini jarak Levenshtein sama dengan 2 (hapus huruf "m" di awal dan sisipkan "g" di akhir), sedangkan [[jarak Hamming]] mereka sebesar 5.
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 ==
Baris 230:
: <math>(\log n)^{O(1/\varepsilon)}</math>
di mana {{Math|''ε'' > 0}} adalah parameter bebas yang dapat diatur, dalam kompleksitas waktu {{Math|''O''(n<sup>1 + ''ε''</sup>)}}.<ref>{{Cite
=== Kompleksitas komputasi ===
Dapat dibuktikan bahwa jarak Levenshtein dari dua string dengan panjang {{Mvar|n}} tidak dapat dihitung dalam waktu {{Math|''O''(n<sup>2 - ''ε''</sup>)}}, untuk setiap ε yang lebih besar dari nol kecuali hipotesis ''strong exponential time'' salah.<ref>{{Cite
== Referensi ==
| |||