Jarak Levenshtein

Jarak Levenshtein adalah metrik untuk mengukur perbedaan antara dua string atau, secara lebih umum, dua barisan hingga simbol. Dalam definisi klasik, nilainya adalah jumlah minimum operasi penyisipan, penghapusan, dan penggantian satu simbol yang diperlukan untuk mengubah satu barisan menjadi barisan lainnya, dengan biaya setiap operasi sama dengan 1.^[1]

Metrik ini dinamai menurut matematikawan Soviet Vladimir Levenshtein, yang memperkenalkannya pada 1965 dalam konteks teori kode untuk kesalahan penyisipan dan penghapusan.^[1] Jarak Levenshtein merupakan salah satu bentuk klasik dari jarak edit. Istilah jarak edit juga digunakan dalam arti yang lebih luas untuk keluarga ukuran yang dapat memakai himpunan operasi atau biaya operasi yang berbeda.^[2]

Jarak Levenshtein digunakan dalam pencocokan string secara samar, pemeriksaan dan koreksi ejaan, normalisasi teks, pencocokan nama, evaluasi pengenalan karakter optik (OCR), serta berbagai tugas pencocokan urutan lainnya.^[2]

Definisi

Misalkan

a = a 1 a 2 … a m {\displaystyle a=a_{1}a_{2}\dots a_{m}} $a=a_{1}a_{2}\dots a_{m}$

dan

b = b 1 b 2 … b n {\displaystyle b=b_{1}b_{2}\dots b_{n}} $b=b_{1}b_{2}\dots b_{n}$

adalah dua barisan. Definisikan D ( i , j ) {\displaystyle D(i,j)} $D(i,j)$ sebagai jarak Levenshtein antara awalan a 1 … a i {\displaystyle a_{1}\dots a_{i}} $a_{1}\dots a_{i}$ dan awalan b 1 … b j {\displaystyle b_{1}\dots b_{j}} $b_{1}\dots b_{j}$ .

Kondisi batasnya adalah

D ( i , 0 ) = i , D ( 0 , j ) = j . {\displaystyle D(i,0)=i,\qquad D(0,j)=j.} $D(i,0)=i,\qquad D(0,j)=j.$

Untuk i > 0 {\displaystyle i>0} $i>0$ dan j > 0 {\displaystyle j>0} $j>0$ ,

D ( i , j ) = min { D ( i − 1 , j ) + 1 , D ( i , j − 1 ) + 1 , D ( i − 1 , j − 1 ) + δ ( a i , b j ) , {\displaystyle D(i,j)=\min {\begin{cases}D(i-1,j)+1,\\D(i,j-1)+1,\\D(i-1,j-1)+\delta (a_{i},b_{j}),\end{cases}}} $D(i,j)=\min {\begin{cases}D(i-1,j)+1,\\D(i,j-1)+1,\\D(i-1,j-1)+\delta (a_{i},b_{j}),\end{cases}}$

dengan

δ ( a i , b j ) = { 0 , a i = b j , 1 , a i ≠ b j . {\displaystyle \delta (a_{i},b_{j})={\begin{cases}0,&a_{i}=b_{j},\\1,&a_{i}\neq b_{j}.\end{cases}}} $\delta (a_{i},b_{j})={\begin{cases}0,&a_{i}=b_{j},\\1,&a_{i}\neq b_{j}.\end{cases}}$

Tiga pilihan tersebut masing-masing mewakili penghapusan satu simbol dari barisan sumber, penyisipan satu simbol dari barisan tujuan, serta kecocokan atau penggantian simbol terakhir kedua awalan.^[3]

Jarak kedua barisan penuh adalah D ( m , n ) {\displaystyle D(m,n)} $D(m,n)$ .

Contoh

Jarak Levenshtein antara kata kartun dan gantung adalah 3. Salah satu urutan operasi minimum adalah:

kartun → gartun — mengganti k dengan g;
gartun → gantun — mengganti r dengan n;
gantun → gantung — menyisipkan g di akhir.

Dengan demikian,

d L ( kartun , gantung ) = 3. {\displaystyle d_{L}({\text{kartun}},{\text{gantung}})=3.} $d_{L}({\text{kartun}},{\text{gantung}})=3.$

Contoh yang menunjukkan perbedaannya dengan jarak Hamming adalah makan dan akang. Keduanya sama-sama berpanjang lima karakter. Jarak Hamming-nya 5 karena setiap posisi berbeda, sedangkan jarak Levenshtein-nya hanya 2: hapus m di awal dan sisipkan g di akhir.

Sifat dan batas

Dengan biaya satu untuk penyisipan, penghapusan, dan penggantian, jarak Levenshtein merupakan metrik: nilainya tidak negatif, bernilai nol jika dan hanya jika kedua barisan identik, bersifat simetris, dan memenuhi pertidaksamaan segitiga.^[2]

Untuk barisan dengan panjang m {\displaystyle m} $m$ dan n {\displaystyle n} $n$ ,

| m − n | ≤ d L ( a , b ) ≤ max ( m , n ) . {\displaystyle |m-n|\leq d_{L}(a,b)\leq \max(m,n).} $|m-n|\leq d_{L}(a,b)\leq \max(m,n).$

Batas bawah berasal dari kenyataan bahwa satu penyisipan atau penghapusan hanya mengubah panjang sebesar satu. Batas atas dapat dicapai dengan mengganti simbol pada bagian yang sama panjang, kemudian menyisipkan atau menghapus simbol yang tersisa.

Jika kedua barisan sama panjang, jarak Hamming merupakan batas atas bagi jarak Levenshtein:

d L ( a , b ) ≤ d H ( a , b ) . {\displaystyle d_{L}(a,b)\leq d_{H}(a,b).} $d_{L}(a,b)\leq d_{H}(a,b).$

Jika penggantian tidak diizinkan dan hanya penyisipan serta penghapusan yang diperbolehkan, jumlah operasi minimum berhubungan dengan panjang L {\displaystyle L} $L$ dari subbarisan bersama terpanjang:

d i n s / d e l ( a , b ) = m + n − 2 L . {\displaystyle d_{\mathrm {ins/del} }(a,b)=m+n-2L.} $d_{\mathrm {ins/del} }(a,b)=m+n-2L.$

Rumus ini tidak dapat diterapkan langsung pada jarak Levenshtein klasik, karena satu penggantian berbiaya 1 sedangkan satu penghapusan yang diikuti satu penyisipan berbiaya 2.^[3]

Perhitungan

Pemrograman dinamis

Metode klasik memakai pemrograman dinamis. Matriks berukuran ( m + 1 ) × ( n + 1 ) {\displaystyle (m+1)\times (n+1)} $(m+1)\times (n+1)$ menyimpan jarak antara seluruh pasangan awalan.^[3]

function JarakLevenshtein(s[1..m], t[1..n]):
    buat d[0..m, 0..n]

    for i = 0..m:
        d[i,0] = i

    for j = 0..n:
        d[0,j] = j

    for i = 1..m:
        for j = 1..n:
            if s[i] = t[j]:
                biaya = 0
            else:
                biaya = 1

            d[i,j] = minimum(
                d[i-1,j]   + 1,      // penghapusan s[i]
                d[i,j-1]   + 1,      // penyisipan t[j]
                d[i-1,j-1] + biaya   // kecocokan atau penggantian
            )

    return d[m,n]

Setiap sel d[i,j] berisi biaya minimum untuk mengubah i simbol pertama dari s menjadi j simbol pertama dari t. Mengisi seluruh matriks memerlukan waktu Θ ( m n ) {\displaystyle \Theta (mn)} $\Theta (mn)$ dan ruang Θ ( m n ) {\displaystyle \Theta (mn)} $\Theta (mn)$ .^[3]

Pengurangan memori

Jika hanya nilai jarak yang diperlukan, seluruh matriks tidak harus disimpan. Satu baris hanya bergantung pada baris sebelumnya dan bagian baris saat ini yang sudah dihitung. Dengan menggunakan barisan yang lebih pendek sebagai dimensi yang disimpan, ruang kerja dapat dikurangi menjadi O ( min ( m , n ) ) {\displaystyle O(\min(m,n))} $O(\min(m,n))$ .^[4]

Rekonstruksi operasi edit

Jika matriks penuh disimpan, salah satu urutan operasi edit yang optimal dapat direkonstruksi dengan menelusuri matriks secara terbalik mulai dari D ( m , n ) {\displaystyle D(m,n)} $D(m,n)$ . Beberapa sel pendahulu dapat menghasilkan nilai minimum yang sama, sehingga satu pasangan string dapat memiliki lebih dari satu urutan edit optimal.

Algoritma yang bergantung pada jarak

Jika jarak sebenarnya kecil dibandingkan panjang string, atau jika terdapat ambang maksimum yang telah diketahui, tidak selalu perlu menghitung seluruh matriks. Ukkonen mengembangkan algoritma eksak yang membatasi perhitungan pada pita yang relevan di sekitar diagonal matriks sehingga biaya komputasi bergantung pada jarak aktual atau ambang yang diizinkan.^[4]

Istilah approximate string matching dalam konteks ini berarti pencocokan yang mengizinkan sejumlah perbedaan, bukan berarti nilai jaraknya sendiri selalu dihitung secara aproksimatif.

Metode bit-paralel

Myers pada 1999 memperkenalkan algoritma berbasis bit-vector untuk pencocokan string secara samar. Sejumlah keadaan pemrograman dinamis dikemas ke dalam bit sebuah kata mesin dan diperbarui secara paralel dengan operasi bit.^[5]

Automata Levenshtein

Automata Levenshtein dapat digunakan untuk mengenali semua string yang berjarak edit tidak lebih dari suatu ambang k {\displaystyle k} $k$ terhadap string acuan tertentu. Schulz dan Mihov mengembangkan konstruksi automata untuk koreksi string yang memungkinkan pencarian berbasis ambang dilakukan secara efisien.^[6]

Aproksimasi dan kompleksitas komputasi

Untuk string dengan panjang n {\displaystyle n} $n$ , Andoni, Krauthgamer, dan Onak memberikan algoritma waktu hampir linear yang mengaproksimasi edit distance dalam faktor polilogaritmik: untuk setiap ε > 0 {\displaystyle \varepsilon >0} $\varepsilon >0$ tetap, faktor aproksimasinya adalah ( log ⁡ n ) O ( 1 / ε ) {\displaystyle (\log n)^{O(1/\varepsilon )}} $(\log n)^{O(1/\varepsilon )}$ dengan waktu n 1 + ε {\displaystyle n^{1+\varepsilon }} $n^{1+\varepsilon }$ .^[7]

Untuk perhitungan eksak pada dua string dengan panjang n {\displaystyle n} $n$ , Backurs dan Indyk menunjukkan batas bawah bersyarat: jika terdapat algoritma dengan waktu O ( n 2 − ε ) {\displaystyle O(n^{2-\varepsilon })} $O(n^{2-\varepsilon })$ untuk suatu konstanta ε > 0 {\displaystyle \varepsilon >0} $\varepsilon >0$ , maka Strong Exponential Time Hypothesis (SETH) akan salah.^[8] Hasil ini merupakan batas bawah bersyarat, bukan bukti tanpa syarat bahwa setiap model komputasi harus memerlukan waktu kuadratik.

Varian dan ukuran terkait

Jarak edit berbobot

Pada jarak edit berbobot, penyisipan, penghapusan, dan penggantian dapat memiliki biaya berbeda, dan biaya penggantian dapat bergantung pada pasangan simbol tertentu. Pemilihan biaya secara sembarang tidak otomatis mempertahankan seluruh sifat metrik; misalnya, biaya yang asimetris dapat merusak sifat simetri.^[2]

Damerau-Levenshtein menambahkan transposisi dua karakter yang bersebelahan sebagai operasi elementer.

Jarak Hamming dan LCS

Jarak Hamming menghitung posisi yang berbeda dan secara langsung berlaku pada dua barisan yang sama panjang. Sebaliknya, varian edit distance yang hanya mengizinkan penyisipan dan penghapusan berhubungan langsung dengan subbarisan bersama terpanjang melalui rumus m + n − 2 L {\displaystyle m+n-2L} $m+n-2L$ .

Panjang subbarisan bersama terpanjang bukan dengan sendirinya sebuah “jarak edit”; ia merupakan besaran yang dapat digunakan untuk memperoleh jarak ketika operasi yang diizinkan dibatasi pada penyisipan dan penghapusan.

Jarak Jaro

Jarak Jaro merupakan ukuran kesamaan string yang terkait, tetapi bukan jarak edit yang dapat dijelaskan sekadar sebagai “hanya mengizinkan transposisi”. Perhitungannya menggunakan jumlah karakter yang cocok dalam suatu jendela posisi dan jumlah transposisi di antara karakter yang cocok. Dalam studi Indonesia yang membandingkan Levenshtein, Hamming, Damerau-Levenshtein, dan Jaro-Winkler untuk identifikasi salah ketik, Jaro-Winkler memperoleh nilai mean average precision tertinggi pada himpunan uji 50 kata salah yang digunakan dalam penelitian tersebut.^[9]

Hasil tersebut berlaku untuk data dan rancangan eksperimen penelitian tersebut dan tidak berarti Jaro-Winkler selalu lebih baik daripada Levenshtein untuk setiap tugas.

Normalisasi

Jarak Levenshtein mentah cenderung memiliki rentang nilai yang lebih besar untuk string yang lebih panjang. Karena itu, sebagian aplikasi menggunakan bentuk yang dinormalisasi. Tidak ada satu definisi universal untuk “jarak Levenshtein ternormalisasi”.

Salah satu bentuk sederhana adalah

d N ( a , b ) = d L ( a , b ) max ( | a | , | b | ) , {\displaystyle d_{N}(a,b)={\frac {d_{L}(a,b)}{\max(|a|,|b|)}},} $d_{N}(a,b)={\frac {d_{L}(a,b)}{\max(|a|,|b|)}},$

dengan ukuran kesamaan yang dapat didefinisikan sebagai

s ( a , b ) = 1 − d N ( a , b ) . {\displaystyle s(a,b)=1-d_{N}(a,b).} $s(a,b)=1-d_{N}(a,b).$

Skema normalisasi lain juga digunakan dan tidak semuanya mempertahankan sifat metrik. Li dan Liu mengusulkan sebuah normalized edit distance khusus dan membahas sifat metriknya.^[10]

Aplikasi

Koreksi ejaan bahasa Indonesia

Dalam dokumen berbahasa Indonesia, jarak Levenshtein dapat digunakan untuk mencari kandidat kata yang hanya berbeda beberapa karakter dari bentuk yang salah ketik. Penelitian Universitas Brawijaya menggabungkan N-gram dan jarak Levenshtein untuk mengidentifikasi kesalahan penulisan kata dan menghasilkan kandidat koreksi pada dokumen bahasa Indonesia.^[11]

Penggunaan jarak string biasanya menjadi salah satu tahap dalam sistem koreksi, bukan seluruh sistem. Pemeringkatan kandidat dapat ditambah dengan frekuensi kata, N-gram, konteks, kamus, atau model bahasa. Studi perbandingan pada bahasa Indonesia juga menunjukkan bahwa metrik lain dapat mengungguli Levenshtein pada data tertentu.^[9]

Normalisasi kata tidak baku dan morfologi

Bahasa Indonesia memiliki variasi ragam baku dan tidak baku, terutama dalam percakapan dan media sosial. Sebuah tugas akhir di Institut Teknologi Bandung meneliti normalisasi kata tidak baku untuk asisten suara dengan membandingkan jarak Levenshtein, Jaro-Winkler, dan LCS. Dalam eksperimen tersebut, normalisasi berbasis Levenshtein mengungguli LCS sebesar 8,34 poin persentase pada data yang digunakan.^[12]

Morfologi juga memengaruhi pemrosesan bentuk tidak baku. Penelitian dari Universitas Amikom Yogyakarta dan Institut Sains & Teknologi AKPRIND membahas penggunaan jarak Levenshtein untuk membantu stemming kata berimbuhan tidak baku ketika bentuk akar mengalami perubahan kecil.^[13]

Contoh-contoh ini menunjukkan bahwa kedekatan karakter dapat membantu normalisasi, tetapi tidak menggantikan analisis morfologi dan konteks bahasa.

Pemrosesan dokumen bahasa Indonesia

Levenshtein juga digunakan sebagai komponen pencocokan dalam sistem pengolahan dokumen. Diana Permata Sari dari LIPI dan Ayu Purwarianti dari Institut Teknologi Bandung mengembangkan sistem ekstraksi kata kunci otomatis untuk artikel jurnal berbahasa Indonesia koleksi PDII LIPI. Setelah kandidat kata kunci dibobotkan dan dibandingkan dengan daftar kosakata terkontrol, algoritma Levenshtein digunakan untuk menemukan istilah terdekat ketika kecocokan persis tidak ditemukan.^[14]

Dalam eksperimen pada 33 artikel, penulis melaporkan peningkatan akurasi setelah memperbarui leksikon, daftar kata kunci, dan menambahkan metode kedekatan string Levenshtein.^[14]

Pencocokan nama dan variasi transliterasi

Variasi transliterasi dan ejaan nama merupakan kasus lain yang relevan di Indonesia. Penelitian di Telkom University menggunakan Levenshtein untuk mencocokkan variasi nama Arab dalam terjemahan bahasa Indonesia. Bentuk seperti Aisyah, Aisha, dan Aisah dapat merujuk pada nama yang sama tetapi memiliki ejaan berbeda.^[15]

Pada tugas seperti ini, jarak edit dapat menjadi salah satu ciri untuk mengukur kemiripan ortografis, tetapi kemiripan pengucapan dan aturan transliterasi dapat membutuhkan metode fonetis atau aturan khusus tambahan.

OCR dan aksara daerah

Pada OCR dan pengenalan urutan tulisan, Levenshtein sering digunakan bukan sebagai model pengenal visual, melainkan untuk mengevaluasi keluaran urutan terhadap teks acuan. Ukuran Character Error Rate (CER) dan Word Error Rate (WER) dapat diturunkan dari jumlah penggantian S {\displaystyle S} $S$ , penghapusan D {\displaystyle D} $D$ , dan penyisipan I {\displaystyle I} $I$ pada penyelarasan edit:

E R = S + D + I N , {\displaystyle \mathrm {ER} ={\frac {S+D+I}{N}},} $\mathrm {ER} ={\frac {S+D+I}{N}},$

dengan N {\displaystyle N} $N$ banyaknya unit dalam urutan acuan.

Dalam penelitian Indonesia tentang pengenalan urutan kata Aksara Jawa menggunakan CRNN dan CTC, hasil sistem dievaluasi dengan CER dan WER berbasis jarak Levenshtein. Penelitian tersebut memakai lebih dari 15.000 citra kata sintetis dan melaporkan akurasi karakter 99,71% pada data uji yang digunakan.^[16]

CER dan WER adalah ukuran galat yang dinormalisasi terhadap panjang urutan acuan; keduanya bukan fungsi matematika yang sama persis dengan jarak Levenshtein mentah yang simetris.

Bioinformatika

Dalam bioinformatika, jarak edit berhubungan erat dengan perbandingan dan penyelarasan urutan biologis. Penyisipan, penghapusan, dan penggantian merupakan model sederhana bagi perbedaan antara urutan DNA atau protein. Namun, algoritma penyelarasan biologis dalam praktik sering menggunakan matriks substitusi dan penalti gap yang lebih kaya daripada jarak Levenshtein berbiaya satu.^[17]

Karena itu, kompleksitas algoritma matriks Levenshtein klasik tidak dengan sendirinya berarti bahwa seluruh perbandingan urutan biologis panjang harus dilakukan dengan satu jenis heuristik tertentu; model dan algoritmanya bergantung pada tujuan penyelarasan.

Unit perbandingan dalam implementasi

Definisi matematika Levenshtein berlaku pada barisan simbol dan tidak menentukan apa yang harus dianggap sebagai satu “karakter” dalam perangkat lunak. Dalam teks Unicode, simbol yang dibandingkan dapat berupa byte, unit kode, titik kode Unicode, atau klaster grafem. Pemilihan unit yang berbeda dapat menghasilkan nilai jarak yang berbeda.

Unicode Standard Annex #15 mendefinisikan bentuk normalisasi seperti NFC dan NFD untuk menangani representasi yang ekuivalen secara kanonik.^[18] Unicode Standard Annex #29 mendefinisikan extended grapheme clusters sebagai pendekatan algoritmis terhadap karakter yang dipersepsikan pengguna.^[19]

Dalam aplikasi bahasa Indonesia, unit perbandingan juga bergantung pada tugas: koreksi ejaan biasanya bekerja pada karakter atau kata; analisis morfologi dapat bekerja pada bentuk kata; sedangkan evaluasi OCR Aksara Jawa dapat dilakukan pada karakter dan kata.^[16] Oleh sebab itu, implementasi perlu menjelaskan unit yang dibandingkan dan setiap normalisasi yang dilakukan sebelumnya.

Keterbatasan

Jarak Levenshtein mengukur biaya edit minimum, bukan kesamaan makna. Dua kata yang artinya sangat berbeda dapat hanya berjarak satu karakter, sedangkan dua bentuk yang secara semantik berkaitan dapat memiliki jarak karakter yang besar.

Dalam versi klasik, semua penggantian memiliki biaya yang sama. Metrik ini tidak secara otomatis memahami kemiripan fonetis, morfologi, konteks, variasi transliterasi, atau frekuensi kata. Pada koreksi ejaan bahasa Indonesia, studi komparatif menunjukkan bahwa pilihan ukuran string dapat memberikan hasil berbeda bergantung pada jenis kesalahan dan data uji.^[9]

Demikian pula, pada bentuk tidak baku atau kata berimbuhan, kedekatan ortografis hanya merupakan salah satu informasi yang dapat digunakan bersama stemming, kamus, atau model konteks.^[12]^[13]

Hasil praktis juga bergantung pada representasi simbol. Jarak pada tingkat karakter, kata, fonem, titik kode Unicode, dan klaster grafem merupakan penerapan berbeda dari konstruksi matematis yang sama dan tidak harus menghasilkan interpretasi yang sama.

Sejarah

Levenshtein memperkenalkan jarak ini pada 1965 dalam penelitian teori kode untuk koreksi kesalahan penyisipan dan penghapusan.^[1] Makalah aslinya tidak menyajikan matriks pemrograman dinamis dua dimensi dalam bentuk yang sekarang umum digunakan dalam pengajaran.

Wagner dan Fischer pada 1974 memberikan formulasi umum berbasis pemrograman dinamis untuk masalah transformasi string-ke-string.^[3] Ukkonen kemudian mengembangkan algoritma pencocokan samar yang komputasinya bergantung pada jarak atau ambang edit,^[4] sedangkan Myers pada 1999 memperkenalkan metode bit-vector yang berpengaruh untuk pencocokan pola secara samar.^[5]

Penelitian berikutnya mencakup automata Levenshtein,^[6] algoritma aproksimasi waktu hampir linear,^[7] serta hasil batas bawah bersyarat untuk perhitungan edit distance eksak.^[8]

Lihat pula

Referensi

1 2 3 V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Doklady Akademii Nauk SSSR, 163(4), 845–848, 1965. Terjemahan bahasa Inggris dimuat dalam Soviet Physics Doklady, 10(8), 707–710, 1966. Math-Net.
1 2 3 4 Gonzalo Navarro, “A guided tour to approximate string matching”, ACM Computing Surveys, 33(1), 31–88, 2001. doi:10.1145/375360.375365.
1 2 3 4 5 Robert A. Wagner dan Michael J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM, 21(1), 168–173, 1974. doi:10.1145/321796.321811.
1 2 3 Esko Ukkonen, “Algorithms for approximate string matching”, Information and Control, 64(1–3), 100–118, 1985. doi:10.1016/S0019-9958(85)80046-2.
1 2 Gene Myers, “A fast bit-vector algorithm for approximate string matching based on dynamic programming”, Journal of the ACM, 46(3), 395–415, 1999. doi:10.1145/316542.316550.
1 2 Klaus U. Schulz dan Stoyan Mihov, “Fast String Correction with Levenshtein-Automata”, International Journal on Document Analysis and Recognition, 5(1), 67–85, 2002. doi:10.1007/s10032-002-0082-8.
1 2 Alexandr Andoni, Robert Krauthgamer, dan Krzysztof Onak, “Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity”, Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS), 377–386, 2010. doi:10.1109/FOCS.2010.43.
1 2 Arturs Backurs dan Piotr Indyk, “Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)”, Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), 51–58, 2015. doi:10.1145/2746539.2746612.
1 2 3 Yeny Rochmawati dan Retno Kusumaningrum, “Studi Perbandingan Algoritma Pencarian String dalam Metode Approximate String Matching untuk Identifikasi Kesalahan Pengetikan Teks”, Jurnal Buana Informatika, 7(2), 125–134, 2016. doi:10.24002/jbi.v7i2.491.
↑ Yujian Li dan Bo Liu, “A Normalized Levenshtein Distance Metric”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(6), 1091–1095, 2007. doi:10.1109/TPAMI.2007.1078.
↑ Arina Indana Fahma, Imam Cholissodin, dan Rizal Setya Perdana, “Identifikasi Kesalahan Penulisan Kata (Typographical Error) pada Dokumen Berbahasa Indonesia Menggunakan Metode N-gram dan Levenshtein Distance”, Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer, 2(1), 2018. Garuda Kemdiktisaintek.
1 2 Rafi Dwi Rizqullah, “Normalisasi Kata Tidak Baku yang Tidak Disingkat dengan Jarak Perubahan”, tugas akhir, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung. Perpustakaan Digital ITB.
1 2 Rahardyan Bisma Setya Putra, Ema Utami, dan Suwanto Raharjo, “Optimalisasi Stemming Kata Berimbuhan Tidak Baku Pada Bahasa Indonesia Dengan Levenshtein Distance”, Jurnal Informatika: Jurnal Pengembangan IT, 3(2), 2018. laman jurnal.
1 2 Diana Permata Sari dan Ayu Purwarianti, “Ekstraksi Kata Kunci Otomatis untuk Dokumen Bahasa Indonesia: Studi Kasus Artikel Jurnal Ilmiah Koleksi PDII LIPI”, BACA: Jurnal Dokumentasi dan Informasi, 35(2), 139–147, 2014. BRIN.
↑ Fauzan Ramadhan, Moch. Arif Bijaksana, dan Bambang Ari Wahyudi, “Analisis Pencocokan Nama Arab Terjemahan Bahasa Indonesia Menggunakan Soundex dan Levenshtein Distance”, eProceedings of Engineering, 5(3), 2018. doi:10.34818/eoe.v5i3.7079.
1 2 Moch. Saefudin Yuhri, Ahmad Bagus Setiawan, dan Intan Nur Faridha, “Pengenalan Sekuens Kata Aksara Jawa Tanpa Segmentasi Menggunakan Arsitektur CRNN dan CTC”, Prosiding SEMNAS INOTEK, 10(3), 2975–2981, 2026. doi:10.29407/trcqtt87.
↑ Bonnie Berger, Michael S. Waterman, dan Yun William Yu, “Levenshtein Distance, Sequence Comparison and Biological Database Search”, IEEE Transactions on Information Theory, 67(6), 3287–3294, 2021. doi:10.1109/TIT.2020.2996543.
↑ Unicode Consortium, “Unicode Standard Annex #15: Unicode Normalization Forms”. Unicode Consortium.
↑ Unicode Consortium, “Unicode Standard Annex #29: Unicode Text Segmentation”. Unicode Consortium.

Bacaan lanjutan

V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Soviet Physics Doklady, 10(8), 707–710, 1966.
Robert A. Wagner dan Michael J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM, 21(1), 168–173, 1974.
Esko Ukkonen, “Algorithms for approximate string matching”, Information and Control, 64(1–3), 100–118, 1985.
Gene Myers, “A fast bit-vector algorithm for approximate string matching based on dynamic programming”, Journal of the ACM, 46(3), 395–415, 1999.
Gonzalo Navarro, “A guided tour to approximate string matching”, ACM Computing Surveys, 33(1), 31–88, 2001.

Pranala luar

Levenshtein distance — Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology (bahasa Inggris).
Levenshtein Distance — sumber rujukan berbahasa Inggris mengenai definisi, algoritma, sejarah, literatur ilmiah, dan penerapan jarak Levenshtein.

Definisi

Contoh

Sifat dan batas