Graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari

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

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.

“haystack”ni indekslash qobiliyati. Agar mavjud bo'lsa, qidiruv juda tezlashadi.

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 orasida qismiy satr qidirish algoritmlari yordamida onlayn tekshiruvlarni amalga oshiradi.

17.2. Qismiy satrlarni qidirish algoritmlarining turlari

Rabin-Karp algoritmi. Rabin-Karp algoritmi-bu matnni xeshlash yordamida berilgan satrdan ichki satrni qidiradigan qidirish algoritmi. U 1987-yilda Maykl Rabin va Richard Karp tomonidan ishlab chiqilgan.
Algoritm kamdan-kam hollarda bitta qismiy satrni topish uchun ishlatiladi, lekin muhim nazariy ahamiyatga ega va bir xil uzunlikdagi bir nechta qismiy satr uchun moslikni topishda juda samarali. n uzunlikdagi matn va m uzunlikdagi qismiy satr uchun uning o'rtacha va eng yaxshi bajarilish vaqti to'g'ri xesh funksiyasi bilan O (n) dir, lekin eng yomon holatda uning samaradorligi 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 kodi qiymatini topamiz.

0	1	2	3
e	s	a	p
↓	↓	↓	↓
5	19	1	16

Xesh-kod qiymati: 5+19+1+16=41