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

En Uzun Ortak Alt Dizi Nedir?

En Uzun Ortak Alt Dizi (LCS), size iki dizi/desen/nesne dizisi verileceği anlamına gelir. Bu iki dizi/dizi arasında, hem dizelerde hem de desenlerde aynı sıradaki öğelerin en uzun alt dizisini bulmanız gerekir.

Örnek E-posta

Örneğin, sağlanan iki dize vardır.

Diyelim ki,

Desen_1 = “RGBGARGA”
Desen_2 = “BGRARG”

• Pattern_1'den “RGB”, “RGGA”, ”RGAR” gibi diziler üretilebilmektedir. Bir dizi oluşturmak için dizedeki her karakterin göreceli konumunu korumanız gerekir.
• Pattern_2'den "BGR", "BRAG", "RARG" gibi diziler üretebiliriz. Orijinal dizenin göreceli konumu korunduğu sürece diziler üretilebilir.

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

Örneğin, "BRG" geçerli bir dizidir çünkü orijinal dize modeli_2'de önce "B", ardından "R" ve ardından "G" göründü. Ancak bir dizi “RBRG” ise geçerli değildir. Çünkü orijinal dizede (pattern_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.

Saf bir Çözüm daha büyük zaman karmaşıklığına sahiptir ve en uygun çözüm değildir. Dinamik Programlama Çözümü (DP) kullanarak karmaşıklık sorununun üstesinden geliriz.

Naif Yöntem

Naif yöntem, zaman karmaşıklığı ve diğer optimizasyon faktörlerinden bağımsız olarak soruna basit bir yaklaşımdır.

Naive yöntemi çoğu durumda “Kaba Kuvvet”, çoklu döngüler, özyinelemeli yöntemlerden oluşur.

Kaba kuvvet terimi, belirli bir sorun için olası tüm kalıpların üzerinden geçmek anlamına gelir.

Ö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 4 harfli basit bir "ABCD" dizisi. Örneğin “ABCD”den bir dizi oluşturmamız gerekiyor. Ya bir karakter alırız ya da alamayız. Bu, her karakter için iki seçeneğimiz olduğu anlamına gelir.

Bunlar:

• 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 şemada 14 dizi var. Temel olarak boş bir dizi olan harfleri almazsak toplam dizi 15 olacaktır. Üstelik “ABCD” dizisinin kendisi de bir dizidir. Yani toplam dizi sayısı 16'dır.

Yani 2 tane üretmek mümkün⁴ veya “ABCD”den 16 alt dizi. Daha sonra uzunluğunda bir dize m toplam 2'nin alt dizisine sahip olması gerekecek^m.

Her alt dizi için, tüm pattern2 için kontrol etmemiz gerekir. 0(n) zaman alacaktır. 0(n), yürütme için gereken zamanı hesaplayan karmaşıklık fonksiyonu anlamına gelir.

Yani, toplam zaman karmaşıklığı şu hale gelir: Ç(n*2^m). Örnek olarak yukarıda m=8 ve n=5 değerini gördük.

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

) 1 Adım Desen1'den bir dizi alın.
) 2 Adım Adım 1'deki sırayı desen2 ile eşleştirin.
) 3 Adım Eşleşiyorsa, alt diziyi kaydedin.
) 4 Adım Desen1'de daha fazla sıra kaldıysa tekrar 1. adıma gidin.
) 5 Adım En uzun alt diziyi yazdırın.

Optimum Altyapı

Optimal altyapı terimi, alt problemlerin çözülmesiyle optimal çözümün (basit) bulunabileceği anlamına gelir. Örneğin, yukarıdaki örnekte model1 ve model2'ye sahibiz.

) 1 Adım Her 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'yi alt dizede (orijinal dizeden oluşturulan dize) buluruz. Daha sonra alt dizilerin LCS uzunluğunun kaydını tutuyoruz.

Şimdi, burada başka bir ilginç özellik daha var: örtüşen alt problemler. Eğer problem tanımı küçük alt problemlere bölünüp programda birkaç kez kullanılabiliyorsa, problemin örtüşen alt problemlere sahip olduğu söylenir.

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

Örneğin özyineleme ağacını görelim.

Koyu renkli kutuda, üst üste binen alt problemleri fark edebilirsiniz. (“RG”, “RA”), (“RG”,”R”) ve diğerleri birkaç kez çağrılmıştır.

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

En Uzun İletişim Dizisinin Yinelemeli Yöntemi

Yukarıda gösterilen grafik özyinelemeli yöntemdir. Her özyinelemeli işlevin özyinelemeyi kırmak veya yığınından geri dönmeye başlamak için bir temel durumu vardır.

Bu uygulama için bir temel durum kullanacağız. Böylece algoritma aşağıdaki gibidir:

• Son öğeden önceki tüm öğelerin eşleşmesi varsa uzunluğu bir artırın ve geri dönün.
• İşleve iki desen iletin ve dönüşün maksimum değerini 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.

Sahte Kod:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of 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

Python'da uygulama

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("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Çıktı:

Lenght of LCS is:  5

En Uzun Ortak Alt Dizinin (LCS) Dinamik Programlama yöntemi

Dinamik programlama, düz özyinelemeli yöntemin optimize edilmesi anlamına gelir. Örneğin özyinelemeli veya naif yaklaşım grafiğini görürsek, aynı işlev çağrılarının birden fazla olduğunu görebiliriz. Dinamik Programlama yöntemi tüm hesaplamaları bir diziye kaydeder ve gerektiğinde kullanır.

Mxn boyutlarına sahip 2 boyutlu bir dizi kullanacağız; burada m ve n, model1 ve model2'nin uzunluklarıdır.

Her Ticaretçi İçin Mükemmellik 2 boyutlu dizi, Python'da Liste veri yapılarını veya vektör/dizi veri yapılarını kullanabiliriz C++.

DP kullanan LCS için Sahte Kod:

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]

Burada dinamik programlama yaklaşımı için 2 boyutlu dizi veri yapısı olarak kullanılan LCS tablosu verilmiştir.

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ıyoruz ve ortak alt dizileri bulmaya çalışıyoruz. Ancak aldığımız alt dizi boş olduğundan alt dizi uzunluğu 0 olur.

) 2 Adım İki karakter eşleşirse, (i-1,j-1) dizininde (önceki satırdan) bulunan, önceden hesaplanan LCS'yi artırarak değeri (i,j) dizinine atayacağız.

) 3 Adım Eşleşmiyorsa bitişik iki endeksin maksimum LCS'sini alırız. Ve bu şekilde 2D 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.

Temel olarak, 2B dizideki tüm değerler ortak alt dizilerin uzunluğunu içerir. Bunlardan 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 & lt; n + 1; i++) {
    for (int j = 0; j & lt; 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 basitçe bir kez hesaplıyoruz. Özyinelemeli yöntemde örtüşen alt problemlerimiz olabilir.

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.
• Desen1[i], model2[j]'ye eşitse, DP[i][j] = DP[i-1][j-1] + 1'i güncelleyin
• Eğer model1[i], model2[j]'ye eşit değilse, o zaman DP[i][j], DP[i-1][j] ve DP[i][j-1] arasındaki maksimum değer olacaktır.
• i ve j, m ve n'ye ulaşana kadar devam edin.
• Son eleman veya DP[m-1][n-1] uzunluğu içerecektir.

Burada DP[m-1][n-1] olarak adreslenir çünkü dizi indeksi 0'dan başlar.

ÖZET

• DP yöntemi daha düşük zaman karmaşıklığına sahiptir; m ve n giriş dizisinin veya dizisinin uzunluğu olmak üzere O(mn)'dir.
• DP, zaman karmaşıklığı nedeniyle yinelemeli yaklaşımdan daha hızlı bir yaklaşımdır. Ç(n*2^m).
• Dinamik programlama (DP) bellek açısından optimize edilmemiştir. m*n uzunluğunda bir 2D dizi kullandık. Bu nedenle, uzay karmaşıklığı (m*n)'dir.
• Özyinelemeli yöntem, en kötü senaryoda, kaplayacağı en yüksek bellek m+n, yani girilen dizenin toplam uzunluğu olacaktır.
• Günümüzün modern bilgisayarı bu miktardaki belleği işlemek için yeterlidir.