Lihat sumber Jarak Levenshtein

Dalam [[teori informasi]], [[linguistik]], dan [[ilmu komputer]], '''jarak Levenshtein''' adalah [[Metrik (matematika)|metrik]] untuk mengukur perbedaan antara dua barisan. Secara informal, jarak Levenshtein antara dua kata adalah jumlah minimum perubahan karakter (penyisipan, penghapusan, atau penggantian) 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.<ref>{{Cite journal|last=Влади́мир И. Левенштейн|year=1965|script-title=ru:Двоичные коды с исправлением выпадений, вставок и замещений символов|trans-title=Binary codes capable of correcting deletions, insertions, and reversals|journal=Доклады Академий Наук СССР|language=ru|volume=163|issue=4|pages=845–8}} Appeared in English as: {{Cite journal|last=Levenshtein, Vladimir I.|date=February 1966|title=Binary codes capable of correcting deletions, insertions, and reversals|url=<!--http://profs.sci.univr.it/~liptak/ALBioinfo/files/levenshtein66.pdf right to publish copy of journal unclear: see http://www.sherpa.ac.uk/romeo/search.php?issn=1028-3358&type=issn&la=en/&fIDnum=%7C&mode=simple ; in any event, liptak does not appear to be the author or the translator -->|journal=Soviet Physics Doklady|volume=10|pages=707–710|bibcode=1966SPhD...10..707L}}</ref>

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]].<ref name="navarro">{{Cite journal|last=Navarro|first=Gonzalo|year=2001|title=A guided tour to approximate string matching|url=http://repositorio.uchile.cl/bitstream/handle/2250/126168/Navarro_Gonzalo_Guided_tour.pdf|journal=ACM Computing Surveys|volume=33|issue=1|pages=31–88|doi=10.1145/375360.375365}}</ref>

== Definisi ==
Jarak Levenshtein antara dua [[string]] <math>a, b</math> (yang panjangnya masing-masing <math>|a|</math> dan <math>|b|</math>) didapatkan dengan menghitung <math>\operatorname{lev}(a, b)</math>, yang didefinisikan sebagai

<math>\qquad\operatorname{lev}(a,b) = \begin{cases}
 |a| & \text{ jika } |b| = 0, \\
 |b| & \text{ jika } |a| = 0, \\
 \operatorname{lev}(\operatorname{tail}(a),\operatorname{tail}(b)) & \text{ jika } a[0] = b[0] \\
 1 + \min \begin{cases}
     \operatorname{lev}(\operatorname{tail}(a), b) \\
     \operatorname{lev}(a, \operatorname{tail}(b)) \\
     \operatorname{lev}(\operatorname{tail}(a), \operatorname{tail}(b)) \\
    \end{cases} & \text{ lainnya.}
\end{cases}</math>

Dengan <math>\operatorname{tail}</math> dari string <math>x</math> adalah string dari semua kecuali karakter pertama dari <math>x</math>, dan <math>x[n]</math> adalah karakter ke-<math>n</math> dari string <math>x</math>, dengan <math>n=0</math> menandakan karakter pertama. Perhatikan bahwa elemen-elemen di <math>\min</math> secara berurutan adalah penghapusan (dari <math>a</math> ke <math>b</math>), penyisipan, dan subtitusi. Definisi ini adalah salah bentuk definisi yang rekursif.

=== Contoh ===
[[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:

# '''k'''artun → '''g'''artun (substitusi "k" menjadi "g")
# ga'''r'''tun → ga'''n'''tun (substitusi "r" menjadi "n")
# gantun → gantun'''g''' (penyisipan "g" di akhir).

=== Batas atas dan batas bawah ===
Jarak Levenshtein memiliki beberapa batas atas dan batas bawah yang sederhana. Beberapa diantaranya adalah:

* 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]]).

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.

== Aplikasi ==
Dalam [[Pencarian string samar|pencocokan string secara samar]], tujuan yang ingin dicapai adalah untuk menemukan kecocokan antara sebuah string pendek dengan string lain di dalam sebuah teks yang lebih panjang; dengan anggapan hanya ada sedikit perbedaan diantara mereka. Misalnya, teks yang lebih panjang dapat berupa kamus, dan string yang pendek berasal dari masukan pengguna. Hal Ini memiliki berbagai aplikasi, misalnya untuk [[pemeriksa ejaan]] dan sistem koreksi untuk [[Pengenalan karakter optis|pengenalan karakter optik]].

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.<ref name="ref05xubej">{{Citation|title=Receptive multilingualism: linguistic analyses, language policies, and didactic concepts|last=Jan D. ten Thije|last2=Ludger Zeevaert|publisher=John Benjamins Publishing Company, 2007|isbn=978-90-272-1926-8|url=https://books.google.com/books?id=8gIEN068J3gC&q=Levenshtein|quote=''... Assuming that intelligibility is inversely related to linguistic distance ... the content words the percentage of cognates (related directly or via a synonym) ... lexical relatedness ... grammatical relatedness ...''|date=2007-01-01}}</ref> Hal ini terkait dengan [[Kesalingpahaman|kejelasan timbal balik]], semakin tinggi jarak linguistik, semakin rendah kejelasan timbal balik, dan semakin rendah jarak linguistik, semakin tinggi kejelasan timbal balik tersebut.

== Hubungan dengan metrik jarak edit lainnya ==
Ada beberapa [[jarak edit]] lain yang populer, yang dihitung berdasarkan operasi-operasi edit yang diizinkan. Sebagai contoh:

* jarak [[Jarak Damerau-Levenshtein|Damerau-Levenshtein]] memperbolehkan [[Permutasi|transposisi]] dua karakter yang bersebelahan, di samping penyisipan, penghapusan, dan substitusi;
* jarak subbarisan terpanjang bersama (Inggris: ''longest common subsequence'', LCS) hanya memungkinkan penyisipan dan penghapusan, namun tidak substitusi;
* [[jarak Hamming]] hanya memungkinkan substitusi, oleh karena itu, ini hanya berlaku untuk string dengan panjang yang sama.
* [[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 ==

=== Rekursif ===
Ini adalah implementasi [[Haskell]] rekursif namun tidak efisien, dari fungsi <code>lDistance</code> yang mengambil dua string, ''s'' dan ''t'', bersama dengan panjangnya, dan mengembalikan jarak Levenshtein di antara keduanya:<syntaxhighlight lang="haskell">
lDistance :: ( Eq a ) => [a] -> [a] -> Int
lDistance [] t = length t   -- Jika s kosong maka jarak adalah banyak karakter di t
lDistance s [] = length s   -- Jika t kosong maka jarak adalah banyak karakter di s
lDistance (a:s') (b:t') =
  if
    a == b
  then
    lDistance s' t'         -- Jika karakter pertama mereka sama maka dapat diabaikan
  else
    1 + minimum             -- Untuk kasus lain, cari nilai minimum dari tiga aksi ini
      [ lDistance (a:s') t' -- Karakter disisipkan  (b disisipkan)
      , lDistance s' (b:t') -- Karakter dihapus     (a dihapus)
      , lDistance s' t'     -- Karakter disubtitusi (a diganti dengan b)
      ]
</syntaxhighlight>Implementasi ini sangat tidak efisien karena menghitung ulang jarak Levenshtein dari substring yang sama berkali-kali. Metode yang lebih efisien tidak mengulangi penghitungan jarak yang sama. Misalnya, dengan menyimpan jarak Levenshtein yang telah dihitung ke dalam suatu matriks <math>M</math> dimana <math>M[i][j]</math> adalah jarak antara yang terakhir <math>i</math> karakter dari string <code>s</code> dan yang terakhir <math>j</math> karakter string <code>t</code> . Matriks mudah dibuat satu baris dalam satu waktu, dimulai dengan baris 0. Ketika seluruh tabel telah selesai dibangun, jarak yang diinginkan ada pada tabel di baris dan kolom terakhir, yang merepresentasikan jarak antara semua karakter di <code>s</code> dan semua karakter di <code>t</code>.

=== Iteratif dengan matriks ===
Menghitung jarak Levenshtein yang lebih efisien didasarkan pada pengamatan bahwa jika kita menyimpan [[Matriks (matematika)|matriks]] untuk mencatat jarak Levenshtein antara semua awalan dari string pertama dan semua awalan pada string kedua, maka kita dapat menghitung nilai-nilai dalam matriks dalam bentuk [[pemrograman dinamis]], sehingga jarak antara dua string penuh sebagai elemen terakhir yang dihitung.

Algoritma ini, contoh dari [[pemrograman dinamis]] tipe ''bottom-up'', dibahas dalam artikel 1974 "''The String-to-string correction problem''" oleh Robert A. Wagner dan Michael J. Fischer.<ref>{{Citation|first=Robert A.|last=Wagner|first2=Michael J.|last2=Fischer|author2-link=Michael J. Fischer|title=The String-to-String Correction Problem|journal=Journal of the ACM|volume=21|number=1|year=1974|pages=168–173|doi=10.1145/321796.321811}}</ref> Berikut ini adalah implementasi [[Kode semu|pseudocode]] untuk fungsi <code>LevenshteinDistance</code> yang mengambil dua string, ''s'' dengan panjang ''m'', dan ''t'' dengan panjang ''n'', dan mengembalikan jarak Levenshtein di antara keduanya:<syntaxhighlight lang="pascal">
function LevenshteinDistance(char s[1..m], char t[1..n]):
  // untuk setiap i and j, d[i,j] akan menyimpan jarak Levenshtein distance antara
  // i karakter pertama dari s dan j karakter pertama dari t
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // awalan di sumber dapat diubah menjadi string kosong
  // dengan menghapus semua karakter
  for i from 1 to m:
      d[i, 0] := i
 
  // awalan di target dapat dicapai dari awalan berupa string kosong
  // dengan menyisipkan semua karakter
  for j from 1 to n:
      d[0, j] := j
 
  for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // penghapusan
                             d[i, j-1] + 1,                   // penyisipan
                             d[i-1, j-1] + substitutionCost)  // subtitusi
 
  return d[m, n]
</syntaxhighlight>Dua contoh matriks yang dihasilkan (mengarahkan kursor ke nomor yang diberi tag akan mengungkapkan operasi yang dilakukan untuk mendapatkan nomor tersebut):{{col-begin|width=auto}}
{{col-break}}
{|class="wikitable"
|-
| 
| 
!k
!i
!t
!t
!e
!n
|-
| ||0 ||1 ||2 ||3 ||4 ||5 ||6
|-
!s
|1 ||{{H:title|substitusi 's' ke 'k'|1}} ||2 ||3 ||4 ||5 ||6
|-
!i
|2 ||2 ||{{H:title|'i' sama dengan 'i'|1}} ||2 ||3 ||4 ||5
|-
!t
|3 ||3 ||2 ||{{H:title|'t' sama dengan 't'|1}} ||2 ||3 ||4
|-
!t
|4 ||4 ||3 ||2 ||{{H:title|'t' sama dengan 't'|1}} ||2 ||3
|-
!i
|5 ||5 ||4 ||3 ||2 ||{{H:title|substitusi 'i' ke 'e'|2}} ||3
|-
!n
|6 ||6 ||5 ||4 ||3 ||3 ||{{H:title|'n' sama dengan 'n'|2}}
|-
!g
|7 ||7 ||6 ||5 ||4 ||4 ||{{H:title|sisipkan 'g'|3}}
|}
{{col-break|gap=1em}}
{|class="wikitable"
|
|
!S
!a
!t
!u
!r
!d
!a
!y
|-
| 
|0 ||1 ||2 ||3 ||4 ||5 ||6 ||7 ||8
|-
!S
|1 ||{{H:title|'S' sama dengan 'S'|0}} ||{{H:title|sisipkan 'a'|1}} ||{{H:title|sisipkan 't'|2}} ||3 ||4 ||5 ||6 ||7
|-
!u
|2 ||1 ||1 ||2 ||{{H:title|'u' sama dengan 'u'|2}} ||3 ||4 ||5 ||6
|-
!n
|3 ||2 ||2 ||2 ||3 ||{{H:title|substitusi 'n' ke 'r'|3}} ||4 ||5 ||6
|-
!d
|4 ||3 ||3 ||3 ||3 ||4 ||{{H:title|'d' sama dengan 'd'|3}} ||4 ||5
|-
!a
|5 ||4 ||3 ||4 ||4 ||4 ||4 ||{{H:title|'a' sama dengan 'a'|3}} ||4
|-
!y
|6 ||5 ||4 ||4 ||5 ||5 ||5 ||4 ||{{H:title|'y' sama dengan 'y'|3}}
|}
{{col-end}}

=== Iteratif dengan dua baris matriks ===
Pada pengamatan lebih lanjut, hanya dua baris matriks yang diperlukan untuk menghitung jarak Levenshtein; jika tidak ingin merekonstruksi string input yang diedit. Jarak Levenshtein dapat dihitung secara iteratif menggunakan algoritma berikut:<ref>{{Citation|title=Fast, memory efficient Levenshtein algorithm|first=Sten|last=Hjelmqvist|date=26 Mar 2012|url=http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm}}</ref><syntaxhighlight lang="pascal">
function LevenshteinDistance(char s[0..m-1], char t[0..n-1]):
    // bentuk dua vektor kerja dengan jarak integer
    declare int v0[n + 1]
    declare int v1[n + 1]

    // inisialisasi v0 (baris jarak sebelumnya)
    // Baris ini setara dengan A[0][i]: jarak edit bagi s yang kosong
    // Jaraknya cuma banyaknya karakter yang perlu dihapus dari t
    for i from 0 to n:
        v0[i] = i

    for i from 0 to m-1:
        // hitung v1 (baris jarak saat ini) dari baris v0 sebelumnya

        // elemen pertama v1 setara dengan A[i+1][0]
        //   jarak editnya adalah menghapus (i+1) chars dari s agar sama dengan t yang kosong
        v1[0] = i + 1

        // gunakan formula untuk mengisi sisa elemen di baris
        for j from 0 to n-1:
            // hitung biaya untuk A[i+1][j+1]
            deletionCost := v0[j + 1] + 1
            insertionCost := v1[j] + 1
            if s[i] = t[j]:
                substitutionCost := v0[j]
            else:
                substitutionCost := v0[j] + 1;

            v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

        // salin v1 (baris saat ini) ke v0 (baris sebelumnya) untuk iterasi selanjutnya
        // karena data di v1 tidak pernah dipakai lagi, swap tanpa copy dapat lebih efisien
        swap v0 with v1
    // setelah swap terakhir, hasil di v1 ada di v0
    return v0[n]
</syntaxhighlight>Variasi dua baris ini masih kurang optimal — jumlah memori yang diperlukan dapat dikurangi menjadi satu baris dan satu ''word of overhead'' (indeks), untuk ''caching'' yang lebih baik.<ref name="iosifovich">{{Cite web|title=Clearer / Iosifovich: Blazingly fast levenshtein distance function|url=https://bitbucket.org/clearer/iosifovich/|archive-url=https://web.archive.org/web/20180612143641/https://bitbucket.org/clearer/iosifovich/|archive-date=June 12, 2018|quote=It gets {{sic|it|'s|nolink=y}} speed from using very little memory, often keeping the buffer entirely in cache, and reducing the amount of work by skipping any prefix and postfix that won't add to the cost. [...] The point is, you only really need to know the three values when you want to update a cell in the matrix and you can keep two of them in a buffer, while keeping the third value in a fixed location.}} [https://github.com/rljacobson/Levenshtein/blob/master/damlev.cpp Live descendent code.]</ref>

== Variasi adaptif ==
Variasi pemrograman dinamis bukanlah implementasi yang ideal. Pendekatan adaptif dalam kasus terbaik dapat mengurangi jumlah memori yang dibutuhkan dan dapat mengurangi kompleksitas waktu menjadi linier (dalam panjang string terpendek). Sedangkan dalam kasus terburuk, kompleksitas waktunya tidak lebih dari kuadrat panjang string terpendek. Ide dari variasi ini adalah bahwa ''library function'' yang efisien (seperti {{code|std::mismatch}}di [[C (bahasa pemrograman)|C]] ) dapat digunakan untuk memeriksa awalan dan akhiran kedua string yang sama, dan hanya mengerjakan pemrograman dinamis bagian string yang berbeda.<ref name="iosifovich2">{{Cite web|title=Clearer / Iosifovich: Blazingly fast levenshtein distance function|url=https://bitbucket.org/clearer/iosifovich/|archive-url=https://web.archive.org/web/20180612143641/https://bitbucket.org/clearer/iosifovich/|archive-date=June 12, 2018|quote=It gets {{sic|it|'s|nolink=y}} speed from using very little memory, often keeping the buffer entirely in cache, and reducing the amount of work by skipping any prefix and postfix that won't add to the cost. [...] The point is, you only really need to know the three values when you want to update a cell in the matrix and you can keep two of them in a buffer, while keeping the third value in a fixed location.}} [https://github.com/rljacobson/Levenshtein/blob/master/damlev.cpp Live descendent code.]</ref>

=== Automata ===
[[Automata Levenshtein]] dapat secara efisien menentukan apakah sebuah string memiliki jarak edit lebih rendah dari suatu konstanta, yang diberikan dari string tertentu.<ref name="ssm">{{Cite journal|last=Schulz|first=Klaus U.|last2=Mihov|first2=Stoyan|year=2002|title=Fast String Correction with Levenshtein-Automata|journal=International Journal of Document Analysis and Recognition|volume=5|issue=1|pages=67–85|doi=10.1007/s10032-002-0082-8}}</ref>

=== Perkiraan ===
Jarak Levenshtein antara dua string dengan panjang {{Mvar|n}} dapat [[Algoritme perkiraan|diperkirakan]] dalam faktor 

: <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 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 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 ==
<references />