Revisi per 11 Februari 2021 07.50 sunting Kekavigi (bicara \| kontrib) Peninjau otomatis, Pengecualian blokir IP 1.794 suntingan Konten dalam edit ini adalah alih bahasa dari artikel Wikipedia Bahasa Inggris en:Levenshtein distance; Lihat sejarahnya untuk atribusi. Tag: VisualEditor ← Revisi sebelumnya		Revisi per 7 Maret 2021 08.50 sunting balikkan Kekavigi (bicara \| kontrib) Peninjau otomatis, Pengecualian blokir IP 1.794 suntingan k memperbaiki galat referensi kosong di →Variasi adaptif Tag: VisualEditor Revisi selanjutnya →
Baris 20: === Contoh === [[~~Berkas:Levenshtein_distance_animation.gif\|pra=https://wiki-indonesia.club/wiki/~~Berkas:Levenshtein_distance_animation.gif\|ka\|jmpl\|400x400px\|matriks jarak edit untuk dua kata dengan biaya substitusi sebesar 1 dan biaya penghapusan atau penyisipan sebesar 0,5.]] 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 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 ~~conference~~journal\|last=Andoni\|first=Alexandr\|last2=Krauthgamer\|first2=Robert\|last3=Onak\|first3=Krzysztof\|date=2010-05\|title=Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity\|url=https://ui.adsabs.harvard.edu/abs/2010arXiv1005.4033A/abstract\|journal=arXiv e-prints\|language=en\|pages=arXiv:1005.4033}}</ref> === 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 ~~conference~~journal\|last=Backurs\|first=Arturs\|last2=Indyk\|first2=Piotr\|date=2014-11\|title=Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)\|url=https://ui.adsabs.harvard.edu/abs/2014arXiv1412.0348B/abstract\|journal=arXiv e-prints\|language=en\|pages=arXiv:1412.0348}}</ref> == Referensi ==

Jarak Levenshtein: Perbedaan antara revisi