Longest Common Subsequence

Eng uzun umumiy qism-ketma-ketlik (LCS) — bu berilgan barcha ketma-ketliklar uchun umumiy bo'lgan eng uzun qism-ketma-ketlikdir. Bunda qism-ketma-ketlik elementlari dastlabki ketma-ketliklarda yonma-yon (ketma-ket) joylashishi shart emas, ammo ularning nisbiy tartibi buzilmasligi kerak.

Agar S1 va S2 ikkita berilgan ketma-ketlik bo'lsa, Z ketma-ketligi ham S1 ning, ham S2 ning qism-ketma-ketligi bo'lsa, Z umumiy qism-ketma-ketlik hisoblanadi. Bundan tashqari, Z dagi elementlarning asl ketma-ketlikdagi indekslari qat'iy o'suvchi tartibda bo'lishi shart.

Masalan:

S1 = {B, C, D, A, A, C, D}

Bu yerda {A, D, B} ketma-ketligi S1 ning qism-ketma-ketligi bo'la olmaydi, chunki elementlarning joylashuv tartibi o'zgargan (ya'ni qat'iy o'suvchi indekslar qoidasi buzilgan).

LCS misoli

Keling, LCS tushunchasini ikkita ketma-ketlik misolida ko'rib chiqamiz:

S1 = {B, C, D, A, A, C, D}
S2 = {A, C, D, B, A, C}

Qism-ketma-ketlik (subsequence) — bu dastlabki ketma-ketlikdan qolgan elementlar tartibini o'zgartirmasdan, ba'zi elementlarni o'chirish (yoki hech birini o'chirmaslik) orqali hosil qilingan ketma-ketlikdir. Umumiy qism-ketma-ketlik esa ikkala satrda ham bir xil tartibda mavjud bo'lgan ketma-ketlikdir.

Yuqoridagi ikki ketma-ketlik uchun umumiy qism-ketma-ketliklar quyidagilardir: {B, C}, {C, D, A, C}, {D, A, C}, {A, A, C}, {A, C}, {C, D}, ...

Ushbu variantlar orasida eng uzuni {C, D, A, C} bo'lib, uning uzunligi 4 ga teng. Biz aynan shu eng uzun umumiy qism-ketma-ketlikni dinamik dasturlash yordamida qanday topishni ko'rib chiqamiz.

LCS ni topishda Dinamik dasturlashni qo'llash

Keling, quyidagi ikkita qisqaroq ketma-ketlikni olaylik:

Birinchi ketma-ketlik X

Ikkinchi ketma-ketlik Y

Eng uzun umumiy qism-ketma-ketlikni topish uchun quyidagi qadamlar bajariladi:

1. O'lchami (n + 1) * (m + 1) bo'lgan jadval (matritsa) hosil qilamiz (n va m — mos ravishda X va Y ketma-ketliklarining uzunliklari). Birinchi qator va birinchi ustunni to'liq 0 bilan to'ldiramiz:

   

   Jadvalni initsializatsiya qilish

2. Jadvalning qolgan kataklarini quyidagi mantiq asosida to'ldirib boramiz:

3. Agar joriy qator va joriy ustunga mos keluvchi belgilar teng bo'lsa (X[i-1] == Y[j-1]), joriy katakka diagonal qo'shnisining qiymatiga 1 qo'shib yozamiz (L[i][j] = L[i-1][j-1] + 1). Va diagonal katakka qarata ko'rsatgich (strelka) yo'naltiramiz.

4. Agar belgilar mos kelmasa, chapdagi (L[i][j-1]) va yuqoridagi (L[i-1][j]) kataklar orasidan kattasini olib joriy katakka yozamiz. Strelkani kattaroq qiymatli katakka qaratamiz:

   

   Qiymatlarni to'ldirish

5. Jadval to'liq to'lguncha ushbu jarayonni takrorlaymiz:

   

   Barcha kataklarni to'ldirish

6. Jadvalning eng pastki o'ng burchagidagi (L[m][n]) qiymat eng uzun umumiy qism-ketma-ketlikning uzunligini beradi:

   

   Pastki o'ng burchak — LCS uzunligi

7. LCS ning o'zini (harflarini) topish uchun eng oxirgi katakdan boshlab strelkalar yo'nalishi bo'ylab teskari harakatlanamiz (backtracking). Diagonal bo'yicha siljigan kataklardagi harflar eng uzun umumiy qism-ketma-ketlikni tashkil qiladi:

   

   Strelkalar bo'yicha orqaga qaytib yo'lni tiklash

Natijada, eng uzun umumiy qism-ketma-ketlik CA ekanligi aniqlanadi:

LCS natijasi: CA

Nega dinamik dasturlash oddiy rekursiyadan ancha samarali?

Dinamik dasturlash usuli funksiya chaqiruvlari sonini keskin qisqartiradi. U har bir qism-taqqoslash natijasini jadvalda saqlaydi, shuning uchun bir xil qism-masalalar qayta-qayta hisoblanmaydi.

Dinamik yondashuvda sarflanadigan vaqt jadvalni to'ldirish vaqtiga, ya'ni O(m * n) ga teng bo'ladi. Oddiy sodda rekursiv usulning vaqt murakkabligi esa eksponentsial — O(2^(max(m, n))) bo'lib, uzun satrlarda dastur to'xtab qolishiga olib keladi.

Longest Common Subsequence algoritmi psevdokodi

X and Y be two given sequences
Initialize a table LCS of dimension (X.length + 1) * (Y.length + 1)
LCS[0][] = 0
LCS[][0] = 0

for i = 1 to X.length:
    for j = 1 to Y.length:
        if X[i-1] == Y[j-1]:
            LCS[i][j] = 1 + LCS[i-1][j-1]
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

return LCS[X.length][Y.length]

Dasturiy kod

package main

import (
	"fmt"
)

// Eng uzun umumiy qism-ketma-ketlikni (LCS) topish funksiyasi
func lcsAlgo(S1, S2 string, m, n int) {
	L := make([][]int, m+1)
	for i := range L {
		L[i] = make([]int, n+1)
	}

	// Matritsani pastdan-yuqoriga (bottom-up) to'ldirish
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			if i == 0 || j == 0 {
				L[i][j] = 0
			} else if S1[i-1] == S2[j-1] {
				L[i][j] = L[i-1][j-1] + 1
			} else {
				if L[i-1][j] > L[i][j-1] {
					L[i][j] = L[i-1][j]
				} else {
					L[i][j] = L[i][j-1]
				}
			}
		}
	}

	index := L[m][n]
	lcsArr := make([]byte, index)
	i, j := m, n

	for i > 0 && j > 0 {
		if S1[i-1] == S2[j-1] {
			lcsArr[index-1] = S1[i-1]
			i--
			j--
			index--
		} else if L[i-1][j] > L[i][j-1] {
			i--
		} else {
			j--
		}
	}

	fmt.Printf("S1 : %s\nS2 : %s\n", S1, S2)
	fmt.Printf("LCS: %s\n", string(lcsArr))
}

func main() {
	S1 := "ACADB"
	S2 := "CBDA"
	m := len(S1)
	n := len(S2)

	lcsAlgo(S1, S2, m, n)
}

LCS algoritmining murakkabligi

• Vaqt murakkabligi (Time Complexity): O(m * n), bu yerda m va n — ikkita ketma-ketlikning uzunliklari.
• Xotira murakkabligi (Space Complexity): O(m * n) (dinamik dasturlash jadvali uchun).

LCS algoritmining qo'llanilishi

• Bioinformatika va genetikada: DNK va RNK genom ketma-ketliklarini taqqoslash hamda ma'lumotlarni siqish.
• Matn taqqoslash va versiyalar nazorati: git diff va matn muharrirlarida ikki fayl orasidagi o'zgarishlar va qo'shilgan/o'chirilgan qatorlarni aniqlash.
• Biometrik xavfsizlik: Mobil qurilmalarda foydalanuvchilarning fazoviy imo-ishora (in-air signatures) imzolarini tanish va autentifikatsiya qilish.