Bizda quyidagi matn bor bo’lsin

Rabin-Karp String Search

Garvard universiteti professori Maykl O. Rabin va Richard Karp O ( MN ) dan farqli ravishda O ( M + N ) tilida qator qidirishni amalga oshirish uchun xeshingdan foydalanish usulini ishlab chiqdilar . Boshqacha qilib aytganda, kvadratik vaqtdan farqli o'laroq, chiziqli vaqtda, yaxshi tezlik.
Rabin-Karp algoritmi barmoq izlari deb ataladigan texnikadan foydalanadi.
1. Uzunligi n naqshini hisobga olib , uni hashlang. 2. Endi matn satrining birinchi n ta belgisini xeshlang. 3. Xesh qiymatlarini solishtiring. Ular bir xilmi? Agar yo'q bo'lsa, unda ikkita satr bir xil bo'lishi mumkin emas. Agar ular shunday bo'lsa, ular aslida bir xil satr ekanligini yoki bir xil qiymatga xeshlanganligini tekshirish uchun oddiy satrlarni taqqoslashimiz kerak (ikki xil satr bir xil qiymatga xeshlanishi mumkinligini yodda tuting). Agar ular mos kelsa, biz tugatamiz. Agar yo'q bo'lsa, biz davom etamiz. 4. Endi matn qatoridagi belgi ustiga siljiting. Xesh qiymatini oling. Satr topilmaguncha yoki matn qatorining oxiriga yetguncha yuqoridagi kabi davom eting.
Endi siz o'zingizga hayron bo'lishingiz mumkin: "Tushunmadim. Qanday qilib bu matn qatoridagi har bir joy uchun xeshni yaratish uchun O ( MN ) dan kam bo'lishi mumkin, biz har bir belgini ko'rib chiqishimiz shart emasmi? unda?" Javob yo'q va bu Rabin va Karp kashf etgan hiyla.
Dastlabki xeshlar barmoq izlari deb ataladi. Rabin va Karp doimiy ravishda bu barmoq izlarini yangilash usulini topdilar. Boshqacha qilib aytganda, matn qatoridagi pastki satr xeshidan keyingi xesh qiymatiga o'tish uchun faqat doimiy vaqt kerak bo'ladi. Keling, oddiy xesh funktsiyasini olaylik va bu nima uchun va qanday ishlashini ko'rish uchun misolni ko'rib chiqamiz.
Hayotimizni osonlashtirish uchun oddiy xesh funksiyasidan foydalanamiz. Bu xesh-funktsiyaning barchasi har bir harfning ASCII qiymatlarini qo'shish va uni bir nechta asosiy raqam bilan o'zgartirishdir:
int hash(char* str) { int sum = 0; while (*str != '\0') summa += (int) *str++; qaytarish summasi % 3; }
Endi bir misol keltiramiz. Aytaylik, bizning naqshimiz "kabin". Aytaylik, bizning matn qatorimiz "aabbcaba". Aniqlik uchun biz bu yerda harflarni haqiqiy ASCII qiymatlaridan farqli ravishda ifodalash uchun 0 dan 26 gacha foydalanamiz.
Birinchidan, biz "abc" xeshini olamiz va bu hash("abc") == 0 ni topamiz . Endi biz matn satrining dastlabki uchta belgisini xeshlaymiz va bu hash("aab") == 1 ni topamiz .
Rasm %: Dastlabki barmoq izlari
Ular mos keladimi? 1 = = 0 bo'ladimi ? Yo'q. Shunday qilib, biz davom etishimiz mumkin. Endi doimiy vaqtda xesh qiymatini yangilash muammosi keladi. Biz ishlatgan xesh funktsiyasining yaxshi tomoni shundaki, u bizga buni amalga oshirishga imkon beradigan ba'zi xususiyatlarga ega. Buni sinab ko'ring. Biz "aab" bilan boshladik, u 1 ga xeshlangan. Keyingi belgi nima? 'b'. Ushbu yig'indiga "b" qo'shing, natijada 1 + 1 = 2 bo'ladi . Oldingi xeshdagi birinchi belgi nima edi? 'a'. Shunday qilib, 2 dan "a" ni ayiring; 2 - 0 = 2 . Endi modulni yana oling; 2%3 = 2. Shunday qilib, bizning taxminimiz shundan iboratki, oynani surganimizda, biz shunchaki matn qatorida paydo bo'ladigan keyingi belgini qo'shishimiz va derazamizdan chiqib ketayotgan birinchi belgini o'chirishimiz mumkin. Bu ishlaydimi? Agar biz buni oddiy usulda qilsak, "abb" xesh qiymati qanday bo'ladi: (0 + 1 + 1)%2 = 2 . Albatta, bu hech narsani isbotlamaydi, lekin biz rasmiy dalil qilmaymiz. Agar bu sizni shunchalik bezovta qilsa, buni mashq sifatida bajaring.
Rasm %: Barmoq izi yangilanmoqda
Yangilashni amalga oshirish uchun ishlatiladigan kod quyidagicha ko'rinadi:
int hash_increment(char* str, int prevIndex, int prevHash, int keyLength) { int val = (prevHash - ((int) str[prevIndex]) + ((int) str[prevIndex + keyLength])) % 3; Qaytish (val <0) ? (val + 3) : val; }
Keling, misol bilan davom etaylik. Yangilanish tugallandi va biz mos keladigan matn "abb":
Rasm %: Ikkinchi taqqoslash
Xesh qiymatlari boshqacha, shuning uchun biz davom etamiz. Keyingisi:
Rasm %: Uchinchi taqqoslash
Turli xil xesh qiymatlari. Keyingisi:
Rasm %: Toʻrtinchi taqqoslash
Hmm. Bu ikki xesh qiymatlari bir xil, shuning uchun biz "bca" va "cab" o'rtasida qator taqqoslashimiz kerak. Ular bir xilmi? Yo'q. Shunday qilib, biz davom etamiz:
Rasm %: Beshinchi taqqoslash
Shunga qaramay, biz xesh qiymatlari bir xil ekanligini topamiz, shuning uchun biz "cab" va "cab" qatorlarini taqqoslaymiz. Bizda g'olib bor.
Yuqoridagi kabi Rabin-Karpni bajarish uchun kod quyidagicha ko'rinadi:
int rksearch(char* naqsh, char* matn) { int naqsh_xesh, matn_xesh, naqsh_len, takroriy sonlar, i; /* naqsh va matn qonuniy satrlarmi? */ agar (naqsh == NULL || matn == NULL) -1ni qaytaradi; /* satrlarning uzunligi va takrorlanishlar sonini oling */ pattern_len = strlen(pattern); takrorlashlar soni = strlen (matn) - naqsh_len + 1; /* Dastlabki xeshlarni bajaring */ pattern_hash = hash(pattern); text_hash = hashn (matn, naqsh_len); /* Asosiy taqqoslash tsikli */ for (i = 0; i < num_iterations; i) { if (pattern_hash == text_hash && !strncmp(pattern, &(matn[i]), pattern_len)) return i; text_hash = hash_increment(matn, i, matn_hash, naqsh_len); } /* Naqsh topilmadi, shuning uchun -1 qaytaring */ -1; } /* barmoq izlarini olish uchun xesh funksiyasi */ int hash(char* str) { int sum = 0; while (*str != '\0') summa += (int) *str; qaytarish summasi % MODULUS; } int hashn(char* str, int n) { char ch = str[n]; int sum; str[n] = '\0'; summa = hash(str); str[n] = ch; qaytarish summasi; } int hash_increment(char* str, int prevIndex, int prevHash, int keyLength) { int val = (prevHash - ((int) str[prevIndex]) + ((int) str[prevIndex + keyLength])) % MODULUS; Qaytish (val <0) ? (val + MODUL) : val; } int prevIndex, int prevHash, int keyLength) { int val = (prevHash - ((int) str[prevIndex]) + ((int) str[prevIndex + keyLength])) % MODUL; Qaytish (val <0) ? (val + MODUL) : val; } int prevIndex, int prevHash, int keyLength) { int val = (prevHash - ((int) str[prevIndex]) + ((int) str[prevIndex + keyLength])) % MODUL; Qaytish (val <0) ? (val + MODUL) : val; }

Muammo: Xesh jadvalining joriy qo'llanilishini kengaytirib, xesh jadvalidan satrni olib tashlash uchun o'chirish funktsiyasini yozing.
int delete_string(hash_table_t *heshtable, char *str) { int i; list_t *ro‘yxat, *oldingi; unsigned int hashval = hash(str); /* roʻyxat bandini kuzatib boradigan jadvaldagi satrni toping * unga ishora qiluvchi */
for(prev=NULL, list=hashtable->table[hashval]; list != NULL && strcmp(str, list->str) ); oldingi = ro'yxat, ro'yxat = ro'yxat->keyingi); /* agar topilmasa, xato sifatida 1ni qaytaring */ agar (list==NULL) 1ni qaytaring; /* string */ /* jadvalida mavjud emas, aks holda u mavjud. uni jadvaldan olib tashlang */ if (oldingi==NULL) hashtable[hashval] = list->keyingi; else prev->keyingi = list->keyingi; /* u bilan bog'langan xotirani bo'shatish */ free(list->str); bepul (ro'yxat); qaytish 0; }
Muammo: Joriy amaliyotimizni kengaytirish uchun xesh jadvalida saqlangan satrlar sonini hisoblaydigan funktsiyani yozing.
int count_strings(hash_table_t *heshtable) { int i, count = 0; list_t *ro‘yxat; /* xeshtable mavjudligiga ishonch hosil qilish uchun xato tekshiruvi */ if (hashtable==NULL) -1ni qaytaradi; /* har bir indeksni ko'rib chiqing va har bir indeksdagi barcha ro'yxat elementlarini hisoblang */ for(i=0; isize; i) { for(list=hashtable[i]; list != NULL; list = list- >keyingi) hisoblash; } qaytish soni; }