En Uzun Ortak Alt Dizi: Python, C++ Örnek E-posta

En Uzun Ortak Alt Dizi Nedir?

En Uzun Ortak Alt Dizi (LCS), size iki dize, desen veya nesne dizisi verileceği anlamına gelir. Bu iki dizi veya dize arasında, her iki dizede veya desende de aynı sırada bulunan elemanların en uzun alt dizisini bulmanız gerekir.

Örnek E-posta

Örneğin, iki dize verilmiştir. Şunu varsayalım:

Desen_1 = “RGBGARGA”
Desen_2 = “BGRARG”

• Pattern_1'den "RGB", "RGGA", "RGAR" gibi diziler üretilebilir. Bir dizi oluşturmak için, dizedeki her karakterin göreceli konumunu korumanız gerekir.
• Pattern_2'den "BGR", "BRAG", "RARG" gibi diziler üretebiliriz. Diziler, orijinal dizenin göreceli konumunu korudukları sürece üretilebilir.

Göreceli konum terimi düzen anlamına gelir.

Örneğin, “BRG” geçerli bir dizidir çünkü orijinal dize kalıbı_2'de önce “B”, sonra “R” ve ardından “G” gelmiştir. Ancak, eğer bir dizi “RBRG” ise, geçerli değildir çünkü orijinal dizede (kalıp_2) önce “B” gelir.

Verilen iki diziden veya diziden En Uzun Ortak Alt Diziyi bulmak için iki seçeneğimiz var.

• Saf yöntem
• Dinamik Programlama Çözümü: En Uzun Ortak Alt Dizi aynı zamanda LCS olarak da bilinir.

Basit bir çözüm daha yüksek zaman karmaşıklığına sahiptir ve en uygun çözüm değildir. Dinamik Programlama Çözümü (DP) kullanarak bu karmaşıklık sorununu aşıyoruz.

Naif Yöntem

Naif yöntem, zaman karmaşıklığı ve diğer optimizasyon faktörlerinden bağımsız olarak, probleme basit bir yaklaşım sunar. Çoğu durumda "kaba kuvvet", çoklu döngüler ve özyinelemeli çağrılardan oluşur. Kaba kuvvet terimi, verilen bir problem için tüm olası kalıpları denemeyi ifade eder.

Örnek E-posta

Yukarıdaki model1 ve model2 örneğinden, model1'in uzunluğunun m ve model2'nin uzunluğunun n olduğunu varsayalım. Olası her durumu kontrol etmek için, model1'in olası her alt dizisini model2 ile değerlendirmemiz gerekir.

İşte basit bir 4 harfli dize: "ABCD". Örneğin, "ABCD"den bir dizi oluşturmamız gerekiyor. Ya bir karakter alabiliriz ya da almayabiliriz. Yani, her karakter için iki seçeneğimiz var:

• Karakter alt diziye eklenecektir.
• Karakter alt diziye eklenmeyecektir.

Burada görseller “ABCD” dizisinden yapabileceğimiz tüm dizileri gösteriyor.

1 karakterli dizi:

2 karakterli diziler:

3 karakterli diziler:

Yukarıdaki şemadan 14 dizi olduğu görülmektedir. Eğer hiçbir harf almazsak, yani boş bir dize alırsak, toplam dizi sayısı 15 olur. Dahası, "ABCD" dizesi kendi başına bir dizidir. Dolayısıyla, toplam dizi sayısı 16'dır.

Dolayısıyla, "ABCD" dizisinden 2^4 veya 16 alt dizi oluşturmak mümkündür. Ardından, uzunluğu olan bir dize elde edilir. m Toplam alt dizisi 2^m olacaktır.

Her bir alt dizi için, tüm pattern2'yi kontrol etmemiz gerekiyor. Bu işlem O(n) zaman alacaktır. O(n), yürütme için geçen süreyi hesaplayan karmaşıklık fonksiyonunu ifade eder.

Yani, toplam zaman karmaşıklığı şu hale gelir: O(n*2^m). Yukarıda gördüğümüz örnekte, m=8 ve n=5 değerleri elde edilmiştir.

Naif Yöntemin adımları şunlardır:

) 1 Adım Pattern1'den bir dizi alın.
) 2 Adım 1. adımdaki diziyi 2. desenle eşleştirin.
) 3 Adım Eşleşiyorsa, alt diziyi kaydedin.
) 4 Adım Pattern1'de daha fazla dizi kaldıysa, tekrar 1. adıma geçin.
) 5 Adım En uzun alt diziyi yazdırın.

Optimum Altyapı

"Optimal alt yapı" terimi, alt problemlerin çözülmesiyle optimal bir çözümün bulunabileceği anlamına gelir. Örneğin, yukarıdaki örnekte, pattern1 ve pattern2'ye sahibiz.

) 1 Adım Her bir kalıptan ilk iki karakteri alın.

) 2 Adım Her desenden üçüncü ila beşinci karakterleri alın.

) 3 Adım Kalan karakterlerle benzer şekilde devam edin.

LCS probleminin Özyinelemeli Yapısı

Orijinal dizeden türetilen alt dizenin en uzun ortak alt dizisini (LCS) buluyoruz. Ardından, alt dizelerin LCS'lerinin uzunluğunu kaydediyoruz.

Şimdi, burada başka bir ilginç özellik daha var: üst üste gelmekping alt problemlerBir problemin örtüşme gösterdiği söylenir.ping Eğer problem ifadesi küçük alt problemlere bölünebiliyorsa ve bu alt problemler programda birkaç kez kullanılabiliyorsa, bu alt problemler de ele alınabilir.

Aşağıdaki şema, özyinelemeli algoritmanın, işlevi aynı parametreyle birkaç kez çağırdığını göstermektedir.

Örneğin, özyineleme ağacına bakın. Koyu renkli kutuda, örtüşmeyi fark edebilirsiniz.ping Alt problemler. (“RG”, “RA”), (“RG”, “R”) ve diğerleri birkaç kez çağrılır.

Bunu optimize etmek için şu yaklaşımı benimsedik: Dinamik program (DP).

En Uzun Ortak Alt Dizinin Özyinelemeli Yöntemi

Yukarıda gösterilen grafik özyinelemeli metodu temsil etmektedir. Her özyinelemeli fonksiyonun, özyinelemeyi sonlandırmak veya yığınından dönmeye başlamak için bir temel durumu vardır.

Bu uygulama için temel bir durum kullanacağız. Yani, algoritma aşağıdaki gibidir:

• Son öğeden önceki tüm öğeler eşleşiyorsa, uzunluğu bir artırın ve geri dönün.
• Fonksiyona iki desen iletin ve döndürülen değerlerden en büyüğünü alın.
• Bir modelin uzunluğu sıfırsa, karşılaştırılacak bir alt dizimiz yoktur. Bu durumda 0 değerini döndürün. Bu yinelemenin temel durumudur.

Sözde Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

Uygulama C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Çıktı:

Length of LCS is: 5

Uygulama Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Çıktı:

Length of LCS is:  5

En Uzun Ortak Alt Dizi (LCS) Dinamik Programlama Yöntemi

Dinamik programlama, basit özyinelemeli yöntemi optimize etmek anlamına gelir. Örneğin, özyinelemeli veya basit yaklaşım grafiğine baktığımızda, birçok özdeş fonksiyon çağrısı olduğunu görebiliriz. Dinamik programlama yöntemi, tüm hesaplamaları bir diziye kaydeder ve gerektiğinde yeniden kullanır.

Boyutları mxn olan 2 boyutlu bir dizi kullanacağız; burada m ve n, pattern1 ve pattern2'nin uzunluklarıdır. 2 boyutlu diziList veri yapılarını şu şekilde kullanabiliriz: Python veya vektör/dizi veri yapıları C++.

Sözde Code DP kullanarak LCS için:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Dinamik programlama yaklaşımı için 2 boyutlu dizi veri yapısı olarak kullanılan LCS tablosu aşağıdadır.

Şimdi burada kullandığımız mantığı tartışalım. Adımlar şunlardır:

) 1 Adım Eğer i veya j sıfır ise, verilen iki dizeden boş bir dize alıp ortak alt dizileri bulmaya çalışıyoruz. Ancak, aldığımız alt dizi boş olduğundan, alt dizinin uzunluğu 0'dır.

) 2 Adım İki karakter eşleşirse, daha önce hesaplanan ve (i-1,j-1) dizininde (önceki satırdan) bulunan en uzun ortak alt karakteri (LCS) artırarak değeri (i,j) dizinine atayacağız.

) 3 Adım Eğer eşleşme olmazsa, bitişik iki indeksin en büyük en küçük ortak alt dizisini alacağız. Ve bu şekilde, 2 boyutlu dizideki tüm değerleri doldurmamız gerekiyor.

) 4 Adım Son olarak 2 boyutlu dizinin son hücresinin değerini döndüreceğiz.

Temelde, 2 boyutlu dizideki tüm değerler ortak alt dizilerin uzunluğunu içerir. Bunların arasında son hücre, en uzun ortak alt dizinin uzunluğunu içerir.

Uygulama C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Çıktı:

Length of LCS: 5

Uygulama Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Çıktı:

Length of LCS: 5

Yani her iki dizi de 5 uzunluğunda en uzun ortak alt diziye sahiptir.

Özetle, DP yönteminde her görevi yalnızca bir kez hesaplıyoruz. Özyinelemeli yöntemde ise çakışmalar olabilir.ping alt sorunlar.

Bu Dinamik Programlama Algoritmasında 2 boyutlu bir matris kullanıyoruz. Verilen iki dize olacaktır (her ikisinin de uzunluğunun n olduğunu varsayalım). O halde dizide ihtiyaç duyulan alan nx n'dir. Dizeler yeterince büyükse DP çözümünün belleği optimize edilmiş bir sürümüne ihtiyacımız olacak.

Kodda alınan basitleştirilmiş mantık şöyledir:

• Bir 2B Dizi DP[m][n] bildirin.
• DP dizisinin ilk satırını ve ilk sütununu 0 ile doldurun.
• Yineleme için i ve j'yi alın.
• Eğer pattern1[i], pattern2[j]'ye eşitse, DP[i][j] = DP[i-1][j-1] + 1 olarak güncelleyin.
• Eğer pattern1[i], pattern2[j]'ye eşit değilse, DP[i][j], DP[i-1][j] ve DP[i][j-1] arasındaki en büyük değer olacaktır.
• i ve j, m ve n'ye ulaşana kadar devam edin.
• Son eleman olan DP[m-1][n-1], uzunluğu içerecektir.

Burada, dizi indeksi 0'dan başladığı için DP[m-1][n-1] olarak ele alınmaktadır.

SSS