76
Nizomaddin XUDAYBERGANOV, Shaxboz HASANOV
LEVDIST(
a.substr(1),b)+1,
//
oʻchirish;
LEVDIST(
b.substr(1),a)+1,
//
qoʻshish;
LEVDIST(
a.substr(1),
b.substr(1))+
indicator);
//
almashtirish;
end
Python dasturlash tiliga tatbig‘i. Avvalambor, berilgan
satrlar uzunligi orqali maxsus Levenshteyin
jadvalimizni hosil
qilamiz. Keyingi qadamlarni kerakli bo‘lgan qiymatlarni hisoblash
hamda ularni maxsus jadvalga saqlash orqali olib boriladi.
#Levenshteyn algoritmi
# ‘a’ va ‘b’ qiymatlarni aniqlash:
a = “matematika”
b = “maktab”
# lev o‘zgaruchi massivini rows = len(a) + 1 va
columns = len(b) + 1
orqali kiritish
lev = [[0 for i in range(len(b) + 1)] for j in
range(len(a) + 1)]
# Birinchi qatordagi(row) sonlarni aniqlash:
for i in range(len(a) + 1):
lev[i][0] = i
# Birinchi ustundagi(column) sonlarni aniqlash:
for j in range(len(b) + 1):
lev[0][j] = j
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
lev[i][j] = lev[i - 1][j - 1]
else:
insertion = 1 + lev[i][j - 1]
#belgini qo‘shish
deletion = 1 + lev[i - 1][j]
#belgini o‘chirish
replacement = 1 + lev[i - 1][j - 1]
#belgini
almashtirish
Tabiiy tilni qayta ishlashda so‘zlar orasidagi masofani aniqlash algoritmlaridan foydalanish
77
# Eng foydali o‘zgarishni
tanlash:
lev[i][j] = min(insertion,
deletion, replacement)
#Levenshtein
Masofasini ekranga chiqar
print(“Levenshtein Masofasi: “, lev[len(a)][len(b)])