Вагнер-Фишеров алгоритам
У информатици, Вагнер-Фишеров алгоритам је алгоритам динамичког програмирања који мери Левенштајново растојање између две ниске карактера.
Израчунавање растојања
уредиВагнер-Фишеров алгоритам израчунава Левенштајново растојање на основу посматрања, на пример ако направимо матрицу која ће да садржи Левенштајнова растојања између свих префикса прве ниске и свих префикса друге ниске, онда можемо да израчунамо вредности у матрици тако што ћемо да „поплавимо“ матрицу (такозваним алгоритмом „пуњење поплавом“ или на енг. флоод филлинг).Последња израчуната вредност ће представљати растојање између две ниске. Што је Левенштајново растојање две ниске веће, то се оне више разликују међу собом.
Једноставна имплементација, у облику псеудокода за функцију ЛевенстајновоРастојање узима две ниске, м је дужина ниске с, и н је дужина ниске т, и враћа њихово Левенштајново растојање:
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] }
Пример формирања матрице:
|
|
На крају, у доњем десном углу се налази одговор колико можемо минимално операција да искористимо да бисмо сегмент с[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]
Горње и доње границе
уредиЛевенштајново растојање има неколико простих горњих и доњих граница које су корисне у применама у којима се рачунају и упоређују. Ово укључује да:
- Увек је барем разлика у величини две ниске.
- У већини случајева је дужина дуже ниске.
- Нула је ако и само ако су ниске идентичне.
- Ако су ниске истих величина, Хамингово растојање је горња граница Левенштајновог растојања.
Референце
уреди- ^ Гусфиелд 1997.
- ^ Наварро, Г. (2001). „А гуидед тоур то аппроxимате стринг матцхинг”. АЦМ Цомпутинг Сурвеyс. 33 (1): 31—88. дои:10.1145/375360.375365.
- ^ Бруно Wолтзенлогел Палео. Ан аппроxимате газеттеер фор ГАТЕ басед он левенсхтеин дистанце Архивирано на сајту Wayback Machine (8. мај 2013). Студент Сецтион оф тхе Еуропеан Суммер Сцхоол ин Логиц, Лангуаге анд Информатион (ЕССЛЛИ), 2007.
- ^ Аллисон, L. (1992). „Лазy Дyнамиц-Программинг цан бе Еагер”. Инф. Проц. Леттерс. 43 (4): 207—12. дои:10.1016/0020-0190(92)90202-7.
Литература
уреди- Гусфиелд, Дан (1997). Алгоритхмс он стрингс, треес, анд сеqуенцес: цомпутер сциенце анд цомпутатионал биологy. Цамбридге, УК: Цамбридге Университy Пресс. ИСБН 978-0-521-58519-4.
- R.A. Wagner and M.J. Fischer. 1974. „The String-to-String Correction Problem”. Journal of the ACM. 21 (1): 168—173..