Відстань Левенштейна: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м суміш розкладок, Replaced: aі-fіnal → ai-final з допомогою AWB |
Panas (обговорення | внесок) →Алгоритм: хто в курсі - перевірте таблицю у прикладі |
||
Рядок 13:
==Алгоритм==
Для розрахунку відстані Левенштейна найчастіше використовують простий [[алгоритм]], в якому використовується матриця розміром (n + 1) * (m + 1), де n і m - довжини порівнюваних рядків.
Для конструювання матриці використовують таке рекурсивне рівняння:
:<math>D_{0, 0} = 0</math>
:<math>
D_{i, j} = min \begin{cases}
D_{i - 1, j - 1}&+ 0 \ {\rm(equal, no change)} \\
D_{i - 1, j - 1}&+ 1 \ {\rm(replace)} \\
D_{i - 1, j}&+ 1 \ {\rm(insert)} \\
D_{i, j - 1}&+ 1 \ {\rm(delete)}
\end{cases}</math>
У [[псевдокод]]і алгоритм виглядає так:
'''int''' LevenshteinDistance('''char''' str1[1..lenStr1], '''char''' str2[1..lenStr2])
''// d
'''declare''' '''int''' d[0..lenStr1, 0..lenStr2]
''// i
'''declare''' '''int''' i, j, cost
Рядок 28 ⟶ 40:
'''for''' i '''from''' 1 '''to''' lenStr1
'''for''' j '''from''' 1 '''to''' lenStr2
'''if''' str1[i] = str2[j] '''then''' cost := 0 ''//одинкові''
'''else''' cost := 1 ''//заміна''
d[i, j] := minimum(
d[i-1, j ] + 1, ''//
d[i , j-1] + 1, ''//
d[i-1, j-1] + cost ''//
)
'''return''' d[lenStr1, lenStr2]
Цей алгоритм легко реалізовується також вручну
ε - т.зв. ''пусте'' слово, без літер
'''ε К О Р А Б Е Л Ь'''
'''ε''' 0 1 2 3 4 5 6 7 8 ''/* тобто відстань між пустим словом і словом КОРАБЕЛЬ = 8 (довжина слова КОРАБЕЛЬ) */''
'''Б''' 1 1 2 3 4 4 5 6 7 ''/* між Б і КОРАБЕЛЬ відстань = 7 (літера Б в обох словах і може бути використана) */''
'''А''' 2 2 2 3 3 4 5 6 7 ''/* між БА і КОРАБЕЛЬ відстань = 7 (лише одну з літер Б або А можна використати) */''
'''Л''' 3 3 3 3 4 4 5 5 <span style="color:#ff0000;">'''6'''</span> ''/* між БАЛ і КОРАБЕЛЬ відстань = 6 (можна використати дві літери (Б або А) + Л) */''
Як видно з прикладу існувє декілька еквівалентних шляхів і алгоритм вираховує усі шляхи, використовуючи у кожному наступному кроці інформацію здобуту у попередніх кроках (принцип динамічного програмування).
Мовою програмування [[PHP]] цей алгоритм реалізований
==Межі==
| |||