qismiy satrlarni qidirish algoritmlari

DOCX 11 стр. 30,7 КБ Бесплатная загрузка

11 стр.

FaylHub.uz

Скачать через Telegram

Размер 30,7 КБ

Тип файла DOCX

Страницы 11

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

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 …

Хотите читать дальше?

Скачайте все 11 страниц бесплатно через Telegram.

Скачать полный файл

О "qismiy satrlarni qidirish algoritmlari"

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...

Этот файл содержит 11 стр. в формате DOCX (30,7 КБ). Чтобы скачать "qismiy satrlarni qidirish algoritmlari", нажмите кнопку Telegram слева.

Теги: qismiy satrlarni qidirish algor… DOCX 11 стр. Бесплатная загрузка Telegram