Eng katta qismiy ketma- ketlikni tezkor qidirish
![MUNDARIJA:
I-bob. Kirish ..................................................................................................................................................................... 3
II-bob. Asosiy qism .......................................................................................................................................................... 4
ENG KATTA QISMIY KETMA- KETLIKNI TEZKOR QIDIRISH ............................................................................................... 4
O(n log log k) optimallashtirish. ...................................................................................................................................... 9
Eng uzun ortib borayotgan qismiy ketma-ketmaketlikni qayta tiklash ........................................................................ 16
Eng uzun ortib borayotgan keyingi ketma-ketlik muammosi ....................................................................................... 17
Bizga quyidagicha masala berilgan bo’lsin: Massivi berilgan : a [ 0 .. n - 1 ] va uning n ta elementi mavjud. Ushbu
ketma-ketlikda eng uzun uzunlikdagi qat'iy ortib boruvchi ketma-ketlikni topish talab qilinadi. Eng ortib boruvchi
pastki ketma-ketlik (NVP) (Ing. Eng uzun ortib borayotgan quyi ketma-ketlik, LIS ) qatori x, uzunligi n Bu ketma-
x[i1]<x[i2]< <x[ik] qator belgilar⋯ x shu kabi i1<i2< <ik,1 ij n , va ⋯ ⩽ ⩽ k - mumkin bo'lgan eng katta qiymat. ................ 17
Algoritmik murakkabligi O (N 2
). .................................................................................................................................. 17
O(N log N) dagi yechim ................................................................................................................................................. 19
O(N log N) dagi boshqa yechim .................................................................................................................................... 21
Maksimal umumiy ketma-ketlikni topish ..................................................................................................................... 23
Joy uchun kurash yoki Xirshberg algoritmi. Ushbu algoritm ortidagi g'oya oddiy: agar siz x = x 1 x 2 ... x m kirish
ketma-ketligini istalgan i chegara indeksida ikkita ixtiyoriy qismga bo'lsangiz, xb = x 1 x 2 ... x i va xe = x i + 1 x i +
2 ... x m , keyin y ni shunga o'xshash tarzda bo'lish usuli mavjud (y ni yb = y 1 y 2 ... y j va ye = y ga ajratadigan j
indeksi mavjud. j + 1 y j + 2 ... y n ) shunday bo‘lsinki, LCS (x, y) = LCS (xb, yb) + LCS (xe, ye). Ushbu bo'linishni topish
uchun y taklif qilinadi: ................................................................................................................................................... 27
III-bob.Xulosa ................................................................................................................................................................ 34
Foydalanilgan adabiyotlar ............................................................................................................................................. 35
2](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_2.png?v=1)
![⟶
3-rasm.
Ketma-ketlik misoli
4-rasm.
Har bir qo'shimcha bilan navbat holati
5-rasm.
Endi shu amallarni python dasturlash tilida ifodalaymiz.
int LIS(ππ[n])
6](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_6.png?v=1)
![PriorityQueue B // Ustuvor navbat
int k = 0 // eng ortib boruvchi pastki ketma-ketlik uzunligi
for i = 1 to n
x = ππ[i]
// har qanday holatda navbatga yangi element qo’shing
//eski elementlarni esa o’chiring
B.insert(x)
if ∃∃ B.next(x)
// element qo’shish — maksimal bo’lmagan
// x dan keying elementni o’chiring
B.delete(B.next(x))
else
// element qo’shish — maksimal
// qiymat oshdi
k = k + 1
return k
Qisman ketma-ketlik chegarasi . Qisman chegarasi ba'zi ketma-
ketlikda emas chegarasi u mavjud bo'lsa, uning pastki biri. Raqamli ketma-
ketliklarni yig'ish uchun qisman chegara ikkinchisining o'ziga xosligi tufayli odatiy
chegaraga to'g'ri keladi; ammo, eng umumiy holatda, ixtiyoriy ketma-ketlik noldan
cheksizgacha turli xil qisman chegaralarga ega bo'lishi mumkin. Bundan tashqari,
agar odatiy chegara ketma-ketlik elementlarining soni ortib borishi bilan
yaqinlashadigan nuqtani tavsiflasa, qisman chegaralar ketma-ketlikning cheksiz
ko'p elementlari mavjud bo'lgan nuqtalarni tavsiflaydi.
7](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_7.png?v=1)
![Qisman chegaraning ikkita muhim maxsus holati yuqori va pastki chegaralardir.
Eng katta qismiy ketma- ketlikni tezkor qidirish uchun algoritm .
Biz juftlarni yodlaymiz: har bir element uchun biz uning "oldingi" ni
yozamiz. Keyin, navbatdagi oxirgi elementdan boshlab, B oldingilarni kesib o'tish ,
biz eng katta qismiy ketma-ketlini tiklashimiz mumkin.
6-rasm.
7-rasm.
Dasturlash tilida esa
int[] LIS(π[n])
PriorityQueue B
int k = 0
8](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_8.png?v=1)
![int predecessor[n] // qo’shimcha n massiv
for i = 1 to n
x = π[i]
B.insert(x)
predecessor[x] = B.prev(x)
if ∃ B.next(x)
B.delete(B.next(x))
else
k = k + 1
int result[k]
int cur = B.max
for i = k - 1 downto 0
result[i] = cur
cur = predecessor[cur]
return result
quyidagicha ifodalanadi.
O (n log log k) optimallashtirish.
van Emde Boas daraxt uchun operatsiyalarini amalga O ( loglog k )
murakkablikda , qayta ishlangan qiymatlarning alifbosini qisqartirish
kerak O ( k ) …
Faraz qilaylik, biz raqamning bunday yaqinligini bilamiz k raqam m : m ⩾ k .
Buni qanday topish mumkinligini keyinroq muhokama qilamiz. Element kalitlarini
qayta ishlash jarayonida yuqoridagi algoritm LIS faqat navbat bilan ishlaydi B va
navbatda bo'lmagan ketma-ketlikning oldingi elementlariga bog'liq emas. Shuning
uchun, agar biz butun ketma-ketlikni bloklarga ajratsak m elementlar (oxirgi blok
9](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_9.png?v=1)
![9-rasm.
Teskari almashtirish natijasida esa quyidagilarga ega bo’lamiz.
10-rasm.
Blokni qayta ishlash. Blokni qayta ishlashda har bir element x bu blok
ichida biz kalitni birma-bir moslashtiramiz y = key ( x ); x = elt ( y ) ) ularning
qiymatlari intervalda bo'lishi uchun { 1 , 2 , ... , 2 m } Navbat B to'g'ridan-to'g'ri
element kalitlari bilan ishlaydi.
Blok bilan ishlash Cj , biz kalitlari navbatda turgan elementlarni birlashtiramiz B ,
Bilan Cjs ro'yxatga birlashtiramiz . Biz buni taxmin qilganimizdan m ⩾ k , keyin
kalitlar soni B dan m ko’p emas, keyin uzunlik birlashtirish Ko'p emas 2 m , bu
to'plamdagi kalitlarni aniqlash imkonini beradi { 1 , 2 , ... , 2 m } ... Yuqorida aytib
o'tilganidek, kalitlari B bo'lgan elementlar, Tartibini narvondan ajratish, shuning
uchun Birlashtirish ishlashini algoritmik murakkabligi O(m) . ga teng .
Natijada biz tartiblangan ro'yxatni olamiz va birlashtiramiz ... Keling, har bir
elementga kalitni ushbu ro'yxatdagi o'rni sifatida moslashtiramiz, keyin bu gaplar
to'g'ri bo'ladi. . elt ( x )= merged [ x ] elt(x)=merged[x] и ( π i < π k ⟺ key ( π i )< key ( π k ))
qayerda pi , pk ∈ me r g e shuning uchun element tugmachalarining har qanday
ortib boruvchi ketma-ketligi elementlarning ortib borayotgan ketma-ketligiga mos
keladi. Shunday qilib, ustuvor navbat elementlarning kalitlari bilan to'g'ri ishlashi
mumkin bo'ladi.
Blok elementlariga mos keladigan tugmalar ketma-ketligini toping Csj ... Bu
ketma-ketlikni almashtirish orqali harakat qilish pj , biz asl blokning tartibida
kalitlar ketma-ketligini olamiz.
11](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_11.png?v=1)
![Algoritmni bajarish natijasi:
B : { 1 , 2 , 3 , 4 , 5 }
me r g e d :{1,2,5,7,11,12}
Biz eng katta qismiy ketma-ketlik uzunligini olamiz - 55 .
Eng uzun ortib borayotgan qismiy ketma-ketmaketlikni qayta
tiklash
22-rasm.
dan tiklanishni boshlaymiz me r g e d [ 5 ]= 11
24-rasm.
Blok hajmini topish
Ketma-ketlikni ko'rib { m 0 , m 1 , m 2 , …} - ba'zilari kamroq
mi + 1 = mlogmii = 2 log 2 mi mi+1=mi log mi=2log2 mi , m 0 m0 qiymatga ega k k ...
Ushbu ketma-ketlikning elementlari uchun yuqorida keltirilgan algoritmni ketma-
ket bajaramiz. Agar navbat o'lchami bo'lsa B kattalashib bormoqda mi , keyin
shart m ⩾ k bajarishni to'xtatadi, keyin biz algoritmni to'xtatamiz va keyingi
qiymatga o'tamiz mi + 1 .
Hamma uchun mi mi ro'yxat hajmi me r g e d . Ko'p emas 2 mi , va jami bloklar
soni ⌈ n / mi ⌉ ga teng bo’ladi. Keyin ketma-ketlik elementlariga yangi kalitlarni
tayinlashning umumiy soni, shuningdek ro'yxatlardagi birlashma operatsiyalari
soni ko'p emas 2 cm i ⋅ nm i = O ( n )
. bu yerda c qandaydir doimiydir. Har bir ustuvor
navbat operatsiyasi talab qiladi O ( loglog m i ) vaqt, chunki elementlar B Ko'p
emas 2mi elementga ega.
16](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_16.png?v=1)
![Shunday qilib, har biri uchun ishlaydigan algoritmning ishlash
vaqti mi mi - m i — O ( nloglogmi ) O(nlog log mi) . Birinchisi topilganda mj :
mj : mj ⩾ k mj:mj ⩾ k , keyin algoritm muvaffaqiyatli yakunlanadi.
loglogmi+1=loglog2log2mi=loglog2mi=2loglogmilog
log mi+1=log log 2log2 mi=lo
g
log2 mi=2log log mi .
loglogmj=2j−iloglogmi
Barcha qayta ishlangan qiymatlar uchun algoritmning umumiy ishlash vaqti
.. e'tibor bering, chunki
boshqacha mi < klogk mi<klog
k , bu haqiqatga zid keladi mi - kattaroq
bo'lganlarning birinchisi k .. Binobarin, .
Biz algoritmning vaqtga nisbatan murakkabligini O ( n loglog k ) ekanligini topamiz .
Eng uzun ortib borayotgan keyingi ketma-ketlik muammosi
Bizga quyidagicha masala berilgan bo’lsin: Massivi berilgan : a [ 0 .. n - 1 ]
va uning n ta elementi mavjud. Ushbu ketma-ketlikda eng uzun uzunlikdagi qat'iy
ortib boruvchi ketma-ketlikni topish talab qilinadi. Eng ortib boruvchi pastki
ketma-ketlik (NVP) (Ing. Eng uzun ortib borayotgan quyi ketma-ketlik, LIS )
qatori x, uzunligi n Bu ketma- x [ i 1 ]< x [ i 2 ]< ⋯ < x [ i k ] qator belgilar x shu
kabi i 1 < i 2 < ⋯ < i k , 1 ⩽ i j ⩽ n , va k - mumkin bo'lgan eng katta qiymat.
Algoritmik murakkabligi O (N 2
).
Keling, d massiv tuzamiz , qayerda d[i] Indeksli elementda tugaydigan eng uzun
o suvchi quyi ketma-ketlikning uzunligi
ʻ i ga teng. Biz massivni asta-sekin
to'ldiramiz – birinchi d[ 0 ], keyin d[ 1 ] va hokazo. Bizning muammomizga javob
massivning barcha elementlarining maksimali bo'ladi d ... Massivni to'ldirish
quyidagicha bo'ladi: agar d d [ i ]= 1 , keyin qidirilayotgan ketma-ketlik faqat sondan
iborat a [ i ] > 1 , keyin raqamdan oldin a [ i ] pastki qator boshqa raqamni o'z
ichiga oladi. Keling, uni takrorlaymiz: u har qanday element bo'lishi
17](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_17.png?v=1)
![mumkin a [ j ] ( j = 0 ... i - 1 )a[j](j=0 ...i-bitta) lekin shunday a [ j ] < a [ i ] . Keling,
bir qadamda keyingisini hisoblashimiz kerak d[i] ... Massivning barcha elementlari
d dan oldin allaqachon hisoblangan. Shunday qilib, bizning d[i] quyidagicha
hisoblashimiz mumkin: d [ i ]= 1 +max j = 0 .. i − 1 d [ j ] d[i]=1+maxj=0..i−1d[j] va
quyidagi shart bilan tekshirilib boriladi a [ j ]< a [ i ].
Hozircha biz eng katta ortib boruvchi pastki ketma-ketlikning faqat
maksimal uzunligini topdik, ammo biz uni o'zidan chiqara olmaymiz. Javobni
tiklash uchun massiv yarataylik
prev [ 0... n − 1 ] qayerda prev [ i ] bo’lsa massivdagi indeksni bildiradi a [ , bunda
maksimal qiymatga erishildi d[i] ... Javobni ko'rsatish uchun biz maksimal
qiymatlarga ega elementdan o'tamiz d[i] ajdodlariga ko'ra.
Endi esa bu jarayonni python dasturlash tilidagi kodini yozamiz:
vector<int> findLIS(vector<int> a):
int n = a.size
int prev[0..n - 1]
int d[0..n - 1]
for i = 0 to n - 1
d[i] = 1
prev[i] = -1
for j = 0 to i - 1
if (a[j] < a[i] and d[j] + 1 > d[i])
d[i] = d[j] + 1
prev[i] = j
pos = 0
length = d[0]
for i = 0 to n - 1
if d[i] > length
18](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_18.png?v=1)
![pos = i
length = d[i]
vector<int> answer
while pos != -1
answer.push_back(a[pos])
pos = prev[pos]
reverse(answer)
return answer
O(N log N) dagi yechim
Ushbu muammoni tezroq hal qilish uchun biz quyidagi dinamikani tuzamiz: d [ i ]
( i = 0... n ) - uzunlikning ortib boruvchi ketma-ketligi i tugaydigan raqam, va agar
bunday raqamlar bir nechta bo'lsa, ularning eng kichigi. Dastlab, biz buni taxmin
qilamiz d [ 0 ] = - ∞ , va boshqa barcha elementlar d [ i ] = ∞ ... Ushbu dinamikaning
ikkita muhim xususiyatiga e'tibor bering : d [ i - 1 ] ⩽ d[i] , Barcha uchun i = 1 va
har bir element a [ i ] ko'pi bilan bitta elementni yangilaydi d [ j ] . Bu shuni
anglatadiki, keyingi ishlov berishda a [ i ] , biz uchun mumkin O ( logn )
murakkablikdagi massivda ikkilik qidiruvdan foydalanish d joriydan katta yoki
unga teng bo'lgan birinchi sonni toping a [ i ] va uni yangilang.
Javobni tiklash uchun biz ikkita massivni to'ldirishni qo'llab-quvvatlaymiz: p o s
va prev ... p o s [ i ] biz uzunlikning optimal keyingi ketma-ketligi tugaydigan
element indeksini saqlaymiz va ichida p r e v [ i ] - oldingi elementning
joylashuvi a [ i ] mavjud bo’ladi. Endi bu jarayonni dasturlash tilida yozamiz.
vector<int> findLIS(vector<int> a):
int n = a.size
19](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_19.png?v=1)
![int d[0..n]
int pos[0..n]
int prev[0..n - 1]
length = 0
pos[0] = -1
d[0] =
for i = 1 to n
d[i] =
for i = 0 to n - 1
j = binary_search(d, a[i])
if (d[j - 1] < a[i] and a[i] < d[j])
d[j] = a[i]
pos[j] = i
prev[i] = pos[j - 1]
length = max(length, j)
vector<int> answer
p = pos[length]
20](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_20.png?v=1)
![while p != -1
answer.push_back(a[p])
p = prev[p]
reverse(answer)
return answer
O(N log N) dagi boshqa yechim
Yana bir yechim bor, bu bizga eng uzun ortib boruvchi ketma-ketlikning
uzunligini topishga imkon beradi, lekin bu pastki ketma-ketlikni tiklash
imkoniyatisiz. Buning uchun biz Young stolidan foydalanamiz. U shunday
xususiyatga egaki, tablaning birinchi qatorining uzunligi kerakli qiymat bo'ladi [1]
.
Tabloning o'zi joylashuvni ko'rsatadi n 1 + n 2 +...+ n M chapga tekislangan satrlar
massividagi alohida butun sonlar, bu yerda i i qatorni o'z ichiga
oladi ni ni elementlar; lekin har bir satrda elementlar chapdan o ngga, har bir ʻ
ustundagi elementlar esa yuqoridan pastga qarab ortadi. Tabloni yaratish uchun siz
keyingi elementni o'qishingiz kerak ai ai dan katta yoki teng bo'lsa nj nj , qayerda j -
satrning uzunligi, keyin faqat satrning oxiriga qo'shing, agar kamroq bo'lsa,
birinchi elementni topishingiz kerak. b b bu berilganidan
kattaroqdir ai ai ... Elementni qo'ying a ning o'rniga b ... Element b bilan bir xil
harakatlarni bajarish talab etiladi a ga ham , faqat allaqachon yoqilgan i + 1 tabla
chizig'i.
Massivda tabla qurishga misol a = [ 3 , 4 , 9 , 2 , 5 , 1 ]
1. 3- Elementni oling . Biz buni ko'ramiz 3 >0 indeksli katakning birinchi
qatorida joylashgan j = 0 ... Biz ko'paytiramiz j va t [ i ] [ j ] = 3 ...
3
21](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_21.png?v=1)
![2. 4-Elementni oling . Biz buni ko'ramiz 4 >3 ... Biz ko'paytiramiz
j va t [ i ] [ j ] = 4 ...
3 4
3. Xuddi shunday element uchun 9 ...
3 4 9
4. 2 Elementni oling . Chunki 2 <9 , keyin ikkilik qidiruv orqali biz kerakli
pozitsiyani topamiz z shu kabi t [ i ] [ z - 1 ] ⩽ 2 < t [ i ] [ z ] . Bunday holda, bu
birinchi pozitsiya. Biz tayinlaymiz t [ i ] [ z ] = 2 va xuddi shu amalni bajaring,
lekin indeksli chiziq uchun i + 1 ga oshiring …
2 4 9
3
5. Element uchun ham xuddi shunday 5 uchun ham.
2 4 5
3 9
6. Xuddi shunday element 1 uchun ...
1 4 5
2 9
3
22](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_22.png?v=1)
![Shunday qilib, massiv uchun eng uzun o'suvchi pastki ketma-ketlikning uzunligi
a 3 ga teng (masalan, elementlarning pastki ketma-ketligi [ 3 , 4 , 9 ] [3,4,9] ).
Maksimal umumiy ketma-ketlikni topish
Ketma-ket narsalarning tartiblangan to'plamidir. Satr ketma-ketlikning
maxsus holatidir, keyingi misollar oddiylik uchun faqat satrlarni ko'rib chiqadi,
ammo o'zgartirishlarsiz ular ixtiyoriy matn yoki boshqa ketma-ketlik uchun
ishlatilishi mumkin.
Bir natija bor bo'lsin x elementlardan tashkil topgan x
1 x
2 ... x
m va a
oqibat y elementlar iborat y
1 ,
y
2 ... y
n . z - x ning kichik ketma-
ketligi, agar x elementlarning qat'iy ortib borayotgan indekslari to'plami mavjud
bo'lsa.undan z olinadi .
Umumiy tadrijiylik uchun x va y bir natija z bir tadrijiylik ham x va tadrijiy y .
Maksimal umumiy pastki ketma-ketlik maksimal uzunlikdagi umumiy ketma-
ketlikdir. Keyinchalik matnda biz LCS qisqartmasidan foydalanamiz .
Misol tariqasida, x
= HA B R AHA BR , y = HARB OU R , bu holda LCS (x, y)
= HARBR bo'lsin. ... Siz to'g'ridan-to'g'ri LCS ni hisoblash algoritmiga o'tishingiz
mumkin, ammo bu bizga nima uchun kerakligini tushunish yaxshi bo'lar edi.
Amalda
qo'llash
Eng keng tarqalgan foydalanish GNU diff kabi fayllarni taqqoslash
dasturlarida. Ikkita matn uchun LCS ni topib, x ni y ga yoki aksincha aylantirish
uchun elementar o'zgarishlar ro'yxatini tuzish juda oddiy vazifadir. Bonus sifatida,
umumiy pastki ketma-ketlikning uzunligiga asoslanib, siz ikkita ketma-ketlikning
o'xshashligini aniqlash uchun metrikani belgilashingiz mumkin. Hamma narsa,
endi siz aniq biznesga kirishingiz mumkin.
23](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_23.png?v=1)
![Birinchi yondashuv yoki xalq san'ati
Birinchidan,
bir nechta kuzatishlar:
1. Agar x va y ketma-ketliklar uchun biz allaqachon LCS (x, y) = z ni
hisoblagan bo'lsak, u holda bir xil elementni qo'shish orqali x va y dan
olingan ketma-ketliklar uchun LCS z va ushbu qo'shilgan elementdan iborat
bo'ladi.
2. Agar x va y ketma-ketliklariga bir xil element qo‘shsak, shu tarzda olingan
xa va yb uchun LCS ikkitadan kattaroq bo‘lishi kerak: LCS (x, yb) yoki LCS
(xa, y)
Ushbu kuzatishlar rekursiyani amalga oshirish uchun allaqachon yetarli.(python
dasturlash tilida)
def LCS_RECURSIVE(x, y):
if len(x) == 0 or len(y) == 0:
return []
if x[-1] == y[-1]:
return LCS_RECURSIVE(x[:-1], y[:-1]) + [x[-1]]
else:
left = LCS_RECURSIVE(x[:-1], y)
right = LCS_RECURSIVE(x, y[:-1])
return left if len(left) > len(right) else right
Endi siz ushbu dasturda nima noto'g'ri ekanligini o'ylashingiz mumkin. Eng yomon
holatda, agar x va y o'rtasida bir xil elementlar bo'lmasa, LCS_RECURSIVE len (x) +
24](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_24.png?v=1)
![len (y)
rekursiya darajasida 2 len (x) + len (y)
marta chaqiriladi . Ishlash uchun ko'zimizni
yumsak ham, kod:
from uuid import uuid4
x = [uuid4().hex for _ in xrange(500)]
y = [uuid4().hex for _ in xrange(500)]
print LCS_RECURSIVE(x,y)
sys.setrecursionlimit ga qo'shimcha qo'ng'iroq qilmasdan, u muvaffaqiyatsiz
bo'ladi. Eng muvaffaqiyatli amalga oshirish emas.
Dinamik dasturlash yoki 64 kb hamma uchun etarli.
Ko'rib chiqilgan algoritm Needleman-Wunsch algoritmi sifatida ham tanilgan.
Butun yondashuv matritsani bosqichma-bosqich to'ldirishga to'g'ri keladi, bu erda
satrlar x element, ustunlar esa y elementdir. To'ldirishda allaqachon o'tkazilgan
kuzatishlardan kelib chiqadigan ikkita qoida mavjud:
1. Agar x
i elementi y
j ga teng bo'lsa
, u holda (i, j) katakchada (i-1, j-1)
katakchaning qiymati yoziladi. bitta qo'shilishi
2. Agar x
i elementi y
j ga teng bo'lmasa
, u holda (i, j) katakchaga (i-1, j) va (i, j-1)
qiymatlarning maksimali yoziladi. .
To'ldirish i va j bo'ylab er-xotin aylanada sodir bo'ladi, shuning uchun har bir
iteratsiyada ushbu bosqichda talab qilinadigan hujayra qiymatlari allaqachon
hisoblab chiqilgan:
def fill_dyn_matrix(x, y):
L = [[0]*(len(y)+1) for _ in xrange(len(x)+1)]
for x_i,x_elem in enumerate(x):
for y_i,y_elem in enumerate(y):
if x_elem == y_elem:
25](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_25.png?v=1)
![L[x_i][y_i] = L[x_i-1][y_i-1] + 1
else:
L[x_i][y_i] = max((L[x_i][y_i-1],L[x_i-1][y_i]))
return L
25-rasm.
Qiymat to'g'ridan-to'g'ri oshirilgan hujayralar ta'kidlangan. Matritsani
to'ldirgandan so'ng, ushbu hujayralarni ulab, biz kerakli LCSni olamiz. Bunday
holda, siz maksimal indekslardan minimal darajaga o'tish orqali ulanishingiz kerak,
agar hujayra ajratilgan bo'lsa, biz LCS ga mos keladigan elementni qo'shamiz, agar
bo'lmasa, qayerga qarab yuqoriga yoki chapga siljiymiz. kattaroq qiymat
matritsada:
def LCS_DYN(x, y):
L = fill_dyn_matrix(x, y)
LCS = []
26](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_26.png?v=1)
![x_i,y_i = len(x)-1,len(y)-1
while x_i >= 0 and y_i >= 0:
if x[x_i] == y[y_i]:
LCS.append(x[x_i])
x_i, y_i = x_i-1, y_i-1
elif L[x_i-1][y_i] > L[x_i][y_i-1]:
x_i -= 1
else:
y_i -= 1
LCS.reverse()
return LCS
Allogoritimning murakkabligi O (len (x) * len (y)), xotiradan bir xil ball. Shunday
qilib, agar men 100 000 satrdan iborat ikkita fayl o'rtasida satrma-satr
solishtirmoqchi bo'lsam, xotirada 10 10
elementdan iborat matritsani saqlashim
kerak bo'ladi . Bular. real foydalanish MemoryError-ni deyarli ko'kdan chiqarish
bilan tahdid qiladi. Keyingi algoritmga o'tishdan oldin, shuni yodda tutingki, L
matritsasini x elementlari ustidagi har bir iteratsiyada to'ldirganda, bizga faqat
oldingi harakat paytida olingan qator kerak bo'ladi. Bular. agar muammo LCS ning
o'zini hisoblamasdan faqat LCS uzunligini topish bilan cheklangan bo'lsa, u holda
L matritsasining faqat ikkita qatorini saqlab, xotiradan foydalanishni O (len (y)) ga
kamaytirish mumkin edi. bir vaqt.
Joy uchun kurash yoki Xirshberg algoritmi.
Ushbu algoritm ortidagi g'oya oddiy: agar siz x = x 1 x 2 ... x m kirish ketma-
27](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_27.png?v=1)
![ketligini istalgan i chegara indeksida ikkita ixtiyoriy qismga bo'lsangiz, xb =
x 1 x 2 ... x i va xe = x i + 1 x i + 2 ... x m , keyin y ni shunga o'xshash tarzda
bo'lish usuli mavjud (y ni yb = y 1 y 2 ... y j va ye = y ga ajratadigan j indeksi
mavjud. j + 1 y j + 2 ... y n ) shunday bo‘lsinki, LCS (x, y) = LCS (xb, yb) + LCS
(xe, ye).
Ushbu bo'linishni topish uchun y taklif qilinadi:
1. L dinamik matritsasini xs va y uchun fill_dyn_matrix bilan to'ldiring. L1
hisoblangan L matritsaning oxirgi qatorini tenglashtiramiz
2. * xe va * y uchun L matritsasini to'ldiring (xe va y uchun teskari ketma-
ketliklar, Python shartlarida: ro'yxat (teskari (x)), ro'yxat (teskari
(y))). Hisoblangan L matritsaning oxirgi qatoriga * L2 tenglang, L2 daryo *
L2
3. L1 [j] + L2 [j] yig'indisi maksimal bo'lgan indeksga teng j ni oling
Bu L matritsasini ikkita qarama-qarshi tomondan to'ldirish sifatida ifodalanishi
mumkin:
28](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_28.png?v=1)
![26-rasm.
E'tibor bering, L matritsasining faqat oxirgi qatoriga ehtiyoj borligi sababli,
hisoblash paytida butun matritsani saqlash shart emas. Fill_dyn_matrix ilovasini
biroz o'zgartirib, biz quyidagilarni olamiz:
def lcs_length(x, y):
curr = [0]*(1 + len(y))
for x_elem in x:
prev = curr[:]
29](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_29.png?v=1)
![for y_i, y_elem in enumerate(y):
if x_elem == y_elem:
curr[y_i + 1] = prev[y_i] + 1
else:
curr[y_i + 1] = max(curr[y_i], prev[y_i + 1])
return curr
Endi to'g'ridan-to'g'ri, algoritmning o'zi haqida. Bu klassik bo'linish va zabt
etish: x ketma-ketligida elementlar mavjud ekan, biz x ni ikkiga bo'lamiz, y uchun
mos bo'lim topamiz va ketma-ketlik juftliklari (xb, yb) va (xe,) uchun rekursiv
chaqiruvlar yig'indisini qaytaramiz. ye). E'tibor bering, arzimas holatda, agar x
bitta element bo'lsa va y da sodir bo'lsa, biz shunchaki bitta x elementdan ketma-
ketlikni qaytaramiz.
def LCS_HIRSHBERG(x, y):
x_len = len(x)
if x_len == 0:
return []
elif x_len == 1:
if x[0] in y:
return [x[0]]
else:
return []
30](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_30.png?v=1)
![else:
i = x_len // 2
xb, xe = x[:i], x[i:]
L1 = lcs_length(xb, y)
L2 = reversed(lcs_length(xe[::-1], y[::-1]))
SUM = (l1 + l2 for l1,l2 in itertools.izip(L1, L2))
_, j = max((sum_val, sum_i) for sum_i, sum_val in enumerate(SUM))
yb, ye = y[:j], y[j:]
return LCS_HIRSHBERG(xb, yb) + LCS_HIRSHBERG(xe, ye)
Endi bizning xotira talablarimiz O (len (y)), hisoblash uchun zarur bo'lgan
vaqt ikki baravar ko'paydi, ammo asimptotik ravishda hali ham O (len (x) len (y)).
Hunt-Szymanski algoritmi
Bizga
kerak bo'lgan birinchi narsa - ikkinchi ketma-ketliklar elementlarining
indekslarini
o'z ichiga olgan xesh-jadval, matchlar ro'yxatini yaratish. Buning
uchun
talab qilinadigan vaqt O (len (y)). Quyidagi python kodi buni amalga
oshiradi:
y_matchlist = {}
for index, elem in enumerate(y):
indexes = y_matchlist.setdefault(elem, [])
indexes.append(index)
y_matchlist[elem] = indexes
31](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_31.png?v=1)
!["HARBOR" ketma-ketligi uchun xesh {'A': [1], 'B': [3], 'H': [0], 'O': [4], 'R':
[2bo'ladi.,6],'U':[5]}.
Keyin, x ketma-ketligining elementlarini takrorlab, THRESH massivini
tayyorlangan moslik ro yxatidagi mos indekslar bilan to ldiring, shunda k-ʻ ʻ
THRESH elementining qiymati y_index indeksi bo lishi kerak, THRESH [k-1]
ʻ
<y_index va y_index <THRESH [k]. Shunday qilib, istalgan vaqtda THRESH
massivi saralanadi va mos k ni topish uchun ikkilik qidiruvdan foydalanishimiz
mumkin. THRESH elementini yangilaganimizda, biz LCS ga y_index ga mos
keladigan ketma-ketlik elementini ham qo'shamiz. Quyidagi kod aniqlik kiritishi
mumkin:
x_length, y_length = len(x), len(y)
min_length = min(x_length, y_length)
THRESH = list(itertools.repeat(y_length, min_length+1))
LINK_s1 = list(itertools.repeat(None, min_length+1))
LINK_s2 = list(itertools.repeat(None, min_length+1))
THRESH[0], t = -1, 0
for x_index,x_elem in enumerate(x):
y_indexes = y_matchlist.get(x_elem, [])
for y_index in reversed(y_indexes):
k_start = bisect.bisect_left(THRESH, y_index, 1, t)
k_end = bisect.bisect_right(THRESH, y_index, k_start, t)
32](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_32.png?v=1)
![for k in xrange(k_start, k_end+2):
if THRESH[k-1] < y_index and y_index < THRESH[k]:
THRESH[k] = y_index
LINK_x[k] = (x_index, LINK_x[k-1])
if k > t:
t = k
Shundan so'ng, biz LINK_x dan ketma-ketlikni yig'ishimiz kerak.
Ushbu algoritmning ishlash vaqti O ((r + n) log n), bu erda n - kattaroq ketma-
ketlikning uzunligi va r - mos keladiganlar soni, eng yomon holatda r = n * n bilan,
biz olamiz ish vaqti oldingi yechimga qaraganda yomonroq. Xotira talablari
O(r+n)_tartibida_qoladi.
Ushbu muammoni hal qiladigan juda ko'p algoritmlar mavjud, asimptotik tarzda,
eng samarali algoritm (Masek va Paterson) O (n * n / log n) vaqtini taxmin
qiladi. LCS hisob-kitoblarida umumiy past samaradorlikni hisobga olgan holda,
amalda, algoritm ishlamasdan oldin, ketma-ketlikning boshida va oxirida bir xil
elementlarni tashlash va ketma-ketliklar orasidagi ahamiyatsiz farqlarni izlash kabi
eng oddiy tayyorgarliklar amalga oshiriladi. Bundan tashqari, ish vaqtining
asimptotik xatti-harakatiga ta'sir qilmaydigan bitli operatsiyalar yordamida ba'zi
optimallashtirishlar mavjud.
33](https://docx.uz/documents/745df24a-4e6f-4cad-9602-4798dccce8ad/page_33.png?v=1)
Eng katta qismiy ketma- ketlikni tezkor qidirish