Psevdokodi
function hamming_masofasi(a,b)
indicator ← 0
len1 ← length(a)
for n from 1 to len1 do
if
a[n] <> b[n] then
indicator ← indicator +1
return indicator
end
Algoritmning Python dasturlashga tatbiq qilinishi.
Hamming masofasini hisoblovchi funksiya yaratiladi hamda unga
2 ta satr elementlari qabul qilinadi. Funksiya ishlash jarayonida
berilgan qiymatlarning har bir belgisini o‘zaro tekshiradi hamda
yakuniy qiymatni qaytaradi.
def hamming_masofasi (satr1, satr2):
masofa_hisoblovchi = 0
for n in range(len(satr1)):
if satr1[n]!=satr2[n]:
masofa_hisoblovchi += 1
return masofa_hisoblovchi
Levenshteyin masofasi.
Levenshteyin
masofasi
(Levenshteyin distance) — tabiiy tilni qayta ishlash yo‘nalishida
Levenshteyin masofasi ikki satr (bir yoki bir nechta so‘zlar)
o‘rtasidagi masofani o‘lchash uchun qo‘llanadigan ko‘rsatkichidir.
Boshqacha qilib aytganda, ikki so‘z orasidagi Levenshteyin masofasi
bir so‘zni boshqasiga o‘zgartirish uchun zarur bo‘lgan tahrirlarning
Tabiiy tilni qayta ishlashda so‘zlar orasidagi masofani aniqlash algoritmlaridan foydalanish
73
(qo‘shish, o‘chirish yoki almashtirish) minimal soni hisoblanadi. Bu
masofani 1965-yilda Vladimir Levenshteyin sharafiga nomlangan.
Levenshteyin masofasini tahrirlash masofasi deb ham atash
mumkin. Vladimir Iosifovich Levenshteyin - rus olimi bo‘lib, u axborot
texnologiyalari, xatolarni to‘g‘rilash nazariyalari va kombinator
dizayni bo‘yicha tadqiqotlar olib borgan. Fanga qo‘shgan boshqa
hissalari orasida u 1965-yilda ishlab chiqqan Levenshteyin masofasi
va Levenshteyin algoritmi mashhur [Levenshteyin, 1966].
Demak algoritm a satrni b satrga aylantirish uchun zarur
bo‘lgan o‘zgarishlarning minimal sonini aniqlashda foydalaniladi.
Ushbu jarayonni amalga oshirishda 3 xildagi amallar qo‘llaniladi:
belgi qo‘shish, o‘chirish hamda almashtirish. Ushbu algoritmda
satrlar uzunligi bir xil bo‘lishi talab qilinmaydi. Ushbu nazariyaning
samaradorligini oshirish maqsadida pastdan yuqoriga dinamik
dasturlashning namunasi bo‘lgan algoritm 1974-yilda Robert A.
Vagner va Maykl J. Fisherning “Satrdan-satrga tuzatish muammosi”
maqolasida muhokama qilingan.
Levenshteyin masofasidan tabiiy tilni qayta ishlash
yo‘nalishida so‘zlarning o‘zaro mosligini aniqlashda foydalanish
mumkin. Bunda asosiy maqsad kam sonli farqlar kutilgan
vaziyatlarda, berilgan matnlardagi satrlar o‘xshashligini aniqlash
bo‘ladi. Bu esa masalan, imlo tekshiruvi, optik belgilarni aniqlash
uchun tuzatish tizimlari va tarjima xotirasi asosida tabiiy tilga
tarjima qilishga yordam beradigan dasturiy ta’minotlar uchun asosiy
qismlardan biri sifatida xizmat qila oladi. Optik belgilarni aniqlash
yoki optik belgilarni o‘quvchi dasturlar - skanerlangan hujjat,
qo‘lyozma fotosurati yoki subtitrdan bo‘ladimi, qo‘lda yozilgan yoki
bosilgan matn tasvirlarini mashina tiliga elektron yoki mexanik
aylantirish jarayonlaridan tashkil topadi. Bundan tashqari ushbu
o‘xshashlikdan plagiatni tekshirish kabi maqsadlarda foydalanish
muvaffaqiyatli natija beradi. Bundan tashqari taxminiy satrlarni
moslashtirish jarayonida ham keng qo‘llaniladi. Taxminiy satrlarni
moslashtirish (ko‘pincha so‘zlashuv tilida noaniq satrlarni qidirish
deb ataladi) aniq bo‘lmagan ko‘rinishdagi namunalarga mos
keladigan satrlarni topish usulidir. Taxminiy satrlarni moslashtirish
muammosi odatda ikkita kichik muammoga bo‘linadi: berilgan satr
ichida taxminiy namuna mosliklarini topish va namunaga taxminan
mos keladigan satrlarni topish.
Levenshteyin masofasi bir nechta oddiy yuqori va quyi
chegaralarga ega. Bularga quyidagilar kiradi:
1. Berilgan ikki satrlar uzunliklari orasidagi farq.
74
Nizomaddin XUDAYBERGANOV, Shaxboz HASANOV
2. Uzunligi kattaroq bo‘lgan satrning uzunlik qiymatini
aniqlovchi birlik.
3. Agar satrlar bir xil uzunlikka ega bo‘lsa ular orasidagi farq
0 ga teng.
4. Agar satrlar bir xil o‘lchamga ega bo‘lsa, Hamming masofasi
Levenshteyin masofasining yuqori chegarasi hisoblanadi.
5. Ikki satr orasidagi Levenshteyin masofasi ularning uchinchi
satr bilan o‘zaro Levenshteyin masofalarining yig‘indisidan katta
emas (uchburchak tengsizligi o‘rinli).
Levenshteyin masofasini ikkita uzunroq satrlar orasida ham
hisoblash mumkin, ammo uni hisoblash uchun sarflanadigan vaqt,
bu ikki satrlar uzunligiga taxminan proporsional bo‘lib, buni amaliy
jarayonlarda foydalanish nisbatan kamroq unumdorlikka sabab
bo‘ladi. Shunday qilib, taqqoslash tezligini yaxshilash maqsadida
odatda qisqa satrlardan foydalaniladi.
Quyidagi misollar orqali nazariy bilimlarni amaliy ko‘rinishga
olib kelish mumkin.
1. “olma” so‘zidan “olmaxon” so‘zini hosil qilish uchun so‘zning
davomiga “x”, “o” va “n” harflarini qo‘shish orqali natijaga erishiladi.
Bunda umumiy 3 o‘zgarish, ya’ni qo‘shish amalga oshirildi. Demak
Levenshteyin masofasi 3 ga teng bo‘ladi.
2. Yuqoridagi misolni teskari holati qaraladigan bo‘lsa,
“olmaxon” so‘zidan “olma” so‘zini hosil qilish uchun 3 o‘zgarishni,
ya’ni so‘z oxiridagi 3 harfni o‘chirishni amalga oshirish talab qilinadi.
Bu vaziyatda ham Levenshteyin masofasi 3 ga teng bo‘ladi.
3. “men” so‘zi xatolik tufayli “man” kabi yozilgan vaziyatda
Levenshteyin masofasi nechta o‘zgartirish orqali to‘g‘ri so‘zga
erishish mumkinligini ko‘rsatadi. Bu vaziyatda faqat “a” harfini “e”
harfiga o‘zgartirish yetarli. Demak Levenshteyin masofasi 1ga teng.
Endi umumiy vaziyatda Levenshteyin masofasini yanada
chuqurroq tushunish maqsadida quyidagi o‘zbek tiliga oid bo‘lgan
“matematika” hamda “maktab” so‘zlari ko‘rib chiqiladi. Berilgan
“matematika” so‘zidan “maktab” so‘zini hosil qilish uchun o‘zaro
mos tushuvchi harflarni belgilab olish hamda boshqa belgilar uchun
o‘zgarishlarni amalga oshirish lozim bo‘ladi.
1. M, A harflaridan so‘ng K harfini qo‘shish (1 ta o‘zgarish)
2. 1- T harfidan so‘ng E, M harflarini o‘chirish (2 ta o‘zgarish)
3. 2- T harfini B harfiga almashtirish (1 ta o‘zgarish)
4. 2- T harfidan so‘ng I, K va A harflarini o‘chirish (3 ta
o‘zgarish)
|
