String / Pattern Matching

Zor

Sedgewick

Aho

Metin içerisinde bir veya birden fazla deseni aramak için Kaba Kuvvet, Boyer-Moore varyantları, Durum Makinesi (FSM), NFA ve Düzenli İfade eşleştirmelerini kullanan yaklaşımlardır.

String Arama ve Eşleştirme (String Search & Matching) Algoritması

String Arama ve Eşleştirme (String Search & Matching) Açıklaması

Metin arama algoritmaları bilgisayar bilimlerinin en temel alanlarından biridir. Basit Kaba Kuvvet (Brute-Force) araması her adımı tek tek denerken, Boyer-Moore ve onun uyuşmayan karakter (mismatched-character) varyantı sağdan sola eşleştirme yaparak gereksiz karşılaştırmaları atlar.

Durum Makinesi (Finite State Machine - FSM) ile desen arama, deseni bir DFA haline getirerek metindeki her karakter için O(1) geçiş süresi sunar. NFA (Nondeterministic Finite Automata) simülasyonu ve Düzenli İfade (Regular Expression) eşleştirme ise joker karakterler, gruplar ve tekrarlar barındıran daha karmaşık kurallı kalıpları kontrol etmeyi sağlar.

Çoklu String Aramaları (Aho-Corasick vb.) ise tek bir geçişte metin içerisinde yüzlerce farklı kelimeyi aynı anda aramak için bir arama ağacı (trie) ve hata geçişleri kullanır.

Kaynak Notları

Sedgewick: Brute force matches in O(NM) in the worst case.
Sedgewick: Boyer-Moore variant uses the right-to-left scan and the bad-character mismatch heuristic.
Aho: Regular expressions are converted to NFA via Thompson's construction and simulated using active state sets.

Çalışma Prensibi

Boyer-Moore için: Desen karakterlerinin en sağdaki konumlarını tutan bir bad-character tablosu hazırla.
Metin penceresini hizala, deseni sağdan sola doğru metinle karşılaştır.
Uyuşmazlık olduğunda, uyuşmayan karakterin tablodaki değerine göre pencereyi sağa doğru kaydır.
DFA/NFA için: Düzenli ifadeyi/deseni durumlarına ayır. Metinden okunan her karakterle durumlar arası geçişleri tetikle.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

String Arama ve Eşleştirme (String Search & Matching) Algoritması - TypeScript

1function boyerMooreSearch(text: string, pattern: string): number[] {
2  const n = text.length;
3  const m = pattern.length;
4  if (m === 0) return [];
5
6  // Bad character tablosu oluştur
7  const badChar: Record = {};
8  for (let i = 0; i < m; i++) {
9    badChar[pattern[i]] = i;
10  }
11
12  const shifts: number[] = [];
13  let s = 0;
14  while (s <= n - m) {
15    let j = m - 1;
16    while (j >= 0 && pattern[j] === text[s + j]) {
17      j--;
18    }
19    if (j < 0) {
20      shifts.push(s);
21      s += (s + m < n) ? m - (badChar[text[s + m]] ?? -1) : 1;
22    } else {
23      s += Math.max(1, j - (badChar[text[s + j]] ?? -1));
24    }
25  }
26  return shifts;
27}

Kendi Verilerinizle Test Edin

Modu, deseni ve metni noktalı virgülle ayırarak girin. Modlar: BF (Kaba Kuvvet), BM (Boyer-Moore), FSM (Durum Makinesi), REGEX (NFA/Regex). Örnek: BM; NEEDLE; FINDINNEEDLESTACK

Metin Arama ve Düzenli İfade Demo

Modu, deseni ve metni noktalı virgülle ayırarak girin. Modlar: BF (Kaba Kuvvet), BM (Boyer-Moore), FSM (Durum Makinesi), REGEX (NFA/Regex). Örnek: BM; NEEDLE; FINDINNEEDLESTACK

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(N / M) Boyer-Moore ile

Ortalama Durum: O(N + M)

En Kötü Durum: O(N * M) Kaba Kuvvet ile

Alan Karmaşıklığı

O(M + Σ) bad-char tablosu veya FSM geçişleri için - Bu algoritmanın karmaşıklığı belirtilmemiş.

Eşleştirme Seçenekleri

Boyer-Moore, alfabetik genişliği büyük olan dillerde ve uzun desenlerde O(N/M) performansı ile alt-doğrusal (sub-linear) çalışabilir.
DFA tabanlı arama, her karakterde tek bir dizi okuması yaptığı için O(N) süresini garanti eder, ancak durum geçiş tablosunun oluşturulması O(M * Σ) yer kaplar.
Regex NFA eşleştirmesinde, geriye izleme (backtracking) içeren naif yapılar üstel O(2^N) zaman alabilirken, Thompson NFA simülasyonu O(N * M) zamanında tamamlanır.

Avantajlar ve Dezavantajlar

Avantajlar

Boyer-Moore uzun kelimelerde metnin büyük bir kısmını atlayarak inanılmaz hızlı çalışır.
NFA ve Regex esnek kalıp tanımlama imkanı tanır.

Dezavantajlar

Boyer-Moore kısa veya çok tekrarlı desenlerde (örn. "AAAA") Brute-Force seviyesine düşebilir.
FSM geçiş tabloları büyük alfabelerde (Unicode) çok yer kaplar.

İlgili Algoritmalar

String Arama ve Eşleştirme (String Search & Matching) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

KMP Algorithm

Metinde geriye sarmadan arama yapabilen deterministik algoritma.

Rabin-Karp Algorithm

Rolling hash kullanarak desen arama yapan algoritma.

Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...

String Arama ve Eşleştirme (String Search & Matching) Algoritması

String Arama ve Eşleştirme (String Search & Matching) Açıklaması

Çoklu String Aramaları (Aho-Corasick vb.) ise tek bir geçişte metin içerisinde yüzlerce farklı kelimeyi aynı anda aramak için bir arama ağacı (trie) ve hata geçişleri kullanır.

Kaynak Notları

Sedgewick: Brute force matches in O(NM) in the worst case.
Sedgewick: Boyer-Moore variant uses the right-to-left scan and the bad-character mismatch heuristic.
Aho: Regular expressions are converted to NFA via Thompson's construction and simulated using active state sets.

Çalışma Prensibi

Boyer-Moore için: Desen karakterlerinin en sağdaki konumlarını tutan bir bad-character tablosu hazırla.
Metin penceresini hizala, deseni sağdan sola doğru metinle karşılaştır.
Uyuşmazlık olduğunda, uyuşmayan karakterin tablodaki değerine göre pencereyi sağa doğru kaydır.
DFA/NFA için: Düzenli ifadeyi/deseni durumlarına ayır. Metinden okunan her karakterle durumlar arası geçişleri tetikle.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

String Arama ve Eşleştirme (String Search & Matching) Algoritması - TypeScript

1function boyerMooreSearch(text: string, pattern: string): number[] {
2  const n = text.length;
3  const m = pattern.length;
4  if (m === 0) return [];
5
6  // Bad character tablosu oluştur
7  const badChar: Record = {};
8  for (let i = 0; i < m; i++) {
9    badChar[pattern[i]] = i;
10  }
11
12  const shifts: number[] = [];
13  let s = 0;
14  while (s <= n - m) {
15    let j = m - 1;
16    while (j >= 0 && pattern[j] === text[s + j]) {
17      j--;
18    }
19    if (j < 0) {
20      shifts.push(s);
21      s += (s + m < n) ? m - (badChar[text[s + m]] ?? -1) : 1;
22    } else {
23      s += Math.max(1, j - (badChar[text[s + j]] ?? -1));
24    }
25  }
26  return shifts;
27}

Kendi Verilerinizle Test Edin

Modu, deseni ve metni noktalı virgülle ayırarak girin. Modlar: BF (Kaba Kuvvet), BM (Boyer-Moore), FSM (Durum Makinesi), REGEX (NFA/Regex). Örnek: BM; NEEDLE; FINDINNEEDLESTACK

Metin Arama ve Düzenli İfade Demo

Modu, deseni ve metni noktalı virgülle ayırarak girin. Modlar: BF (Kaba Kuvvet), BM (Boyer-Moore), FSM (Durum Makinesi), REGEX (NFA/Regex). Örnek: BM; NEEDLE; FINDINNEEDLESTACK

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(N / M) Boyer-Moore ile

Ortalama Durum: O(N + M)

En Kötü Durum: O(N * M) Kaba Kuvvet ile

Alan Karmaşıklığı

O(M + Σ) bad-char tablosu veya FSM geçişleri için - Bu algoritmanın karmaşıklığı belirtilmemiş.

Eşleştirme Seçenekleri

Boyer-Moore, alfabetik genişliği büyük olan dillerde ve uzun desenlerde O(N/M) performansı ile alt-doğrusal (sub-linear) çalışabilir.
DFA tabanlı arama, her karakterde tek bir dizi okuması yaptığı için O(N) süresini garanti eder, ancak durum geçiş tablosunun oluşturulması O(M * Σ) yer kaplar.
Regex NFA eşleştirmesinde, geriye izleme (backtracking) içeren naif yapılar üstel O(2^N) zaman alabilirken, Thompson NFA simülasyonu O(N * M) zamanında tamamlanır.

Avantajlar ve Dezavantajlar

Avantajlar

Boyer-Moore uzun kelimelerde metnin büyük bir kısmını atlayarak inanılmaz hızlı çalışır.
NFA ve Regex esnek kalıp tanımlama imkanı tanır.

Dezavantajlar

Boyer-Moore kısa veya çok tekrarlı desenlerde (örn. "AAAA") Brute-Force seviyesine düşebilir.
FSM geçiş tabloları büyük alfabelerde (Unicode) çok yer kaplar.