Python'da Naive String Eşleştirme Algoritması: Örnekler, Öne Çıkanlar ve Artıları ve Eksileri

Bir karakter dizisinde bir girdi modeli bulmaya ihtiyaç duyulduğunda, kodlayıcılar ve programcılar dizi eşleştirme algoritmasını kullanır. Genellikle, kısa bir dize durumunda, python programcıları, programın sorgu deseni için giriş dizesindeki her konumu kontrol ettiği naif yaklaşımı kullanmayı tercih eder. Eşleşmesi durumunda pozisyon numarası ile çıktı verir.

Naive string eşleştirme algoritmasının kullanılmasının en büyük nedenlerinden biri hızlı olması ve oldukça doğru sonuçlar vermesidir. Üstelik ön işlem gerektirmez. Her durumda, bu yazının ilerleyen aşamalarında bu avantajları tartışacağız. Önce saf yaklaşımı kullanarak kalıp arama algoritmasını anlayalım.

Naif Desen Arama Algoritması

Saf dizi desen aramasında, program, T [1…..m] karakter dizisinde P [1……i] giriş modelinin konumunu test eder.

Giriş metninin veya dizesinin uzunluğunun her zaman kalıbın uzunluğundan büyük veya ona eşit olacağını unutmayın.

İşte farklı programlama dilleri için saf model arama algoritması.

Başlamak

pat = desen Boyutu

str = dize boyutu

i = 0 ila (str – pat) için, do

j = 0 için pat, yap

eğer metin[i+j] ≠ desen[j] ise, o zaman

döngüyü kırmak

tamamlamak

j == pat ise, o zaman

i'nin konumunu desen bulundu olarak göster

tamamlamak

Son

Bu algoritma, arama sonuçlarının çıktı olarak verilmesine yardımcı olduğu için bilgisayar bilimlerinde oldukça önemlidir.

Okuyun: Bilmeniz Gereken Yapay Zeka Algoritma Türleri

Python'da Naive String Eşleştirme Örnekleri

İşte bir python kodunda saf model arama yaklaşımının kullanıldığı bir örnek.

# Naive String Matching için Python programı

# Arama algoritması

def arama(P, T):

X = uzun (P)

Y = uzun (T)

# P[]'yi tek tek kaydırmak için bir döngü */

i aralığında (X – Y + 1 ):

j = 0

# Mevcut dizin i için, kontrol edin

# desen eşleşmesi için */

aralığındaki j için (0, X):

if (txt[i + j] ! = P[j]):

kırmak

eğer (j == X – 1):

print ("Desen " konumunda bulundu, i)

# Sürücü Kodu

eğer __name__ == '__main__':

T = “YÜKSELTİLMİŞUBUPGRAABUPGRADEDU”

P = "YÜKSELTME"

arama(P, T)

çıktı :

0 konumunda desen bulundu

17 konumunda bulunan desen

Açıklama: İlk konum 0. konumdur . "UPGRAD" modeli burada ilk kez görüldüğü için çıktı, modelin 0 konumunda bulunduğunu gösterdi.

Benzer şekilde, bir sonraki kalıp 17 konumunda bulundu.

En İyi Naive Model Arama Örneği

En kötü iki durumdan farklı olarak, saf model arama algoritması için yalnızca bir en iyi durum vardır.

En iyi durum, kalıp metnindeki ilk karakterin giriş dizesinde hiçbir yerde olmadığı zaman ortaya çıkar.

Örnek vermek:

T [] = “YÜKSELTMEDUHIJKLUPGRA”;

P [] = “TÜPGRA”;

Ve bu nedenle, eşleşen desenlerin sayısı O(n)'dir.

En Kötü Naif Kalıp Arama Örneği

Saf dizi arama yaklaşımında en kötü iki durum vardır.

1. Kalıptaki tüm karakterler giriş dizesindeki karakterlerle aynı olduğunda.

T [] = “EEEEEEEEEEEEEEEE”;

P [] = “EEE”;

1. Yalnızca kalıptaki son karakter giriş dizesinden farklı olduğunda.

T [] = “EEEEEEEEEEED”;

P [] = “EEEED”;

Bu gibi durumlarda, O(m*(n-m+1)) içindeki karşılaştırma sayısı.

Naive String Matching Algoritmasının Özellikleri

Dize eşleştirme algoritması, bir metindeki belirli bir kalıbın tüm oluşumlarını bulmak içindir.

İşte algoritmanın en önemli özellikleri.

1. Bir giriş metninde kalıp aramak, aralarındaki en basit yöntemdir. Verilen karakter dizisindeki tüm karakterleri tek tek kontrol eder.
2. Tam dize eşleşmelerini bulur - kalıbın daha fazla veya daha fazla kesin oluşumları olsun.
3. Küçük metin olduğunda daha çok kullanılır. Üstelik herhangi bir ön işleme aşaması gerektirmez.
4. Bu arama yöntemi, dizedeki kalıpları aramak ve çalışmak için fazladan yer kaplamaz.

Ayrıca okuyun: Python'da Veri Yapısı ve Algoritma

Naive Pattern Search'ün Avantajları

1. Çalışma süresi eşleşme süresine eşit olduğu için, saf arama yaklaşımında gerekli ön işleme aşamaları yoktur.
2. Ekstra çalışma alanına ihtiyaç yoktur.
3. Desenlerin dizelerle karşılaştırılması herhangi bir sırada yapılabilir.

Naive String Matching'in Dezavantajları

Saf dizi eşleştirme yaklaşımının tek dezavantajı verimsiz olmasıdır. Bunun nedeni, bir pozisyon bulduğunda, diğer pozisyonu bulmak için tekrar kullanmamasıdır. Başlangıç ​​noktasına geri döner ve deseni tekrar arar. Ve böylece bir önceki vardiyadan gelen bilgiyi tekrar kullanmaz.

Çözüm

Naif dizi eşleme algoritması, belirli bir metindeki söz konusu örüntülerin konumlarını bulmak için ön işleme gereksinimi olmaması, işlem için fazladan boşluk olmaması gibi çeşitli nedenlerle en çok tercih edilen yaklaşımdır. Ancak, daha büyük metinler için kullanılamaz çünkü büyük işlemleri daha hızlı gerçekleştirme konusundaki verimsizliği.

Bu yazının size python'daki saf kalıp arama yaklaşımı hakkında önemli ölçüde iyi bir fikir verdiğini umuyoruz. Bu yaklaşımın kullanımları hakkında bilgi edinmek ve konuyu daha geniş bir şekilde anlamak için upGrad'daki uzmanlarla iletişime geçin. Beceri setlerini genişletmek isteyen bireyler için özel olarak tasarlanmış kurslarımız var. Bugün bize ulaşın!

Yapay zeka, makine öğrenimi hakkında daha fazla bilgi edinmek istiyorsanız, çalışan profesyoneller için tasarlanmış ve 450+ saatlik zorlu eğitim, 30'dan fazla vaka çalışması ve ödev sunan IIIT-B & upGrad'ın Makine Öğrenimi ve Yapay Zeka alanında PG Diplomasına göz atın. IIIT-B Mezun statüsü, 5+ pratik uygulamalı bitirme projesi ve en iyi firmalarla iş yardımı.