Левенштајново растојање — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
м Разне исправке |
||
Ред 20:
\end{cases}</math>
Имајте на уму да први елемент одговара брисању (из <<math>a</math>
==Примена==
У приближном подударању стрингова, циљ је да се пронађе погодак за краће стрингове у великим текстовима, у ситуацијама када се очекује мали број разлика. Краћи стринг мозе доћи из речника на пример. Овде је један стринг типично краћи, док је други дужи. Ово има широк спектар примена, нпр. Spell-checker-и, системи корекције за оптичко препознавање карактера и за софтвер који асистира у превођењу.
Ред 56:
===Итеративно са целом матрицом===
Израчунавање Левенштајновог растојања је базирано на запажању да ако резервишемо матрицу за чување растојања између свих префикса првог стринга и свих префикса другог, онда можемо да израчунамо вредности у матрици помоћу динамичког програмирања и тако нађемо растојање између два пуна стринга.
Овај алгоритам је пример bottom-up динамичког програмирања, као сто је дискутовано са варијацима 1974. године у ''The [[String-to-string correction problem]]'' од Robert A. Wagner and Michael J. Fischer.<ref>{{citation |first=Robert A. |last=Wagner |first2=Michael J. |last2=Fischer |author2-link=Michael J. Fischer |title=The String-to-String Correction Problem |journal=Journal of the ACM |volume=21 |issue=1 |year=1974 |pages=168–173 |doi= 10.1145/321796.321811}}</ref>
Имплементација функције Леванштајновог растојања која узима два стринга „с“ дужине “м“ и стринг „т“ дужине „н“ и враћа Левенштајново растојање између та два стринга.
<source lang="C">
| |||