Va innovatsiyalar vazirligi osiyo xalqaro universitetining ijtimoiy

Shift qoidalari
Shishish ikki qoidani qo'llash orqali hisoblanadi: yomon belgilar qoidasi va yaxshi qo'shimchalar qoidasi. Haqiqiy siljish ofset - bu qoidalar bilan hisoblangan siljishlarning maksimali.
Yomon xarakter qoidasi
Tavsif
Yomon belgilar qoidasi T-dagi taqqoslash jarayoni muvaffaqiyatsizlikka uchragan belgini ko'rib chiqadi (bunday nosozlik sodir bo'lgan deb hisoblanadi). Bu belgining keyingi P da chapga kelishi topiladi va bu hodisani T dagi mos kelmaydigan hodisaga mos keladigan siljish taklif etiladi. Agar mos kelmaydigan belgi P ning chap tomoniga tushmasa, P ning to'liq mos kelmasligi nuqtasidan o'tib ketadigan siljish taklif etiladi.

-	-	-	-	X	-	-	K	-	-	-
A	N	P	A	N	M	A	N	A	M	-
-	N	N	A	A	M	A	N	-	-	-
-	-	-	N	N	A	A	M	A	N

P = NNAAMAN naqshli yomon xarakterli qoidani namoyish qilish. X bilan belgilangan ustunda N (kiritilgan matnda) va A (naqshda) oʻrtasida nomuvofiqlik bor. Naqsh oʻngga (bu holda 2ga) siljiydi, shunda N belgisi keyingi paydo boʻladi. qolip P da joriy belgining chap tomonida (o'rta A) topiladi.

Oldindan ishlov berish
Usullar yomon belgilar qoidasi uchun jadval qanday shaklga ega bo'lishi kerakligiga qarab farqlanadi, lekin oddiy doimiy qidiruv yechimi quyidagicha: 2D jadval yarating, u avval alifbodagi c belgisi indeksi, ikkinchisi esa tomonidan indekslanadi. naqshdagi i indeksi. Bu qidiruv, agar bunday hodisa bo'lmasa, keyingi eng yuqori indeks jQuyidagi C va Java ilovalari O(k) fazoviy murakkablikka ega (make_delta1, makeCharTable). Bu asl delta1 va BMH yomon belgilar jadvali bilan bir xil. Ushbu jadval i pozitsiyasidagi belgini len (p)-1-i ga siljitish uchun xaritalaydi, oxirgi misol - eng kam siljish miqdori - ustunlik qiladi. Barcha foydalanilmagan belgilar sifatida o'rnatiladi len (p) qo'riqchi qiymat sifatida.


Yaxshi qo'shimcha qoidasi
Tavsif
Yaxshi qo'shimchalar qoidasi yomon belgilar qoidasiga qaraganda tushunchada ham, amalga oshirishda ham sezilarli darajada murakkabroq. Yomon belgilar qoidasi singari, u naqsh oxiridan boshlanib, naqsh boshlanishigacha davom etadigan taqqoslash algoritmining xususiyatidan ham foydalanadi.

-

-

-

-

X

-

-

K

-

-

-

-

-

M

A

N

P

A

N

A

M

A

N

A

P

-

A

N

A

M

P

N

A

M

-

-

-

-

-

-

-

-

-

A

N

A

M

P

N

A

M

-

P = ANAMPNAM naqshli yaxshi qo'shimchalar qoidasini namoyish qilish. Bu yerda t - T[6..8] va t' - P[2..4]
Uni quyidagicha tavsiflash mumkin:
Aytaylik, P va T ning berilgan tekislashi uchun T ning t pastki qatori P qo‘shimchasiga to‘g‘ri keladi va t berilgan tekislash uchun shunday eng katta qator bo‘lsin.

1. 
   So‘ngra, agar u mavjud bo‘lsa, P dagi t ning eng o‘ngdagi nusxasini toping, shunda t’ P ning qo‘shimchasi emas va P dagi t ning chap tomonidagi belgi
   
2. 
   P dagi t ning chap tomonidagi belgidan farq qiladi. P ni o'ngga o'tkazing, shunda P dagi t 'pastki qator T dagi t qatoriga to'g'ri keladi.
   
3. 
   Agar t' mavjud bo'lmasa, P harfining chap uchini eng kam miqdorda o'ngga
   
4. 
   (T dagi t ning chap uchidan o'tib) siljiting, shunda o'zgartirilgan naqsh prefiksi
   
5. 
   T dagi t qo'shimchasiga mos keladi. Bunga holatlar ham kiradi.
   
6. 
   Bu yerda t - P ning aniq mosligi.
   
7. 
   Agar bunday siljishning iloji bo'lmasa, u holda P ni m (P uzunligi) joylarini o'ngga siljiting.