O’zbekiston aloqa, axboratlashtirish va telekommunikatsiya texnologiyalari davlat qo’mitasi toshkent axborot texnologiyalari universiteti

Bajardi: Mamatqulov Mavlon
Raxbar:
O’ZBEKISTON ALOQA, AXBORATLASHTIRISH VA TELEKOMMUNIKATSIYA
TEXNOLOGIYALARI DAVLAT QO’MITASI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
“Lug'atlarni qayta tiklash asoslari” mavzusidagi
MUSTAQIL ISHI
Mavzu rejasi:

• Lug'atlar uchun tuzilmalarni qidirish, joker belgili so'rovlar.
• vaqtinchalik indekslar, joker belgilar so'rovlari uchun k-gram indekslari
• imlo tuzatish va uning shakllari, masofani tahrirlash


• imloni tuzatish uchun k-gramm indekslari, Fonetik tuzatishlar.

1
2
3
Qurilish mahsulotlari axborot
tizimini tahlil qilish.
Axbarot tizimini ishlab chiqishda raqamli texnologiyalarning o’rni.
Axborot tizimini ishlab chiqish,
Dasturchi va foydalanuvchi
yo’riqnomasi bilan tanishtrish.
Vazifalari
Lug'atlar uchun tuzilmalarni qidirish
Inverted indeks va so'rovni hisobga olgan holda, bizning birinchi vazifamiz har bir so'rov atamasi lug'atda mavjudligini aniqlash va agar mavjud bo'lsa, tegishli xabarlarga ko'rsatgichni aniqlashdir. Ushbu lug'atni qidirish operatsiyasi lug'at deb ataladigan klassik ma'lumotlar tuzilmasidan foydalanadi va ikkita keng toifadagi echimlarga ega: xeshlash va qidiruv daraxtlari. Ma'lumotlar tuzilmalari adabiyotida lug'atdagi yozuvlar (bizning holatlarimizda, atamalar) ko'pincha kalitlar deb ataladi.. Yechimni tanlash (hashing yoki qidiruv daraxtlari) bir qator savollar bilan tartibga solinadi: (1) Bizda nechta kalit bo'lishi mumkin? (2) Raqam statik bo'lib qolishi yoki ko'p o'zgarishi mumkinmi - va o'zgarishlar bo'lsa, bizda faqat yangi kalitlar kiritilishi yoki lug'atdagi ba'zi kalitlar o'chirilishi mumkinmi? (3) Turli kalitlarga kirish mumkin bo'lgan nisbiy chastotalar qanday?
Hashing ba'zi qidiruv tizimlarida lug'at qidirish uchun ishlatilgan. Har bir lug'at atamasi (kalit) etarlicha katta bo'shliqda butun songa xeshlangan bo'lib, xesh to'qnashuvi ehtimoli yo'q; to'qnashuvlar, agar mavjud bo'lsa, parvarish qilishni talab qiladigan yordamchi tuzilmalar tomonidan hal qilinadi.   So'rov vaqtida biz har bir so'rov atamasini alohida-alohida va mos keladigan xabarlarga ko'rsatgichni kuzatib, xesh to'qnashuvlarini hal qilish uchun har qanday mantiqni hisobga olgan holda hash qilamiz. So'rov atamasining kichik variantlarini topishning oson yo'li yo'q (masalan, rezyume kabi so'zning urg'uli va urg'usiz versiyalari), chunki ularni juda boshqacha butun sonlarga xeshlash mumkin. Xususan, biz (masalan, avtomat prefiksi) bilan boshlangan barcha atamalarni qidira olmaymiz, biz quyida 3.2- bo'limda talab qiladigan operatsiya. Va nihoyat, lug'at hajmi doimiy ravishda o'sib borayotgan muhitda (masalan, Internetda), joriy ehtiyojlar uchun mo'ljallangan hash funktsiyasi bir necha yil ichida etarli bo'lmasligi mumkin.
Joker belgilar so'rovlari
Joker belgilar soʻrovlari quyidagi vaziyatlarning har qandayida qoʻllaniladi: (1) foydalanuvchi soʻrov atamasining imlosiga ishonchsiz boʻlsa (masalan, S*dney joker belgisi soʻroviga olib keladigan Sidney va Sidney); (2) foydalanuvchi atama imlosining bir nechta variantlarini biladi va (ongli ravishda) har qanday variantni o'z ichiga olgan hujjatlarni qidiradi (masalan, rang va rang); (3) foydalanuvchi atamaning stemming orqali qo‘lga olinishi mumkin bo‘lgan variantlarini o‘z ichiga olgan hujjatlarni qidiradi, lekin qidiruv tizimi stemmingni amalga oshiradimi yoki yo‘qmi (masalan, sud va sud tizimi, judicia* joker belgisiga olib keladi); (4) foydalanuvchi xorijiy so‘z yoki iboraning to‘g‘ri talqin qilinishiga ishonchi yo‘q (masalan, Universit* Stuttgart so‘rovi).
Mon* kabi so'rov keyingi joker so'rov sifatida tanilgan, chunki * belgisi faqat bir marta, qidiruv satrining oxirida bo'ladi. Lug'atdagi qidiruv daraxti keyingi joker so'rovlarni boshqarishning qulay usulidir: biz navbatma-navbat m, o va n belgilari bo'yicha daraxt bo'ylab yuramiz, shu nuqtada lug'atdagi atamalar to'plamini $W$ bilan sanashimiz mumkin. mon prefiksi. Va nihoyat, biz $W$ dagi istalgan atamani o'z ichiga olgan barcha hujjatlarni olish uchun standart teskari indeksda $\vert W\vert$ qidiruvlaridan foydalanamiz.
Joker belgilar so'rovlari
Ammo * belgisi qidiruv satrining oxirida bo'lishi cheklanmagan joker belgilar so'rovlari haqida nima deyish mumkin? Ushbu umumiy holatni ko'rib chiqishdan oldin, biz keyingi joker belgilar so'rovlarini biroz umumlashtirishni eslatib o'tamiz. Birinchidan, etakchi joker so'rovlarni yoki *mon shaklidagi so'rovlarni ko'rib chiqing. Lug'atdagi teskari B-daraxtni ko'rib chiqing - unda B-daraxtning har bir ildizdan bargga o'tish yo'li lug'atdagi teskari yozilgan atamaga to'g'ri keladi: shunday qilib, limon atamasi B daraxtida ifodalanadi. ildiz-n-o-m-e-l yo'li bilan. Teskari B-daraxt bo‘ylab sayr qilib, keyin berilgan prefiks bilan lug‘atdagi barcha $R$ atamalarini sanab o‘tadi.
Haqiqatan ham, oddiy B-daraxtni teskari B-daraxt bilan birgalikda ishlatib, biz yanada umumiy holatni hal qilishimiz mumkin: bitta * belgisi bo'lgan joker belgilar so'rovlari, masalan, se*mon. Buning uchun se prefiksi bilan boshlangan $W$ lug‘at atamalarini sanab o‘tish uchun oddiy B daraxtidan, so‘ng teskari B daraxtidan mon qo‘shimchasi bilan tugaydigan $R$ to‘plamini sanab o‘tamiz. Keyinchalik, se prefiksi bilan boshlanib, mon qo'shimchasi bilan tugaydigan atamalar to'plamiga kelish uchun ushbu ikki to'plamning $W\cap R$ kesishmasini olamiz. Nihoyat, biz ushbu kesishmadagi har qanday atamalarni o'z ichiga olgan barcha hujjatlarni olish uchun standart teskari indeksdan foydalanamiz. Shunday qilib, biz ikkita B-daraxt, oddiy B-daraxt va teskari B-daraxt yordamida bitta * belgisini o'z ichiga olgan joker belgilar so'rovlarini boshqarishimiz mumkin.
x`
joker belgilar so'rovlari uchun k-gram indekslari
Vaqtinchalik indeks oddiy bo'lsa-da, bir muddatda aylanishlar sonidan sezilarli portlashga olib kelishi mumkin; Ingliz tilidagi atamalar lug'ati uchun bu deyarli o'n baravar ko'paygan joyni ko'rsatishi mumkin. Endi biz joker belgilar so'rovlarini qayta ishlash uchun -gram indeksi deb nomlanuvchi ikkinchi texnikani taqdim etamiz $k$. 3.3.4-$k$ bo'limda -gram indekslaridan ham foydalanamiz . A - gramm belgilar ketma-ketligi$k$$k$. Shunday qilib, cas, ast va stl qal'a atamasida uchraydigan 3 grammdir. Biz atamaning boshini yoki oxirini belgilash uchun maxsus $ belgisidan foydalanamiz, shuning uchun qal'a uchun yaratilgan 3-grammning to'liq to'plami: $ca, cas, ast, stl, tle, le$.
x`