Левенштајново растојање

У рачунарству, Левенштајново растојање је метрика за ниске, која је један од начина да се одреди растојање уређивања (енгл. edit distance) две ниске. Левенштајново растојање две ниске је одређено минималним бројем операција неопходним да се једна ниска трансформише у другу, а операције су уметање, брисање или замена једног карактера другим. Добило је име по Владимиру Левенштајну, који га је развио 1965.^[1] Левенштајново растојање је корисно у одређивању сличности две ниске, на пример у софтверу за проналажење грешака у куцању.

На пример, Левенштајново растојање речи "kitten" и "sitting" је 3, јер су потребне најмање три операције измене да се једна реч трансформише у другу:

kitten → sitten (замена 's' са 'k')
sitten → sittin (замена 'i' са 'e')
sittin → sitting (уметање 'g' на крај)

Ово растојање се може посматрати као уопштење Хаминговог растојања, које се користи да ниске исте дужине, и које подразумева искључиво замене карактера. Постоје и даље генерализације Левенштајновог растојања, на пример Дамерау-Левенштајново растојање које дозвољава операцију промене места карактеру (које се код Левенштајновог растојања посматра као две операције - брисање и потом уметање).

Дефиниција уреди

Математички, Левенштајново растојање између два стринга $a,b$ је дато $\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}}$

Имајте на уму да први елемент одговара брисању (из < $a$ до $b$ ), други одговара уметању а трећи се подудара.

Примена уреди

У приближном подударању ниски, циљ је да се пронађе погодак за краће ниске у великим текстовима, у ситуацијама када се очекује мали број разлика. Краћа ниска може доћи из речника на пример. Овде је једна ниска типично краћа, док је друга дужа. Ово има широк спектар примена, нпр. провера правописа (енг. Spell-checker), системи корекције за оптичко препознавање карактера и за софтвер који асистира у превођењу. Левенштајново растојање се може израчунати и између два дуже ниске, али цена тог израчунавања које је грубо речено пропорционална производу дужине та две ниске доводи до непрактичности овог алгоритма.

Алгоритам уреди

Рекурзивно уреди

Рекурзивна имплементација LevenshteinDistance функције узима две ниске, „s“ и „t“ и враћа Левенштајново растојање између њих:

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)
}

Рекурзивна имплементација је доста неефикасна због тога што рачуна Левенштајново растојање подниске много пута. Бољи метод не би понављао израчунавања. На пример, Левенштајново растојање свих могућих префикса може бити смештено у низ d[][] где је d[i][j] растојање између првог i карактера ниске s и првог j карактера ниске t. Табела је једноставна за конструкцију почевши од реда 0. Када је цела табела израђена, жељена дистанца је d[len_s][len_t].. Иако је ова техника значајно бржа захтеваће len_s * len_t више меморије него рекурзивна имплементација.

Итеративно са целом матрицом уреди

Израчунавање Левенштајновог растојања је базирано на запажању да ако резервишемо матрицу за чување растојања између свих префикса прве ниске и свих префикса друге, онда можемо да израчунамо вредности у матрици помоћу динамичког програмирања и тако нађемо растојање између два пуне ниске. Овај алгоритам је пример „одоздо нагоре“ динамичког програмирања, као што је дискутовано, са варијацима, 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]
}

Запазите да ова имплементација не одговара дефиницији прецизно: увек преферише поготке, чак ако уметање или брисање пружа бољи резултат. Ово је еквивалент; може се показати да за свако оптимално поравнање (које укључује Левенштајново растојање) постоји друго оптимално поравнање. Два примера резултујуће матрице(прелазак миша преко броја открива која је операција извршена да би се добио тај број)

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	substitution of 'k' for 's'	2	3	4	5	6
i	2	2	'i' equals 'i'	2	3	4	5
t	3	3	2	't' equals 't'	2	3	4
t	4	4	3	2	't' equals 't'	2	3
i	5	5	4	3	2	substitution of 'e' for 'i'	3
n	6	6	5	4	3	3	'n' equals 'n'
g	7	7	6	5	4	4	insert 'g'

		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	'S' equals 'S'	delete 'a'	delete 't'	3	4	5	6	7
u	2	1	1	2	'u' equals 'u'	3	4	5	6
n	3	2	2	2	3	substitution of 'r' for 'n'	4	5	6
d	4	3	3	3	3	4	'd' equals 'd'	4	5
a	5	4	3	4	4	4	4	'a' equals 'a'	4
y	6	5	4	4	5	5	5	4	'y' equals 'y'

Инваријанта је одржана кроз алгоритам и можемо трансформисати почетни сегмент s[1..i] у t[1..j] користећи минимум d[i,j] операција. На крају, доњи десни елемент низа садржи одговор.

Итеративно са два реда матрице уреди

Испада да само два реда табеле су потребна за конструкцију: претходни ред и тренутни ред(онај који се рачуна). Левенштајново растојање може се рачунати итеративно користећи следећи алгоритам: : :^[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];
}

Доказ коректности уреди

Као што је претходно поменуто, инваријанта је да умемо да трансформишемо почетни сегмент s[1..i] у t[1..j] коришћењем минимума операција, d[i,j]. Ова инваријанта важи јер:

У почетку је ово тачно за врсту и колону 0 јер се s[1..i] може трансформисати у празну ниску t[1..0] простим брисањем свих i карактера. Слично, можемо да трансформишемо s[1..0] у t[1..j] простим додавањем свих j карактера.
Минимум се добија од три раздаљине, од које је свака изводљива:
- Ако умемо да трансформишемо s[1..i] у t[1..j-1] са k операција, онда просто можемо да додамо t[j] након тога, и да добијемо t[1..j] са k+1 операција.
- Ако умемо да трансформишемо s[1..i-1] у t[1..j] са k операција, онда можемо да спроведемо исте операције на s[1..i] а затим да уклонимо s[i] са краја, и да добијемо укупан број од k+1 операција.
- Ако умемо да трансформишемо s[1..i-1] у t[1..j-1] са k операција, умемо да урадимо исто и са s[1..i] а затим да заменимо t[j] са s[i] на крају, уколико је неопходно, што захтева укупно k+cost операција.
Број операција неопходних да се трансформише s[1..n] у t[1..m] је број операција потребних да се свако s трансформише у свако t, па тако d[n,m] важи за наш резултат.

Овај доказ не доказује да је број који се налази у матрици, d[i,j] заиста минималан; ово је теже показати, и неопходно је користити свођење на контрадикцију.

Могућа унапређења и варијације уреди

Међу могућим унапређењима алгоритма су:

Можемо да направимо варијацију алгоритма да захтева мање простора, O(m) уместо O(mn), јер је неопходно да памтимо само претходну и тренутну врсту матрице у сваком тренутку.
Можемо да ускладиштимо број уметања, брисања и замена одвојено, или чак на позицијама на којима се јављају, што је увек j.
Можемо да дајемо различите цене операцијама уметања, брисања и замене.
Иницијализација d[i,0] се може преместити у главну спољашњу петљу.
Овај алгоритам се лоше паралелизује, услед велике количине зависних података. Међутим, све cost вредности се могу израчунати паралелно.

Горње и доње границе уреди

Левенштајново растојање има неколико једноставних горњих и доњих граница које су корисне у применама које рачунају много њих, и пореде их. Међу њима су:

Растојање никад није мање од разлике у дужинама две ниске.
Растојање није дуже од дужине дуже од ниски.
Растојање је једнако нули ако и само ако су ниске идентичне.
Ако су ниске једнаких дужина, Хамингово растојање је горња граница Левенштајновог растојања.
Ако две ниске означимо са s и t, број карактера (искључујући дупликате) који се појављују у s али не и у t је доња граница.

Види још уреди

Референце уреди

^ В. И. Левенштейн (1965) Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР 163.4:845–848.
^ Wagner, Robert A.; Fischer, Michael J. (1974), „The String-to-String Correction Problem”, Journal of the ACM, 21 (1): 168—173, doi:10.1145/321796.321811
^ Hjelmqvist, Sten (26. 3. 2012), Fast, memory efficient Levenshtein algorithm

Спољашње везе уреди

[1] В. И. Левенштейн (1965) Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР 163.4:845–848.

[2] Wagner, Robert A.; Fischer, Michael J. (1974), „The String-to-String Correction Problem”, Journal of the ACM, 21 (1): 168—173, doi:10.1145/321796.321811

[3] Hjelmqvist, Sten (26. 3. 2012), Fast, memory efficient Levenshtein algorithm

[1]

[2]

[3]