Левенштајново растојањеУ рачунарству, Левенштајново растојање је метрика за ниске, која је један од начина да се одреди растојање уређивања (енгл. edit distance) две ниске. Левенштајново растојање две ниске је одређено минималним бројем операција неопходним да се једна ниска трансформише у другу, а операције су уметање, брисање или замена једног карактера другим. Добило је име по Владимиру Левенштајну, који га је развио 1965.[1] Левенштајново растојање је корисно у одређивању сличности две ниске, на пример у софтверу за проналажење грешака у куцању. На пример, Левенштајново растојање речи "kitten" и "sitting" је 3, јер су потребне најмање три операције измене да се једна реч трансформише у другу:
Ово растојање се може посматрати као уопштење Хаминговог растојања, које се користи да ниске исте дужине, и које подразумева искључиво замене карактера. Постоје и даље генерализације Левенштајновог растојања, на пример Дамерау-Левенштајново растојање које дозвољава операцију промене места карактеру (које се код Левенштајновог растојања посматра као две операције - брисање и потом уметање). ДефиницијаМатематички, Левенштајново растојање између два стринга је дато Имајте на уму да први елемент одговара брисању (из < до ), други одговара уметању а трећи се подудара. ПрименаУ приближном подударању ниски, циљ је да се пронађе погодак за краће ниске у великим текстовима, у ситуацијама када се очекује мали број разлика. Краћа ниска може доћи из речника на пример. Овде је једна ниска типично краћа, док је друга дужа. Ово има широк спектар примена, нпр. провера правописа (енг. Spell-checker), системи корекције за оптичко препознавање карактера и за софтвер који асистира у превођењу. Левенштајново растојање се може израчунати и између два дуже ниске, али цена тог израчунавања које је грубо речено пропорционална производу дужине та две ниске доводи до непрактичности овог алгоритма. АлгоритамРекурзивноРекурзивна имплементација int LevenshteinDistance(string s, string t)
{
int len_s = length(s);
int len_t = length(t);
/* test for degenerate cases of empty strings */
if (len_s == 0) return len_t;
if (len_t == 0) return len_s;
/* test if last characters of the strings match */
if (s[len_s-1] == t[len_t-1]) cost = 0;
else cost = 1;
/* return minimum of delete char from s, delete char from t, and delete char from both */
return minimum(LevenshteinDistance(s[0..len_s-1], t) + 1,
LevenshteinDistance(s, t[0..len_t-1]) + 1,
LevenshteinDistance(s[0..len_s-1], t[0..len_t-1]) + cost)
}
Итеративно са целом матрицомИзрачунавање Левенштајновог растојања је базирано на запажању да ако резервишемо матрицу за чување растојања између свих префикса прве ниске и свих префикса друге, онда можемо да израчунамо вредности у матрици помоћу динамичког програмирања и тако нађемо растојање између два пуне ниске. Овај алгоритам је пример „одоздо нагоре“ динамичког програмирања, као што је дискутовано, са варијацима, 1974. године у The String-to-string correction problem од Robert A. Wagner and Michael J. Fischer.[2] Имплементација функције Леванштајновог растојања која узима две ниске, „с“ дужине “м“ и ниску „т“ дужине „н“ и враћа Левенштајново растојање између та две ниске. int LevenshteinDistance(char s[1..m], char t[1..n])
{
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t;
// note that d has (m+1)*(n+1) values
declare int d[0..m, 0..n]
clear all elements in d // set each element to zero
// source prefixes can be transformed into empty string by
// dropping all characters
for i from 1 to m
{
d[i, 0] := i
}
// target prefixes can be reached from empty source prefix
// by inserting every characters
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] then //going on the assumption that string indexes are 1-based in your chosen language<!-- not: s[i-1] = t[j-1] -->
//else you will have to use s[i-1] = t[j-1] Not doing this might throw an IndexOutOfBound error
d[i, j] := d[i-1, j-1] // no operation required
else
d[i, j] := minimum
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
}
}
return d[m,n]
}
Запазите да ова имплементација не одговара дефиницији прецизно: увек преферише поготке, чак ако уметање или брисање пружа бољи резултат. Ово је еквивалент; може се показати да за свако оптимално поравнање (које укључује Левенштајново растојање) постоји друго оптимално поравнање. Два примера резултујуће матрице(прелазак миша преко броја открива која је операција извршена да би се добио тај број)
Инваријанта је одржана кроз алгоритам и можемо трансформисати почетни сегмент Итеративно са два реда матрицеИспада да само два реда табеле су потребна за конструкцију: претходни ред и тренутни ред(онај који се рачуна). Левенштајново растојање може се рачунати итеративно користећи следећи алгоритам: : :[3] static int LevenshteinDistance(string s, string t)
{
// degenerate cases
if (s == t) return 0;
if (s.Length == 0) return t.Length;
if (t.Length == 0) return s.Length;
// create two work vectors of integer distances
int[] v0 = new int[t.Length + 1];
int[] v1 = new int[t.Length + 1];
// initialize v0 (the previous row of distances)
// this row is A[0][i]: edit distance for an empty s
// the distance is just the number of characters to delete from t
for (int i = 0; i < v0.Length; i++)
v0[i] = i;
for (int i = 0; i < s.Length; i++)
{
// calculate v1 (current row distances) from the previous row v0
// first element of v1 is A[i+1][0]
// edit distance is delete (i+1) chars from s to match empty t
v1[0] = i + 1;
// use formula to fill in the rest of the row
for (int j = 0; j < t.Length; j++)
{
var cost = (s[i] == t[j]) ? 0 : 1;
v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
}
// copy v1 (current row) to v0 (previous row) for next interation
for (int j = 0; j < v0.Length; j++)
v0[j] = v1[j];
}
return v1[t.Length];
}
Доказ коректностиКао што је претходно поменуто, инваријанта је да умемо да трансформишемо почетни сегмент
Овај доказ не доказује да је број који се налази у матрици, Могућа унапређења и варијацијеМеђу могућим унапређењима алгоритма су:
Горње и доње границеЛевенштајново растојање има неколико једноставних горњих и доњих граница које су корисне у применама које рачунају много њих, и пореде их. Међу њима су:
Види још Викикњиге имају више информација о Strings/Levenshtein distance
Референце
Спољашње везе |
![{\displaystyle \operatorname {lev} _{a,b}(|a|,|b|):<math>\qquad \operatorname {lev} _{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ if}}\min(i,j)=0,\\\min {\begin{cases}\operatorname {lev} _{a,b}(i-1,j)+1\\\operatorname {lev} _{a,b}(i,j-1)+1\\\operatorname {lev} _{a,b}(i-1,j-1)+[a_{i}\neq b_{j}]\end{cases}}&{\text{ otherwise.}}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/637acfdab42e688491f2953a17614987ae92ea7e)
Portal di Ensiklopedia Dunia
