Левенштајново растојање — разлика између измена
Садржај обрисан Садржај додат
м Робот: додато {{subst:User:Autobot/sandbox2}} |
м Разне исправке |
||
Ред 56:
=== Итеративно са целом матрицом ===
Израчунавање Левенштајновог растојања је базирано на запажању да ако резервишемо матрицу за чување растојања између свих префикса прве ниске и свих префикса друге, онда можемо да израчунамо вредности у матрици помоћу динамичког програмирања и тако нађемо растојање између два пуне ниске.
Овај алгоритам је пример „одоздо на горе“ динамичког програмирања, као што је дискутовано, са варијацима, 1974. године у ''The [[String-to-string correction problem]]'' од Robert A. Wagner and Michael J. Fischer.<ref>{{citation |first=Robert A. |last=Wagner
Имплементација функције Леванштајновог растојања која узима две ниске, „с“ дужине “м“ и ниску „т“ дужине „н“ и враћа Левенштајново растојање између та две ниске.
<source lang="C">
Ред 182:
=== Итеративно са два реда матрице ===
Испада да само два реда табеле су потребна за конструкцију: претходни ред и тренутни ред(онај који се рачуна).
Левенштајново растојање може се рачунати итеративно користећи следећи алгоритам: : :<ref>{{Citation |title=Fast, memory efficient Levenshtein algorithm
<syntaxhighlight lang="CSharp">
static int LevenshteinDistance(string s, string t)
| |||