qismiy satrlarni qidirish algoritmlari

DOCX 11 sahifa 30,7 KB Bepul yuklash

11 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 30,7 KB

Fayl turi DOCX

Sahifalar 11

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 11

8-ma’ruza.satrlarda qismiy satrlarni qidirish algoritmlari qismiy satrlarni izlashda primitive algoritmlarning kamchiligi satrlardan qismiy satrni qidirish algoritmi – bu matnda (text) qismiy satr (pattern) topishga imkon beradigan satrlar ustidagi algoritmlar sinfi. u matn muharrirlari, mbbt, qidiruv tizimlari, dasturlash tillari va boshqalarda o'rnatilgan funksiya sifatida ishlatiladi. qidiruv vazifalarida qidiruv satrni “igna” (inglizchadan - "needle") va qidiruv o'tkaziladigan satrni “g’aram” (ingliz tilidan - "haystack") deb belgilash odat tusiga kirgan. shuningdek, biz qidirish olib boriladigan alifboni σ bilan belgilaymiz. primitiv algoritmning muvaffaqiyatsizligi. agar satrlar birdan boshlab raqamlangan deb hisoblasak, eng oddiy “qo'pol kuch” (brute force) algoritmi (sodda algoritm) quyidagicha bo’ladi: for i=0...|haystack|-|needle| for j=0...|needle| if haystack[i+j + 1]<>needle[j] then goto 1 output("topildi: ", i+1) 1: eng oddiy qidirish algoritmi, eng yaxshisi, |haystack| - |needle| +1 taqqoslash; agar bir-biriga o'xshashliklar ko'p bo'lsa, tezlik o(|haystack|·|needle|) ga tushadi. primitiv algoritm o'rtacha 2 soatlik taqqoslashda ishlayotgani isbotlangan. bugungi kunda qismiy satrlarni qidirish algoritmlarining xilma-xilligi mavjud. dasturchi bunday omillarga …

2 / 11

rxitekturasi. ba'zi protsessorlarda avtomatik kattalashtirish yoki simd amallari mavjud bo'lib, ular sizga ikkita operativ xotirani tez taqqoslashga imkon beradi (masalan, x86-da rep cmpsd). bunday protsessorlarda “needle”ni “haystack” bilan taqqoslaydigan algoritmni qo'llash juda qiziq - albatta, hamma pozitsiyalarda emas. 5. alifbo o'lchami. ko'p algoritmlar (ayniqsa, oxirigacha taqqoslashga asoslangan), mos kelmaydigan belgi bilan bog'liq evristikaga ega. katta alifbolarda ramzlar jadvali ko'p xotirani egallaydi, kichik alifbolarda tegishli evristik samarasiz bo'ladi. 6. “haystack”ni indekslash qobiliyati. agar mavjud bo'lsa, qidiruv juda tezlashadi. 7. bir vaqtning o'zida bir nechta satrlarni qidirish kerakmi? ba'zi algoritmlarning yon xususiyatlari (axo-korasik, ikkilik algoritm) bunga imkon beradi. qoida tariqasida, matn tahrirlovchisida boyer-mur-xorspul kabi eng oddiy evristik algoritmni olish kifoya-hatto juda sekin kompyuter ham bir soniya ichida qidirishni amalga oshira oladi. agar matn hajmi gigabaytda o'lchanadigan bo'lsa yoki qidiruv ko'plab so'rovlarni bajaradigan serverda ishlayotgan bo'lsa, siz eng muvaffaqiyatli algoritmni tanlashingiz kerak bo'ladi. masalan, plagiatni aniqlash dasturlari o'z ma'lumotlar bazasida saqlanadigan ko'plab hujjatlar …

3 / 11

orligi o (nm) ga teng. bu esa keng qo'llanilmasligining sabablaridan biridir. rabin-karp algoritmining eng oddiy amaliy qo'llanmalaridan biri plagiatni aniqlashdir. rabin-karp algoritmi tekshirilgan maqoladagi manba materiallardan ba'zi jumlalar paydo bo'lishining misollarini tezda topishi mumkin. algoritmning kichik farqlarga sezgirligini yo'q qilish uchun siz ularni olib tashlash orqali harf yoki tinish belgi kabi tafsilotlarni e'tiborsiz qoldirishingiz mumkin. biz qidirayotgan qatorlar soni juda katta bo'lgani uchun, bitta satrlarni topishning an'anaviy algoritmlari samarasiz bo'lib qoladi. quyidagi misol orqali rabin-karp algoritmini ko’rib chiqamiz. berilgan matn s= “aevesapng” izlanadigan satr p= “esap” 0 1 2 3 4 5 6 7 8 a e v e s a p n g 0 1 2 3 e s a p quyida simvollar uchun xesh-kod keltirilgan: a → 1 b → 2 c → 3 d → 4 e → 5 f → 6 … → … z → 26 1-qadam. belgilarga tayinlangan xesh kodi yordamida qismiy satrning xesh …

4 / 11

dining qiymati bir xil, shuning uchun biz ichki qismiy belgilarini qidiriluvchi satr bilan birma -bir tekshiramiz. 0 1 2 3 4 5 6 7 8 a e v e s a p n g ↓ ↓ ↓ ↓ e s a p barcha belgilar mos keladi, keyin biz ichki satrning boshlang'ich indeksini chop etamiz va iloji bo'lsa, m uzunlikdagi keyingi qismiy satrga o'tamiz. 6-qadam. 0 1 2 3 4 5 6 7 8 a e v e s a p n g ↓ ↓ ↓ ↓ 19 1 16 14 xesh kod qiymati: 19+1+16+14 = 50 joriy ichki satrning xesh qiymati qismiy satrning xesh qiymatiga mos kelmaydi. shunday qilib, iloji bo'lsa, m uzunligining keyingi ichki satriga o’tamiz, aks holda to'xtatamiz. 7-qadam. 0 1 2 3 4 5 6 7 8 a e v e s a p n g ↓ ↓ ↓ ↓ 1 16 14 7 xesh kod qiymati: …

5 / 11

kelsa, shablon bu qo'shimchaning birinchi mos kelishiga qadar o'ngga siljiydi 1. q w t e e q e w q r w q w r q r q w r q r 2. q w t e e q e r q r w q w r q r q w r q r 3. q w t e e q e w q r w q w r q r q w r q r 4. q w t e e q e w q r w q w r q r q w r q r to'xtatish belgisi jadvali. qismiy satrdagi elementning oxirgi o'rnini belgilaydi (oxirgi harfdan tashqari). agar qismiy satrda element bo'lmasa, jadvalga 0 kiritiladi (bittadan raqamlash uchun) misol. qismiy satr: qwrqr simvol q w r e t oxirgi pozitsiya 4 2 3 0 0 1. q t e e q r w q w r e …

Ko'proq o'qimoqchimisiz?

Barcha 11 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"qismiy satrlarni qidirish algoritmlari" haqida

8-ma’ruza.satrlarda qismiy satrlarni qidirish algoritmlari qismiy satrlarni izlashda primitive algoritmlarning kamchiligi satrlardan qismiy satrni qidirish algoritmi – bu matnda (text) qismiy satr (pattern) topishga imkon beradigan satrlar ustidagi algoritmlar sinfi. u matn muharrirlari, mbbt, qidiruv tizimlari, dasturlash tillari va boshqalarda o'rnatilgan funksiya sifatida ishlatiladi. qidiruv vazifalarida qidiruv satrni “igna” (inglizchadan - "needle") va qidiruv o'tkaziladigan satrni “g’aram” (ingliz tilidan - "haystack") deb belgilash odat tusiga kirgan. shuningdek, biz qidirish olib boriladigan alifboni σ bilan belgilaymiz. primitiv algoritmning muvaffaqiyatsizligi. agar satrlar birdan boshlab raqamlangan deb hisoblasak, eng oddiy “qo'pol kuch” (brute force) algoritmi (sodda algoritm...

Bu fayl DOCX formatida 11 sahifadan iborat (30,7 KB). "qismiy satrlarni qidirish algoritmlari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: qismiy satrlarni qidirish algor… DOCX 11 sahifa Bepul yuklash Telegram