Tabiiy tilni qayta ishlashda so‘zlar orasidagi masofani aniqlash algoritmlaridan foydalanish
71
belgilarini o‘zaro taqqoslash hamda Hamming masofasini aniqlovchi
o‘zgaruvchi olishimiz va uni doimo o‘zgarishlar jarayonida oshirib
borishimiz talab qilinadi. Misol qilib “daftar” hamda “maktab”
so‘zlardan foydalanilganda ular orasidagi Hamming masofasini
hisoblash ko‘rsatilgan.
1-rasm. Hamming masofasini aniqlashga oid misollar
Boshqacha qilib aytganda, “daftar” so‘zidan “maktab” so‘zini
hosil qilishimiz uchun 3 ta belgini o‘zgartirish yetarli bo‘ladi.
Satrlarda belgilar soni tengligi orqali
natijaga erishishimiz uchun
faqatgini belgilar almashuvini qo‘llashimiz yetarli bo‘ladi. Xuddi shu
usulda quyidagi misollarda ham Hamming masofasi hisoblanadi.
1. “kun” va “tun” bir xil uzunlikdagi so‘zlar aynan 1 ta turli
belgiga ega demak, ular orasidagi Hamming masofasi 1 ga teng
bo‘ladi.
2. “uycha” va “uyat” so‘zlarida o‘zbek tilida ikkala so‘z ham 4
ta harfdan iborat, lekin belgilar soni turli (mos ravishda 5 ta va 4 ta)
bo‘lganligi sababli Hamming masofasini aniqlashning iloji yo‘q.
3. 00010011 va 01010111 ikkilik sanoq sistemasiga tegishli
bo‘lgan ushbu sonlar orasidagi 3-va 6-belgilar farq
qilganligi sababli
Hamming masofasi 2 ga teng.
O‘zgarmas n uzunlikdagi satr uchun Hammming masofasi n
uzunlikdagi so‘zlar to‘plamining ko‘rsatkichidir (hamming fazosi deb
ham ataladi). Chunki u musbat va simmetriya shartlarini bajaradi.
Agarda ikki so‘zning Hamming masofasi 0 ga teng bo‘lsa, ular
aynan bir xil bo‘ladi. Bundan tashqari ushbu qiymatlar uchburchak
tengsizligini ham qanoatlantiradi. Haqiqatan ham, agar uchta a,
b va c so‘zlari ko‘riladigan bo‘lsa, a satrning i-o‘rindagi
qiymati
72
Nizomaddin XUDAYBERGANOV, Shaxboz HASANOV
b satrning i-o‘rindagi qiymati va c satrning xuddi shu qiymatlari
solishtiriladigan bo‘lsa nazariya to‘g‘riligini ko‘rish mumkin
bo‘ladi. Demak, a va c orasidagi Hamming masofasi a va b hamda
b va c orasidagi Hamming masofalarining yig‘indisidan katta emas.
Ikkita ikkilik sanoq sistemasidagi a va b qiymatlar uchun Hamming
masofasi a XOR b dagi birlar soniga teng. Ushbu qiymat esa kodlash
nazariyasida xatolikni aniqlash va xatolarni tuzatish yo‘nalishida
foydalaniladi [Derek, 2003, 255].
Tabiiy tilni qayta ishlash yo‘nalishida
qisqa uzunlikdagi
so‘zlar orasidagi masofalarni aniqlash hamda ularni to‘g‘irlash
orqali foydalanish maqsadga muvofiq bo‘ladi. Bundan tashqari
kodlash nazariyasi sohasida ham ikkilik sanoq sistemasida berilgan
xatoliklarni aniqlash va bartaraf etish uchun samarali yechim bo‘la
oladi. Katta hajmdagi matn yoki hujjatlar uchun foydalanish uchun
yuqori samaradorlikka ega emas.