Пређи на садржај

Вагнер-Фишеров алгоритам

С Википедије, слободне енциклопедије

У информатици, Вагнер-Фишеров алгоритам је алгоритам динамичког програмирања који мери Левенштајново растојање између две ниске карактера.

Израчунавање растојања[уреди | уреди извор]

Вагнер-Фишеров алгоритам израчунава Левенштајново растојање на основу посматрања, на пример ако направимо матрицу која ће да садржи Левенштајнова растојања између свих префикса прве ниске и свих префикса друге ниске, онда можемо да израчунамо вредности у матрици тако што ћемо да „поплавимо“ матрицу (такозваним алгоритмом „пуњење поплавом“ или на енг. флоод филлинг).Последња израчуната вредност ће представљати растојање између две ниске. Што је Левенштајново растојање две ниске веће, то се оне више разликују међу собом.

Једноставна имплементација, у облику псеудокода за функцију ЛевенстајновоРастојање узима две ниске, м је дужина ниске с, и н је дужина ниске т, и враћа њихово Левенштајново растојање: 

       int LevenstajnovoRastojanje(char s[1..m], char t[1..n])
 {
   // za svako i i j, d[i,j] ce predstavljati Levenstajnovo rastojanje 
   // izmedju prvih i karaktera niske s i prvih j karaktera niske t;
   // napomena, matrica d je velicine (m+1)*(n+1) 
   int d[0..m, 0..n]
  
   for i from 0 to m
     d[i, 0] := i // rastojanje od bilo koje prve niske do druge prazne niske
   for j from 0 to n
     d[0, j] := j // / rastojanje od bilo koje druge niske do prve prazne niske 
  
   for j od 1 do n
   {
     for i od 1 do m
     {
       if s[i] = t[j] then  
         d[i, j] := d[i-1, j-1]       // nije potrebna nikakva operacija
       else
         d[i, j] := minimum
                    (
                      d[i-1, j] + 1,  // operacija brisanja
                      d[i, j-1] + 1,  // operacija umetanja
                      d[i-1, j-1] + 1 // operacija zamene
                    )
     }
   }
  
   return d[m,n]
 }

Пример формирања матрице:

Н А У К А
0 1 2 3 4 5
Б 1
У 2
К 3
А 4
Н А У К А
0 1 2 3 4 5
Б 1 1 2 3 4 5
У 2 2
К 3 3
А 4 4
Н А У К А
0 1 2 3 4 5
Б 1 1 2 3 4 5
У 2 2 2 2 3 4
К 3 3 3
А 4 4 3
Н А У К А
0 1 2 3 4 5
Б 1 1 2 3 4 5
У 2 2 2 2 3 4
К 3 3 3 3 2 3
А 4 4 3 4
Н А У К А
'С' еqуалс 'С' 1 2 3 4 5
Б 1 'С' еqуалс 'С' 2 3 4 5
У 2 2 'С' еqуалс 'С' 'С' еqуалс 'С' 3 4
К 3 3 3 3 'С' еqуалс 'С' 3
А 4 4 3 4 3 'С' еqуалс 'С'

На крају, у доњем десном углу се налази одговор колико можемо минимално операција да искористимо да бисмо сегмент с[1..и] трансформисали у сегмент т[1..ј].

Доказ коректности[уреди | уреди извор]

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

  • Ово је тачно у нултој колони и нултој врсти, јер s[1..i] може бити трансформисан у празну ниску t[1…0] тако што се једноставно избацују сви i карактери. Исто тако, можемо трансформисати s[1..0] у t[1..j] једноставно додајући све j карактере.
  • Ако s[i]=t[j], и ако можемо да трансформишемо s[1..i-1] у t[1..j-1] уз помоћ k операција, онда то можемо да урадимо и сегменту s[1..i], остављајући последњи карактер по страни.
  • У супротном, растојање је минимум од три могућа начина да се трансформација уради:
    • Ако можемо да трансформишемо s[1..i] у t[1..j] уз помоћ k операција , то значи да можемо једноставно да додамо t[j] да би после тога добили t[1..j] уз помоћ k+1 операција (уметање).
    • Ако можемо да трансформишемо s[1..i-1] у t[1..j] уз помоћ k операција, то значи да можемо да уклонимо s[i] и да затим урадимо исту трансформацију уз помоћ k+1 операција. (брисање).
    • Ако можемо да трансформишемо s[1..i-1] у т[1..ј-1] уз помоћ k операција, то значи да то можемо исто урадити и сегменту s[1..i], и заменити оригинални s[i] са t[j], уз помоћ k+1 операција (замена).
  • Број операција које су задужене да трансформишу s[1..n] у t[1..m], је наравно број који је потребан да би се свако s трансформисало у t, због тога је резултат d(n,m).

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

Могућа побољшања[уреди | уреди извор]

Могућа побољшања овог алгоритма укључују следеће:

  • Можемо да адаптирамо алгоритам тако да заузима мање простора, па ће нам просторна сложеност бити О(м) уместо О(мн), јер је само потребно да се претходна врста и текућа врста чувају у било ком тренутку.
  • Можемо да чувамо број уметања, брисања, и замене одвојено, или чак позиције на којима се јављају, које су увек j.
  • Можемо да нормализујемо растојање до интервала [0,1].
  • Ако бисмо посматрали само растојање, и ако би оно било мање од прага k, онда је довољно да се израчуна дијагонала ширине 2k+1 у матрици. На овај начин, алгоритам може имати временску сложеност О(кл), где је л дужина најкраће ниске.[1]
  • Можемо да дамо различите цене трошкова уметања, брисања, и замене. Можемо такође да дамо цене трошкова које зависе од карактера који убацујемо, бришемо или замењујемо.
  • Ако иницијализујемо прву врсту матрице са 0, алгоритам може да се искористи за такозвано Приближно Претраживање Ниске у тексту (аппроxимате стринг матцхинг или фуззy стринг сеарцхинг).[2] Ова модификација пружа крајњу позицију подударних субниски текста. Да би одредили почетну позицију подударних субниски, број уметања и брисања се може чувати одвојено, и може се искористити да се израчуна почетна позиција поцевши од задње позиције.[3]
  • Овај алгоритам лоше паралелно рачуна, због великог броја зависних података. Међутим, све цене трошкова могу бити израчунате паралелно, и алгоритам се може модификовати тако да изводи минимум функција у фазама како би избегао зависност.
  • Посматрајући дијагонале уместо врсте, и користећи такозвану лењу процену (лазy евалуатион), можемо да нађемо Левенштајново растојање и да добијемо временску сложеност О(м(1+д)) (д је Левенштајново растојање). Овај начин је много бржи од алгоритма обичног динамичког програмирања ако је растојање мало.[4]

Горње и доње границе[уреди | уреди извор]

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

  • Увек је барем разлика у величини две ниске.
  • У већини случајева је дужина дуже ниске.
  • Нула је ако и само ако су ниске идентичне.
  • Ако су ниске истих величина, Хамингово растојање је горња граница Левенштајновог растојања.

Референце[уреди | уреди извор]

  1. ^ Гусфиелд 1997.
  2. ^ Наварро, Г. (2001). „А гуидед тоур то аппроxимате стринг матцхинг”. АЦМ Цомпутинг Сурвеyс. 33 (1): 31—88. дои:10.1145/375360.375365. 
  3. ^ Бруно Wолтзенлогел Палео. Ан аппроxимате газеттеер фор ГАТЕ басед он левенсхтеин дистанце Архивирано на сајту Wayback Machine (8. мај 2013). Студент Сецтион оф тхе Еуропеан Суммер Сцхоол ин Логиц, Лангуаге анд Информатион (ЕССЛЛИ), 2007.
  4. ^ Аллисон, L. (1992). „Лазy Дyнамиц-Программинг цан бе Еагер”. Инф. Проц. Леттерс. 43 (4): 207—12. дои:10.1016/0020-0190(92)90202-7. 

Литература[уреди | уреди извор]

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

Преузето из „https://sr.wikipedia.org/w/index.php?title=Vagner-Fišerov_algoritam&oldid=26791114”