Левенштајново растојање — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 26:
== Алгоритам ==
===Рекурзивно===
Рекурзивна имплементација <code>LevenshteinDistance</code> функције узима два стринга, „s“ и „t“ и враћа Левенштајново растојање између њих:
<!-- This routine would be clearer if len_s and len_t were args. -->
<source lang="C">
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)
}
</source>
Рекурзивна имплементација је доста неефикасна због тога што рачуна Левенштајново растојање субстринга много пута. Бољи метод не би понављао израчунавања.На пример, Левенштајново растојање свих могућих префикса мозе бити смештен у низ <code>d[][]</code> где <code>d[i][j]</code> је растојање између првог <code>i</code> карактера стринга <code>s</code> и првог <code>j</code> карактера стринга <code>t</code>. Табела је једноставна за конструкцију почевши од реда 0. Када је цела табела израђена, зељена дистанца је <цоде>д[лен_с][лен_т]</цоде>.Иако је ова техника значајно брза захтеваће <code>d[len_s][len_t]</code>. више меморије него рекурзивна имплементација.
===Итеративно са целом матрицом===
Израчунавање Левенштајновог растојања је базирано на запажању да ако резервишемо матрицу за чување растојања између свих префикса првог стринга и свих префикса другог, онда можемо да израчунамо вредности у матрици помоћу динамичког програмирања и тако нађемо растојање између два пуна стринга.
| |||