In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences.
Dalam teori informasi, linguistik, dan ilmu komputer, jarak Levenshtein adalah metrik untuk mengukur perbedaan antara dua barisan.
The Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.
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.
It is named after Soviet mathematician Vladimir Levenshtein, who defined the metric in 1965.
Jarak ini dinamai dengan nama matematikawan Soviet Vladimir Levenshtein, yang mempertimbangkan jarak ini pada tahun 1965.
head ⁡ ( b ) , 1 + min { lev ⁡ ( tail ⁡ ( a ) , b ) lev ⁡ ( a , tail ⁡ ( b ) ) lev ⁡ ( tail ⁡ ( a ) , tail ⁡ ( b ) ) otherwise (a,b)={\begin{cases}|a|&{\text{ if }}|b|=0,\\|b|&{\text{ if }}|a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ if }}\operatorname {head} (a)=\operatorname {head} (b),\\1+\min {\begin{cases}\operatorname {lev} {\big (}\operatorname {tail} (a),b{\big )}\\\operatorname {lev} {\big (}a,\operatorname {tail} (b){\big )}\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}
(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}}} Dengan tail } dari string x adalah string dari semua kecuali karakter pertama dari x , dan x [ n ] adalah karakter ke- n dari string x , dengan n0 menandakan karakter pertama.
It is zero if and only if the strings are equal.
Bernilai nol jika dan hanya jika kedua string sama.
If the strings have the same size, the Hamming distance is an upper bound on the Levenshtein distance.
Jika kedua string berukuran sama, jarak Hamming adalah batas atas bagi jarak Levenshtein.
The Levenshtein distance between two strings is no greater than the sum of their Levenshtein distances from a third string (triangle inequality).
Jarak Levenshtein antara dua string tidak pernah lebih besar dari jumlah jarak Levenshtein mereka dengan suatu string lain (pertidaksamaan segitiga).
In linguistics, the Levenshtein distance is used as a metric to quantify the linguistic distance, or how different two languages are from one another.
Dalam linguistik, jarak Levenshtein digunakan sebagai metrik untuk mengukur jarak linguistik, atau seberapa berbedanya dua bahasa satu sama lain.
There are other popular measures of edit distance, which are calculated using a different set of allowable edit operations.
Ada beberapa jarak edit lain yang populer, yang dihitung berdasarkan operasi-operasi edit yang diizinkan.
For instance: the Damerau–Levenshtein distance allows the transposition of two adjacent characters alongside insertion, deletion, substitution; the longest common subsequence (LCS) distance allows only insertion and deletion, not substitution; the Hamming distance allows only substitution, hence, it only applies to strings of the same length.
Sebagai contoh: jarak Damerau-Levenshtein memperbolehkan 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;
the Jaro distance allows only transposition.
jarak Jaro hanya memungkinkan transposisi .
This is further generalized by DNA sequence alignment algorithms such as the Smith–Waterman algorithm, which make an operation's cost depend on where it is applied.
Hal ini selanjutnya digeneralisasikan oleh algoritma penyelarasan urutan DNA seperti algoritma Smith-Waterman, dengan biaya operasi bergantung pada tempat penerapannya.
This is a straightforward, but inefficient, recursive Haskell implementation of a lDistance function that takes two strings, s and t, together with their lengths, and returns the Levenshtein distance between them:
Ini adalah implementasi Haskell rekursif namun tidak efisien, dari fungsi lDistance yang mengambil dua string, s dan t, bersama dengan panjangnya, dan mengembalikan jarak Levenshtein di antara keduanya:
This implementation is very inefficient because it recomputes the Levenshtein distance of the same substrings many times.
Implementasi ini sangat tidak efisien karena menghitung ulang jarak Levenshtein dari substring yang sama berkali-kali.
[ j ] is the distance between the last i characters of string s and the last j characters of string t.
[ i ] [ j ] adalah jarak antara yang terakhir i karakter dari string s dan yang terakhir j karakter string t .
When the entire table has been built, the desired distance is in the table in the last row and column, representing the distance between all of the characters in s and all the characters in t. This section uses 1-based strings rather than 0-based strings.
Ketika seluruh tabel telah selesai dibangun, jarak yang diinginkan ada pada tabel di baris dan kolom terakhir, yang merepresentasikan jarak antara semua karakter di s dan semua karakter di t.Iteratif dengan matriks
Computing the Levenshtein distance is based on the observation that if we reserve a matrix to hold the Levenshtein distances between all prefixes of the first string and all prefixes of the second, then we can compute the values in the matrix in a dynamic programming fashion, and thus find the distance between the two full strings as the last value computed.
Menghitung jarak Levenshtein yang lebih efisien didasarkan pada pengamatan bahwa jika kita menyimpan 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,
This algorithm, an example of bottom-up dynamic programming, is discussed, with variants, in the 1974 article The String-to-string correction problem by Robert A. Wagner and Michael J. Fischer.
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.
This is a straightforward pseudocode implementation for a function LevenshteinDistance that takes two strings, s of length m, and t of length n, and returns the Levenshtein distance between them: Two examples of the resulting matrix (hovering over a tagged number reveals the operation performed to get that number):
Berikut ini adalah implementasi pseudocode untuk fungsi LevenshteinDistance yang mengambil dua string, s dengan panjang m, dan t dengan panjang n, dan mengembalikan jarak Levenshtein di antara keduanya:
Levenshtein automata efficiently determine whether a string has an edit distance lower than a given constant from a given string.
Automata Levenshtein dapat secara efisien menentukan apakah sebuah string memiliki jarak edit lebih rendah dari suatu konstanta, yang diberikan dari string tertentu.
It has been shown that the Levenshtein distance of two strings of length n cannot be computed in time O(n2 − ε) for any ε greater than zero unless the strong exponential time hypothesis is false.
Dapat dibuktikan bahwa jarak Levenshtein dari dua string dengan panjang n tidak dapat dihitung dalam waktu O(n2 - ε), untuk setiap ε yang lebih besar dari nol kecuali hipotesis strong exponential time salah.