Bölüm 5.1: Dizgi Algoritmaları

5.1.1Dizgi eşleştirme problemi

Bilgisayarların işlediği verinin büyük bölümü metindir: e-postalar, iletiler, sosyal medya paylaşımları, haber metinleri, program kaynak kodları, kayıt dosyaları. Bu metinler üzerinde en sık yapılan işlem aramadır. Bir kelimenin geçtiği yerler bulunur, bir ifade başka bir ifadeyle değiştirilir ya da iki metnin benzerliği ölçülür. Bu tür işlemleri yapan algoritmalara dizgi algoritmaları (string algorithms) denir. Bölümün iki ana konusu vardır: bir örüntüyü metinde bulmak (dizgi eşleştirme) ve metni daha az yerde saklamak (dizgi sıkıştırma). Bu kesim eşleştirme problemini tanımlar ve kullanılacak gösterimi kurar.

5.1.1.1Metin arama her yerde

Dizgi eşleştirme günlük yazılımların içine gömülüdür. Metin düzenleyicilerdeki Ctrl+F araması, Unix'in grep komutu ve arama motorlarının dizinleri bunun en bilinen örnekleridir. Daha az görünen kullanımlar da vardır. Virüs tarayıcıları dosyalarda bilinen kötü amaçlı yazılımların bayt dizilerini (imzalarını) arar. İntihal tespit araçları iki belgede ortak geçen uzun parçaları bulur. Biyoinformatikte bir genin ya da kısa bir DNA parçasının milyonlarca harflik bir dizide nerede geçtiği sorulur.

Sıkıştırma da aynı ölçüde yaygındır. ZIP arşivleri, GIF ve PNG resimleri, PDF belgeleri ve faks makineleri veriyi daha az bitle saklamak için dizgi algoritmalarından yararlanır. Bu yöntemlerin çoğu da özünde bir aramadır: daha önce görülmüş bir parçanın tekrarını bulup onu kısa bir göstergeyle değiştirir.

Bu uygulamalarda metinler büyüktür. Bir kayıt dosyası gigabaytlarca, bir insan genomu yaklaşık üç milyar harf uzunluğundadır. Bu yüzden algoritmanın her karakteri kaç kez okuduğu doğrudan çalışma süresini belirler. Bölümdeki algoritmaların hepsi aynı soruyu yanıtlar. Farkları, bu soruyu kaç karşılaştırmayla yanıtladıklarıdır.

5.1.1.2Temel kavramlar ve gösterim

Dizgiler bir karakter kümesinden oluşur. Bu kümeye alfabe (alphabet) denir ve Σ ile gösterilir. İngilizce küçük harfler için Σ = {a, b, …, z}, DNA için Σ = {A, C, G, T}, ikili veri için Σ = {0, 1}'dir. Alfabenin büyüklüğü σ = |Σ| ile yazılır. Bazı algoritmaların hızı bu sayıya bağlıdır.

Aramanın yapıldığı uzun dizgiye metin (text), aranan kısa dizgiye örüntü (pattern) denir. Metin T[0..n−1], örüntü P[0..m−1] biçiminde yazılır. Böylece n metnin, m örüntünün uzunluğudur ve genellikle m ≤ n'dir. İndisler Java'daki gibi 0'dan başlar. Kodlarda metin t, örüntü p adıyla geçer; t.charAt(i), T[i]'nin karşılığıdır.

Algoritmaların çoğu, örüntünün baş ve son parçaları üzerine kuruludur. Bir dizginin başından alınan parçaya önek (prefix), sonundan alınan parçaya sonek (suffix) denir. P'nin k uzunluklu öneki P[0..k−1], k uzunluklu soneki P[m−k..m−1]'dir. Dizginin kendisi de hem öneki hem sonekidir. Dizginin kendisine eşit olmayan öneke uygun önek (proper prefix), kendisine eşit olmayan sonek ise uygun sonek adını alır. Kaynaklarda “öz önek” adı da kullanılır.

Karakter karşılaştırmasının sonucu iki türlüdür. Karakterler aynıysa eşleşme, farklıysa uyuşmazlık (mismatch) vardır. Notun şekillerinde eşleşen karakterler yeşil, uyuşmayan karakterler kırmızı kutuyla gösterilir. Algoritmaların maliyeti çoğunlukla toplam karakter karşılaştırma sayısıyla ölçülür. Bu sayı, makineden ve dilden bağımsız, sayılabilir bir büyüklüktür.

5.1.1.3Algoritmaların haritası

Bölümde altı algoritma ele alınır. İlk dördü eşleştirme, son ikisi sıkıştırma algoritmasıdır:

• Kaba kuvvet (brute force, naive): metindeki her konum, örüntüyle eşleşip eşleşmediği için ayrı ayrı denetlenir. En fazla karşılaştırmayı bu yöntem yapabilir.
• Knuth-Morris-Pratt (KMP): aramadan önce örüntüden bir tablo (LPS tablosu) kurulur. Arama sırasında metinde hiç geri gidilmez; en kötü durumda bile süre doğrusaldır.
• Boyer-Moore: karşılaştırma sağdan sola yapılır. Kötü karakter ve iyi sonek kuralları uzun atlamalar sağlar; uzun örüntülerde çok etkilidir.
• Rabin-Karp: karakterler yerine hash (özet) değerleri karşılaştırılır. Pencere kaydıkça hash O(1) sürede güncellenir; algoritma beklenen durumda hızlıdır.
• Sıralı sıkıştırma kodlaması (run-length encoding, RLE): ardışık tekrar eden değerler tek değer ve bir tekrar sayısıyla saklanır.
• Lempel-Ziv-Welch (LZW): sözlük tabanlı sıkıştırmadır. Tekrar eden dizgiler, sıkıştırma sırasında büyüyen bir sözlüğün kısa kodlarıyla temsil edilir. GIF biçimi bu yöntemi kullanır.

Eşleştirme algoritmalarının hepsi aynı çıktıyı üretir. Aralarındaki fark, uyuşmazlık anında ne yaptıklarıdır. Kaba kuvvet uyuşmazlıktan hiçbir şey öğrenmez ve örüntüyü bir konum kaydırır. KMP, eşleşmiş parçanın yapısından yararlanarak gereksiz kaymaları atlar. Boyer-Moore, uyuşmayan metin karakterinin örüntüde nerede geçtiğine bakar. Rabin-Karp ise karşılaştırmanın kendisini ucuzlatır. Bu dört bakış açısı, aynı problemin neden birden çok çözümü olduğunu da açıklar.

5.1.2Kaba kuvvet algoritması

Kaba kuvvet algoritması, metin içinde bir örüntü arayan en basit yöntemdir. İngilizcedeki “naive” (saf) adı da bu sadelikten gelir. Algoritma hiçbir ön hazırlık yapmaz ve hiçbir ek bellek kullanmaz. Bu yüzden hem öbür algoritmaların karşılaştırıldığı ölçüttür hem de kısa örüntülerde hâlâ kullanılan pratik bir yöntemdir.

5.1.2.1İşleyiş

Algoritma, olası her kaymayı soldan sağa sırayla dener:

1. Hizalama. s = 0, 1, …, n − m kaymalarının her biri için örüntü metnin altına, ilk karakteri T[s]'nin altına gelecek biçimde yerleştirilir.
2. Karşılaştırma. P[0] ile T[s], P[1] ile T[s+1] diye soldan sağa karşılaştırılır. İlk uyuşmazlıkta bu hizanın denetimi biter.
3. Karar. m karakterin hepsi eşleşmişse s rapor edilir. Aksi hâlde örüntü bir konum sağa kaydırılır ve bir sonraki kayma denenir.

Karşılaştırma sayısı metne ve örüntüye bağlıdır. En kötü durumda her hizada m karakterin hepsi karşılaştırılır: (n − m + 1) · m karşılaştırma, yani O(n · m). En iyi durumda her hizada ilk karakter uyuşmaz: n − m + 1 karşılaştırma, yani O(n).

5.1.2.2Örnek: SIMPLE araması

Şekil 5.1.3 "THIS IS A SIMPLE EXAMPLE" metninde (n = 24) "SIMPLE" örüntüsünün (m = 6) aranışını gösterir. Her satır bir kaymadır. Boşluk karakteri ␣ işaretiyle gösterilmiştir.

Algoritma s = 0'dan başlar. s = 0, 1, …, 9 kaymalarında ya örüntünün ilk karakteri S metindeki karakterle uyuşmaz ya da yalnız S eşleşir. s = 3'te T[3] = S eşleşir, ardından T[4] = ␣ ile I uyuşmaz. s = 6'da da aynı şey olur: S eşleşir, ␣ uyuşmaz. Diğer kaymaların hepsi ilk karşılaştırmada biter. s = 10'da altı karakterin altısı da eşleşir. Tablo 5.1.1 karşılaştırmaları kayma kayma sayar.

Toplam 18 karşılaştırma, metnin uzunluğuna (24) yakındır. Bunun nedeni, doğal dil metninde iki rastgele karakterin çoğunlukla farklı olmasıdır. Uyuşmazlık genellikle ilk karakterde çıkar. Kaba kuvvetin pratikte çoğu zaman kabul edilebilir hızda çalışması bu gözleme dayanır.

5.1.2.3Java kodu ve izleme

Algoritmanın Java kodu iki iç içe döngüden oluşur. Dış döngü kaymaları, iç döngü bir hizadaki karakterleri dolaşır. Metot ilk geçişin konumunu döndürür; örüntü yoksa −1 döner.

int kabaKuvvet(String t, String p) {
  int n = t.length(), m = p.length();
  for (int i = 0; i <= n - m; i++) {
    int j = 0;
    while (j < m &&
      t.charAt(i + j) == p.charAt(j))
      j++;
    if (j == m) return i;
  }
  return -1;
}

Kod satır satır şöyle okunur:

• Dış döngü: i kaymadır ve 0'dan n - m'ye kadar artar. Koşul i <= n - m biçimindedir, çünkü son geçerli kayma n − m'dir. i + j en çok n − m + m − 1 = n − 1 olur; dizinin dışına çıkılmaz.
• İç döngü: j, o hizada eşleşen karakter sayısıdır. j < m ve karakterler eşit olduğu sürece j artar. İki koşulun sırası önemlidir: && işleci ikinci koşulu ancak birincisi doğruysa değerlendirir. Böylece j == m olduğunda p.charAt(m) çağrılmaz.
• Karar: iç döngü j == m ile bittiyse bütün karakterler eşleşmiştir ve i döndürülür. Döngü daha erken bittiyse bir uyuşmazlık vardır ve dış döngü bir sonraki kaymaya geçer.

Kodu kabaKuvvet("HELLO WORLD", "LO") çağrısıyla izleyelim. n = 11, m = 2'dir; kaymalar i = 0, 1, …, 9'dur. Tablo 5.1.2 her karşılaştırmayı sırasıyla verir.

Toplam 6 karşılaştırma yapılır. 4. ve 5. adımlara dikkat: T[3] = 'L' iki kez okunur. İlkinde örüntünün ikinci karakteriyle, sonra birinci karakteriyle karşılaştırılır. Kaba kuvvetin temel kusuru budur: örüntü kaydığında metinde geri gidilir ve aynı karakterler yeniden okunur.

Bellek maliyeti O(1)'dir; yalnız i, j, n ve m tutulur. Bütün geçişler isteniyorsa return i yerine i bir listeye eklenir ve döngü sürer; karmaşıklık değişmez.

5.1.2.4En iyi, ortalama ve en kötü durum

Kaba kuvvetin karşılaştırma sayısı, her hizada kaç karakterin eşleştiğine bağlıdır. Tablo 5.1.3 üç durumu özetler.

Ortalama durumdaki σ/(σ − 1) çarpanı basit bir olasılık hesabından gelir. Metnin karakterleri alfabeden bağımsız ve eşit olasılıkla seçilmiş olsun. Bir hizada ilk karşılaştırma her zaman yapılır. İkinci karşılaştırma ancak ilk karakter eşleşirse yapılır; bunun olasılığı 1/σ'dır. Üçüncüsü için ilk iki karakterin eşleşmesi gerekir: olasılık 1/σ². Bir hizadaki beklenen karşılaştırma sayısı bu yüzden en çok 1 + 1/σ + 1/σ² + … = σ/(σ − 1)'dir. İngilizce harflerde (σ = 26) bu sayı yaklaşık 1,04'tür; ikili alfabede (σ = 2) 2'dir. İki durumda da hiza başına iş sabittir ve toplam süre O(n) olur.

En kötü durumda neler olduğu dikkatle incelenmeye değer. s = 0'da ilk üç karakter eşleşmiştir. Bu bilgi, metnin T[0..2] = "aaa" olduğunu söyler. s = 1'e geçildiğinde algoritma T[1] ve T[2]'yi yeniden okur, oysa bu karakterler zaten biliniyordu. Kaba kuvvetin asıl kusuru buradadır: uyuşmazlıkta öğrenilen bilgi atılır, metinde geri gidilir ve aynı karakterler tekrar karşılaştırılır. KMP algoritması tam olarak bu bilgiyi saklayıp kullanır.

5.1.3Knuth-Morris-Pratt algoritması

Knuth-Morris-Pratt (KMP) algoritması, kaba kuvvetin attığı bilgiyi saklayan ilk doğrusal zamanlı eşleştirme algoritmasıdır. James H. Morris ve Vaughan Pratt algoritmayı 1970'te birlikte buldu. Donald Knuth da aynı fikre otomatlar kuramından bağımsız olarak ulaştı. Üçü sonuçlarını 1977'de ortak bir makalede yayımladı. Algoritmanın adı bu üç kişinin soyadlarından gelir.

5.1.3.1Eşleşen kısmı unutmamak

KMP'nin temel fikri şudur: uyuşmazlık anında örüntünün zaten eşleşmiş kısmı hakkında bilinenler kullanılır. Bir hizada P[0..q−1] metinle eşleşmiş ve P[q] uyuşmamış olsun. O zaman metnin son q karakteri tam olarak P[0..q−1]'dir. Bu karakterleri yeniden okumaya gerek yoktur; örüntünün kendisine bakarak ne oldukları bilinir.

Bu bilgi iki şey kazandırır. Birincisi, metin işaretçisi hiç geri gitmez. Metin soldan sağa bir kez okunur. İkincisi, kesinlikle eşleşemeyecek hizalar hiç denenmez. Örüntü, eşleşmiş parçanın yapısının izin verdiği en uzak konuma doğrudan kaydırılır.

Şekil 5.1.5 bu fikri küçük bir örnekle gösterir. Metin "ABABABC", örüntü "ABABC" olsun. s = 0'da ilk dört karakter "ABAB" eşleşir, T[4] = A ile P[4] = C uyuşmaz. Kaba kuvvet örüntüyü bir kaydırıp T[1]'den yeniden başlardı. Oysa metnin son dört karakterinin "ABAB" olduğu biliniyor. "ABAB"ın soneki olan "AB", örüntünün de önekidir. Öyleyse örüntü iki konum kaydırılırsa önündeki "AB" metindeki "AB" ile zaten eşleşmiş olur. Karşılaştırma P[2] ile T[4] arasında sürer. Gerçekten de bu hizada örüntünün kalan "ABC" kısmı da eşleşir ve örüntü s = 2'de bulunur.

Bu kaydırmanın ne kadar olacağı yalnız örüntüye bağlıdır, metne bağlı değildir. Bu yüzden her olası q için önceden hesaplanıp bir tabloya yazılabilir. Bu tabloya LPS tablosu ya da önek fonksiyonu (prefix function) denir ve kaynaklarda π ile de gösterilir.

5.1.3.2LPS tablosu

LPS, “en uzun uygun önek ve aynı zamanda sonek” anlamındaki longest proper prefix which is also suffix ifadesinin kısaltmasıdır. Tablonun her hücresi, örüntünün bir önekinin içindeki en uzun “kendine benzeyen” parçanın uzunluğudur.

Tanımdaki “uygun” sözcüğü önemlidir. Dizginin kendisi de hem öneki hem sonekidir. Tanım onu dışarıda bırakmasaydı her hücre q + 1 olurdu ve tablo hiçbir bilgi taşımazdı. Uygunluk koşulu ayrıca lps[q] ≤ q sonucunu verir. Bu eşitsizlik, algoritmanın her geri çekilmede ilerleme kaydettiğini gösteren kanıtta kullanılır.

Tablonun anlamı aramada ortaya çıkar. Örüntünün ilk q karakteri eşleşmiş ve (q + 1)'inci karakter uyuşmamış olsun. Eşleşmiş parça P[0..q−1]'dir ve onun “kendine benzeyen” en uzun parçası lps[q − 1] uzunluğundadır. Örüntü, bu parça metindeki aynı parçanın altına gelecek kadar kaydırılır. Kayma miktarı q − lps[q − 1], karşılaştırmanın süreceği yeni örüntü konumu ise lps[q − 1]'dir.

Teorem, KMP'nin hiçbir geçişi kaçırmadığını söyler. Atlanan kaymalar, örüntüyle metin arasında kesin bir çelişki içerir. Algoritmanın doğruluğu bu gözleme dayanır.

5.1.3.3LPS tablosunu kurmak

LPS tablosu tanımdan doğrudan hesaplanabilir: her q için bütün önek uzunlukları denenir ve sonekle karşılaştırılır. Bu yol O(m³) sürer. KMP'nin tabloyu kurma yöntemi daha akıllıcadır: tablo, örüntünün kendi içinde aranmasıyla, yani KMP'nin kendisiyle kurulur. Toplam süre O(m)'dir.

int[] lpsHesapla(String p) {
  int m = p.length(), k = 0;
  int[] lps = new int[m];
  for (int q = 1; q < m; q++) {
    while (k > 0 &&
      p.charAt(k) != p.charAt(q))
      k = lps[k - 1];
    if (p.charAt(k) == p.charAt(q))
      k++;
    lps[q] = k;
  }
  return lps;
}

Kodda k, o ana kadar eşleşen önek uzunluğudur. Döngünün her adımında q bir artar ve p[q] karakteri işlenir:

• Geri çekilme: k > 0 iken p[k] ile p[q] farklıysa, uzunluğu k olan önek uzatılamaz. Bir sonraki aday, bu önekin kendi içindeki en uzun “kendine benzeyen” parçasıdır: k = lps[k - 1]. Bu adım, aramadaki uyuşmazlık adımının aynısıdır.
• Uzatma: p[k] == p[q] ise eşleşen önek bir karakter uzar ve k bir artar.
• Yazma: k, P[0..q] için en uzun uygun önek-sonek uzunluğudur ve lps[q]'ya yazılır.

Geri çekilmenin neden lps[k - 1] olduğu şöyle açıklanır. P[0..q]'nun önek-sonek parçalarını uzunluğa göre azalan sırayla denemek gerekir. Bu parçaların her biri, P[0..q−1]'in bir önek-sonek parçasının bir karakter uzatılmış hâlidir. P[0..q−1]'in önek-sonek parçaları da bir zincir oluşturur. En uzunu k, ondan sonraki lps[k − 1], sonraki lps[lps[k − 1] − 1]… Zincirdeki her uzunluk, bir önceki parçanın içindeki en uzun önek-sonek parçasıdır. Algoritma zinciri büyükten küçüğe izler ve uzatılabilen ilk adayda durur.

Kurma işleminin süresi O(m)'dir. Gerekçe, aramanın doğrusallık kanıtının aynısıdır: k her adımda en çok bir artar; toplam artış m − 1'i geçemez. Her geri çekilme k'yi en az bir azaltır ve k negatif olamaz. Bu yüzden toplam geri çekilme sayısı da m − 1'i geçemez. Örnekte 8 artış fırsatına karşılık 3 geri çekilme vardır. Tablo için O(m) ek bellek gerekir.

5.1.3.4Aramanın üç evresi

KMP araması iki işaretçiyle çalışır. i metindeki, q örüntüdeki konumdur; q aynı zamanda o ana kadar eşleşen karakter sayısıdır. Algoritmanın davranışı üç evreye ayrılabilir:

1. İlk karakteri arama. q = 0'dır. Örüntünün ilk karakteriyle eşleşen bir metin karakteri bulunana kadar i ilerletilir.
2. Birlikte ilerleme. Karakterler eşleştikçe iki işaretçi de ilerler. q = m olursa örüntünün sonuna ulaşılmıştır ve i − m + 1 konumu döndürülür.
3. LPS ile geri çekilme. Uyuşmazlıkta yalnız örüntü işaretçisi geri çekilir: q = lps[q − 1]. Metin işaretçisi i yerinde kalır. Bir eşleşme bulununca 2. evreye, q 0'a inerse 1. evreye dönülür.

Evrelerin hiçbirinde i azalmaz. Kaba kuvvetle en önemli fark budur. Kaba kuvvet her yeni hizada metin işaretçisini s'ye geri çeker. KMP'de ise metin bir akış gibi okunur: her karakter bir kez gelir, işlenir ve bir daha istenmez.

5.1.3.5Örnek: ABCDABD araması

Örüntü "ABCDABD", metin "ABCABCDABABCDABCDABDE" olsun (m = 7, n = 21). Örüntünün LPS tablosu [0, 0, 0, 0, 1, 2, 0]'dır: "ABCDA"nın sonundaki "A" ve "ABCDAB"ın sonundaki "AB" aynı zamanda örüntünün önekidir. Şekil 5.1.8 aramanın beş hizasını gösterir.

1. s = 0. "ABC" eşleşir; T[3] = A ile P[3] = D uyuşmaz. q = 3'tür ve q = lps[2] = 0 olur. Örüntü 3 kayar; T[3] bu kez P[0] ile karşılaştırılır.
2. s = 3. "ABCDAB" eşleşir; T[9] = A ile D uyuşmaz. q = 6'dır ve q = lps[5] = 2 olur. Eşleşmiş "ABCDAB"ın sonundaki "AB" önek olduğu için örüntü 4 kayar.
3. s = 7. "AB"nin eşleştiği bilinir, yeniden karşılaştırılmaz. T[9] = A ile P[2] = C uyuşmaz; q = lps[1] = 0.
4. s = 9. T[9] = A, P[0] ile eşleşir. "ABCDAB" eşleşir; T[15] = C ile D uyuşmaz. q = 6 → lps[5] = 2; örüntü 4 kayar.
5. s = 13. "AB" bilinir; ardından "CDABD" de eşleşir. Örüntü 13. konumda bulunur.

Arama boyunca metin işaretçisi hiç geri gitmez. Toplam karakter karşılaştırması 24'tür. Metnin 20 karakteri birer kez okunur. Üç uyuşmazlık noktasında (i = 3, 9, 15) aynı metin karakteri, örüntünün başka bir karakteriyle bir kez daha karşılaştırılır. i = 9'da bu iki kez olur. Kaba kuvvet aynı metinde 14 hiza dener ve 37 karşılaştırma yapar.

5.1.3.6Java kodu ve izleme

Aramanın Java kodu, LPS kurma kodunun neredeyse aynısıdır. Tek fark, örüntünün kendisiyle değil metinle karşılaştırılmasıdır.

int kmpAra(String t, String p) {
  int n = t.length(), m = p.length();
  int[] lps = lpsHesapla(p);
  int q = 0;  // eşleşen uzunluk
  for (int i = 0; i < n; i++) {
    while (q > 0 &&
      p.charAt(q) != t.charAt(i))
      q = lps[q - 1];
    if (p.charAt(q) == t.charAt(i))
      q++;
    if (q == m)
      return i - m + 1;
  }
  return -1;
}

• Hazırlık: LPS tablosu kurulur (O(m)) ve q = 0 yapılır. q, eşleşen önek uzunluğudur.
• Dış döngü: i metni soldan sağa bir kez dolaşır. Kodda i'yi azaltan hiçbir satır yoktur.
• while döngüsü: uyuşmazlık olduğu sürece q LPS zinciri boyunca geri çekilir. q == 0 olunca döngü durur; daha geriye gidilecek yer yoktur.
• if (eşleşme): p[q] ile t[i] eşitse eşleşen önek bir uzar.
• if (q == m): örüntünün tamamı eşleşmiştir. Son eşleşen karakter i'de olduğu için başlangıç i - m + 1'dir.

Kod kmpAra("ababcababcabababd", "ababd") çağrısıyla izlenecek. n = 17, m = 5, lps = [0, 0, 1, 2, 0]'dır. Tablo 5.1.6 her metin karakteri için q'nun değişimini verir.

i = 16'da q == m olur ve 16 − 5 + 1 = 12 döndürülür. Metin yalnız bir kez taranmıştır. i = 14 satırı KMP'nin kazancını en iyi gösteren adımdır. Uyuşmazlık anında metnin son dört karakteri "abab"dır. Bunun sonundaki "ab" örüntünün önekidir; q = 2 ile örüntü iki konum ileriden sürer ve T[14] = a hemen eşleşir. Kaba kuvvet bu noktada T[11]'e geri dönerdi.

Bu izlemede toplam 22 karakter karşılaştırması yapılır: 17 metin karakterinin her biri en az bir kez, uyuşmazlık noktaları birkaç kez okunur. Kaba kuvvet aynı aramada 13 hiza dener ve 33 karşılaştırma yapar.

5.1.3.7Neden O(n + m)?

KMP kodunda iç içe iki döngü vardır. İlk bakışta bu, O(n · m) süre gibi görünür. Oysa while döngüsünün toplam dönme sayısı sınırlıdır. Bu tür, işlemlerin tek tek değil toplamda sayıldığı çözümlemeye amortize analiz (amortized analysis) denir.

Kanıttaki düşünce bir banka hesabı benzetmesiyle de anlatılabilir. Her eşleşme hesaba bir lira yatırır, her geri çekilme hesaptan bir lira çeker. Hesap hiçbir zaman eksiye düşemez. Öyleyse çekilen toplam para, yatırılan toplam paradan fazla olamaz. Tek bir i için while birçok kez dönebilir; Tablo 5.1.6'daki i = 4 satırında iki kez döner. Ama bu ancak önceki adımlarda aynı miktarda eşleşme biriktirilmişse mümkündür.

5.1.3.8Bütün geçişleri bulmak; artılar ve eksiler

Sunumdaki kmpAra ilk geçişte durur. Bütün geçişler isteniyorsa q == m olduğunda konum bir listeye eklenir ve arama sürdürülür. Sürdürmeden önce q, lps[m − 1]'e çekilir. Bu adım, uyuşmazlık adımıyla aynı mantıktadır: örüntünün tamamı eşleşmiştir ve bir sonraki olası geçiş, eşleşen örüntünün en uzun önek-sonek parçasından başlar. Böylece birbiriyle çakışan geçişler de bulunur.

List<Integer> kmpHepsi(String t, String p) {
  int n = t.length(), m = p.length();
  int[] lps = lpsHesapla(p);
  List<Integer> konumlar = new ArrayList<>();
  int q = 0;
  for (int i = 0; i < n; i++) {
    while (q > 0 &&
      p.charAt(q) != t.charAt(i))
      q = lps[q - 1];
    if (p.charAt(q) == t.charAt(i))
      q++;
    if (q == m) {
      konumlar.add(i - m + 1);
      q = lps[q - 1];  // çakışan geçişler için
    }
  }
  return konumlar;
}

Kod Java ile denenmiştir. kmpHepsi("abababa", "aba") çağrısı [0, 2, 4] döndürür. Geçişler birbirine biner: 0'daki "aba"nın son a'sı 2'deki "aba"nın ilk a'sıdır. "aba"nın LPS tablosu [0, 0, 1] olduğu için her bulunuştan sonra q = 1 olur ve tek a yeniden okunmaz. kmpHepsi("aaaaa", "aa") ise [0, 1, 2, 3] verir. q = lps[q − 1] satırı unutulursa q bir sonraki turda m'yi geçer ve p.charAt(q) dizinin dışına çıkar.

KMP'nin güçlü ve zayıf yanları şöyle özetlenebilir:

• En kötü durumda bile doğrusal. Süre girdinin yapısından bağımsız olarak O(n + m)'dir. Kaba kuvvetin en kötü girdisi olan T = a…a, P = a…ab KMP için sorun değildir.
• Metinde geri gitmez. Bu özellik, metnin bir ağdan ya da diskten parça parça geldiği akış (stream) verisinde önemlidir. Metnin önceki parçalarını bellekte tutmak gerekmez.
• Pratikte Boyer-Moore'dan genellikle yavaştır. KMP metnin her karakterini en az bir kez okur. Boyer-Moore ise birçok karakteri hiç okumadan atlar.
• Küçük alfabede kazanç sınırlıdır. DNA gibi dört harfli alfabelerde LPS değerleri büyük çıkabilir ve kaymalar kısa kalır. Sınır yine doğrusaldır, ama sabit çarpan büyür.

5.1.4Boyer-Moore algoritması

Robert S. Boyer ve J Strother Moore 1977'de yayımladıkları algoritmayla şaşırtıcı bir sonuç gösterdi: bir örüntüyü bulmak için metnin her karakterini okumak gerekmez. KMP metnin her karakterine en az bir kez bakar. Boyer-Moore ise doğal dil metninde karakterlerin çoğunu hiç okumadan atlar. Metin düzenleyicilerin ve grep gibi araçların aramaları bu algoritma ailesine dayanır.

5.1.4.1Sağdan sola karşılaştırma

Algoritmanın ilk farkı karşılaştırma yönüdür. Örüntü, kaba kuvvette olduğu gibi metin boyunca soldan sağa kaydırılır. Ama bir hizadaki karakterler sağdan sola, örüntünün son karakterinden başlanarak karşılaştırılır. Bu tercihin nedeni, uyuşmazlığın en çok bilgiyi sağ uçta vermesidir. Sağ uçtaki metin karakteri örüntüde hiç yoksa, o karakteri kapsayan hiçbir hiza eşleşemez. Örüntü tümüyle bu karakterin ötesine, yani m konum kaydırılabilir.

Algoritma dört adımda çalışır:

1. Ön işleme. Örüntüden kaydırma tabloları kurulur: her karakterin örüntüdeki son görülme konumu (kötü karakter tablosu) ve her sonek için kaydırma miktarı (iyi sonek tablosu).
2. Arama. Örüntü metnin altına hizalanır. Karşılaştırma örüntünün son karakterinden başlar ve sola doğru ilerler.
3. Eşleşme denetimi. Bütün karakterler eşleşirse konum rapor edilir.
4. Kaydırma. Uyuşmazlıkta iki kural ayrı ayrı bir kaydırma önerir: kötü karakter kuralı ve iyi sonek kuralı. Örüntü, ikisinden büyük olanı kadar kaydırılır.

İki kural da güvenlidir: önerdikleri kaydırma, eşleşme olabilecek hiçbir hizayı atlamaz. Bu yüzden ikisinin büyüğünü almak da güvenlidir.

5.1.4.2Kötü karakter kuralı

Bir hizada sağdan sola karşılaştırırken j konumunda uyuşmazlık çıktığını varsayalım: P[j] ≠ T[s + j]. Uyuşmayan metin karakterine c = T[s + j] denir ve kötü karakter (bad character) adını alır. Kural, örüntüyü c'nin örüntüdeki yerine göre kaydırır.

Kuralın üç durumu vardır:

• c örüntüde j'nin solunda geçiyor. Örüntü, en sağdaki c metindeki c'nin altına gelecek biçimde kaydırılır. Kaydırma miktarı j − son[c]'dir.
• c örüntüde hiç yok. son[c] = −1 olduğu için kaydırma j + 1 olur. Örüntü, c'nin tamamen ötesine geçer.
• c'nin son geçişi j'nin sağında. Bu durumda j − son[c] ≤ 0 çıkar. Kural, örüntünün geri gitmesini önlemek için en az 1 kaydırır.

Kuralın güvenliği son görülme konumunun tanımından gelir. son[c] en sağdaki geçiş olduğu için son[c] + 1 ile j arasındaki örüntü konumlarında c yoktur. 1, 2, …, j − son[c] − 1 kadarlık daha küçük kaydırmalar, bu konumlardan birini metindeki c'nin altına getirir. Orada bir uyuşmazlık kesindir; bu hizalar atlanabilir.

int[] sonGorulme(String p) {
  int[] son = new int[256];
  Arrays.fill(son, -1);
  for (int i = 0; i < p.length(); i++)
    son[p.charAt(i)] = i;
  return son;
}

sonGorulme metodu 256 hücreli bir dizi kurar ve hepsini −1 yapar. Dizi her ASCII karakteri için bir hücre içerir. Ardından örüntü soldan sağa taranır ve her karakterin hücresine o anki konum yazılır. Aynı karakter birden çok kez geçiyorsa son yazılan, yani en sağdaki konum kalır. Süre O(m + σ), bellek O(σ)'dır; burada σ = 256'dır.

5.1.4.3İyi sonek kuralı

Kötü karakter kuralı yalnız uyuşmayan karaktere bakar; o ana kadar eşleşen karakterlerden yararlanmaz. İkinci kural bu boşluğu doldurur. Uyuşmazlıktan önce eşleşen sonek u = P[j+1..m−1], metinde de bulunmuştur. Bu sonek “iyi sonek” adını alır. İyi sonek kuralı (good suffix rule), örüntüyü u'nun örüntüdeki başka bir geçişine göre kaydırır:

1. Durum 1. u örüntüde başka bir yerde, önünde farklı bir karakterle geçiyorsa örüntü, o geçiş metindeki u'nun altına gelecek biçimde kaydırılır. Önündeki karakterin farklı olması gerekir; aynı karakter aynı uyuşmazlığı tekrarlardı.
2. Durum 2. Böyle bir geçiş yoksa, u'nun bir sonekine eşit olan en uzun P öneki hizalanır.
3. Durum 3. İkisi de yoksa örüntü m konum kaydırılır.

İyi sonek tablosu her j için bu kaydırmayı önceden hesaplar. Tablo, KMP'nin LPS fikrine benzer bir yöntemle, bu kez sonekler üzerinde O(m) sürede kurulur. Kurma yönteminin ayrıntısı uzundur; ders kapsamında kuralın anlamı ve elle uygulanması yeterlidir.

Şekil 5.1.12 iki kuralın farkını gösterir. Kötü karakter A'dır ve son[A] = 3 > j = 2'dir; kötü karakter kuralı yalnız 1 kaydırma önerir. İyi sonek kuralı ise 2 önerir. Algoritma büyüğünü seçer ve örüntüyü 2 kaydırır. Tam Boyer-Moore'da iki tablo birlikte kullanılır.

Küçük alfabelerde iyi sonek kuralı daha da önem kazanır. DNA'da (σ = 4) dört harfin her biri uzun bir örüntüde neredeyse kesin olarak sağ uca yakın bir yerde geçer. Kötü karakter kuralı bu yüzden çoğunlukla 1–2 konumluk kaydırmalar önerir. İyi sonek kuralı ise eşleşmiş parçanın yapısına baktığı için uzun kaydırmalar bulabilir.

5.1.4.4Örnek: HELLO araması

Metin "LO LOELLO O HELLO" (n = 17), örüntü "HELLO" (m = 5) olsun. Örnek yalnız kötü karakter kuralıyla çalıştırılacak. Son görülme tablosu Tablo 5.1.7'de verilmiştir; L iki kez geçtiği için en sağdaki konum (3) yazılmıştır.

Örüntü 7 hizada ve 17 karşılaştırmada s = 12'de bulunur. Hiza 3 dikkat çekicidir: dört karakter eşleştikten sonra uyuşmazlık sol uçta çıkar. Kötü karakter O'nun son geçişi j = 0'ın sağındadır ve kural yalnız 1 kaydırır. Bu hizada iyi sonek kuralı daha fazlasını önerirdi: eşleşen "ELLO", örüntüde başka yerde geçmez ve hiçbir önekle de çakışmaz; kaydırma 5 olurdu. Kuralların birbirini nasıl tamamladığı bu örnekte açıkça görülür.

5.1.4.5Horspool basitleştirmesi

R. Nigel Horspool 1980'de Boyer-Moore'un pratikte çok kullanılan bir sadeleştirmesini önerdi. İyi sonek tablosu tümüyle atılır. Kötü karakter kuralı da değiştirilir: kaydırma, uyuşmazlığın nerede çıktığına bakmadan, hizanın son karakterinin altındaki metin karakterine göre yapılır.

Tabloya örüntünün son karakteri katılmaz. Katılsaydı son karakterin kaydırması m − 1 − (m − 1) = 0 olurdu ve örüntü yerinde sayardı. "HELLO" için tablo şöyledir: H → 4, E → 3, L → 1, O → 5, diğer → 5. L iki kez geçer (konum 2 ve 3); en sağdaki 3 kullanılır ve kaydırma 1 olur. O yalnız son konumda geçtiği için tabloya hiç girmez ve “diğer” gibi 5 alır.

Aynı örnekte Horspool 5 hiza ve 11 karşılaştırmayla yetinir; temel kötü karakter kuralı 7 hiza ve 17 karşılaştırma yapmıştı. Farkın kaynağı ilk hizadır. Temel kural uyuşmayan boşluk karakterine bakıp 3 kaydırır. Horspool ise son karakter O'ya bakar. O, örüntünün ilk dört karakterinde geçmediği için örüntü 5 kayar. Basitleştirme her zaman daha iyi sonuç vermez, ama tek tablosu ve kısa koduyla pratikte çok hızlıdır.

int horspool(String t, String p) {
  int n = t.length(), m = p.length();
  int[] kayd = new int[256];
  Arrays.fill(kayd, m);
  for (int i = 0; i < m - 1; i++)
    kayd[p.charAt(i)] = m - 1 - i;
  int s = 0;
  while (s <= n - m) {
    int j = m - 1;
    while (j >= 0 &&
      p.charAt(j) == t.charAt(s + j))
      j--;
    if (j < 0) return s;
    s += kayd[t.charAt(s + m - 1)];
  }
  return -1;
}

• Tablo: kayd dizisinin 256 hücresi önce m ile doldurulur. Ardından P[0..m−2] soldan sağa taranır ve her karakter için m - 1 - i yazılır. Soldan sağa tarandığı için en sağdaki geçiş en son yazılır ve kalır.
• Karşılaştırma: j sağ uçtan başlar ve karakterler eşleştikçe azalır. j < 0 olursa bütün karakterler eşleşmiştir ve s döndürülür.
• Kaydırma: uyuşmazlık hangi j'de çıkarsa çıksın, s hizanın son karakteri t[s + m - 1]'in tablo değeri kadar artar. Bu değer en az 1 olduğu için örüntü hiç geri gitmez.

horspool("LO LOELLO O HELLO", "HELLO") çağrısı Tablo 5.1.9'daki adımları birebir izler ve 12 döndürür. Kod Java ile çalıştırılarak 5 hiza ve 11 karşılaştırma sayısı doğrulanmıştır.

5.1.4.6Örnek: abacab ile bütün geçişler

Bu örnek, kötü karakter kuralının bütün durumlarını bir arada gösterir. Metin "abacaabadcabacabaabb" (n = 20), örüntü "abacab" (m = 6) olsun. Son görülme tablosu a = 4, b = 5, c = 3, diğerleri −1'dir. Bütün geçişler aranacak; bir eşleşmeden sonra örüntü 1 kaydırılıp aramaya devam edilir.

Arama 10 hizada ve 20 karşılaştırmada biter; örüntü yalnız s = 10'da geçer. Kaydırmaların çoğu 1'dir, çünkü metindeki a ve b karakterleri örüntünün sağ ucuna yakın yerlerde geçer. Tek büyük atlamayı d sağlar. Bu tablo, Boyer-Moore'un hızının alfabeye ve metne bağlı olduğunu gösterir: örüntüde olmayan karakterler ne kadar sıksa atlamalar o kadar uzundur.

5.1.4.7Java kodu ve izleme

Yalnız kötü karakter kuralını kullanan Boyer-Moore kodu, Horspool koduna çok benzer. Tek fark kaydırma satırıdır: kaydırma, son karaktere göre değil uyuşmayan karaktere göre hesaplanır.

int boyerMoore(String t, String p) {
  int n = t.length(), m = p.length();
  int[] son = sonGorulme(p);
  int s = 0;
  while (s <= n - m) {
    int j = m - 1;
    while (j >= 0 &&
      p.charAt(j) == t.charAt(s + j))
      j--;
    if (j < 0) return s;
    s += Math.max(1,
      j - son[t.charAt(s + j)]);
  }
  return -1;
}

Kod boyerMoore("merhaba naber", "abe") çağrısıyla izlenecek. n = 13, m = 3'tür. Son görülme tablosu a = 0, b = 1, e = 2, diğerleri −1'dir.

Arama 5 hizada ve 7 karşılaştırmada biter. Kaba kuvvet aynı aramada 10 hiza dener ve 15 karşılaştırma yapar. 13 karakterlik metnin yalnız 7 karakterine bakılmıştır. 0, 1, 3, 4, 7 ve 12. konumlardaki karakterler hiç okunmamıştır. Boyer-Moore'u kaba kuvvetten ve KMP'den ayıran özellik budur.

5.1.4.8Analiz

Boyer-Moore'un performansı geniş bir aralıkta değişir:

• En iyi durum: metindeki karakterler örüntüde hiç geçmez. Her hizada tek karşılaştırma yapılır ve örüntü m konum atlar. Toplam yaklaşık n/m karşılaştırma yeterlidir: O(n/m). Süre, örüntü uzadıkça kısalır. Kaba kuvvette ve KMP'de bunun tersi olur.
• Ortalama durum: doğal dil metninde ve geniş alfabede çoğu uyuşmazlık sağ uçta çıkar ve kaydırmalar uzundur. Süre alt-doğrusaldır; yani metnin uzunluğundan daha az karakter okunur.
• En kötü durum (yalnız kötü karakter): T = aaaa…a, P = baaa…a. Her hizada sağdan m − 1 a eşleşir, sol uçtaki b uyuşmaz. Kötü karakter a'nın son geçişi sağ uçtadır ve kaydırma 1 olur. Süre O(n · m)'dir. Örneğin n = 20, m = 5 için 16 hizanın her birinde 5 karşılaştırma, toplam 80 karşılaştırma yapılır.
• En kötü durum (tam algoritma): iyi sonek kuralı ve Zvi Galil'in 1979'da önerdiği iyileştirme birlikte kullanılırsa en kötü durum O(n + m)'ye iner.

Boyer-Moore'un ön işleme maliyeti O(m + σ), ek belleği O(m + σ)'dır. Kötü karakter tablosu alfabenin her harfi için bir hücre tuttuğundan büyük alfabelerde (ör. Unicode'un bütün karakterleri) dizi yerine hash tablosu kullanılır.

5.1.5Rabin-Karp algoritması

Michael O. Rabin ve Richard M. Karp'ın 1987'de yayımladığı algoritma soruna başka bir yerden yaklaşır. Kaydırmaları akıllıca seçmek yerine her hizadaki karşılaştırmanın kendisini ucuzlatır. Örüntü ve metin pencereleri birer sayıya dönüştürülür; iki dizginin eşitliği yerine iki sayının eşitliği sınanır.

5.1.5.1Karakter yerine sayı karşılaştırmak

Rabin-Karp, örüntünün ve metindeki her m uzunluklu pencerenin hash değerini hesaplar. Hash, bir dizgiyi küçük bir tam sayıya eşleyen bir fonksiyondur ve dizginin bir tür özetidir. İki sayının karşılaştırılması tek işlemdir; iki dizginin karşılaştırılması ise m işleme kadar çıkabilir.

Bu fikrin iki sorunu vardır. Birincisi, her pencerenin hash'ini baştan hesaplamak O(m) sürer; bu durumda hiçbir kazanç olmaz. Çözüm kayan hash'tir (rolling hash): pencere bir sağa kaydığında yeni hash eskisinden O(1) sürede hesaplanır. İkincisi, farklı dizgiler aynı hash değerini verebilir. Hash eşitliği bu yüzden eşleşmeyi garanti etmez. Hash'leri eşit çıkan pencere yalnız bir adaydır ve karakter karakter doğrulanmalıdır.

Algoritmanın adımları şöyledir:

1. Hash hesabı. Örüntünün ve metnin ilk penceresinin hash değerleri hesaplanır.
2. Eşleşme denetimi. Hash değeri örüntününkine eşit olan pencere aday kabul edilir.
3. Doğrulama. Aday pencere karakter karakter örüntüyle karşılaştırılır.
4. Kaydırma ve yeniden hesap. Eşleşme yoksa pencere bir sağa kaydırılır ve hash güncellenir.
5. Tekrar. Adımlar metnin sonuna kadar sürer.

5.1.5.2Toplam hash ve sahte eşleşme

Fikri en basit hash ile görelim: karakter değerlerinin toplamı. Harflere U = 1, T = 2, S = 3, A = 4, V = 5 değerleri verilsin. "VUATS" metninde "TS" aranıyor; örüntünün hash'i 2 + 3 = 5'tir.

• "VU": 5 + 1 = 6 ≠ 5. Hash farklıdır; karakterlere hiç bakılmaz.
• "UA": 1 + 4 = 5. Hash eşittir, ama "UA" ≠ "TS". Bu bir sahte eşleşmedir (spurious hit); doğrulama boşa harcanır.
• "AT": 4 + 2 = 6 ≠ 5. Yeni hash eskisinden bulunur: çıkan U'nun değeri düşülür, giren T'ninki eklenir: 5 − 1 + 2 = 6. İşlem pencere uzunluğundan bağımsızdır, O(1)'dir.
• "TS": 2 + 3 = 5. Hash eşittir ve karakter karşılaştırması da tutar: eşleşme, s = 3.

Toplam hash kayan güncellemenin ne olduğunu iyi gösterir, ama zayıf bir hash'tir. Harflerin sırasına duyarsızdır: "ST" de 5 verir. Uzun pencerelerde değerler dar bir aralıkta toplanır ve birçok pencere aynı toplamı verir. Gerçek uygulamalarda bu yüzden konum ağırlıklı polinom hash ve büyük bir asal modül kullanılır.

5.1.5.3Polinom hash ve kayan güncelleme

Polinom hash, dizgiyi B tabanında yazılmış bir sayı gibi okur. Karakter kodları basamaklardır; soldaki karakter en büyük basamaktır. Sayı çok büyüyebileceği için bir Q asalına göre kalanı alınır.

Formül üç adımı tek satırda yapar. Önce çıkan karakterin katkısı T[s] · B^m−1 düşülür. Ardından kalan basamaklar B ile çarpılarak bir basamak sola kaydırılır. Son olarak giren karakter en küçük basamağa eklenir. Ondalık bir benzetme bunu açıkça gösterir: "314"ten "141"e geçmek için 3 yüzlüğü atılır (14), bir basamak sola kaydırılır (140) ve 1 eklenir (141).

B^m−1 mod Q değeri her güncellemede gerekir ve pencere uzunluğu değişmediği için bir kez hesaplanıp saklanır. Modüler aritmetiğin kuralları her ara adımda kalan almaya izin verir. (a + b) mod Q ve (a · b) mod Q değerleri, a ile b'nin kalanlarıyla da hesaplanabilir. Bu sayede sayılar hiçbir zaman büyümez.

5.1.5.4Java kodu ve izleme

Sunumdaki kod ASCII kodlarını basamak olarak kullanır: taban B = 256, modül Q = 101'dir. esit(t, p, s) yardımcı metodu, aday pencereyi karakter karakter örüntüyle karşılaştırır.

int rabinKarp(String t, String p) {
  int n = t.length(), m = p.length();
  int B = 256, Q = 101, h = 1;
  for (int i = 0; i < m - 1; i++)
    h = (h * B) % Q;  // B^(m-1) mod Q
  int ph = 0, th = 0;
  for (int i = 0; i < m; i++) {
    ph = (B * ph + p.charAt(i)) % Q;
    th = (B * th + t.charAt(i)) % Q;
  }
  for (int s = 0; s <= n - m; s++) {
    if (ph == th && esit(t, p, s))
      return s;
    if (s < n - m) {
      th = (B * (th - t.charAt(s) * h)
            + t.charAt(s + m)) % Q;
      if (th < 0) th += Q;
    }
  }
  return -1;
}

• İlk döngü: h = Bm−1 mod Q hesaplanır. Bu, çıkan karakterin ağırlığıdır.
• İkinci döngü: ph (örüntü hash'i) ve th (ilk pencerenin hash'i) Horner yöntemiyle hesaplanır: her adımda önceki değer B ile çarpılır ve yeni karakter eklenir. Bu döngü O(m) sürer.
• Ana döngü: her kayma için önce hash'ler karşılaştırılır. && sayesinde esit ancak hash'ler eşitse çağrılır. Eşleşme yoksa ve metnin sonuna gelinmemişse th kayan formülle güncellenir.
• if (th < 0) th += Q; satırı Java'nın negatif kalan sorununu giderir. th - t.charAt(s) * h çoğunlukla negatiftir ve % işleci negatif bir kalan döndürür.

Kod rabinKarp("abracadabra", "cad") çağrısıyla izlenecek. n = 11, m = 3'tür. h = 256² mod 101 = 88'dir. Örüntü hash'i ph = (99 · 256² + 97 · 256 + 100) mod 101 = 11'dir (c = 99, a = 97, d = 100). İlk pencere "abr"nin hash'i 4'tür.

İzlemede dört pencerede hash'ler farklı çıkar ve karakterlere hiç bakılmaz. Karakter karşılaştırması yalnız beşinci pencerede, üç karakter için yapılır. Tablodaki “ara” değerlerinin hepsi negatiftir. Java'nın % işleci bu yüzden her adımda negatif kalan verir ve düzeltme satırı her adımda çalışır. Bu satır unutulsaydı ikinci pencerenin hash'i 30 yerine −71 olurdu. Sonraki hash'ler de yanlış çıkardı ve "cad" penceresinin hash'i 11'e hiç eşit olmayabilirdi.

5.1.5.5Analiz ve çok sayıda örüntü

Rabin-Karp'ın maliyeti iki parçadan oluşur: hash hesapları ve doğrulamalar. Hash hesapları her durumda O(m) + (n − m) · O(1) = O(n + m) tutar. Doğrulamaların maliyeti ise kaç pencerenin aday olduğuna bağlıdır.

• En iyi ve ortalama durum: Q büyük bir asal seçilirse rastgele bir pencerenin hash'inin örüntününkine yanlışlıkla eşit çıkma olasılığı yaklaşık 1/Q'dur. Beklenen sahte eşleşme sayısı (n − m + 1)/Q'dur. n = 10⁶ ve Q ≈ 10⁹ için bu sayı yaklaşık 0,001'dir: bütün metin boyunca büyük olasılıkla hiç sahte eşleşme çıkmaz. Gerçek geçişler k tane ise beklenen süre O(n + m + k · m)'dir; az sayıda geçiş için O(n + m).
• En kötü durum: kötü bir Q seçilir ya da girdi kasıtlı olarak çakışmalar üretecek biçimde hazırlanırsa her pencere aday olur. Örneğin T = a…a ve P = a…a için bütün pencereler gerçek eşleşmedir ve her biri m karakterle doğrulanır. Süre O(n · m)'dir.

Ek bellek O(1)'dir; yalnız birkaç tam sayı tutulur. Rabin-Karp'ın asıl gücü tek örüntüde değil, çok sayıda örüntüde ortaya çıkar. Aynı uzunlukta k örüntünün hash'leri bir kümeye (HashSet) konur. Metin bir kez taranır ve her pencerenin hash'i kümede aranır. Küme araması ortalama O(1) olduğu için bütün örüntüler beklenen O(n + k · m) sürede bulunur. KMP ya da Boyer-Moore ile aynı iş, metni k kez taramayı gerektirirdi.

List<Integer> rkCoklu(String t, List<String> desenler) {
  int n = t.length(), m = desenler.get(0).length();
  int B = 256, Q = 101, h = 1;
  for (int i = 0; i < m - 1; i++)
    h = (h * B) % Q;
  Set<Integer> hashler = new HashSet<>();
  Set<String> kume = new HashSet<>(desenler);
  for (String p : desenler) {
    int ph = 0;
    for (int i = 0; i < m; i++)
      ph = (B * ph + p.charAt(i)) % Q;
    hashler.add(ph);
  }
  List<Integer> konumlar = new ArrayList<>();
  int th = 0;
  for (int i = 0; i < m; i++)
    th = (B * th + t.charAt(i)) % Q;
  for (int s = 0; s <= n - m; s++) {
    if (hashler.contains(th)
        && kume.contains(t.substring(s, s + m)))
      konumlar.add(s);
    if (s < n - m) {
      th = (B * (th - t.charAt(s) * h)
            + t.charAt(s + m)) % Q;
      if (th < 0) th += Q;
    }
  }
  return konumlar;
}

Kod Java ile denenmiştir: rkCoklu("abracadabra", List.of("cad", "bra", "xyz")) çağrısı [1, 4, 8] döndürür. "bra" 1 ve 8'de, "cad" 4'te geçer; "xyz" metinde yoktur. Doğrulama, pencerenin kendisinin örüntü kümesinde bulunup bulunmadığına bakar. Böylece hash'i bir örüntününkiyle çakışan ama hiçbir örüntüye eşit olmayan pencereler elenir.

Bu teknik intihal tespitinin ve belge benzerliği ölçümünün temelidir. Bir belgedeki bütün k kelimelik parçaların hash'leri çıkarılır ve başka bir belgenin parçalarıyla karşılaştırılır. Aynı düşünce iki boyuta da genişletilebilir: bir görüntünün içinde küçük bir görüntü bloğu, satır ve sütun hash'leriyle aranabilir.

5.1.6Eşleştirme algoritmalarının karşılaştırması

Dört algoritma aynı soruyu yanıtlar, ama farklı varsayımlar altında en iyidir. Tablo 5.1.13 temel özelliklerini yan yana koyar.

* Rastgele metin ve geniş alfabe için; tekrarlı metinde O(n · m)'ye yaklaşır. ** Yalnız kötü karakter kuralıyla; iyi sonek kuralı ve Galil iyileştirmesiyle O(n + m).

Asimptotik sınırlar resmin yalnız bir parçasıdır. Tablo 5.1.14, notta kullanılan örneklerde dört yöntemin karakter karşılaştırma sayılarını verir. Sayılar algoritmalar Python ve Java ile çalıştırılarak elde edilmiştir. KMP'de her karakter çifti bir kez sayılmıştır; while döngüsünden eşitlikle çıkılıp if'te aynı çiftin yeniden denetlenmesi ayrıca sayılmamıştır. Boyer-Moore sütunu yalnız kötü karakter kuralını kullanır.

Tablodan üç gözlem çıkar. Birincisi, KMP kaba kuvvetten hiçbir zaman kötü değildir. Kazancı, eşleşmiş parçaların uzun olduğu tekrarlı metinlerde büyür. Doğal dil metninde (SIMPLE satırı) iki yöntem neredeyse aynı işi yapar. İkincisi, Boyer-Moore çoğu satırda açık ara öndedir. Son satırda kaba kuvvetin en kötü girdisi, Boyer-Moore için en kolay girdilerden biridir. Örüntünün sağ ucundaki b her hizada ilk karşılaştırmada uyuşmaz ve örüntü her seferinde ilerler. Üçüncüsü, hiçbir yöntem her girdide en iyi değildir. HELLO satırında temel kötü karakter kuralı kaba kuvvetten iyi değildir, Horspool ise daha iyidir.

Seçim için kaba bir yol haritası şöyledir:

• Garanti gerekiyorsa KMP. Akış verisinde (ağdan gelen, geri okunamayan veride) ya da en kötü durum sınırının önemli olduğu gerçek zamanlı sistemlerde tercih edilir.
• Uzun örüntü ve doğal dil metni için Boyer-Moore ya da Horspool. Metin düzenleyicilerde ve komut satırı araçlarında pratikte en hızlı seçenektir.
• Çok sayıda örüntü için Rabin-Karp. Aynı uzunlukta birçok örüntü tek geçişte aranır: intihal kontrolü, virüs imzaları.
• Kısa örüntü ve kısa metin için kaba kuvvet. Ön işlemesi yoktur, kodu kısadır ve ek bellek istemez. Birkaç karakterlik örüntülerde öbür yöntemlerin hazırlık maliyeti kazancı aşabilir.

5.1.7Dizgi sıkıştırma

Bölümün ikinci konusu, metni ya da genel olarak veriyi daha az bitle saklamak ve iletmektir. Sıkıştırma disk alanından ve ağ bant genişliğinden tasarruf sağlar. Bir dosyanın boyutu yarıya inerse indirme süresi de kabaca yarıya iner. Sıkıştırma algoritmaları verideki fazlalığı, yani tekrar eden ya da tahmin edilebilir kısımları bulur ve bunları daha kısa biçimde yazar.

5.1.7.1Kayıpsız ve kayıplı sıkıştırma

Kayıplı sıkıştırma JPEG resimlerinde ve MP3 seslerinde kullanılır. Bir fotoğrafın gözün fark etmeyeceği renk geçişlerini atmak büyük kazanç sağlar. Metin için ise kayıplı sıkıştırma uygun değildir. Bir programdaki tek bir karakterin değişmesi programı bozar; bir sözleşmedeki tek bir rakamın değişmesi anlamı değiştirir. Bu yüzden metin, program, PNG ve GIF resimleri kayıpsız sıkıştırılır. Bölümdeki iki yöntem, RLE ve LZW, kayıpsızdır.

Oranın kullanımına bir örnek: 15 karakterlik bir metin 8 karaktere iniyorsa oran 8/15 ≈ 0,53'tür; veri yaklaşık yarıya inmiştir. Kaynaklarda oran bazen ters yönde (orijinal / sıkıştırılmış) ya da yüzde kazanç olarak da verilir. Bu notta sunumdaki tanım kullanılır.

5.1.7.2Her girdiyi küçülten yöntem yoktur

Sıkıştırmanın aşılamaz bir sınırı vardır. Hiçbir kayıpsız yöntem her girdiyi küçültemez. Bu sonuç, basit bir sayma argümanına, güvercin yuvası ilkesine dayanır: k + 1 güvercin k yuvaya yerleşirse en az bir yuvada iki güvercin olur.

Örneğin 8 bitlik 256 farklı bayt vardır, ama 8 bitten kısa yalnız 255 farklı bit dizisi vardır. Teoremin pratik sonucu şudur: sıkıştırma algoritmaları belirli türden fazlalığı hedefler. O fazlalığı içeren girdileri küçültür, içermeyenleri biraz büyütür. RLE ve LZW'yi değerlendirirken sorulacak soru, hangi fazlalığı yakaladıkları ve hangi girdide başarısız olduklarıdır. Zaten sıkıştırılmış bir dosyayı yeniden sıkıştırmanın neredeyse hiç kazanç sağlamaması da aynı nedenden kaynaklanır.

5.1.8Sıralı sıkıştırma kodlaması (RLE)

Sıralı sıkıştırma kodlaması (run-length encoding, RLE) en basit sıkıştırma yöntemlerinden biridir. Yakaladığı fazlalık, aynı sembolün art arda tekrarıdır.

5.1.8.1Koşular

Yöntemin adımları şöyledir: metin soldan sağa taranır, ardışık tekrarlar sayılır, her koşu için sayı ve karakter yan yana yazılır ve sonuç sıkıştırılmış metin olarak saklanır. Metin bir kez tarandığı için süre O(n)'dir.

15 karakterlik "AAAAABBBCCCCDDD" metni "5A3B4C3D" olur; 8 karakter, oran 8/15 ≈ 0,53. Uzun koşular varsa kazanç büyüktür: 1000 tane a'dan oluşan bir metin "1000a" olur, yani 5 karaktere iner.

Tekrar az ise RLE işe yaramaz, hatta zararlıdır. "ABCD"de her koşu tek karakterliktir ve sonuç "1A1B1C1D" olur: 4 karakter 8'e çıkar, oran 2'dir. Güvercin yuvası teoreminin öngördüğü gibi RLE, koşu içermeyen girdileri büyütür. "abababab" gibi tekrarlı ama ardışık tekrarı olmayan bir girdi de "1a1b1a1b1a1b1a1b" olur; 8 karakter 16'ya çıkar. RLE bu tür tekrarı göremez.

RLE'nin doğal kullanım alanları, uzun düz bölgeler içeren verilerdir. Faks makineleri siyah-beyaz sayfaların satırlarını RLE ile kodlar; bir satırın çoğu beyazdır. BMP, PCX ve TIFF gibi eski resim biçimleri ve basit simgeler de RLE kullanır.

5.1.8.2Java kodu ve izleme

String rleSikistir(String s) {
  StringBuilder sonuc = new StringBuilder();
  int n = s.length();
  for (int i = 0; i < n; i++) {
    char c = s.charAt(i);
    int sayac = 1;
    while (i + 1 < n &&
      s.charAt(i + 1) == c) {
      sayac++;
      i++;
    }
    sonuc.append(sayac).append(c);
  }
  return sonuc.toString();
}

• Dış döngü: i her yeni koşunun ilk karakterinde durur. c bu karakterdir ve sayac 1'den başlar.
• İç döngü: bir sonraki karakter c ile aynı olduğu sürece sayac ve i birlikte artar. i + 1 < n koşulu önce denetlenir; metnin sonunda charAt dizinin dışına çıkmaz.
• Yazma: iç döngü bittiğinde i koşunun son karakterindedir. Sayı ve karakter sonuca eklenir. Dış döngünün i++'ı i'yi bir sonraki koşunun başına taşır.

İç döngü i'yi de artırdığı için kod iç içe döngüye rağmen doğrusaldır: her karakter bir kez ya dış döngüde ya da iç döngüde ziyaret edilir. Toplam süre O(n)'dir. Sonuç StringBuilder ile kurulur; String birleştirmesi her eklemede yeni bir nesne yaratır ve O(n²) süreye yol açabilirdi.

5.1.8.3Açma ve çok basamaklı sayılar

RLE'nin açılması sıkıştırmanın tersidir: her (sayı, karakter) çifti için karakter sayı kadar yazılır. Metin biçimindeki RLE'de tek bir incelik vardır: sayılar birden çok basamaklı olabilir. "12A3B" çözülürken "1" tek başına okunursa çıktı “bir tane 2” gibi anlamsız bir şeye döner. Doğru okuma, rakamları bir harf gelene kadar biriktirip tek bir sayı oluşturmaktır.

String rleAc(String s) {
  StringBuilder sonuc = new StringBuilder();
  int sayi = 0;
  for (char c : s.toCharArray()) {
    if (Character.isDigit(c)) {
      sayi = sayi * 10 + (c - '0');
    } else {
      for (int k = 0; k < sayi; k++)
        sonuc.append(c);
      sayi = 0;
    }
  }
  return sonuc.toString();
}

Kodda sayi, o ana kadar okunan rakamlardan oluşan sayıdır. Her rakam geldiğinde onluk sistemdeki gibi eski değer 10 ile çarpılıp rakam eklenir: "12" için önce 1, sonra 1 · 10 + 2 = 12. Harf gelince harf sayi kez yazılır ve sayi sıfırlanır. Kod Java ile denenmiştir: rleAc("12A3B1C") on iki A, üç B ve bir C üretir; rleAc("5A3B4C3D") özgün metni geri verir. Süre, çıktının uzunluğuyla doğrusaldır.

Bu yöntemin bir sınırı vardır: metnin kendisinde rakam varsa sayılarla karakterler karışır. "3" karakterinin 12 kez tekrarı "123" olarak yazılırdı ve "123 tane ne?" sorusu yanıtsız kalırdı. Bayt düzeyinde RLE bu sorunu sayıları ayrı baytlarda tutarak çözer.

5.1.8.4Bayt düzeyinde RLE ve bayrak baytı

Gerçek dosyalarda RLE baytlar üzerinde çalışır. En basit biçimde her koşu iki baytla yazılır: önce sayı, sonra karakterin kodu. Sayı tek bayta sığmalıdır; 255'ten uzun koşular birden çok koşuya bölünür. Bu biçim, rakam sorununu ortadan kaldırır, ama tekrarsız bölgelerde her karakteri iki bayta çıkarır.

Bayraklı RLE bu kaybı azaltır. Yalnız uzun koşular özel bir bayrak baytıyla başlayan üç baytlık bir grupla yazılır: bayrak, sayı, karakter. Kısa koşulardaki karakterler olduğu gibi bırakılır. Açıcı bir bayrak baytı görünce sonraki iki baytı sayı ve karakter olarak okur; başka bir bayt görünce onu doğrudan çıktıya yazar.

Bayrak baytının değeri metinde de geçebilir. 255 değerli bir karakter doğrudan yazılsaydı açıcı onu bayrak sanardı. Bu yüzden bu karakter de bir kaçış (escape) biçimiyle, örneğin 255 1 255 üçlüsüyle yazılmalıdır. Koşunun kaç karakterden itibaren “uzun” sayılacağı da bir tasarım kararıdır. Üç baytlık grup ancak dört ve daha uzun koşularda kazanç sağlar. Üç karakterlik koşuda iki yazım aynı uzunluktadır; iki karakterlik koşuyu olduğu gibi yazmak daha kısadır.

5.1.8.5Görüntülerde RLE

RLE'nin en etkili olduğu yer, büyük düz alanlar içeren görüntülerdir. Siyah-beyaz bir görüntüde her satır soldan sağa taranır ve renk değişene kadar aynı renkteki pikseller sayılır.

Şekil 5.1.22'deki 42 piksellik görüntü 18 koşuyla yazılır. Satırlar ayrı ayrı kodlanır; ilk satır "W1B1W3B1W1" olur ve beş koşudan oluşur. Her satırın koşu uzunlukları toplamı 7'dir. Bu bir denetim olanağı sağlar: açıcı her satırda 7 piksel üretmezse veri bozuktur.

Yalnız iki renk olduğu için renk adı bile yazılmayabilir. Koşuların dönüşümlü olarak beyaz ve siyah olduğu kabul edilir; satır siyahla başlıyorsa ilk beyaz koşu 0 uzunluklu yazılır. Faks standardı bu fikri kullanır ve koşu uzunluklarını ayrıca değişken uzunluklu kodlarla sıkıştırır. Büyük düz alanlı görüntülerde (çizimler, metin taramaları) RLE çok etkilidir. Fotoğraflarda ise komşu pikseller nadiren tam olarak aynı renktedir ve RLE etkisiz kalır.

Renkli görüntülerde koşular piksel düzeyinde tanımlanır. Her pikselin rengi üç baytlık bir (R, G, B) üçlüsüdür ve bir koşu, aynı renkteki ardışık piksellerden oluşur.

5.1.9Lempel-Ziv-Welch (LZW)

RLE yalnız ardışık tekrarı görür. Doğal dil metninde ise tekrarlar çoğunlukla ardışık değildir: "ve", "bir", "için" gibi kelimeler ya da "-ler", "-dır" gibi ekler metnin her yerine dağılmıştır. LZW bu tür tekrarı yakalar.

5.1.9.1Sözlük fikri

Abraham Lempel ve Jacob Ziv 1977 ve 1978'de sözlük tabanlı iki sıkıştırma yöntemi yayımladı (LZ77 ve LZ78). Terry Welch 1984'te LZ78'i sadeleştirdi ve donanımda hızla çalışacak bir biçime getirdi. Ortaya çıkan yöntem LZW adını aldı ve GIF, TIFF, PDF biçimlerinde ve Unix'in compress programında kullanıldı.

Yöntemin özü şudur: sıkıştırıcı daha önce gördüğü dizgileri bir sözlükte numaralandırır. Aynı dizgiyle yeniden karşılaşınca dizginin kendisi yerine sözlükteki numarasını, yani kodunu yazar. Sözlük dinamiktir: sıkıştırma ilerledikçe büyür. Sözlük çıktıyla birlikte gönderilmez. Açıcı aynı sözlüğü, sıkıştırıcıyla aynı kuralları uygulayarak kendisi yeniden kurar.

Kural bir açgözlülük içerir: sıkıştırıcı her adımda sözlükte bulunan en uzun parçayı yazar. Ardından bu parçanın bir karakter uzatılmış hâlini sözlüğe ekler. Böylece sözlükteki dizgiler zamanla uzar. Sık tekrar eden parçalar giderek daha uzun sözlük girdileriyle ve tek bir kodla yazılır.

5.1.9.2Sıkıştırma: Java kodu ve izleme

List<Integer> lzw(String s) {
  Map<String, Integer> sozluk =
      ilkSozluk(s);  // A=0, B=1, C=2
  String w = "";
  List<Integer> kod = new ArrayList<>();
  for (char c : s.toCharArray()) {
    String wc = w + c;
    if (sozluk.containsKey(wc)) {
      w = wc;
    } else {
      kod.add(sozluk.get(w));
      sozluk.put(wc, sozluk.size());
      w = "" + c;
    }
  }
  if (!w.isEmpty())
    kod.add(sozluk.get(w));
  return kod;
}

• Sözlük: Map<String, Integer>, her dizgiyi koduna eşler. ilkSozluk(s) metindeki farklı karakterleri 0'dan başlayarak numaralandırır; bu örnekte A = 0, B = 1, C = 2.
• Uzatma: wc = w + c sözlükteyse yalnız w uzar; çıktı yazılmaz.
• Yazma ve ekleme: wc sözlükte yoksa w'nin kodu yazılır. wc, sozluk.size() koduyla eklenir; bu, her zaman bir sonraki boş koddur. w yalnız c'den oluşan dizgiye döner.
• Son w: döngü bittiğinde w'de henüz yazılmamış bir parça kalır ve kodu eklenir.

Kod lzw("ABABCABABCA") çağrısıyla izlenecek. Tablo 5.1.16 her karakterden sonraki durumu verir.

Çıktı 0 1 3 2 3 5 0'dır: 11 sembol yerine 7 kod. 10. adım sözlüğün nasıl işe yaradığını gösterir. 5. adımda eklenen "ABC", metnin ikinci yarısında yeniden görülür ve tek bir kodla (5) yazılır. Sözlük bu kadar kısa bir metinde ancak birkaç kez kullanılabilir. Uzun metinlerde sözlükteki dizgiler uzar ve kazanç artar.

Sürenin hesabı şöyledir: her karakter için bir sözlük araması ve en çok bir ekleme yapılır. Sözlük hash tablosuyla tutulursa her işlem ortalama O(1) beklenir ve toplam süre O(n)'dir. Bu hesapta bir incelik vardır: w + c dizgisi her adımda yeniden oluşturulur ve hash'i hesaplanır; maliyeti w'nin uzunluğuyla orantılıdır. Pratik uygulamalar bu yüzden sözlüğü bir trie olarak tutar ya da her girdiyi (önek kodu, son karakter) çiftiyle saklar. Böylece her adım gerçekten sabit süre alır.

5.1.9.3Açma

Açıcı yalnız başlangıç sözlüğünü bilir. Sözlüğün geri kalanını, kodları okurken sıkıştırıcıyla aynı sırada kendisi kurar. Kural şudur: her yeni k kodu için e = sözlük[k] çıktıya yazılır, sözlüğe w + e[0] eklenir ve w ← e yapılır. e[0], e'nin ilk karakteridir.

Eklenen dizginin neden w + e[0] olduğu sıkıştırıcının davranışından anlaşılır. Sıkıştırıcı w'yi yazdığında sözlüğe w + c'yi eklemişti; c, bir sonraki parçanın ilk karakteriydi. Açıcı w'yi çözdüğü anda bir sonraki parçayı henüz bilmez. Bir sonraki kodu çözünce parçanın ilk karakterini öğrenir ve eksik girdiyi tamamlar. Açıcı bu yüzden sözlükte hep bir adım geride kalır.

Çıktılar art arda yazılınca A·B·AB·C·AB·ABC·A = ABABCABABCA elde edilir; özgün metin geri gelmiştir. Açıcının kurduğu 3–8 kodları, sıkıştırıcınınkilerle birebir aynıdır.

Bir durumda bu kural tıkanır. Açıcı, sözlüğünde henüz bulunmayan bir kod okuyabilir. Bu ancak tek bir biçimde olur: kod, açıcının bir sonra ekleyeceği koddur.

Bu durum, sıkıştırıcının bir girdiyi ekledikten hemen sonra kullandığı zaman ortaya çıkar. Bunun için metinde c · S · c · S · c biçiminde bir parça bulunmalı ve cS sözlükte olmalıdır. Burada c bir karakter, S bir dizgidir. Bu yüzden kaynaklarda “cScSc durumu” diye anılır.

5.1.9.4Örnek: DNA dizisi

LZW alfabeye bağlı değildir. DNA dizilerinde başlangıç sözlüğü dört nükleotittir: A = 0, T = 1, G = 2, C = 3. Metin "ATGATCATGAG" (11 sembol) olsun.

Çıktı 0 1 2 4 3 4 6 2'dir: 11 sembol yerine 8 kod. "AT" ikinci ve üçüncü kez görüldüğünde tek kodla (4) yazılır; "GA" da ikinci kez görüldüğünde tek kodla (6) yazılır. Döngüden sonra kalan w = G'nin kodu (2) en sona eklenir. Gerçek genomlarda tekrar eden diziler çok uzun olduğu için sözlük girdileri de uzar.

5.1.9.5ASCII sözlük ve özel durum

Pratikte başlangıç sözlüğü 256 ASCII karakterinin hepsidir; metinde hangi karakterlerin geçtiğine bakılmaz. Örneğin a = 97, b = 98, c = 99'dur. Yeni dizgiler 256'dan itibaren numaralanır. Böylece başlangıç sözlüğünü gönderme gereği de ortadan kalkar.

Metin 9 koda iner: 97 97 98 256 99 257 261 99 98. Tablonun altıncı ve yedinci satırları özel durumu içerir. "ab" (257) yazılırken sözlüğe 261 = "aba" eklenir. Bir sonraki parça tam olarak "aba"dır ve 261 hemen kullanılır. Açıcı 261'i okuduğunda sözlüğünde henüz 260'a kadar kod vardır.

Açma kodu, özel durumu tek bir koşullu ifadeyle ele alır:

String lzwAc(List<Integer> kod) {
  List<String> sozluk =
      ilkSozluk();      // 0..255: ASCII
  String w = sozluk.get(kod.get(0));
  StringBuilder s = new StringBuilder(w);
  for (int i = 1; i < kod.size(); i++) {
    int k = kod.get(i);
    String e = k < sozluk.size()
        ? sozluk.get(k)
        : w + w.charAt(0); // özel durum
    s.append(e);
    sozluk.add(w + e.charAt(0));
    w = e;
  }
  return s.toString();
}

• Başlangıç: sözlük 0–255 ASCII karakterleriyle dolar. İlk kod her zaman tek karakterdir; doğrudan çözülür ve çıktıya yazılır.
• Çözme: k < sozluk.size() ise kod tanımlıdır ve e = sozluk.get(k). Değilse özel durumdur ve e = w + w.charAt(0).
• Ekleme: her adımda w + e.charAt(0) sözlüğün sonuna eklenir; List yapısında yeni girdinin kodu kendiliğinden bir sonraki indistir.

Kod Java ile çalıştırılmış ve "aabaacababacb" çıktısı doğrulanmıştır. Açmanın süresi çıktının uzunluğuyla doğrusaldır.

5.1.9.6Sözlük büyüklüğü ve kod genişliği

Kodların kaç bitle yazılacağı sözlüğün büyüklüğüne bağlıdır. 256 ASCII karakteri 8 bitle yazılabilir. Sözlüğe yeni girdiler eklendiğinde kodlar 8 bite sığmaz. Bu yüzden LZW uygulamaları 9 bitlik kodlarla başlar ve sözlük 512, 1024… sınırlarını geçtikçe kod genişliğini birer bit artırır.

Bu hesap, kod sayısındaki azalmanın neden doğrudan bit kazancı olmadığını gösterir. ASCII örneğinde metin 13 bayt, yani 104 bittir. 9 kod 9'ar bitle 9 · 9 = 81 bit tutar; oran 81/104 ≈ 0,78'dir. "ABABCABABCA" örneği ASCII ile kodlansaydı 11 bayt (88 bit) yerine 7 kod (63 bit) yazılırdı. Kısa metinlerde kazanç küçüktür. Uzun ve tekrarlı metinlerde tek bir kod onlarca karakterin yerini tutar ve kazanç büyür.

Sözlük büyüdükçe iki sorun çıkar: kod genişliği (bit sayısı) artar ve sözlüğün kapladığı bellek büyür. Pratikte sözlük sınırlandırılır. GIF'te en büyük kod genişliği 12 bittir; sözlük en çok 2¹² = 4096 girdi tutar. Sözlük dolunca ya donar (yeni girdi eklenmez) ya da sıfırlanıp yeniden kurulur. Sıfırlama, metnin içeriği değiştiğinde (örneğin bir dosyanın metin bölümünden sayısal bölümüne geçildiğinde) eski girdilerin yer kaplamasını önler.

5.1.9.7LZ78: LZW'nin atası

LZW'nin dayandığı LZ78 yönteminde sözlük boş başlar. Çıktı kodlardan değil (indis, karakter) çiftlerinden oluşur: sözlükteki en uzun eşleşmenin indisi (eşleşme yoksa 0) ve onu izleyen karakter. Her çift aynı zamanda sözlüğe yeni bir girdi ekler.

List<String> lz78(String s) {
  Map<String, Integer> sozluk =
      new HashMap<>();
  List<String> cikti = new ArrayList<>();
  String w = "";
  for (char c : s.toCharArray()) {
    if (sozluk.containsKey(w + c)) {
      w = w + c;               // uzat
    } else {
      int k = w.isEmpty() ? 0
                          : sozluk.get(w);
      cikti.add("(" + k + ", " + c + ")");
      sozluk.put(w + c, sozluk.size() + 1);
      w = "";
    }
  }
  if (!w.isEmpty())        // son parça
    cikti.add("(" + sozluk.get(w) + ")");
  return cikti;
}

Kod LZW koduna çok benzer. Farklar şunlardır: w + c sözlükte yoksa hem w'nin indisi hem de c karakteri yazılır; ardından w boş dizgiye döner. İndisler 1'den başlar, çünkü 0 boş önek için ayrılmıştır. Metin bittiğinde w'de yazılmamış bir parça kalabilir; bu parça sözlükte vardır ve döngüden sonra yalnız indisiyle yazılır. Örneğin "aabaacababacb" metninde son b, sözlükte 6 numaralı girdidir ve çıktının sonuna "(6)" eklenir. Bu satır unutulursa metnin sonu kaybolur. Tablodaki örnekte metin bir çiftle tam biter, w boş kalır ve son satır çalışmaz.

Metin 6 çifte dönüşür: (0, a) (1, b) (1, a) (0, c) (2, c) (5, b). Parçalar a, ab, aa, c, abc ve abcb'dir; her parça, sözlükteki bir parçanın bir karakter uzatılmış hâlidir.

Welch'in değişikliği tek bir fikirden ibarettir: sözlüğü bütün tek karakterlerle başlatmak. LZ78'de bir karakter ilk kez görüldüğünde (0, c) çifti gerekir, çünkü sözlükte yoktur. LZW'de her tek karakter baştan sözlüktedir. Bu yüzden çıktıda karakter yazmaya gerek kalmaz; yalnız kodlar yazılır ve her kodun ardından gelen karakter, bir sonraki kodun ilk karakterinden çıkarılır.

Lempel ve Ziv'in 1977 tarihli öbür yöntemi LZ77 ise sözlük tutmaz. Onun yerine son birkaç kilobaytlık bir kayan pencerede geriye bakar ve tekrarları (geri uzaklık, uzunluk) çiftleriyle yazar. LZ77 ailesi, ZIP ve gzip'in kullandığı DEFLATE biçiminin ve PNG resimlerinin temelidir.

5.1.9.8RLE ile LZW'nin karşılaştırması

İki yöntem de kayıpsızdır ve ikisi de doğrusal sürede çalışır. Seçimi verinin yapısı belirler. Uzun düz alanlı görüntülerde RLE basitliğiyle öne çıkar. Doğal dil metninde ya da programlarda ardışık tekrar azdır, ama tekrar eden kelimeler ve kalıplar boldur; burada LZW çok daha etkilidir. Güvercin yuvası teoremi ikisinin de bazı girdileri büyüteceğini söyler: RLE için "abababab", LZW için kısa ve rastgele veriler bu türdendir.

5.1.10Sık yapılan hatalar

Bölüm boyunca anılan hatalar burada bir arada toplanmıştır. Hepsi küçük bir kod ayrıntısından doğar, ama ya yanlış sonuç ya da sonsuz döngü üretir.

• Döngü sınırı. Kaba kuvvette i < n - m yazmak son kaymayı (s = n − m) atlar. Doğrusu i <= n - m'dir. Örüntü metnin en sonunda geçiyorsa bulunamaz.
• LPS'yi yanlış tanımlamak. Örüntünün kendisi sayılmaz: lps("aaaa") = [0, 1, 2, 3]'tür, [1, 2, 3, 4] değildir. KMP'de uyuşmazlıkta lps[q - 1] kullanılır, lps[q] değil.
• Negatif kaydırma. Boyer-Moore'da j − son[c] negatif olabilir; c'nin son geçişi j'nin sağındadır. max(1, …) unutulursa örüntü geri gider ya da algoritma sonsuz döngüye girer.
• Horspool tablosuna son karakteri katmak. Son karakter tabloya girerse onun kaydırması 0 olur ve örüntü yerinde sayar. Tablo yalnız P[0..m−2]'den kurulur.
• Hash eşitliğine güvenmek. Rabin-Karp'ta hash eşitliği eşleşme demek değildir; aday pencere karakter karakter doğrulanmalıdır. Java'da % negatif sonuç verebilir: if (th < 0) th += Q; satırı gerekir. Büyük Q ile int taşar; long kullanılmalıdır.
• RLE'de çok basamaklı sayılar. "12A" çözülürken sayıyı tek rakam okumak hatalıdır (bir tane '2' mi?). Rakamlar bir harf gelene kadar biriktirilmeli ya da sayılar ayrı baytlarda yazılmalıdır.
• LZW'de son w ve özel durum. Döngüden sonra kalan w'nin kodunu yazmayı unutmak metnin sonunu kaybettirir; aynı satır LZ78'de de gereklidir. Açarken henüz tanımlanmamış kodu (w + w[0]) ele almamak cScSc biçimli metinlerde çökmeye yol açar.
• Karşılaştırma sayısını yanlış saymak. Bir hizadaki uyuşmazlık da bir karşılaştırmadır. Kaba kuvvette her hiza en az bir karşılaştırma yapar; toplam en az n − m + 1'dir.

5.1.11Özet

• Dizgi eşleştirme, m uzunluklu bir P örüntüsünün n uzunluklu bir T metni içinde geçtiği bütün kaymaları bulma problemidir. Olası kaymalar 0 ≤ s ≤ n − m'dir.
• Kaba kuvvet her kaymayı soldan sağa dener. Ön işlemesi ve ek belleği yoktur. Ortalama durumda O(n), en kötü durumda (n − m + 1) · m karşılaştırmayla O(n · m)'dir. Kusuru, uyuşmazlıkta öğrenilen bilgiyi atmasıdır.
• KMP, lps[q] = P[0..q]'nun en uzun uygun önek-sonek uzunluğu tablosunu O(m)'de kurar. Uyuşmazlıkta q = lps[q − 1] yapılır ve metin işaretçisi geri gitmez. En kötü durumda bile O(n + m)'dir; amortize argüman en çok 2n karşılaştırma verir.
• Boyer-Moore sağdan sola karşılaştırır ve s += max(1, j − son[c]) (kötü karakter) ile iyi sonek kuralının büyüğü kadar kaydırır. En iyi durumda O(n/m)'dir, pratikte en hızlısıdır. Horspool, kaydırmayı hizanın son karakterine göre yapan tek tablolu sadeleştirmedir.
• Rabin-Karp, polinom kayan hash'i O(1)'de günceller. Hash eşitse pencere doğrulanır. Beklenen süre O(n + m), en kötü süre O(n · m)'dir. Aynı uzunlukta çok sayıda örüntüyü tek geçişte arayabilir.
• Hiçbir kayıpsız sıkıştırma yöntemi her girdiyi küçültemez (güvercin yuvası ilkesi). Sıkıştırma oranı, sıkıştırılmış boyutun orijinal boyuta oranıdır.
• RLE her koşuyu (sayı, sembol) çiftiyle yazar ve O(n) sürer. Tekrar yoksa veriyi iki katına çıkarır; bayrak baytı bu kaybı azaltır. Düz alanlı görüntülerde etkilidir.
• LZW'de w + c sözlükteyse w uzatılır; değilse w'nin kodu yazılır ve w + c sözlüğe eklenir. Açıcı sözlüğü kendisi kurar ve bir adım geride kalır. Tanımsız kod okununca e = w + w[0]'dır. LZ78'in farkı, sözlüğün boş başlaması ve (indis, karakter) çiftleri yazmasıdır.

5.1.12Kavram listesi

• dizgi string
• alfabe alphabet
• alt dizgi substring
• örüntü pattern
• dizgi eşleştirme string matching
• önek prefix
• sonek suffix
• kaba kuvvet brute force (naive)
• Knuth-Morris-Pratt (KMP) Knuth-Morris-Pratt
• LPS tablosu LPS table
• amortize analiz amortized analysis
• Boyer-Moore algoritması Boyer-Moore algorithm
• kötü karakter kuralı bad character rule
• iyi sonek kuralı good suffix rule
• Rabin-Karp algoritması Rabin-Karp algorithm
• kayan hash rolling hash
• sıkıştırma compression
• sıralı sıkıştırma kodlaması (RLE) run-length encoding
• Lempel-Ziv-Welch (LZW) Lempel-Ziv-Welch

Sözlükte ayrıca yer almayan, notta tanımlanan terimler: kayma (shift), uygun önek (proper prefix), son görülme tablosu, Horspool kaydırma tablosu, sahte eşleşme (spurious hit), polinom hash, kayıpsız ve kayıplı sıkıştırma, sıkıştırma oranı, koşu (run), bayrak baytı, LZ78.

5.1.13Kendini Dene

1. "abaabab" örüntüsünün LPS tablosu nedir?

   Cevap

   [0, 0, 1, 1, 2, 3, 2]. q = 3'te "abaa"nın en uzun önek-sonek parçası "a"dır. q = 5'te "abaaba" için "aba" (3) bulunur. q = 6'da "abaa" ile "abab" uyuşmaz; k = lps[2] = 1'e çekilir ve "ab" (2) bulunur.

2. kabaKuvvet("aaaab", "ab") hangi değeri döndürür ve kaç karşılaştırma yapar? Yalnız kötü karakter kuralıyla Boyer-Moore kaç karşılaştırma yapar?

   Cevap

   3 döner. Kaba kuvvet s = 0, 1, 2'de a eşleşir ve b uyuşmaz (3 × 2 = 6), s = 3'te iki karakter eşleşir (2): toplam 8. Boyer-Moore her hizada sağ uçtaki b'yi metindeki a ile karşılaştırır; son[a] = 0 olduğundan 1 kayar. s = 0, 1, 2'de 1'er, s = 3'te 2 karşılaştırma: toplam 5.

3. "aabaab" örüntüsü için KMP aramasında "aabaa" eşleşmişken (q = 5) sıradaki metin karakteri b değil. q hangi değeri alır, örüntü kaç konum kaymış olur?

   Cevap

   LPS tablosu [0, 1, 0, 1, 2, 3]'tür. q = lps[4] = 2: "aabaa"nın sonundaki "aa" aynı zamanda önektir. Kayma 5 − 2 = 3'tür. Ardından aynı metin karakteri P[2] = b ile karşılaştırılır; o da uyuşmazsa q = lps[1] = 1 olur.

4. "ANANAS" örüntüsünün son görülme tablosu nedir? "BANANAS ANANAS" metninde yalnız kötü karakter kuralıyla ilk kaydırma kaç olur?

   Cevap

   son[A] = 4, son[N] = 3, son[S] = 5, diğerleri −1. s = 0'da P[5] = S ile T[5] = A uyuşmaz; kaydırma max(1, 5 − 4) = 1. s = 1'de altı karakter eşleşir: toplam 7 karşılaştırma.

5. "ANANAS" için Horspool kaydırma tablosu nedir? Hizanın son karakterinin altına S gelirse örüntü kaç kayar?

   Cevap

   Tabloya yalnız P[0..4] = ANANA katılır: A → 5 − 4 = 1, N → 5 − 3 = 2, diğer → 6. S yalnız son konumda geçtiği için tabloda yoktur ve 6 kaydırır.

6. B = 10, Q = 7, karakterler rakam. "27182818" metninde "18" aranıyor. Hangi pencereler aday olur, hangileri sahte eşleşmedir?

   Cevap

   h("18") = 18 mod 7 = 4. Pencere hash'leri: 27 → 6, 71 → 1, 18 → 4, 82 → 5, 28 → 0, 81 → 4, 18 → 4. Adaylar s = 2, 5, 6'dır. s = 5'teki "81" sahte eşleşmedir; s = 2 ve s = 6 gerçek geçişlerdir.

7. "WWWWWWWWWWWWBWWW" (16 karakter) metni karakter RLE'siyle nasıl yazılır? Bayt düzeyinde bayraksız ve bayraklı (dört ve daha uzun koşular bayrakla) biçimler kaç bayt tutar?

   Cevap

   "12W1B3W": 7 karakter, oran 7/16 ≈ 0,44. Bayraksız: 3 koşu × 2 = 6 bayt. Bayraklı: 12 W için 3 bayt, B ve üç W olduğu gibi 4 bayt: 7 bayt. Bu girdide tekrarsız bölge olmadığı için bayraksız biçim daha kısadır.

8. A = 0 sözlüğüyle "AAAAAAA" (7 tane A) LZW ile sıkıştırılırsa hangi kodlar çıkar? Açıcı bu kodları çözerken kaç kez özel durumla karşılaşır?

   Cevap

   Çıktı 0 1 2 0; sözlüğe 1 = AA, 2 = AAA, 3 = AAAA eklenir. Açarken 0 → A. 1 tanımsızdır: e = A + A = AA. 2 de tanımsızdır: e = AA + A = AAA. 0 → A. Özel durum iki kez çıkar; çıktı A·AA·AAA·A = 7 A.

9. LZ78, on tane a'dan oluşan "aaaaaaaaaa" dizgisini hangi çiftlere dönüştürür?

   Cevap

   (0, a) (1, a) (2, a) (3, a). Parçalar a, aa, aaa, aaaa'dır; uzunlukları 1 + 2 + 3 + 4 = 10. Parça uzunlukları her adımda bir arttığı için n uzunluklu bir koşu yaklaşık √(2n) çiftle yazılır.

10. Bir milyon karakterlik bir metinde, metinde hiç geçmeyen karakterlerden oluşan 10 harflik bir örüntü aranıyor. Boyer-Moore yaklaşık kaç karşılaştırma yapar? Kaba kuvvet ve KMP en az kaç karşılaştırma yapar?

    Cevap

    Boyer-Moore'da her hizada sağ uçtaki karakter uyuşmaz ve örüntü 10 konum atlar: yaklaşık n/m = 10⁵ karşılaştırma. Kaba kuvvet ve KMP her metin karakterine en az bir kez bakar: yaklaşık 10⁶ karşılaştırma. Bu en iyi durumda Boyer-Moore on kat daha az iş yapar.

5.1.14İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 32: Rabin-Karp'ı, sonlu otomatla eşleştirmeyi ve KMP'nin önek fonksiyonunu kanıtlarıyla verir; sonek dizilerine de değinir.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 5.3 ve 5.5: KMP'nin otomat sürümünü, Boyer-Moore ve Rabin-Karp'ın Java kodlarını, RLE, Huffman ve LZW sıkıştırmasını anlatır.
• D. Gusfield, Algorithms on Strings, Trees, and Sequences (1997): iyi sonek tablosunun O(m) sürede kurulmasını, Z algoritmasını ve biyoinformatik uygulamalarını ayrıntılı ele alır.
• K. Sayood, Introduction to Data Compression (5. baskı, 2017): sözlük tabanlı yöntemleri (LZ77, LZ78, LZW) ve kayıpsız sıkıştırmanın bilgi kuramsal sınırlarını anlatır.

5.1.15Kaynaklar

1. R. S. Boyer, J S. Moore, “A Fast String Searching Algorithm”, Communications of the ACM 20(10), 1977.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 32: String Matching).
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014 (Bölüm 13).
4. R. N. Horspool, “Practical Fast Searching in Strings”, Software: Practice and Experience 10(6), 1980.
5. R. M. Karp, M. O. Rabin, “Efficient Randomized Pattern-Matching Algorithms”, IBM Journal of Research and Development 31(2), 1987.
6. D. E. Knuth, J. H. Morris, V. R. Pratt, “Fast Pattern Matching in Strings”, SIAM Journal on Computing 6(2), 1977.
7. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Kesim 5.3: Substring Search, 5.5: Data Compression).
8. T. A. Welch, “A Technique for High-Performance Data Compression”, IEEE Computer 17(6), 1984.
9. J. Ziv, A. Lempel, “Compression of Individual Sequences via Variable-Rate Coding”, IEEE Transactions on Information Theory 24(5), 1978.

İlgili sayfalar: Bölüm 5.1 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.