--- title: 'Kaba Kuvvet Örüntü Arama' source: 'https://academia.sh/tr/kurslar/algoritmalar/kaba-kuvvet-oruntu-arama' course: Algoritmalar language: tr updated: '2026-08-17T18:07:46+00:00' license: 'CC BY-SA 4.0' --- # Kaba Kuvvet Örüntü Arama Metin içinde örüntü arama probleminin tanımı, kaydırmalı tarama, karakter karşılaştırma sayısı, en kötü durum girdileri ve gerçek metindeki davranış. Çizge algoritmaları, aralarında bağlantı bulunan verilerle çalıştı. Bu konu farklı bir yapıya geçer: **sıralı simge dizileri** — metin. Metin işlemenin temel sorusu örüntü aramadır ve bu ders, sorunun kendisini ve en yalın çözümünü kurar. Sonraki dört ders aynı problemi farklı fikirlerle iyileştirecek; ölçüt hep aynı olacak: karakter karşılaştırma sayısı. ## Problem **Örüntü arama:** Uzunluğu $n$ olan bir metin ve uzunluğu $m$ olan bir örüntü verilir; örüntünün metinde geçtiği konumlar istenir. Sorunun üç yaygın biçimi vardır ve maliyetleri farklıdır: - **İlk geçiş.** Bulunduğu anda durulur. - **Tüm geçişler.** Metnin sonuna kadar sürer. - **Geçiş sayısı.** Konumlar saklanmadan sayılır. Bu konu boyunca aynı metin ve örüntü kullanılır: ```python metin = "ABABDABACDABABCABAB" oruntu = "ABABCABAB" ``` Örüntü metinde 10 numaralı dizinde bir kez geçer. Örnek, örüntünün kendi içinde tekrarlar barındırdığı için sonraki derslerin fikirlerini de sınamaya elverişlidir. ## Kaydırmalı Tarama En yalın çözüm, örüntüyü metnin her konumuna yerleştirip karakter karakter karşılaştırmaktır. Uyuşmazlıkta örüntü bir konum sağa kaydırılır ve karşılaştırma baştan başlar. ```python def kaba_kuvvet(metin: str, oruntu: str) -> tuple[list[int], int]: """(bulunan konumlar, karakter karşılaştırma sayısı)""" n, m = len(metin), len(oruntu) konumlar: list[int] = [] sayac = 0 for kaydirma in range(n - m + 1): j = 0 while j < m: sayac += 1 if metin[kaydirma + j] != oruntu[j]: break j += 1 if j == m: konumlar.append(kaydirma) return konumlar, sayac print(kaba_kuvvet(metin, oruntu)) # ([10], 29) print(kaba_kuvvet("ABABAB", "AB")) # ([0, 2, 4], 8) ``` Değişmez şudur: `kaydirma` konumundan önceki hiçbir konumda tam eşleşme yoktur. Sonlanma, kaydırmanın her turda bir artmasından gelir. Algoritma doğrudur ve ek alan kullanmaz. Sorunu maliyetindedir. ## Maliyet Dış döngü $n - m + 1$ kez, iç döngü en çok $m$ kez çalışır: $$ O\big((n - m + 1)\, m\big) = O(nm) $$ En kötü duruma ulaşmak için, her kaydırmada uzun bir öneki eşleşen ama sonda uyuşmayan bir girdi gerekir. ```python kotu_metin = "A" * 30 + "B" kotu_oruntu = "A" * 10 + "B" print(kaba_kuvvet(kotu_metin, kotu_oruntu)) # ([20], 231) print(len(kotu_metin), len(kotu_oruntu)) # 31 11 ``` Her kaydırmada on `A` eşleşir, sonuncu karakter uyuşmaz ve tüm iş boşa gider. Karşılaştırma sayısı $(n - m + 1) \cdot m$ çarpımına yaklaşır: $21 \times 11 = 231$. Bu tür girdiler yapay görünür, ancak ikilik veri, sınırlı abeceli diziler (genetik diziler gibi) ve tekrarlı yapılar taşıyan kütükler bu davranışı gerçekten üretir. ## Gerçek Metinde Davranış Doğal dilde durum farklıdır: uyuşmazlık genellikle ilk birkaç karakterde ortaya çıkar ve iç döngü erken kırılır. ```python uzun_metin = ("bir metin icinde oruntu aramanin maliyeti " "abecenin buyuklugune ve tekrarlara baglidir. ") * 10 for desen in ("oruntu", "maliyeti", "zzz"): konumlar, sayac = kaba_kuvvet(uzun_metin, desen) print(desen, len(konumlar), sayac, len(uzun_metin)) # oruntu 10 915 870 # maliyeti 10 963 870 # zzz 0 868 870 ``` Karşılaştırma sayısı, metin uzunluğunun küçük bir katı kadardır — çarpımsal en kötü duruma hiç yaklaşılmaz. Beklenen karşılaştırma sayısı, abece büyüklüğü $\sigma$ iken kaydırma başına yaklaşık $1/(1 - 1/\sigma)$'dır; abece büyüdükçe bu değer 1'e yaklaşır. Sonuç, çözümleme derslerinin bir uyarısını hatırlatır: **en kötü durum ile tipik durum farklı sorulardır.** Kaba kuvvet arama, büyük abeceli metinlerde pratikte hızlıdır; onu sorunlu kılan, kötü girdide sessizce karesele düşmesidir. ## Karşılaştırma Birimi Algoritmalar "karakter" üzerinde tanımlanır, ama gerçek metinde bu birimin ne olduğu bir seçimdir ve sonucu değiştirir. Bilgisayarlar Nasıl Çalışır kursundaki kodlama dersi üç düzeyi ayırmıştı: **bayt**, **kod noktası** ve kullanıcının tek harf saydığı **öbek**. Bir örüntü arama, bunların hangisinde çalıştığını belirtmek zorundadır. Bayt düzeyinde arama en hızlısıdır ve çok baytlı kodlamalarda hatalı eşleşme üretmez — kodlama, bir karakterin baytlarının başka bir karakterin baytlarının ortasında görünmemesini sağlar. Ancak bulunan konum bayt cinsindendir; karakter konumu isteniyorsa dönüşüm gerekir. Kod noktası düzeyinde arama, birleşik yazılan harflerde şaşırtır: aynı görünen iki metin farklı kod noktası dizileriyle yazılmış olabilir. Bu durumda arama öncesinde bir **normalleştirme** adımı gerekir. Büyük–küçük harf duyarsız arama ise dile bağlıdır; harf katlama kuralları her dilde aynı değildir ve tek karakterlik bir dönüşümün her zaman tek karakter üretmesi de garanti değildir. Bu ayrımlar algoritmayı değiştirmez, ama karşılaştırma işleminin maliyetini ve doğruluğunu belirler. Bu derste ve sonrakilerde karşılaştırma birimi tek kod birimi sayılır. ## Kaybedilen Bilgi Algoritmanın israfı tek bir noktada toplanır: **uyuşmazlıktan önce yapılan karşılaştırmalar unutulur.** `ABABC` örüntüsü `ABABD…` metniyle karşılaştırılırken ilk dört karakterin eşleştiği bilinir. Kaba kuvvet bunu atar ve bir sağa kayıp yeniden başlar — oysa eşleşen kısmın yapısından, bazı kaydırmaların denenmesinin gereksiz olduğu çıkarılabilir. Sonraki üç ders bu bilgiyi üç farklı biçimde kullanır: | Yaklaşım | Kullanılan bilgi | |---|---| | Rabin–Karp | Pencerenin karma değeri; karşılaştırma yerine sayı eşitliği | | Knuth–Morris–Pratt | Örüntünün kendi önek–sonek yapısı | | Boyer–Moore | Uyuşmayan metin karakteri ve örüntünün sonundan eşleme | Üçü de aynı problemi çözer ve aynı sonucu üretir; ayrıldıkları nokta, hangi ön bilgiyi hesaplayıp aramada kullandıklarıdır. ## Ne Zaman Yeterli Kaba kuvvet aramanın iki üstünlüğü vardır: önişleme yapmaz ve ek alan kullanmaz. Bu, şu durumlarda onu doğru seçim yapar: - Örüntü kısa ve metin küçükse; kurulum maliyeti kazançtan büyüktür. - Her arama farklı bir örüntüyle yapılıyorsa; önişleme her seferinde yeniden ödenir. - Abece büyük ve metin doğal dilse; tipik davranış zaten doğrusala yakındır. Buna karşılık aynı örüntü çok kez aranacaksa önişlemeli yöntemler, aynı **metin** çok kez sorgulanacaksa metni önişleyen yapılar öne çıkar. Bu ikinci yol, sonek dizileri dersinin konusudur. ## Özet - Örüntü arama, bir metinde verilen dizinin geçtiği konumları bulur; ilk geçiş, tüm geçişler ve sayım biçimleri farklı maliyetlidir. - Kaba kuvvet arama her kaydırmada baştan karşılaştırır; ek alan kullanmaz ve önişleme gerektirmez. - En kötü durum $O(nm)$'dir ve tekrarlı, küçük abeceli girdilerde gerçekten ortaya çıkar. - Doğal dilde uyuşmazlık erken oluştuğu için tipik maliyet doğrusala yakındır. - Algoritmanın israfı, uyuşmazlıktan önce elde edilen bilginin atılmasıdır. - Sonraki yöntemler bu bilgiyi karma değeri, örüntünün önek–sonek yapısı veya sondan eşleme yoluyla kullanır. ## Sonraki Adım İlk iyileştirme fikri şaşırtıcıdır: karakterleri hiç karşılaştırmamak. Metnin her penceresi bir sayıya indirgenip örüntünün sayısıyla karşılaştırılırsa, çoğu konum tek işlemde elenir. Sonraki ders, pencereden pencereye sabit maliyetle güncellenen yuvarlanan karma fikrini ve karma çakışmalarının nasıl ele alındığını kuracak.