Bölüm 5.2: Dizgi Algoritmaları (2)

5.2.1Dört problem ailesi

Bir dizgi (string), belirli bir alfabeden alınmış karakterlerin sonlu dizisidir. Alfabe (alphabet) kullanılabilecek karakterlerin kümesidir ve Σ ile gösterilir. İkili dizgilerde Σ = {0, 1}'dir, DNA dizilerinde Σ = {A, C, G, T}'dir. Java'da ise bir String içindeki her karakter 16 bitlik bir char değeridir. Alfabenin boyu R ile gösterilir: ASCII için R = 128 ya da genişletilmiş biçimiyle R = 256'dır.

Dizgiler üzerine kurulan problemler çok çeşitlidir; ama çoğu dört aileden birine girer. Bu ailelerin her biri farklı bir soruya cevap verir ve farklı bir algoritma tekniği kullanır.

Sıralama ailesinde dizgiler sözlükteki gibi dizilir. Dizgileri karakter karakter karşılaştıran yöntemler genel amaçlıdır. Basamak sıralaması ise hiç karşılaştırma yapmaz; her karakteri bir basamak gibi kullanıp dizgileri gruplara dağıtır. Ayrıştırma ailesinde bir arama örüntüsü düzenli ifadeyle yazılır ve bu ifadeyi tanıyan bir sonlu durum makinesi girdiyi karakter karakter okur. Benzerlik ailesinde iki dizgi arasındaki fark bir sayıyla ölçülür. En bilineni, bir dizgiyi ötekine çeviren en az tek karakterlik düzenleme sayısı olan Levenshtein uzaklığıdır. Dönüşüm ailesinde dizgi yeniden düzenlenir: sonek dizisi bütün sonekleri sıralı tutarak aramayı hızlandırır, Burrows–Wheeler dönüşümü ise aynı harfleri bir araya toplayarak sıkıştırmaya hazırlık yapar.

Dört ailenin ortak bir noktası vardır: hepsi dizginin bir yapısını kullanır. Sözlüksel sıra, karakterlerin soldan sağa önemini kullanır. Sonlu durum makinesi, girdinin şimdiye kadar okunan kısmını tek bir durumla özetler. Levenshtein uzaklığı, iki dizginin önekleri arasındaki uzaklıklardan kurulur. Sonek dizisi ve BWT ise dizginin bütün sonekleri ya da döndürmeleri sıralandığında ortaya çıkan düzene dayanır. Notta önek, sonek ve alt dizgi terimleri sık geçer. Önek (prefix) dizginin başından, sonek (suffix) sonundan alınan parçadır. Alt dizgi (substring) ardışık karakterlerden oluşan herhangi bir parçadır. Örneğin “banana” için “ban” bir önek, “ana” bir sonek, “nan” bir alt dizgidir.

5.2.2Sözlüksel sıra

Bir sözlükte kelimeler belirli bir düzende dizilir: “armut”, “elma”dan önce gelir, “elma” da “elmas”tan önce. Bu düzenin kuralı basittir ve bilgisayarda da aynen kullanılır. Tek fark, bilgisayarın harflerin sırasını bir alfabe ezberinden değil, karakter kodlarından öğrenmesidir.

5.2.2.1Karşılaştırma kuralı

Kural karşılaştırmayı ilk karakterlerle başlatır. İlk karakterler eşitse ikinci karakterlere, onlar da eşitse üçüncülere bakılır. İlk farklı karakter sonucu belirler ve sonraki karakterlere hiç bakılmaz. Bir dizgi tükenirse kısa olan önce gelir. Tablo 5.2.2 dört karşılaştırmada kararı neyin verdiğini gösterir.

Son satır ilk bakışta şaşırtıcıdır: bir insan “apple”ı “Zebra”dan önce yazar. Bilgisayar ise büyük Z'nin kodunu (90) küçük a'nın kodundan (97) küçük bulur ve harfin büyük ya da küçük olmasını ayrıca dikkate almaz.

Sözlüksel sıra bir tam sıradır: herhangi iki farklı dizgiden biri ötekinden küçüktür ve sıra geçişlidir. Bu yüzden dizgiler tam sayılar gibi sıralanabilir; sıralama algoritmalarının hepsi dizgilerle de çalışır. Yalnız bir karşılaştırmanın maliyeti artık sabit değildir. İki tam sayı tek işlemle karşılaştırılır. İki dizgi ise en kötü durumda kısa olanın uzunluğu kadar karakter karşılaştırması gerektirir.

5.2.2.2Kod izleme: apple ve apricot

Kuralı doğrudan uygulayan Java metodu aşağıdadır. Metot negatif bir sayı döndürürse a önce, pozitif bir sayı döndürürse b önce gelir; sıfır, iki dizginin eşit olduğunu gösterir. Java'nın String.compareTo metodu da aynı biçimde çalışır.

int karsilastir(String a, String b) {
  int n = Math.min(a.length(), b.length());
  for (int k = 0; k < n; k++) {
    char x = a.charAt(k), y = b.charAt(k);
    if (x != y)
      return x - y;   // ilk farklı karakter
  }
  return a.length() - b.length();
}

n, iki dizgiden kısa olanın uzunluğudur; döngü en fazla bu kadar karakter karşılaştırabilir. Döngünün her turunda iki dizginin k. karakterleri x ve y olarak okunur. Karakterler farklıysa x - y döndürülür. Java'da iki char çıkarıldığında karakter kodlarının farkı elde edilir; işaret, hangi karakterin önce geldiğini gösterir. Döngü bir fark bulmadan biterse kısa dizgi uzun olanın önekidir. Bu durumda a.length() - b.length() döner: kısa olan önce gelir, uzunluklar eşitse sonuç sıfırdır.

Sonuç negatif olduğu için “apple”, “apricot”tan önce gelir. Karşılaştırma üç karakterde bitti; “apple”ın son iki harfine ve “apricot”un son dört harfine hiç bakılmadı. Aynı metot başka girdilerle şu değerleri döndürür: karsilastir("car", "cart") için ilk üç karakter eşittir ve kısa dizgi tükenir; sonuç 3 − 4 = −1'dir. karsilastir("Zebra", "apple") ilk karakterde 90 − 97 = −7 döndürür. karsilastir("kale", "kaba") ise üçüncü karakterde 108 − 98 = 10 döndürür; pozitif sonuç “kaba”nın önce geldiğini gösterir.

Metodun maliyeti, ilk farklı karaktere kadar okunan karakter sayısıyla orantılıdır. En kötü durumda iki dizgi uzun bir ortak önek paylaşır ve maliyet O(min(|a|, |b|)) olur. Ek bellek kullanılmaz.

5.2.2.3Karakter kodları ve Türkçe

Bilgisayar için “alfabe”, karakter kodlarının oluşturduğu tablodur: ASCII ya da onu içine alan Unicode. Bu tabloda bütün büyük harfler (A = 65 … Z = 90) bütün küçük harflerden (a = 97 … z = 122) önce gelir. Rakamlar (0 = 48 … 9 = 57) ise harflerden de öncedir. Türkçeye özgü ç, ğ, ı, ö, ş, ü harflerinin kodları ASCII tablosunun dışındadır: örneğin ç = 231, ğ = 287, ı = 305, ş = 351'dir. Bu yüzden kod sırasıyla dizildiklerinde hepsi z'den sonra gelir.

Sonuç olarak compareTo ile yapılan sıralama Türkçe sözlük sırasından farklıdır. “şeker” ile “zeytin” karşılaştırıldığında 'ş' (351) 'z'den (122) büyük olduğu için “zeytin” önce gelir. Türkçe sözlükte ise ş, z'den öncedir. Benzer biçimde “Zebra” “apple”dan önce, “Çorum” ise “Zonguldak”tan sonra gelir. Türkçe sözlük sırası gerekiyorsa Java'nın java.text.Collator sınıfı Türkçe yerel ayarla (Collator.getInstance(new Locale("tr", "TR"))) kullanılır. Bu sınıf büyük/küçük harf farkını ve Türkçe harflerin alfabedeki yerini dikkate alır. Yalnız büyük/küçük harf farkını gidermek için compareToIgnoreCase da yeterlidir, ama bu metot Türkçe harflerin yerini düzeltmez.

5.2.2.4Kelimeler ve sayılar

Uzun ortak önekli iki kelimede karşılaştırma birkaç karakter sürebilir. Şekil 5.2.3 “EDUCATIVE” ile “EDUCATED” kelimelerini karşılaştırır. İlk altı harf (EDUCAT) eşittir. Yedinci harfte 'I' (73) ile 'E' (69) karşılaşır; 'E' daha küçük olduğu için “EDUCATED” önce gelir. Kelimelerin uzunluğu sonuca etki etmez: “EDUCATIVE” dokuz, “EDUCATED” sekiz harflidir, ama karar yedinci harfte verilmiştir.

Sayılar dizgi olarak saklandığında sözlüksel sıra, sayısal sıradan ayrılır. Karşılaştırma yine soldan sağa, karakter karakter yapılır. “11” ile “2” karşılaştırılırken ilk karakterler '1' ve '2'dir; '1' küçük olduğu için “11” önce gelir. Sayının kaç basamaklı olduğu hiç dikkate alınmaz. Şekil 5.2.4, 2 ile 29 arasındaki asal sayıları iki sırada gösterir.

Aynı nedenle “123”, “45”, “6”, “789” dizgileri sözlüksel olarak tam bu sıradadır: ilk karakterler 1 < 4 < 6 < 7'dir. Sayısal sıra isteniyorsa iki yol vardır. Birincisi, dizgiler tam sayıya çevrilip sayı olarak sıralanır. İkincisi, bütün sayılar soldan sıfırla aynı uzunluğa getirilir: “02” < “11” olur, çünkü artık ilk karakterler '0' ve '1'dir. Dosya adlarında “resim01, resim02, …, resim10” biçimi bu yüzden kullanılır.

5.2.2.5Karşılaştırmalı dizgi sıralama

Sözlüksel karşılaştırma elde olduğuna göre bilinen herhangi bir sıralama algoritması dizgilere uygulanabilir. Sunumdaki örnek en basit yöntemi kullanır: her konuma, geri kalan dizgilerin sözlüksel olarak en küçüğü takaslarla getirilir.

void sozlukselSirala(String[] a) {
  int n = a.length;
  for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++)
      if (a[i].compareTo(a[j]) > 0) {
        String gecici = a[i];
        a[i] = a[j];
        a[j] = gecici;
      }
}

Dış döngü i konumunu soldan sağa ilerletir. İç döngü i'den sonraki her j için a[i] ile a[j]'yi karşılaştırır. a[i].compareTo(a[j]) > 0 ise a[j] daha küçüktür ve iki öğe takas edilir. İç döngü bittiğinde i konumunda kalanların en küçüğü bulunur. Bu yöntem seçmeli sıralamaya benzer; farkı, en küçük öğeyi bir kez değil, her bulduğunda takas etmesidir. Tablo 5.2.4 kodun iki girdi üzerindeki çıktısını verir.

Maliyet iki çarpandan oluşur. İç içe iki döngü N(N − 1)/2 karşılaştırma yapar; bu O(N²)'dir. Her compareTo çağrısı ise en fazla W karakter okur; W en uzun dizginin uzunluğudur. Toplam zaman O(N² · W) olur. Takaslar yalnız başvuruları (referansları) değiştirir; dizgilerin karakterleri kopyalanmaz. Bu yüzden takas sabit zamanlıdır ve ek bellek O(1)'dir.

Daha iyi bir karşılaştırmalı sıralama, örneğin birleştirme sıralaması, O(N log N) karşılaştırma yapar. Dizgilerde bu, O(W · N log N) zaman demektir. Java'nın Arrays.sort(String[]) metodu da birleştirme sıralamasının bir türevini kullanır ve kararlıdır. Karşılaştırmaya dayanan her sıralama en kötü durumda en az Ω(N log N) karşılaştırma yapmak zorundadır. Bu alt sınırın nedeni, N! farklı olası sıranın her birini ayırt etmek için gereken evet/hayır sorusu sayısıdır: log₂(N!) ≈ N log₂ N. Basamak sıralaması ise karakterleri karşılaştırmaz, sayar. Bu yüzden alt sınır ona uygulanmaz.

Bir sayısal örnek farkı somutlaştırır. N = 10⁶ dizgi, her biri W = 10 karakter olsun. Birleştirme sıralaması yaklaşık N log₂ N ≈ 2 · 10⁷ karşılaştırma yapar; her karşılaştırma en çok 10 karakter okursa üst sınır 2 · 10⁸ karakter işlemidir. LSD basamak sıralaması ise W · (N + R) = 10 · (10⁶ + 256) ≈ 10⁷ adımda biter. Rakamlar yalnız büyüklük sırası verir; sabit çarpanlar ve önbellek davranışı gerçek süreyi değiştirir.

5.2.3Basamak sıralaması

Karşılaştırmalı sıralama iki dizgiyi her seferinde baştan karşılaştırır. Ortak önekleri uzun dizgilerde aynı karakterler defalarca okunur. Basamak sıralaması (radix sort) başka bir yol izler: dizgiyi karakter karakter ele alır ve her karakteri bir sayının basamağı gibi kullanır. Her geçişte dizgiler tek bir karakter konumuna göre kovalara dağıtılır. Dağıtma işi karşılaştırma değil sayma ile yapılır.

İki yön vardır. LSD (least significant digit, en anlamsız basamak) sağdan, yani son karakterden başlar ve sola doğru ilerler. MSD (most significant digit, en anlamlı basamak) soldan, ilk karakterden başlar ve her kovayı ayrı ayrı sıralar. İki yöntem de her geçişte aynı alt işlemi kullanır: tek bir karakter konumuna göre kararlı saymalı sıralama.

5.2.3.1Saymalı sıralama ve kararlılık

Saymalı sıralama (counting sort), anahtarları küçük tam sayılar olan öğeleri sıralar. Burada anahtar, dizginin d. karakteridir ve 0–255 arasında bir koddur. Yöntem üç adımdan oluşur: her anahtarın kaç kez geçtiği sayılır, sayılar önek toplamıyla konumlara çevrilir, öğeler bu konumlara yerleştirilir.

Sunumdaki LSD kodu üç metottan oluşur. radixSirala geçişleri yönetir, sayarakSirala tek bir karakter konumuna göre kararlı saymalı sıralamayı yapar, kar ise dizginin d. karakterini güvenli biçimde okur:

void radixSirala(String[] a) {
  int W = enUzun(a);               // en uzun dizgi
  for (int d = W - 1; d >= 0; d--)
    sayarakSirala(a, d);           // sağdan sola
}
void sayarakSirala(String[] a, int d) {
  int[] say = new int[256];        // ASCII
  for (String s : a) say[kar(s, d)]++;
  for (int r = 1; r < 256; r++) say[r] += say[r - 1];
  String[] gec = new String[a.length];
  for (int i = a.length - 1; i >= 0; i--)   // kararlı
    gec[--say[kar(a[i], d)]] = a[i];
  System.arraycopy(gec, 0, a, 0, a.length);
}
int kar(String s, int d) {         // kısa dizgi → 0
  return d < s.length() ? s.charAt(d) : 0;
}

sayarakSirala metodunun satırları sırayla şu işleri yapar.

1. Sayma. say dizisi 256 hücrelidir; her hücre bir karakter koduna karşılık gelir. for (String s : a) say[kar(s, d)]++; satırı, d. karakteri c olan dizgilerin sayısını say[c]'ye yazar.
2. Önek toplamı. say[r] += say[r - 1] döngüsünden sonra say[c], anahtarı c'ye eşit ya da ondan küçük olan dizgilerin toplam sayısıdır. Bu sayı, c kovasının çıktı dizisinde bittiği konumu gösterir: c kovası say[c − 1]'den başlar ve say[c] − 1'de biter.
3. Yerleştirme. Dizi sondan başa taranır. Her dizgi kendi kovasının son boş hücresine yazılır: gec[--say[kar(a[i], d)]] = a[i]. Önce sayaç bir azaltılır, sonra o konuma yazılır.
4. Geri kopyalama. System.arraycopy, sıralı gec dizisini a'ya kopyalar.

Yerleştirmenin sondan başa yapılması kararlılığı sağlar. Bir kovaya ait dizgilerden girişte en sonda olanı, kovanın en sonuna yazılır. Ondan önceki, bir önceki hücreye yazılır. Böylece kova içindeki sıra girişteki sırayla aynı kalır. kar metodu ise d, dizginin uzunluğunu aşıyorsa 0 döndürür. 0 bütün harflerin kodundan küçük olduğu için kısa dizgi, o konumda karakteri olan dizgilerin önüne geçer. Böylece “car”, “cart”tan önce gelir; bu, sözlüksel sıradaki “önek önce gelir” kuralının karşılığıdır.

Tek bir geçişin maliyeti açıktır. Sayma ve yerleştirme döngüleri N adım, önek toplamı döngüsü R = 256 adım sürer. Bir geçiş O(N + R) zaman ve gec ile say dizileri için O(N + R) ek bellek kullanır.

5.2.3.2LSD: sağdan sola

radixSirala, d'yi W − 1'den 0'a indirerek sayarakSirala'yı W kez çağırır. Önce son karaktere, sonra ortanca karaktere, en son ilk karaktere göre sıralanır. Her geçişte eşit anahtarlı dizgiler bir önceki geçişin kurduğu sırayı korur. Şekiller önceki örneğin üç geçişini gösterir.

İkinci geçişin sonucuna dikkatle bakmak yararlıdır. Dizi artık son iki karaktere göre sıralıdır: “ab” ile bitenler (cab, dab), “ad” ile bitenler (bad, dad, fad), sonra “bb”, “ce”, “dd”, “ed”, “ee”. Üçüncü geçiş ilk karaktere göre gruplar. Aynı ilk harfli dizgiler, örneğin bad, bed ve bee, ikinci geçişin bıraktığı sırayla kalır. O sıra da zaten son iki karaktere göre doğru sıradır.

Dizgilerin uzunlukları farklıysa kar eksik konumlar için 0 döndürür ve kısa dizgi sanki sonuna en küçük karakter eklenmiş gibi davranır. Örneğin car, cart, ca, cat için W = 4'tür. Dördüncü karaktere göre yapılan ilk geçişte “car”, “ca” ve “cat”ın anahtarı 0, “cart”ınki 't'dir; dizi car, ca, cat, cart olur. Üçüncü karaktere göre geçişte “ca”nın anahtarı 0'dır ve öne geçer: ca, car, cart, cat. Kalan iki geçiş bu sırayı değiştirmez. Sonuç sözlüksel sıradır.

5.2.3.3LSD neden doğrudur?

LSD'nin en az önemli karakterden başlaması ilk bakışta tersine görünür. Doğruluğunun anahtarı bir değişmezdir: her geçişten sonra dizi, o ana kadar işlenen son karakterlere göre sıralıdır.

İspat kararlılığın neden vazgeçilmez olduğunu da gösterir. Eşit anahtarlı iki dizginin sırasına son geçiş karar vermez; o kararı önceki geçişler vermiştir. Kararsız bir alt sıralama bu kararı bozar. Örneğin yerleştirme döngüsü sondan başa değil de baştan sona yazılırsa her kova tersine dolar. Sunumdaki on dizgiyle bu bozuk sürüm add, ace, bed, bee, bad, cab, dab, dad, ebb, fad üretir. İlk harfler doğru sıradadır, ama aynı ilk harfli dizgiler karışmıştır.

5.2.3.4MSD: soldan sağa

MSD basamak sıralaması ilk karakterden başlar. Bütün dizgiler önce ilk karakterlerine göre kovalara ayrılır. Ardından her kova, bir sonraki karaktere göre ayrı ayrı ve özyinelemeli olarak sıralanır. Tek öğeli bir kovada ya da dizginin sonuna gelindiğinde özyineleme durur. Dizgi sonu, sunumdaki gösterimde \0 karakteriyle belirtilir ve bütün harflerden küçük kabul edilir.

Şekil 5.2.8'deki dokuz kelime ilk karaktere göre B, C, M ve W kovalarına ayrılır. M kovasında yalnız MIDNIGHT vardır; tek öğeli kova hemen biter ve MIDNIGHT için tek karakter yeter. B kovasında BADGE ve BANNER vardır. İkinci karakterleri aynı (A) olduğu için üçüncü karaktere bakılır: D < N. Bu kelimeler için üç karakter okunur. C kovasında COFFEE, COMPARISON ve COMPUTER vardır. COFFEE üçüncü karakterde (F < M) ayrılır. COMPARISON ile COMPUTER ise ancak beşinci karakterde (A < U) ayrılır; ikisi için beş karakter gerekir. W kovasında WORKER ikinci karakterde (O), WANDER ve WARDROBE üçüncü karakterde (N < R) ayrılır.

Toplam okunan karakter sayısı yeşil hücrelerin sayısıdır: 3 + 3 + 3 + 5 + 5 + 1 + 3 + 3 + 2 = 28. Dokuz kelimenin toplam uzunluğu ise 63 karakterdir. MSD karakterlerin yarısından azını okuyarak sıralamayı bitirmiştir. LSD ise her kelimeyi en uzun kelimenin uzunluğu kadar, yani 10 kez ele alırdı. Bu, MSD'nin asıl üstünlüğüdür: yalnız ayırt edici önekleri inceler.

Sunum MSD'nin kodunu vermez; özyinelemeli yazımı alıştırma olarak bırakır. Aşağıdaki sürüm sunumdaki fikri doğrudan uygular. karM, dizgi bittiyse 0, bitmediyse karakter kodunun bir fazlasını döndürür. Böylece 0 kovası “dizgi burada bitti” anlamına gelir ve bu kova sıralamada en öne düşer.

void msdSirala(String[] a) {
  String[] yardimci = new String[a.length];
  msdSirala(a, yardimci, 0, a.length - 1, 0);
}
int karM(String s, int d) {          // dizgi bittiyse 0, değilse kod + 1
  return d < s.length() ? s.charAt(d) + 1 : 0;
}
void msdSirala(String[] a, String[] yardimci, int alt, int ust, int d) {
  if (alt >= ust) return;            // 0 ya da 1 öğeli kova
  int[] say = new int[258];
  for (int i = alt; i <= ust; i++) say[karM(a[i], d) + 1]++;
  for (int r = 0; r < 257; r++) say[r + 1] += say[r];
  for (int i = alt; i <= ust; i++) yardimci[say[karM(a[i], d)]++] = a[i];
  for (int i = alt; i <= ust; i++) a[i] = yardimci[i - alt];
  for (int r = 0; r < 256; r++)      // her kova bir sonraki karakterle
    msdSirala(a, yardimci, alt + say[r], alt + say[r + 1] - 1, d + 1);
}

Kod, LSD'deki sayma adımını bir alt dizi (alt–ust) üzerinde yapar. say dizisi 258 hücrelidir: dizgi sonu için bir kova, 256 karakter için 256 kova ve önek toplamı için bir fazladan hücre. Önek toplamından sonra say[r], r kovasının alt dizideki başlangıç konumudur. Dağıtma adımı öğeleri yardımcı diziye yazar ve geri kopyalar. Son döngü, her karakter kovasını d + 1 ile özyinelemeli sıralar. 0 kovası (bitmiş dizgiler) yeniden sıralanmaz; içindekiler birbirine eşittir. Kod sunumdaki dokuz kelimeyi BADGE, BANNER, COFFEE, COMPARISON, COMPUTER, MIDNIGHT, WANDER, WARDROBE, WORKER sırasına koyar. car, cart, ca, cat, a, "" girdisini de "", a, ca, car, cart, cat olarak sıralar.

MSD'nin zayıf yanları da vardır. Her özyinelemeli çağrı 258 hücrelik bir say dizisi oluşturur ve tarar. Birkaç öğeli küçük kovalarda bu tarama, öğelerin kendisinden çok daha pahalıdır. Bu yüzden uygulamalarda küçük alt dizilere (ör. 15 öğenin altı) eklemeli sıralama uygulanır. İkinci zayıflık, uzun ortak önekli dizgilerdir. Bütün dizgiler aynı uzun önekle başlıyorsa MSD de bütün karakterleri okumak zorunda kalır. Örneğin URL listelerinde “https://www.” öneki her dizgide ortaktır.

5.2.3.5Karmaşıklık ve yöntem seçimi

LSD W geçiş yapar; W en uzun dizginin uzunluğudur. Her geçiş N dizgiyi ve R kovayı işler. Toplam zaman O(W · (N + R))'dir. Alfabe sabitse (R = 256) ve N, R'den çok büyükse maliyet O(W · N)'ye iner: en uzun dizginin uzunluğu çarpı öğe sayısı. Bu, girdinin toplam karakter sayısıyla aynı büyüklüktedir. Girdiyi okumak bile bu kadar sürdüğünden daha iyisi beklenemez.

MSD'nin ek belleğindeki W · R terimi özyinelemeden gelir. Özyineleme derinliği en çok W'dir ve her düzeyde bir say dizisi canlı kalır. MSD'nin zamanı en kötü durumda O(N · W)'dir; ama rastgele dizgilerde yalnız ayırt edici önekler okunduğu için çok daha azdır. R'nin büyük olduğu küçük kovalarda ise sayma dizisinin maliyeti baskın çıkar.

Seçim anahtarların yapısına bağlıdır. Anahtarlar kısa ve sabit uzunluklu olduğunda LSD idealdir: araç plakaları, posta kodları, IP adresleri, üç harfli havalimanı kodları. Örneğin N = 10⁶ adet üç harfli kod LSD ile 3 · (10⁶ + 256) ≈ 3 · 10⁶ adımda sıralanır; birleştirme sıralaması ise yaklaşık 2 · 10⁷ karşılaştırma yapar. Uzunlukları çok farklı dizgilerde LSD her dizgiyi en uzun dizginin uzunluğu kadar ele alır ve gereksiz iş yapar. Bu durumda MSD ya da karşılaştırmalı sıralama tercih edilir.

5.2.4Düzenli ifadeler

Bir metinde bütün tarihleri bulmak, bir form alanına yazılan telefon numarasının doğru biçimde olup olmadığını denetlemek ya da bir günlük dosyasından hata satırlarını ayıklamak gerekebilir. Bu işlerin her biri için ayrı bir döngü yazmak yorucudur ve hataya açıktır. Düzenli ifadeler bu tür örüntüleri kısa bir dizgiyle tanımlamayı sağlar.

5.2.4.1Düzenli ifade nedir?

Düzenli ifadeler metinde örüntüye uyan parçaları bulmak, bir dizginin bütünüyle örüntüye uyup uymadığını doğrulamak, parçaları ayıklamak ya da başka metinle değiştirmek için kullanılır. Günlük (log) analizi, form doğrulama, veri temizleme ve derleyicilerdeki sözcük çözümleyici (lexer) bunların başında gelir. Sözcük çözümleyici, kaynak kodu anahtar sözcük, değişken adı, sayı gibi parçalara ayıran ilk derleyici aşamasıdır.

Düzenli ifadelerin bir de kuramsal temeli vardır. Kleene teoremi, her düzenli ifadeye eşdeğer bir sonlu durum makinesi bulunduğunu ve bunun tersinin de geçerli olduğunu söyler. Düzenli ifadelerle tanımlanabilen dizgi kümelerine düzenli diller denir. Bu bağ, düzenli ifadelerin nasıl hızlı çalıştırıldığını açıklar: ifade önce bir otomata çevrilir, sonra metin bu otomatla taranır.

İlk satırda u?, u harfinin olabileceğini ya da olmayabileceğini söyler; Amerikan ve İngiliz yazımı birlikte yakalanır. İkinci satırda (a|e) iki seçenekten birini ister; “groy” uymaz. Üçüncü satırda \d+ bir ya da daha çok rakamdan oluşan her parçayı bulur. Nokta bir rakam olmadığı için “20.99” iki ayrı parçaya bölünür. Dördüncü satırda \b kelime sınırıdır; “kodlama” içindeki “kod” bir kelimenin tamamı olmadığı için alınmaz.

Java'da düzenli ifadeler java.util.regex paketindeki Pattern ve Matcher sınıflarıyla kullanılır. String sınıfının matches, replaceAll ve split metotları da düzenli ifade alır. Java dizgisinde ters bölü bir kaçış karakteri olduğu için düzenli ifadedeki her ters bölü iki kez yazılır: \d+ ifadesi kodda "\\d+" olarak görünür.

5.2.4.2Temel operatörler

Düzenli ifadedeki sıradan karakterler kendileriyle eşleşir: abc yalnız “abc” parçasına uyar. Bazı karakterlerin ise özel anlamı vardır. Tablo 5.2.8 en sık kullanılan operatörleri ve her biri için bir örneği verir. Tablonun son iki sütunu, verilen dizginin içinde örüntüye uyan bir parça bulunup bulunmadığını gösterir; bu, Java'daki Matcher.find davranışıdır.

*, + ve ? yalnız hemen önlerindeki öğeye uygulanır. Bu öğe tek bir karakter, bir küme ya da parantezle kurulmuş bir grup olabilir. ab*c ifadesinde yıldız yalnız b'ye aittir: a, ardından sıfır ya da daha çok b, ardından c. Bu yüzden “ac” (sıfır b) ve “abbc” uyar, “adc” uymaz. Bütün bir parçanın tekrarlanması isteniyorsa parça gruplanır: (ab)+, “ab”, “abab”, “ababab” … ile eşleşir.

^ ve $ karakter değil, konum belirtir. ^ab ancak dizginin en başındaki “ab” ile eşleşir; “cab” içindeki “ab” başta olmadığı için alınmaz. ^(ab)+$ ise baştan sona yalnız “ab” tekrarlarından oluşan dizgileri kabul eder. “aba”nın sonunda fazladan bir a vardır ve uymaz.

5.2.4.3Özel karakterler ve kaçış

Temel operatörlerin yanında sık kullanılan birkaç kısaltma vardır. Bu kısaltmalar ters bölüyle başlar ve bir karakter sınıfını ya da bir konumu tanımlar.

Kısaltmaların büyük harfli biçimleri tümleyendir. \D rakam olmayan, \W kelime karakteri olmayan, \S boşluk olmayan bir karakterle eşleşir. \w tek bir karakterdir; bir kelimenin tamamı için \w+ yazılır.

Özel anlamı olan bir karakterin kendisi aranıyorsa önüne ters bölü konur. Buna kaçış denir. \. gerçek bir nokta, \+ artı işareti, \( açma parantezi ile eşleşir. Kaçış unutulursa ifade beklenenden fazlasını yakalar: a.b, nokta herhangi bir karakter anlamına geldiği için “a+b” ile de eşleşir.

Java'da bir ayrıntı Türkçe metinlerde önemlidir. \w varsayılan olarak yalnız ASCII harflerini kapsar. “şeker” kelimesine \w+ uygulandığında ilk eşleşme “eker” olur; 'ş' bir kelime karakteri sayılmaz. Türkçe harfleri de kapsayan bir harf sınıfı için Unicode özelliği \p{L} kullanılır: \p{L}+, “şeker”in tamamıyla eşleşir. Bir başka yol, örüntüyü Pattern.UNICODE_CHARACTER_CLASS bayrağıyla derlemektir; bu bayrak \w'yi de Unicode'a genişletir.

5.2.4.4Karakter sınıfları

Köşeli parantez içine yazılan karakterler bir karakter sınıfı oluşturur. Sınıf, içindeki karakterlerden herhangi biriyle eşleşir. Tire (-) bir aralık bildirir: [a-z], a ile z arasındaki kodlara sahip her küçük harfle eşleşir.

^ işaretinin iki ayrı anlamı vardır. Köşeli parantezin içinde ve başında “değil” anlamına gelir; dışarıda ise dizginin başını belirtir. Küme içinde ., * ve + özel değildir: [.+] bir nokta ya da bir artı ile eşleşir. Tire, aralık bildirdiği için kendisi aranıyorsa kümenin başına ya da sonuna yazılır: [-+].

5.2.4.5Niceleyiciler ve gruplama

Bir öğenin kaç kez tekrarlanacağını belirten operatörlere niceleyici (quantifier) denir. *, + ve ? en kısa niceleyicilerdir. Süslü parantez daha ince ayar sağlar.

Parantezin iki görevi vardır. Birincisi, niceleyicinin bütün bir parçaya uygulanmasını sağlar. İkincisi, eşleşen parçayı yakalar: eşleşme bulunduktan sonra parantezin içine düşen metin ayrıca okunabilir. Gruplar soldan sağa, açma parantezlerinin sırasıyla numaralanır. Java'da 1. grup m.group(1) ile, eşleşmenin tamamı m.group() ya da m.group(0) ile okunur.

Niceleyiciler varsayılan olarak açgözlüdür (greedy): olabildiğince uzun bir parça alırlar. a{2,4}, “aaaaa” içinde mümkün olan en uzun parçayı, yani “aaaa”yı alır. Niceleyiciden sonra bir ? yazılırsa niceleyici tembel (lazy) olur ve olabildiğince kısa bir parça seçer. Fark en iyi HTML etiketleriyle görülür.

5.2.4.6İleri ve geri bakış

Bazen bir parçanın yalnız belirli bir bağlamda geçtiği durumlar aranır, ama bağlamın kendisi eşleşmeye katılmamalıdır. Örneğin “TL”den önce gelen sayılar bulunmak istenir, ama “TL” sonuca girmemelidir. Bakış ifadeleri bu işi görür.

“ab ac ba” metninde üç a vardır: 0, 3 ve 7 numaralı konumlarda. 0'daki a'dan sonra b gelir; ileri bakış bu a'yı seçer. 3'teki a'dan sonra c, 7'deki a'dan sonra metnin sonu gelir; olumsuz ileri bakış bu ikisini seçer. 7'deki a'nın önünde b vardır; geri bakış yalnız onu seçer. Öteki iki a'nın önünde ise boşluk ya da metin başı vardır.

Bakış ifadeleri bir konumu sınar ve karakter tüketmez. a(?=b) eşleşmesinin metni yalnız “a”dır; b eşleşmeye katılmaz ve sonraki aramada yeniden kullanılabilir. Bu yüzden “abacab” metninde a(?=b) iki kez, 0 ve 4 konumlarında, her seferinde “a” olarak eşleşir.

Bakış ifadelerinin en yaygın kullanımı, birden çok koşulu aynı anda sınamaktır. ^(?=.*\d)(?=.*[A-Z]).{8,}$ ifadesi bir parola kuralını denetler. İlk ileri bakış, dizginin bir yerinde bir rakam olduğunu; ikincisi, bir büyük harf olduğunu sınar. İkisi de karakter tüketmediği için konum hâlâ dizginin başındadır. Son parça .{8,}$, dizginin en az 8 karakter olduğunu ister. “Parola12” üç koşulu da sağlar. “parola12”de büyük harf, “PAROLAXY”de rakam yoktur; “Pa1” ise kısadır.

5.2.4.7Doğrulama ifadeleri

Düzenli ifadeler en çok kullanıcıdan gelen verinin biçimini denetlemek için yazılır. Tablo 5.2.13 üç örnek verir. Hepsi ^ ile başlar ve $ ile biter; dizginin bir parçasının değil, tamamının biçime uyması istenir.

E-posta ifadesi üç parçadan oluşur. [a-zA-Z0-9._%+-]+ kullanıcı adıdır: harf, rakam ve birkaç işaretten oluşan, en az bir karakterlik bir parça. Ardından @ gelir. [a-zA-Z0-9.-]+ alan adıdır. \.[a-zA-Z]{2,} ise gerçek bir nokta ve en az iki harfli uzantıdır. “ali@tr” uymaz, çünkü @'den sonra nokta ve uzantı yoktur. “a b@x.com” uymaz, çünkü boşluk kullanıcı adı kümesinde yer almaz.

Telefon ifadesinde (\+\d{1,3}[- ]?)? isteğe bağlı ülke kodudur. Grup bir artı, bir ile üç arası rakam ve isteğe bağlı bir tire ya da boşluktan oluşur; sondaki ? grubun tamamını isteğe bağlı yapar. Ardından tam 10 rakam gelmelidir. “0532 123 45 67” uymaz: hem 11 rakamdır hem de araya boşluklar girmiştir.

URL ifadesinde s? “http” ve “https”i birlikte kabul eder. Ardından :\/\/ gelir. Java'da eğik çizgi özel değildir ve kaçış gerekmez; başka dillerden gelen bu yazım yine de zararsızdır. [^\s/$.?#], ilk karakterin boşluk ya da bu işaretlerden biri olamayacağını söyler. Son parça boşluk içermeyen herhangi bir karakter dizisidir. “ftp://x.com” uymaz, çünkü şema http ya da https değildir. “http:// x” uymaz, çünkü // işaretinden sonraki ilk karakter boşluktur.

Bu ifadeler pratik yaklaşımlardır; ilgili standartların tamamını kapsamaz. E-posta adreslerinin tam söz dizimi RFC 5322'de, URI söz dizimi RFC 3986'da tanımlanır ve çok daha geniştir. Gerçek uygulamalarda düzenli ifade ilk elemeyi yapar; asıl doğrulama, örneğin adrese bir onay iletisi göndermek, başka yolla yapılır.

5.2.4.8Dilbilgisi ve ayrıştırma ağacı

Bir dizginin yapısını tanımlamanın bir başka yolu dilbilgisi (grammar) yazmaktır. Dilbilgisi, büyük bir yapının hangi küçük parçalardan oluştuğunu kurallarla anlatır. Örnek olarak http://didit.csail.mit.edu:4949/ biçimindeki adresler ele alınsın:

url    ::= 'http://' sunucu
           ':' port '/'
sunucu ::= kelime '.' sunucu
         | kelime
kelime ::= [a-z]+
port   ::= [0-9]+

İlk kural bir url'nin “http://”, bir sunucu, iki nokta üst üste, bir port ve bir eğik çizgiden oluştuğunu söyler. İkinci kural özyinelemelidir: bir sunucu ya “kelime . sunucu” biçimindedir ya da tek bir kelimedir. Son iki kural kelimeyi ve portu karakter sınıflarıyla tanımlar. Dilbilgisinin bir dizgiye uygulanması bir ayrıştırma ağacı üretir.

Dilbilgisi özyinelemeli görünse de bu özyineleme kuralın en sonundadır; kuyruk özyinelemesidir. Böyle bir özyineleme bir döngüye çevrilebilir. Bu yüzden aynı dil bir düzenli ifadeyle de tanımlanır: http://([a-z]+\.)*[a-z]+:[0-9]+/. Bu ifade gerçekten de örnek adresle eşleşir.

Her yapı için bu mümkün değildir. Dengeli parantezler, yani “(())()” gibi her açılanın kapandığı dizgiler, düzenli ifadeyle tanımlanamaz. Bir sonlu durum makinesinin belleği yalnız şu anki durumdur ve sınırsız derinlikteki iç içe açılmış parantezleri sayamaz. İç içe yapılar için bağlamdan bağımsız dilbilgisi ve onu işleyen bir ayrıştırıcı (parser) gerekir. Programlama dillerinin derleyicileri bu ikili yapıyı kullanır: sözcük çözümleyici düzenli ifadelerle, ayrıştırıcı bağlamdan bağımsız dilbilgisiyle çalışır.

5.2.4.9Java'da Pattern ve Matcher

Java'da bir düzenli ifade önce Pattern.compile ile derlenir. Derleme, ifadeyi içeride bir otomat benzeri yapıya çevirir; aynı ifade birçok metne uygulanacaksa derlenmiş nesne saklanır ve yeniden kullanılır. Derlenmiş örüntüden matcher metoduyla belirli bir metin için bir Matcher elde edilir.

String girdi = "Ad: Ali Veli, Yaş: 30, E-posta: ali.veli@ornek.com";
Pattern p = Pattern.compile("Yaş: (\\d+),");  // derle
Matcher m = p.matcher(girdi);
if (m.find()) {                          // ilk eşleşmeyi bul
  int yas = Integer.parseInt(m.group(1)); // 1. grup: "30"
  System.out.println("Yaş: " + yas);
}

Kod bir satırlık kayıttan yaşı ayıklar. "Yaş: (\\d+)," örüntüsü “Yaş: ” metnini, ardından bir ya da daha çok rakamı, ardından bir virgülü arar. Rakamlar parantez içinde olduğu için 1. grup olarak yakalanır. m.find() metinde ilk eşleşmeyi arar ve bulursa true döndürür. m.group(1) “30” dizgisini verir; Integer.parseInt bunu sayıya çevirir. Kod Yaş: 30 yazdırır.

İlk satırdaki tembellik önemlidir. Açgözlü Ad: (.*), yazılsaydı .* son virgüle kadar uzanır ve grup “Ali Veli, Yaş: 30” olurdu. Üçüncü satırda .*? tembel olsa da $ onu satır sonuna kadar gitmeye zorlar.

Matcher'ın iki temel metodu farklı sorulara cevap verir. find() metnin bir parçasını arar; her çağrıda bir sonraki eşleşmeye geçer. matches() ise metnin tamamını eşleştirmeye çalışır; ifadenin başına ^, sonuna $ konmuş gibi davranır. String.matches da bu ikinci türdendir. Örneğin "abc123".matches("\\d+") false döndürür, çünkü dizgi rakamla başlamaz. Aynı örüntüyle find() ise “123” parçasını bulur ve true döndürür. Benzer biçimde "2024".matches("\\d{4}") true, "20245".matches("\\d{4}") false'tur: beşinci rakam fazladır.

Aynı iş düzenli ifade olmadan da yapılabilir. Başlangıç işareti (ör. “Yaş: ”) indexOf ile bulunur, bitiş işaretine (“,”) kadar olan kısım substring ile kesilir. Basit bir ayıklamada bu yol daha hızlı ve okunaklı olabilir. Örüntü karmaşıklaştıkça, örneğin isteğe bağlı parçalar ve seçenekler arttıkça, düzenli ifade daha kısa ve daha güvenilir kalır.

5.2.5Sonlu durum makineleri

Bir turnike düşünülsün. Kilitliyken jeton atılırsa açılır; açıkken biri geçerse yeniden kilitlenir. Turnikenin geçmişte ne kadar jeton yuttuğu önemli değildir; davranışını yalnız şu anki durumu, kilitli ya da açık olması belirler. Sonlu durum makinesi bu fikrin matematiksel biçimidir ve dizgileri karakter karakter işlemenin en sade modelidir.

5.2.5.1Biçimsel tanım

Makinenin tek belleği şu anki durumdur. Durum sayısı sonlu olduğu için makine, okuduğu girdinin yalnız sınırlı bir özetini tutabilir. Bu kısıt ilk bakışta zayıflık gibi görünür. Yine de sözcük çözümleme, ağ protokolleri ve örüntü arama gibi pek çok gerçek problem bu kadar bellekle çözülür. Üstelik makine her karakter için tek bir işlem yaptığı için çok hızlıdır.

Durum diyagramında her durum bir daire, her geçiş etiketli bir oktur. Başlangıç durumuna dışarıdan bir ok girer; kabul durumları çift halkayla çizilir. Şekil 5.2.10'daki makinede δ(q₀, 0) = q₀, δ(q₀, 1) = q₁, δ(q₁, 1) = q₁, δ(q₁, 0) = q₀'dır. Durumların anlamı açıktır: q₁ “son okunan sembol 1'di”, q₀ “son okunan sembol 0'dı ya da henüz bir şey okunmadı” demektir.

5.2.5.2DFA, NFA ve ε-NFA

Sonlu durum makinelerinin üç yaygın türü vardır. Farkları, geçiş fonksiyonunun bir (durum, sembol) çiftine kaç hedef verebildiğidir.

• Deterministik sonlu otomat (deterministic finite automaton, DFA): her (durum, sembol) çifti için tam olarak bir geçiş vardır. Makine her an tek bir durumdadır. Çalıştırması basittir ve n uzunluklu bir girdi O(n) zamanda işlenir.
• Deterministik olmayan sonlu otomat (nondeterministic finite automaton, NFA): bir (durum, sembol) çifti için sıfır, bir ya da birden fazla geçiş tanımlanabilir. Makine aynı anda bir durum kümesinde bulunur. Girdi bittiğinde kümede bir kabul durumu varsa dizgi kabul edilir.
• ε-NFA: sembol okumadan yapılan boş geçişlere (epsilon, ε) de izin veren NFA. Bir düzenli ifadeden doğrudan, parça parça kurulabilir. Bu kurulumun adı Thompson yapısıdır.

Sınır gerçekten de aşılabilir. “Sondan üçüncü sembolü a olan” {a, b} dizgilerini tanıyan NFA dört durumludur. Başlangıç durumu her sembolde kendinde kalır ya da bir a okuyunca “a görüldü” durumuna geçer. Ardından iki sembol daha okunur ve kabul durumuna varılır. Bu dili tanıyan DFA ise son üç sembolün hepsini hatırlamak zorundadır ve 2³ = 8 durum ister. “Sondan k. sembol” için NFA k + 1, DFA 2^k durumludur. Uygulamada bu patlama nadiren görülür. grep, lex/flex ve derleyicilerin sözcük çözümleyicileri Şekildeki zinciri kullanır: düzenli ifadeyi NFA'ya, gerekirse DFA'ya çevirir ve metni bu otomatla tarar.

5.2.5.3DFA simülasyonu

Bir DFA'yı çalıştırmak üç adımdan oluşur. Başlangıç durumuna geçilir. Her karakter için durum geçiş tablosundan güncellenir. Dizgi bitince son durumun kabul durumu olup olmadığı denetlenir. Geçiş fonksiyonu bir tabloyla saklanır: satırlar durumlar, sütunlar sembollerdir. Durumlar 0'dan numaralanır ve 0 başlangıç durumudur.

boolean kabulEder(int[][] gecis, boolean[] kabul,
                  String s) {
  int durum = 0;                     // başlangıç durumu
  for (char c : s.toCharArray())
    durum = gecis[durum][c - '0'];   // tek geçiş
  return kabul[durum];               // son durum kabul mü?
}

gecis tablosu int[|Q|][|Σ|] boyutundadır. Bu örnekte alfabe {0, 1}'dir; c - '0' ifadesi '0' karakterini 0'a, '1' karakterini 1'e çevirir ve sütun indisi olarak kullanılır. kabul dizisi her durumun kabul durumu olup olmadığını tutar. Döngü her karakter için tek bir tablo okuması yapar. n uzunluklu dizgi O(n) zamanda, geri dönmeden işlenir; ek bellek yalnız durum değişkenidir. Tablonun kendisi O(|Q| · |Σ|) yer kaplar.

Geri dönmemek önemli bir özelliktir. Düzenli ifade motorlarının bir kısmı, (a+)+$ örneğinde olduğu gibi geri izleme yapar ve kötü durumda üstel süre harcayabilir. DFA ise her karakteri tam bir kez okur; en kötü durumda da doğrusal zamanlıdır.

5.2.5.4Örnek: “nice” tanıyıcısı

Belirli tek bir kelimeyi tanıyan makine, sonlu durum makinelerinin en yalın örneğidir. Şekil 5.2.12'deki makine yalnız “nice” dizgisini kabul eder.

Her durum, o ana kadar okunan öneki temsil eder: 1 boş öneki (ε), 2 “n”yi, 3 “ni”yi, 4 “nic”i, 7 ise “nice”ı. Beklenen karakter gelirse bir sonraki duruma geçilir. Beklenen karakter gelmezse, örneğin 2 durumunda i'den başka bir karakter okunursa, Hata durumuna gidilir. Hata durumundan çıkış yoktur; her karakter makineyi orada tutar. Böyle bir duruma tuzak durum (trap state) denir. Diyagramda tuzak durumun kendine dönen okları çizilmez, ama makinenin DFA olması için var oldukları kabul edilir. Aynı biçimde Başarı durumundan sonra bir karakter daha gelirse makine Hata'ya geçer; “nicer” reddedilir.

“nice” girdisi 1 → 2 → 3 → 4 → 7 yolunu izler ve kabul edilir. “nine” ise 1 → 2 → 3 yolundan sonra üçüncü karakterde 'n' okur. Beklenen 'c'dir; makine 6'ya gider ve dördüncü karakter onu orada tutar. Sonuç rettir.

5.2.5.5Örnek: ikili alfabe üzerinde DFA

Daha büyük bir DFA altı durumludur: A, B, C, D, E ve F. Başlangıç A, tek kabul durumu D'dir. Geçişler Tablo 5.2.15'te ve Şekil 5.2.13'te verilir. Tablonun her hücresinde tek bir durum vardır; bu yüzden makine bir DFA'dır.

Kabul kararı yalnız son duruma bağlıdır. “1011010” girdisi A → B → B → C → D yolundan sonra D'ye varır; ama girdi bitmemiştir. Sonraki 0 makineyi D'de tutar, 1 A'ya götürür, son 0 ise E'ye götürür. E kabul durumu olmadığından dizgi reddedilir. Yolda kabul durumundan geçmiş olmak bir şey değiştirmez. Benzer biçimde “111” A → B → C → D yoluyla kabul edilir, “11” ise C'de biter ve reddedilir.

Tablonun kabulEder metoduna verilmesi kolaydır: A–F durumları 0–5 olarak numaralanır, tablo {{4, 1}, {1, 2}, {1, 3}, {3, 0}, {4, 5}, {5, 0}} olur ve kabul dizisinde yalnız 3. hücre true'dur. Metot “10011” için true, “1011010” için false döndürür.

5.2.5.6Örüntü eşleme otomatı

Sonlu durum makineleri bir metin içinde bir örüntüyü aramak için de kullanılır. Örüntü “ACACAGA” olsun. Metin soldan sağa okunurken makinenin durumu, şimdiye kadar okunan metnin sonunun örüntünün hangi önekiyle uyuştuğunu gösterir.

İleri geçişler kolaydır: q durumunda örüntünün q. karakteri (0'dan sayarak) okunursa q + 1'e geçilir. Asıl ilginç olan geri geçişlerdir. Örneğin 5 durumunda (son okunan beş karakter “ACACA”) C okunsun. Beklenen G'dir, uyuşma bozulmuştur. Ama okunan metnin sonu artık “ACACAC”dır ve bunun soneki “ACAC”, örüntünün 4 uzunluklu önekidir. Makine 0'a değil 4'e döner; uyuşmanın bir kısmı korunur. Otomattaki bütün sıfırdan farklı geri geçişler şunlardır: 1, 3, 5 ve 7 durumlarından A ile 1'e; 5'ten C ile 4'e; 7'den C ile 2'ye.

Bu fikir, Knuth–Morris–Pratt (KMP) algoritmasındaki önek fonksiyonunun otomat biçimidir. KMP uyuşmazlıkta örüntüyü ne kadar kaydıracağını önek fonksiyonundan okur. Otomat ise bu bilgiyi her (durum, karakter) çifti için önceden hesaplayıp tabloya yazar. Tablonun kurulumu O(m · |Σ|), arama O(n) sürer. Sunum otomatın nasıl kurulduğunu göstermez; aşağıdaki metot bu kurulumu yapar:

int[][] otomatKur(String p) {        // örüntü otomatı, O(m · 256)
  int m = p.length();
  int[][] dfa = new int[m + 1][256];
  dfa[0][p.charAt(0)] = 1;
  for (int x = 0, j = 1; j <= m; j++) {
    for (int c = 0; c < 256; c++)
      dfa[j][c] = dfa[x][c];         // uyuşmazlık: x durumundaki gibi
    if (j < m) {
      dfa[j][p.charAt(j)] = j + 1;   // uyuşma: ilerle
      x = dfa[x][p.charAt(j)];       // yeniden başlama durumu
    }
  }
  return dfa;
}

Metodun anahtarı x değişkenidir: x, örüntünün p[1..j−1] parçası otomata verildiğinde varılacak durumdur. j durumunda bir uyuşmazlık olduğunda makine, “son okunanlar örüntünün j karakterlik öneki, ardından yeni karakter” bilgisine sahiptir. En uzun uyan önek, bu metnin ilk karakteri atıldığında elde edilen durumdan, yani x'ten yeni karakterle gidilen durumdur. Bu yüzden j satırı önce x satırından kopyalanır. Sonra uyuşma geçişi j + 1 olarak üzerine yazılır ve x bir adım ilerletilir. Metot “ACACAGA” için tam olarak Şekil 5.2.15'teki geçişleri üretir.

5.2.5.7Kod izleme: dfaAra

Otomat kurulduktan sonra arama birkaç satırdır:

int dfaAra(int[][] dfa, String t, int m) {
  int q = 0;                     // durum
  for (int i = 0; i < t.length(); i++) {
    q = dfa[q][t.charAt(i)];
    if (q == m)
      return i - m + 1;          // eşleşme
  }
  return -1;
}

dfa tablosunun satırları durumlar, sütunları karakter kodlarıdır; dfa[q][t.charAt(i)] doğrudan bir sonraki durumu verir. q == m olduğunda örüntünün son karakteri metnin i konumundadır. Örüntü i − m + 1 konumunda başlar ve bu değer döndürülür. Döngü eşleşme bulamadan biterse -1 döner. Kod dfaAra(dfa, "GACACACAGA", 7) çağrısıyla izlensin.

Örüntü metinde 3 numaralı konumdan başlar: t[3..9] = “ACACAGA”. Dikkat çekici adım i = 6'dır. Saf bir arama yöntemi burada örüntüyü bir kaydırıp metinde geri dönerek yeniden karşılaştırırdı. Otomat ise 4 durumuna geçer ve metnin hiçbir karakterini ikinci kez okumaz. Toplam on karakter, on tablo okumasıyla işlenmiştir.

5.2.5.8FSM ile sayı ayrıştırma

Sonlu durum makineleri metinden parça ayıklamak için de kullanılır. Aşağıdaki metot bir metindeki ondalık sayıları bulup yazdırır. Makinenin üç durumu vardır: BASLA (bir sayının içinde değiliz), RAKAM (tam sayı kısmı okunuyor) ve ONDALIK (nokta görüldü, kesir kısmı okunuyor). Okunan sayı karakterleri bir StringBuilder tamponunda biriktirilir.

void sayilariBul(String s) {
  Durum d = Durum.BASLA;
  StringBuilder tampon = new StringBuilder();
  for (char c : s.toCharArray()) {
    boolean rakam = Character.isDigit(c);
    if (rakam) {
      if (d == Durum.BASLA) d = Durum.RAKAM;
      tampon.append(c);
    } else if (c == '.' && d != Durum.ONDALIK) {
      d = Durum.ONDALIK;
      tampon.append(c);
    } else if (d != Durum.BASLA) {  // sayı bitti
      System.out.println(tampon);
      tampon.setLength(0);
      d = Durum.BASLA;
    }
  }
  if (d != Durum.BASLA) System.out.println(tampon);
}

Döngü her karakter için üç koşuldan birini uygular. Karakter bir rakamsa ve makine BASLA'daysa RAKAM'a geçilir; her durumda rakam tampona eklenir. Karakter bir nokta ise ve makine henüz ONDALIK'ta değilse ONDALIK'a geçilir ve nokta da tampona eklenir. Bu iki koşul tutmazsa ve makine bir sayının içindeyse (BASLA dışında), sayı bitmiştir: tampon yazdırılır, boşaltılır ve BASLA'ya dönülür. Döngüden sonra makine hâlâ bir sayının içindeyse, yani girdi bir sayıyla bitiyorsa, son sayı da yazdırılır.

Metot iki satır yazdırır: “20.99” ve “5.”. İkincisi bir kusurdur: cümle sonundaki nokta sayının parçası sanılmıştır. Kusurun nedeni, makinenin ONDALIK durumuna noktadan sonra rakam gelip gelmeyeceğini bilmeden geçmesidir. Aynı tasarım başka girdilerde de beklenmedik sonuçlar verir. “v1.2.3 ve 7” girdisinde ikinci nokta geldiğinde makine zaten ONDALIK'tadır. Nokta koşulu tutmaz, üçüncü dal çalışır: “1.2” yazdırılır, nokta atılır ve BASLA'ya dönülür. Ardından “3” ve “7” ayrı sayılar olarak yazdırılır. Sürüm numarası iki sayıya bölünmüştür.

Kusur iki yoldan giderilebilir. Birincisi, yazdırmadan önce tampon nokta ile bitiyorsa son karakteri silmektir. İkincisi, noktayı ancak ardından rakam gelirse sayıya katmaktır; bunun için makineye “nokta görüldü ama henüz kesir rakamı yok” anlamında yeni bir durum eklenir. Aşağıdaki sürüm birinci yolu izler ve noktayı yalnız bir rakamdan sonra kabul eder:

void sayilariBulDuzgun(String s) {
  Durum d = Durum.BASLA;
  StringBuilder tampon = new StringBuilder();
  for (char c : (s + " ").toCharArray()) {        // sona ayırıcı eklenir
    if (Character.isDigit(c)) {
      if (d == Durum.BASLA) d = Durum.RAKAM;
      tampon.append(c);
    } else if (c == '.' && d == Durum.RAKAM) {     // nokta yalnız rakamdan sonra
      d = Durum.ONDALIK;
      tampon.append(c);
    } else if (d != Durum.BASLA) {
      if (tampon.charAt(tampon.length() - 1) == '.')
        tampon.setLength(tampon.length() - 1);     // sondaki nokta sayıya ait değil
      System.out.println(tampon);
      tampon.setLength(0);
      d = Durum.BASLA;
    }
  }
}

Girdinin sonuna bir boşluk eklenmesi, döngüden sonraki ayrı if'i gereksiz kılar: son sayı da boşlukla biter ve aynı dalda yazdırılır. Düzeltilmiş metot “$20.99 ve 5.” için “20.99” ve “5” yazdırır. “v1.2.3 ve 7” için davranış değişmez: “1.2”, “3” ve “7”. Noktanın yalnız rakamdan sonra kabul edilmesinin bir yan etkisi vardır: “.5” gibi baştaki sıfırı yazılmamış bir sayı “5” olarak okunur. Hangi davranışın doğru olduğu uygulamanın kurallarına bağlıdır. FSM tasarımının asıl yararı da budur: her kural bir duruma ya da geçişe karşılık gelir ve açıkça görülür.

5.2.6Düzenleme uzaklığı

Bir arama kutusuna “algortima” yazılır ve arama motoru “algoritma”yı önerir. Bunun için iki kelimenin birbirine ne kadar yakın olduğunu ölçen bir sayıya gerek vardır. Eşitlik denetimi yalnız “aynı” ya da “farklı” der; “bir harf eksik” ile “tamamen başka bir kelime” arasında ayrım yapmaz. Düzenleme uzaklığı bu ayrımı yapar.

5.2.6.1Levenshtein uzaklığı

Ölçü, adını 1965'te bu kavramı tanımlayan Sovyet matematikçi Vladimir Levenshtein'dan alır; makalenin İngilizce çevirisi 1966'da yayımlanmıştır. Genel adı düzenleme uzaklığıdır (edit distance). Bu ad, düzenlemelere farklı maliyetler verilen türleri de kapsar. Kullanım alanları geniştir: yazım denetimi ve otomatik düzeltme, klavyede tahmin, DNA dizilerinin karşılaştırılması ve küçük yazım farklarını hoş gören bulanık (fuzzy) arama.

Üç düzenlemenin her birine bir örnek verilebilir. “sittin” → “sitting”: sona g eklenir. “shine” → “shin”: son e silinir. “kitten” → “sitten”: k, s ile değiştirilir. Bu üç işlem art arda kullanılarak “kitten”, “sitting”e üç adımda dönüştürülür: kitten → sitten (k → s) → sittin (e → i) → sitting (+g).

Üçten kısa bir dönüşüm yoktur. Bunu görmek için her olasılığı denemek gerekmez; dinamik programlama tablosu bunu kanıtlar. Yine de kısa bir gerekçe verilebilir. “sitting”, “kitten”den bir harf uzundur; en az bir ekleme gerekir. İlk harfler (k ve s) farklıdır ve öteki harflerle hizalanarak giderilemez; bir değiştirme daha gerekir. Ortadaki e/i farkı da üçüncü bir işlem ister.

Levenshtein uzaklığı matematiksel anlamda bir metriktir. Üç özelliği vardır. Bir dizginin kendisine uzaklığı sıfırdır: d(a, a) = 0, farklı dizgiler için uzaklık pozitiftir. Uzaklık simetriktir: d(a, b) = d(b, a), çünkü her ekleme tersine çevrilince silme, her değiştirme tersine çevrilince yine değiştirme olur. Üçgen eşitsizliği geçerlidir: d(a, c) ≤ d(a, b) + d(b, c); a'dan b'ye, oradan c'ye giden düzenlemeler art arda uygulanarak a'dan c'ye varılır.

5.2.6.2Düzenleme örnekleri

Bir dönüşümü görmenin en kolay yolu iki dizgiyi alt alta hizalamaktır. Eşit harfler aynı sütuna yazılır. Bir dizgide olup ötekinde olmayan harfin karşısına boşluk konur. Şekil 5.2.23'te HONDA'nın H, N, D, A harfleri HYUNDAI'deki karşılıklarıyla hizalanmıştır. O, Y ile değiştirilir; U ve I'nın karşısında boşluk vardır, bu iki harf eklenir. Toplam üç düzenleme yapılır.

(a) ve (b) birbirinin tersidir. “rain”den “shine”a iki değiştirme ve bir ekleme ile gidilir; “shine”dan “rain”e dönerken aynı iki değiştirme tersine yapılır ve ekleme silmeye dönüşür. İki yön de 3 düzenleme sürer; bu, simetrinin somut bir örneğidir. (c)'de “train” bir harf daha uzundur ve uzaklık 4'tür: t eklenir, s → r ve h → a değiştirilir, sondaki e silinir.

5.2.6.3Dinamik programlama bağıntısı

Bütün düzenleme dizilerini denemek olanaksızdır; sayıları dizgi uzunluğuyla üstel artar. Çözüm, problemi önekler üzerinde küçük alt problemlere bölmektir. a dizgisi m, b dizgisi n karakterli olsun.

Bu, dinamik programlama (dynamic programming, DP) yönteminin tipik bir örneğidir. Her alt problem bir kez çözülür ve (m + 1) × (n + 1) boyutlu bir tabloda saklanır; cevap tablonun sağ alt köşesindedir. Bir hücre yalnız üst, sol ve sol üst komşularına bağlı olduğu için tablo satır satır, her satırda soldan sağa doldurulabilir. Hücre başına sabit iş yapılır. Zaman O(m · n), bellek O(m · n)'dir. Yalnız uzaklık gerekiyorsa bellek iki satıra, yani O(min(m, n))'ye indirilebilir.

5.2.6.4DP tablosu: CARS → PAIRS

a = CARS satırlara, b = PAIRS sütunlara yazılsın. Tablonun 0. satırı ve 0. sütunu boş öneke (ε) karşılık gelir.

Tablo yalnız uzaklığı değil, düzenleme dizisini de verir. Sağ alt köşeden başlanır ve her hücrede değerin hangi komşudan geldiğine bakılarak sol üst köşeye geri yürünür. Bu işleme geri okuma (traceback) denir. D[4][5] = 2, S = S olduğu için çaprazdan gelir. D[3][4] = 2, R = R olduğu için yine çaprazdan gelir. D[2][3] = 2, soldaki D[2][2] = 1'den bir ekleme ile gelir: I eklenir. D[2][2] = 1, A = A ile çaprazdan; D[1][1] = 1, C → P değiştirmesiyle çaprazdan gelir. Kalın hücreler bu yolu gösterir. Sonuç: C → P değiştirme, A eşit, I ekleme, R ve S eşit. Dönüşüm CARS → PARS → PAIRS'tir.

5.2.6.5Java kodu ve kod izleme

Bağıntı doğrudan koda çevrilir:

int levenshtein(String a, String b) {
  int m = a.length(), n = b.length();
  int[][] D = new int[m + 1][n + 1];
  for (int i = 0; i <= m; i++) D[i][0] = i;  // silme
  for (int j = 0; j <= n; j++) D[0][j] = j;  // ekleme
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      if (a.charAt(i - 1) == b.charAt(j - 1))
        D[i][j] = D[i - 1][j - 1];            // eşit
      else
        D[i][j] = 1 + Math.min(D[i - 1][j - 1], // değiştir
                  Math.min(D[i][j - 1],         // ekle
                           D[i - 1][j]));       // sil
  return D[m][n];
}

İlk iki döngü tablonun kenarlarını doldurur. İç içe iki döngü kalan hücreleri satır satır doldurur. Karakterler eşitse sol üst değer kopyalanır; değilse üç komşunun en küçüğüne 1 eklenir. Kod sunumdaki örneklerde şu değerleri verir: kitten → sitting = 3, ercan → sercan = 1 (baştaki s eklenir), apple → banana = 5. Kod “kar” → “ark” çağrısıyla izlensin. a = “kar” satırlara, b = “ark” sütunlara yazılır.

Sonuç 2'dir. Geri okuma D[3][3]'ten başlar. Değer, soldaki D[3][2] = 1'den bir ekleme ile gelmiştir: sona k eklenir. D[3][2], r = r ile D[2][1]'den, o da a = a ile D[1][0] = 1'den gelir. D[1][0] ise k'nin silinmesidir. İki karakterin değiştirilmesi de 2 düzenleme sürerdi, ama “kar” ile “ark”ın son iki ve ilk iki harfi zaten ortak olduğundan silme–ekleme yolu doğaldır.

Bu örnek, Levenshtein uzaklığının harf takasını tek işlem saymadığını da hatırlatır. “saat” → “asat” dönüşümünde ilk iki harf yer değiştirmiştir; uzaklık 2'dir. İki komşu harfin takasını tek işlem sayan ölçünün adı Damerau–Levenshtein uzaklığıdır. Yazım hatalarının önemli bir kısmı komşu harf takası olduğu için yazım denetleyicileri bu türü sık kullanır.

5.2.6.6İki satırlık bellek

Bir satırı doldurmak için yalnız bir önceki satır gerekir. Yalnız uzaklık isteniyorsa bütün tabloyu saklamak gereksizdir. İki dizi yeter: onceki ve simdi. Her satır bitince iki dizi yer değiştirir.

int levenshteinIkiSatir(String a, String b) {
  if (a.length() < b.length()) { String t = a; a = b; b = t; }  // b kısa olan
  int n = b.length();
  int[] onceki = new int[n + 1], simdi = new int[n + 1];
  for (int j = 0; j <= n; j++) onceki[j] = j;
  for (int i = 1; i <= a.length(); i++) {
    simdi[0] = i;
    for (int j = 1; j <= n; j++)
      if (a.charAt(i - 1) == b.charAt(j - 1))
        simdi[j] = onceki[j - 1];
      else
        simdi[j] = 1 + Math.min(onceki[j - 1], Math.min(simdi[j - 1], onceki[j]));
    int[] t = onceki; onceki = simdi; simdi = t;   // satırlar yer değiştirir
  }
  return onceki[n];
}

Metot önce kısa dizgiyi b yapar; böylece dizilerin uzunluğu min(m, n) + 1 olur. simdi[0] = i kenar değeridir. İç döngü aynı bağıntıyı uygular: sol üst onceki[j − 1], üst onceki[j], sol simdi[j − 1]'dir. Satır bitince başvurular takas edilir ve yeni satır onceki olur. Döngüden sonra cevap onceki[n]'dedir. Metot, sunumdaki bütün örneklerde tam tabloyla aynı sonucu verir.

Kazanç büyüktür. İki dizgi 10.000'er karakter olsun. Tam tablo 10.001² ≈ 10⁸ tam sayı, yani yaklaşık 400 MB tutar. İki satırlık sürüm 2 · 10.001 tam sayı, yaklaşık 80 KB kullanır. Zaman yine O(m · n)'dir. Bedeli, geri okumanın artık yapılamamasıdır; düzenleme dizisi de isteniyorsa tam tablo ya da daha ileri bir teknik (Hirschberg algoritması) gerekir.

5.2.6.7Öteki benzerlik ölçüleri

Levenshtein tek benzerlik ölçüsü değildir. Problemin yapısına göre daha basit ya da farklı bir ölçü daha uygun olabilir. Tablo 5.2.21 dört ölçüyü aynı dizgi çifti, AGGTAB ve GXTXAYB üzerinde karşılaştırır.

Hamming uzaklığı yalnız eşit uzunluktaki dizgiler için tanımlıdır ve karşılıklı konumlardaki farklı karakterleri sayar. Tek bir geçişle, O(n) zamanda hesaplanır. Örneğin “karolin” ile “kathrin”in Hamming uzaklığı 3'tür (r/t, o/h, l/r). Hamming ölçüsü, kayıp ya da fazla karakterin olmadığı durumlar için uygundur: sabit uzunluklu ikili kodlar, iletişimde bit hataları.

int hamming(String a, String b) {
  if (a.length() != b.length())
    throw new IllegalArgumentException("uzunluklar farklı");
  int d = 0;
  for (int i = 0; i < a.length(); i++)
    if (a.charAt(i) != b.charAt(i)) d++;
  return d;
}

Eşit uzunluktaki iki dizgi için Levenshtein uzaklığı Hamming uzaklığını aşamaz. Hamming'in saydığı her farklı konum bir değiştirmeyle düzeltilir; bu, Levenshtein'a izin verilen bir dönüşümdür. Levenshtein ise ekleme ve silmeyi de kullanarak bazen daha kısa bir yol bulur. “karolin” · “kathrin” çiftinde iki ölçü de 3'tür.

AGGTAB ile GXTXAYB'nin LCS'si GTAB'dir. G, T, A, B harfleri iki dizgide de bu sırayla geçer: AGGTAB'de 2., 4., 5., 6. konumlarda; GXTXAYB'de 1., 3., 5., 7. konumlarda. Arada başka harfler bulunması önemli değildir. En uzun ortak alt dizgi ise yalnız 1 karakterliktir: iki dizgide de ardışık geçen iki harflik bir parça yoktur. LCS de Levenshtein'a benzer bir DP tablosuyla bulunur:

int lcs(String a, String b) {
  int m = a.length(), n = b.length();
  int[][] L = new int[m + 1][n + 1];             // 0. satır ve sütun 0
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      if (a.charAt(i - 1) == b.charAt(j - 1))
        L[i][j] = L[i - 1][j - 1] + 1;           // çapraz + 1
      else
        L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
  return L[m][n];
}

Bağıntı şudur: karakterler eşitse L[i][j] = L[i−1][j−1] + 1, yani çapraz değere 1 eklenir; eşit değilse L[i][j] = max(L[i−1][j], L[i][j−1]). Levenshtein en küçüğü ararken LCS en büyüğü arar. Metot AGGTAB · GXTXAYB için 4, CARS · PAIRS için 3 (ARS), kitten · sitting için 4 (ittn) döndürür.

LCS ile düzenleme uzaklığı arasında basit bir bağ vardır. Yalnız ekleme ve silmeye izin verilirse, değiştirme yasaklanırsa, uzaklık m + n − 2 · LCS olur. LCS'ye girmeyen her karakter ya silinir ya eklenir. AGGTAB · GXTXAYB için bu 6 + 7 − 8 = 5'tir. Değiştirmeye de izin veren Levenshtein bir silme ile bir eklemeyi tek değiştirmede birleştirerek uzaklığı 4'e indirir.

En uzun ortak alt dizgi için bağıntı daha da basittir. Karakterler eşitse L[i][j] = L[i−1][j−1] + 1; eşit değilse L[i][j] = 0, çünkü ardışıklık bozulmuştur. Cevap sağ alt köşede değil, tablonun en büyük değerindedir:

String enUzunOrtakAltDizgi(String a, String b) {
  int m = a.length(), n = b.length(), enIyi = 0, bitis = 0;
  int[][] L = new int[m + 1][n + 1];
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      if (a.charAt(i - 1) == b.charAt(j - 1)) {
        L[i][j] = L[i - 1][j - 1] + 1;           // ardışık parça uzar
        if (L[i][j] > enIyi) { enIyi = L[i][j]; bitis = i; }
      }                                          // eşleşmezse 0 kalır
  return a.substring(bitis - enIyi, bitis);
}

Metot “ercan” · “sercan” için “ercan”ı, kitten · sitting için “itt”yi döndürür. Eşit uzunlukta birden çok parça varsa ilk bulunanı verir; AGGTAB · GXTXAYB çiftinde “A” döner. Kopya metin tespiti ve iki dosyanın ortak bloklarını bulma bu ölçünün kullanıldığı yerlerdir.

Uzaklıklar, karşılaştırılabilir bir benzerlik oranına da çevrilebilir. Yaygın bir tanım 1 − d / max(m, n)'dir: özdeş dizgilerde 1, hiç ortak yanı olmayanlarda 0'a yakın bir değer verir. kitten · sitting için bu 1 − 3/7 ≈ 0,57'dir. Bir yazım denetleyicisi, örneğin benzerliği 0,7'nin üstündeki sözlük kelimelerini öneri olarak gösterebilir.

5.2.7Sonek dizisi

Bir metinde aynı örüntü birçok kez aranacaksa her aramada metni baştan taramak pahalıdır. Kitapların sonundaki dizin bu sorunu çözer: kelimeler sıralı bir listede durur ve her birinin geçtiği sayfalar yanında yazılıdır. Sonek dizisi, bir metnin bütün alt dizgileri için böyle bir dizin kurar.

5.2.7.1Tanım

“banana”nın altı soneki vardır. Sıralandıklarında “a” en öne gelir, çünkü “ana” ve “anana”nın önekidir. Ardından “ana”, “anana”, “banana”, “na”, “nana” gelir. Sonek dizisi SA = [5, 3, 1, 0, 4, 2]'dir. Dizide sonekler değil, yalnız başlangıç indisleri saklanır. Sonekin kendisi gerektiğinde t.substring(SA[k]) ile elde edilir.

Sonek dizisinin gücü basit bir gözleme dayanır: bir dizginin her alt dizgisi, bir sonekin önekidir. “nan” alt dizgisi, 2 konumundan başlayan “nana” sonekinin önekidir. Bu yüzden bir örüntünün metinde nerede geçtiğini bulmak, o örüntüyle başlayan sonekleri bulmak demektir. Sonekler sıralı olduğundan bu sonekler listede yan yana durur.

Aynı işi yapan daha eski bir yapı sonek trie'sidir: bütün sonekleri bir trie'ye ekleyen ağaç. Sonek trie'si çok hızlı arama yapar, ama düğüm sayısı farklı alt dizgi sayısıyla orantılıdır ve en kötü durumda O(n²)'dir. “banana” gibi altı harflik bir dizginin bile 15 farklı alt dizgisi, dolayısıyla kökle birlikte 16 düğümü vardır. Sonek dizisi ise yalnız n tam sayı tutar: O(n) bellek. Dizgi arama, sıralama, genetik dizilim analizi, BWT ve veri sıkıştırma sonek dizisinin başlıca kullanım alanlarıdır.

5.2.7.2Oluşturma yöntemleri

Sonek dizisini kurmanın en kolay yolu, bütün sonekleri bir karşılaştırmalı sıralamayla sıralamaktır:

int[] sonekDizisi(String t) {        // kaba kuvvet: O(n² log n)
  int n = t.length();
  Integer[] ix = new Integer[n];
  for (int i = 0; i < n; i++) ix[i] = i;
  Arrays.sort(ix, (x, y) -> t.substring(x).compareTo(t.substring(y)));
  int[] sa = new int[n];
  for (int i = 0; i < n; i++) sa[i] = ix[i];
  return sa;
}

Bu kaba kuvvet yöntemi O(n log n) karşılaştırma yapar. Her karşılaştırma iki soneki karakter karakter okur ve en kötü durumda O(n) sürer; ayrıca substring her çağrıda yeni bir dizgi kopyalar. Toplam zaman O(n² log n)'dir. Kısa metinlerde yeterlidir, ama birkaç milyon karakterlik bir genom dizisinde kullanılamaz. Daha hızlı yöntemler, sonekleri karakter karakter karşılaştırmaktan kaçınır.

Önek ikiye katlama yöntemleri O(n log n) zamanlıdır, doğrusal değildir. Doğrusal zamanlı kurulum ancak DC3 ve SA-IS gibi sonraki algoritmalarla mümkün olmuştur. SA-IS bugün pratikte de en hızlı yöntemlerden biridir ve birçok biyoinformatik aracında kullanılır.

5.2.7.3Önek ikiye katlama

Manber ve Myers'ın fikri şudur. Önce sonekler yalnız ilk karakterlerine göre sıralanır ve her sonekin bir sırası (rank) belirlenir: ilk karakteri aynı olan soneklerin sırası da aynıdır. Sonra ilk iki karaktere, ilk dört karaktere, ilk sekiz karaktere göre sıralanır. Her turda bakılan önek uzunluğu ikiye katlanır. Bir turu hızlandıran gözlem şudur: i. sonekin ilk 2k karakteri, iki parçadan oluşur. İlk k karakter i'de, sonraki k karakter i + k'da başlayan sonekin önekidir. İkisinin de k karakterlik sırası önceki turdan bilinir. Bu yüzden 2k karakterlik sıralama, harf karşılaştırmadan, (sıra[i], sıra[i + k]) sayı çiftleri sıralanarak yapılır.

Üçüncü turdaki bir satır yöntemi özetler. 3'te başlayan “ana” ile 1'de başlayan “anana”nın ilk iki karakteri aynıdır; ikisinin de 2 karakterlik sırası 1'dir. Fark sonraki iki karakterdedir: 3 + 2 = 5'te başlayan “a”nın sırası 0, 1 + 2 = 3'te başlayan “an…”ın sırası 1'dir. (1, 0) < (1, 1) olduğu için “ana”, “anana”dan önce gelir. Hiçbir harf yeniden okunmamıştır.

Tur sayısı en çok ⌈log₂ n⌉'dir, çünkü 2^k ≥ n olduğunda bakılan önek her soneki baştan sona kapsar ve bütün sıralar farklı olmak zorundadır. Her turda n sayı çifti iki geçişli basamak sıralamasıyla O(n)'de sıralanabilir. Toplam süre O(n log n)'dir. Aşağıdaki sürüm fikri anlaşılır kılmak için sayı çiftlerini Arrays.sort ile sıralar; bu yüzden her tur O(n log n), toplam O(n log² n) sürer:

int[] onekKatla(String t) {          // önek ikiye katlama (sıralama Arrays.sort ile)
  int n = t.length();
  Integer[] sa = new Integer[n];
  int[] sira = new int[n], yeni = new int[n];
  for (int i = 0; i < n; i++) { sa[i] = i; sira[i] = t.charAt(i); }
  for (int k = 1; ; k *= 2) {
    final int kk = k;
    final int[] r = sira;
    Comparator<Integer> cmp = (x, y) -> {
      if (r[x] != r[y]) return Integer.compare(r[x], r[y]);
      int rx = x + kk < n ? r[x + kk] : -1, ry = y + kk < n ? r[y + kk] : -1;
      return Integer.compare(rx, ry);
    };
    Arrays.sort(sa, cmp);            // anahtar: (sira[i], sira[i + k])
    yeni[sa[0]] = 0;
    for (int i = 1; i < n; i++)
      yeni[sa[i]] = yeni[sa[i - 1]] + (cmp.compare(sa[i - 1], sa[i]) < 0 ? 1 : 0);
    System.arraycopy(yeni, 0, sira, 0, n);
    if (sira[sa[n - 1]] == n - 1) break;   // bütün sıralar farklı
  }
  int[] s = new int[n];
  for (int i = 0; i < n; i++) s[i] = sa[i];
  return s;
}

sira dizisi başlangıçta karakter kodlarını tutar. Her turda cmp karşılaştırıcısı önce sira[x], eşitse sira[x + k] değerine bakar. Sıralamadan sonra yeni sıralar verilir: bir sonek kendinden öncekinden farklıysa sırası bir artar, değilse aynı kalır. En son sonekin sırası n − 1 olduğunda bütün sıralar farklıdır ve döngü biter. Metot “banana” için [5, 3, 1, 0, 4, 2], “mississippi” için [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] döndürür; ikisi de kaba kuvvetle aynıdır.

5.2.7.4Sonek dizisiyle arama

Sonekler sıralı olduğundan bir P örüntüsüyle başlayan sonekler SA'da bitişik bir aralık oluşturur. Aralığın iki ucu ikili aramayla bulunur. İlk uç, P'den küçük olmayan ilk sonektir. İkinci uç, bu noktadan sonra P ile başlamayan ilk sonektir.

int[] ara(String t, int[] sa, String p) {
  int lo = 0, hi = sa.length;
  while (lo < hi) {   // ilk >= p
    int mid = (lo + hi) / 2;
    if (t.substring(sa[mid])
          .compareTo(p) < 0) lo = mid + 1;
    else hi = mid;
  }
  int bas = lo;
  hi = sa.length;
  while (lo < hi) {   // p ile başlamayan
    int mid = (lo + hi) / 2;
    if (t.startsWith(p, sa[mid]))
      lo = mid + 1;
    else hi = mid;
  }
  return new int[] { bas, lo };
}

İlk döngü klasik bir “alt sınır” ikili aramasıdır. Ortadaki sonek P'den küçükse aranan uç sağdadır: lo = mid + 1. Değilse uç mid'de ya da solundadır: hi = mid. Döngü bittiğinde lo, P'den küçük olmayan ilk sonekin sırasıdır ve bas'a yazılır. İkinci döngü lo'yu olduğu yerde bırakıp hi'yi dizinin sonuna çeker. Bu kez soru “bu sonek P ile başlıyor mu?”dur. Başlıyorsa aralığın sonu sağdadır. Döngü bittiğinde lo, aralığın hemen sonrasını gösterir. Metot yarı açık [bas, lo) aralığını döndürür.

Sonuç [1, 3)'tür: sıra 1 ve 2. Bu sıralardaki SA değerleri 3 ve 1'dir. “an”, “banana” içinde 1 ve 3 konumlarında geçer. Toplam 5 karşılaştırma yapılmıştır. Her ikili arama en çok ⌊log₂ 6⌋ + 1 = 3 karşılaştırma yapar. Her karşılaştırma ise en çok m = |P| karakter okur. Toplam zaman O(m log n)'dir. Bir milyar karakterlik bir metinde bile her arama yaklaşık 60 sonek karşılaştırmasıyla biter.

Sonek dizisinin yanına bir LCP dizisi (longest common prefix) eklenirse daha fazla soru cevaplanır. LCP dizisi, sıralı listede komşu iki sonekin en uzun ortak önekinin uzunluğunu tutar. “banana” için “a” ile “ana”nın ortak öneki 1, “ana” ile “anana”nınki 3 karakterdir. Metinde iki kez geçen en uzun alt dizgi, LCP dizisinin en büyük değeridir. “banana”da bu “ana”dır ve LCP dizisinin bir taramasıyla, O(n)'de bulunur.

5.2.8Burrows–Wheeler dönüşümü

Sıkıştırma algoritmaları tekrarlardan beslenir: “AAAAA”, “A” harfinin beş kez yazıldığı bilgisiyle kısaltılabilir. Ama doğal metinde aynı harfler genellikle yan yana durmaz. Burrows–Wheeler dönüşümü harflerin yerini, aynı harfler bir araya toplanacak biçimde değiştirir. Üstelik bunu geri alınabilir biçimde yapar.

5.2.8.1Tanım ve adımlar

Bir döndürme, dizginin ilk karakterinin sona taşınmasıyla elde edilir; bu işlem n kez yapılınca dizgi başa döner. n karakterlik bir dizginin n döndürmesi vardır. BWT karakterleri değiştirmez, yalnız yerlerini değiştirir: L sütunu, s'nin harflerinin bir başka sıralamasıdır. Dönüşümü Michael Burrows ve David Wheeler 1994'te bir teknik raporla yayımladı.

Şekil 5.2.32'deki küçük örnekte “aba$”ın dört döndürmesi aba$, ba$a, a$ab ve $aba'dır. $ en küçük karakter olduğu için sıralı listede $aba en öne geçer; ardından a$ab, aba$ ve ba$a gelir. Son karakterler a, b, $, a'dır: L = “ab$a”. Sıralı listenin ilk sütunu ise F sütunudur: $, a, a, b.

5.2.8.2Örnekler: BANANA ve abraca

BWT'nin harfleri nasıl gruplandırdığı “BANANA” örneğinde açıkça görülür. Bu örnekte $ kullanılmaz; orijinal satırın numarası saklanır.

Döndürmeler BANANA, ANANAB, NANABA, ANABAN, NABANA ve ABANAN'dır. Sıralı liste ABANAN, ANABAN, ANANAB, BANANA, NABANA, NANABA'dır. Son karakterler N, N, B, A, A, A'dır. Çıktı (NNBAAA, 3) olur. Orijinal dizgide hiçbir harf komşusuyla aynı değildi; dönüşümden sonra iki N ve üç A yan yana gelmiştir.

Gruplanmanın nedeni sıralamanın yapısıdır. Sıralı listede, aynı karakterlerle başlayan döndürmeler yan yana durur. Örneğin “ANA…” ile başlayan iki döndürme komşudur. L sütunu, her döndürmenin ilk karakterinden hemen önce gelen karakteri tutar. Doğal metinde aynı bağlamdan önce genellikle aynı karakter gelir: İngilizcede “he” bağlamından önce çoğu zaman t gelir (the), Türkçede “ğı” bağlamından önce çoğu zaman a gelir (ağı, dağı). Benzer bağlamlar sıralamada bir araya gelince onlardan önce gelen aynı karakterler de L'de yan yana düşer.

“abraca” için sıralı döndürmeler aabrac, abraca, acaabr, bracaa, caabra, racaab'dır. Son sütun L = “caraab”'dır. Orijinal “abraca” sıralı matriste 0'dan sayarak 1 numaralı satırdadır; ters dönüşüm için bu indis saklanır. İlk sütun F = aaabcr'dir ve L'nin harflerinin sıralanmış hâlidir. Bu her zaman doğrudur: her döndürme aynı harfleri içerdiğinden F ve L aynı harf çoklu kümesini taşır, F ise sıralıdır. L bilindiğinde F'yi bulmak için L'yi sıralamak yeter.

Doğrudan yöntem n döndürmeyi açıkça üretip sıralar:

String bwt(String s) {               // doğrudan yöntem; s sonunda $ var
  int n = s.length();
  String[] dondurme = new String[n];
  for (int i = 0; i < n; i++)
    dondurme[i] = s.substring(i) + s.substring(0, i);
  Arrays.sort(dondurme);             // O(n² log n) zaman, O(n²) bellek
  StringBuilder L = new StringBuilder();
  for (String r : dondurme) L.append(r.charAt(n - 1));
  return L.toString();
}

Bu yöntem O(n²) bellek kullanır, çünkü n döndürmenin her biri n karakterdir. Sıralama O(n log n) karşılaştırma yapar ve her karşılaştırma O(n) sürebilir: toplam O(n² log n) zaman. Bir megabaytlık bir blok için 10¹² karakterlik bir matris gerekir; bu açıkça uygulanamaz. Pratikte BWT sonek dizisinden hesaplanır. Metnin sonunda $ varsa döndürmelerin sırası soneklerin sırasıyla aynıdır. İki döndürme en geç $'a gelince ayrışır; $'dan sonrası karşılaştırmaya katılmaz. k. sıralı döndürme SA[k]'da başlar; son karakteri ondan hemen önceki karakterdir. Bu yüzden L[k] = T[SA[k] − 1]'dir; SA[k] = 0 ise L[k] = $'dır. Sonek dizisi doğrusal zamanda kurulursa BWT de O(n)'de elde edilir.

5.2.8.3Tersine çevirme: LF eşlemesi

BWT'nin asıl şaşırtıcı yanı, yalnız L sütunundan (ve $'dan ya da satır indisinden) orijinal metnin geri elde edilebilmesidir. Örnek olarak T = “banana$” alınsın. $ en küçük ve tekil karakterdir.

BWT çıktısı L = “annb$aa”'dır. F, L'nin sıralanmış hâlidir: F = “$aaabnn”. Her satır bir döndürme olduğundan, satırın son karakteri L[i], metinde ilk karakter F[i]'den hemen önce gelir. Ters dönüşüm bu komşuluğu zincirleme kullanır. Eksik olan tek bilgi, L'deki bir karakterin F'de hangi satıra karşılık geldiğidir. Aynı harf birden çok kez geçtiğinde bu açık değildir. Aşağıdaki teorem bu belirsizliği giderir.

Ters dönüşüm artık basittir. $ ile başlayan satır 0'dır; bu satır metnin kendisinin bir döndürmesidir ve son karakteri L[0], metnin $'dan önceki son karakteridir. L[0] okunur ve LF(0) satırına gidilir. O satırın L'deki karakteri metinde bir önceki karakterdir. Bu yürüyüş sürdürüldükçe metin sondan başa doğru okunur. “banana$” için satırlar 0 → 1 → 5 → 2 → 6 → 3 → 4 sırasıyla gezilir. Okunan L karakterleri a, n, a, n, a, b'dir. Ters çevrilince “banana” elde edilir.

Sıra sayıları ve C tablosu önceden bir geçişte hesaplanırsa her adım sabit zamanlıdır ve ters dönüşüm O(n) sürer. Metinde $ yoksa, BANANA örneğinde olduğu gibi orijinal satır indisi (3) saklanır ve yürüyüş 0 yerine o satırdan başlatılır.

5.2.8.4Kod izleme: bwtTers

String bwtTers(String L) {   // $ ile
  int n = L.length();
  int[] sira = new int[n];
  int[] say = new int[256];
  int[] C = new int[256];
  for (int i = 0; i < n; i++)
    sira[i] = say[L.charAt(i)]++;
  for (int c = 1; c < 256; c++)
    C[c] = C[c - 1] + say[c - 1];
  StringBuilder s = new StringBuilder();
  int i = 0;                   // $ satırı
  for (int k = 0; k < n - 1; k++) {
    char c = L.charAt(i);
    s.insert(0, c);
    i = C[c] + sira[i];        // LF(i)
  }
  return s.toString();
}

Metot dört bölümden oluşur. İlk döngü her i için sira[i]'yi hesaplar: say[c], o ana kadar L'de kaç c görüldüğünü tutar ve sonra bir artar. İkinci döngü C tablosunu bir önek toplamıyla kurar: C[c], c'den küçük bütün karakterlerin sayısıdır. Üçüncü bölüm yürüyüştür. i = 0, yani $ satırından başlanır. Her adımda L.charAt(i) okunur ve oluşan metnin başına eklenir (s.insert(0, c)); metin sondan başa doğru okunduğu için ters çevirmeye gerek kalmaz. Sonra i, LF(i)'ye güncellenir. Döngü n − 1 tur sürer; $ metne eklenmez.

Hazırlık adımlarının sonuçları şunlardır. sıra = [0, 0, 1, 0, 0, 1, 2]: L'deki a'lar (0, 5, 6 konumları) 0, 1, 2 sırasını, n'ler (1, 2) 0, 1 sırasını alır; b ve $ tek oldukları için 0'dır. C tablosu: C[$] = 0, C[a] = 1, C[b] = 4, C[n] = 5. Bu değerler F sütununda her harfin başladığı satırlardır.

Altıncı turdan sonra i = 4'tür. 4 numaralı satırın L karakteri $'dır; bu satır “banana$”ın kendisidir ve yürüyüş başa dönmüştür. Döngü tam bu noktada sona erer. Zaman O(n + R), ek bellek sira, say ve C dizileri için O(n + R)'dir. Bir uygulama ayrıntısı vardır: s.insert(0, c) her çağrıda bütün dizgiyi kaydırdığı için aslında O(n) sürer. Büyük girdilerde karakterler bir diziye sondan başa yazılır ya da sona eklenip en sonda bir kez ters çevrilir.

5.2.8.5Sıkıştırmadaki yeri

BWT kendi başına bir sıkıştırma değildir; çıktı girdiyle aynı uzunluktadır. Sıkıştırmaya hazırlık yapar. Yaygın bzip2 programı BWT'yi dört aşamalı bir zincirin başında kullanır:

1. BWT. Metin bloklara bölünür ve her bloğun dönüşümü alınır. Aynı harfler bir araya toplanır.
2. Öne taşı (move-to-front, MTF). Her karakter, bir listedeki konumuyla kodlanır ve sonra listenin başına taşınır. Yakın zamanda görülen harfler küçük sayılarla kodlanır; art arda gelen aynı harfler 0'lara dönüşür.
3. Sıralı sıkıştırma kodlaması (run-length encoding, RLE). Art arda gelen aynı değerler (değer, tekrar sayısı) çiftiyle yazılır. MTF'nin ürettiği uzun 0 dizileri burada kısalır.
4. Huffman kodlaması. Sık görülen değerlere kısa, seyrek görülenlere uzun bit dizileri verilir.

Zincirin her halkası bir öncekinin hazırladığı yapıdan yararlanır. BWT olmadan MTF'nin çıktısında bu kadar çok 0 bulunmaz; MTF olmadan RLE uzun tekrarlar bulamaz. BWT ayrıca biyoinformatikte de önemlidir. FM-index adı verilen yapı, BWT ile LF eşlemesini birleştirerek milyarlarca harflik bir genomda kısa okumaları sıkıştırılmış veri üzerinde arar.

5.2.9Sık yapılan hatalar

Notun içine dağılmış uyarılar ve sunumdaki hata listesi burada bir arada toplanır.

5.2.10Özet

• Sözlüksel sıra: ilk farklı karakter karar verir; bir dizgi ötekinin önekiyse kısa olan önce gelir. Bilgisayar karakter kodlarını kullanır: büyük harfler küçüklerden önce, Türkçe harfler z'den sonra gelir. Bir karşılaştırma O(W) sürer.
• Karşılaştırmalı sıralama: basit yöntemle O(N² · W), birleştirme sıralamasıyla O(W · N log N). Karşılaştırmaya dayanan her yöntem Ω(N log N) karşılaştırma yapar.
• LSD basamak sıralaması: sağdan sola, her geçişte o karaktere göre kararlı saymalı sıralama; O(W · (N + R)) zaman, O(N + R) bellek. Doğruluğu, “k geçişten sonra son k karaktere göre sıralı” değişmezine ve kararlılığa dayanır.
• MSD basamak sıralaması: soldan sağa, her kova ayrı ayrı özyinelemeli sıralanır; yalnız ayırt edici önekler okunur. Küçük kovalarda eklemeli sıralamaya geçilir.
• Düzenli ifadeler: . * + ? [ ] ^ $ ( ) { } | ve \d \w \s \b; niceleyiciler varsayılan olarak açgözlüdür, ? eklenince tembel olur. Bakış ifadeleri bir konumu sınar, karakter tüketmez. Java'da Pattern/Matcher; find parça, matches bütün dizgi arar.
• Sonlu durum makinesi: (Q, Σ, δ, q₀, F). DFA'da her (durum, sembol) için tek geçiş vardır ve tarama O(n)'dir. DFA, NFA ve düzenli ifadeler aynı dilleri tanır; alt küme kurulumu en kötü 2ⁿ durum üretir.
• Örüntü eşleme otomatı: durum, metnin sonunda örüntüyle uyuşan en uzun önekin uzunluğudur. Kurulum O(m · |Σ|), arama O(n); KMP'nin otomat biçimidir.
• Levenshtein: eşitse sol üst, değilse 1 + min(sil, ekle, değiştir); O(m · n) zaman. Düzenleme dizisi tablodan geri okunur; yalnız uzaklık için iki satır yeter.
• Öteki ölçüler: Hamming eşit uzunlukta, O(n). LCS ve en uzun ortak alt dizgi O(m · n). Yalnız ekleme ve silmeyle uzaklık m + n − 2 · LCS'dir.
• Sonek dizisi: sıralı soneklerin başlangıç indisleri; O(n) bellek. Kaba kuvvetle O(n² log n), önek ikiye katlamayla O(n log n), SA-IS ile O(n) kurulur. Arama iki ikili aramayla O(m log n).
• BWT: sıralı döndürmelerin son sütunu ve satır indisi (ya da $). Aynı harfleri gruplar; LF eşlemesiyle O(n)'de geri çevrilir. bzip2'nin ilk adımıdır: BWT → öne taşı → RLE → Huffman.

5.2.11Kavram listesi

• dizgi string
• alfabe alphabet
• önek prefix
• sonek suffix
• alt dizgi substring
• sözlüksel sıra lexicographic order
• kararlı sıralama stable sort
• saymalı sıralama counting sort
• basamak sıralaması radix sort
• LSD / MSD basamak sıralaması LSD / MSD radix sort
• düzenli ifade regular expression
• niceleyici quantifier
• ileri / geri bakış lookahead / lookbehind
• sonlu durum makinesi finite state machine (FSM)
• deterministik sonlu otomat deterministic finite automaton (DFA)
• alt küme kurulumu subset construction
• tuzak durum trap state
• düzenleme uzaklığı edit distance
• Levenshtein uzaklığı Levenshtein distance
• dinamik programlama dynamic programming
• geri okuma traceback
• en uzun ortak alt dizi longest common subsequence (LCS)
• en uzun ortak alt dizgi longest common substring
• sonek dizisi suffix array
• önek ikiye katlama prefix doubling
• Burrows–Wheeler dönüşümü Burrows–Wheeler transform (BWT)
• öne taşı move-to-front (MTF)

5.2.12Kendini Dene

1. {"kedi", "Kedi", "kediler", "ked", "kafa", "çay"} dizisi Arrays.sort ile sıralanınca sonuç nedir? Türkçe sözlük sırasından farkı nerededir?

   Cevap

   Sonuç Kedi, kafa, ked, kedi, kediler, çay'dır. 'K' (75) bütün küçük harflerden önce gelir. “kafa”, ikinci karakterde a < e ile öne geçer. “ked”, “kedi”nin, “kedi” de “kediler”in önekidir. 'ç' (231) z'den bile büyük olduğu için “çay” en sona düşer. Türkçe sözlükte ise “çay” k ile başlayanlardan öncedir ve “Kedi” ile “kedi” yan yana gelir.

2. dog, cat, dot, cab, cog dizgilerine LSD basamak sıralaması uygulanırsa her geçişten sonra dizi nasıl olur?

   Cevap

   3. karaktere göre: cab, dog, cog, cat, dot (b < g < t; dog ve cog giriş sırasını korur). 2. karaktere göre: cab, cat, dog, cog, dot (a kovasında cab, cat; o kovasında dog, cog, dot önceki sırayla). 1. karaktere göre: cab, cat, cog, dog, dot.

3. ^[A-Z]\d{2,3}[a-z]?$ ifadesi “A12”, “B1234”, “c123”, “Z999x” ve “Q7y” dizgilerinden hangileriyle matches anlamında eşleşir?

   Cevap

   Yalnız “A12” ve “Z999x”. İfade bir büyük harf, iki ya da üç rakam ve isteğe bağlı tek bir küçük harf ister. “B1234”te dört rakam vardır. “c123” küçük harfle başlar. “Q7y”de tek rakam vardır.

4. (?<=a)b örüntüsü “abcabb” metninde hangi konumlarda eşleşir? “abbb” metninde b+ ve b+? ile find döngüsü hangi parçaları bulur?

   Cevap

   Geri bakış, önünde a bulunan b'leri seçer: 1 ve 4 konumları. 5'teki b'nin önünde b vardır. Bakış karakter tüketmediği için iki eşleşmenin metni de yalnız “b”dir. “abbb” metninde açgözlü b+ tek eşleşme olarak “bbb”yi bulur. Tembel b+? her seferinde tek b alır ve üç ayrı “b” eşleşmesi verir.

5. “aab” örüntüsü için örüntü eşleme otomatının geçiş tablosu (alfabe {a, b}) nasıldır? “aaab” metni okunurken durumlar nasıl değişir ve örüntü nerede bulunur?

   Cevap

   Durum 0: a → 1, b → 0. Durum 1: a → 2, b → 0. Durum 2: a → 2, b → 3. Durum 3: a → 1, b → 0. Durum 2'de a gelirse okunanların sonu “aaa” olur ve en uzun uyan önek yine “aa”dır; bu yüzden 2'de kalınır. “aaab” için durumlar 1, 2, 2, 3'tür. Durum 3'e 3 numaralı karakterde ulaşılır; örüntü 3 − 3 + 1 = 1 konumunda başlar.

6. levenshtein("kitap", "katip") kaçtır? Tablonun son satırı nedir ve hangi düzenleme dizisi bu uzaklığı verir?

   Cevap

   Uzaklık 2'dir. Son satır (p) 5, 4, 3, 3, 3, 2'dir. k, t ve p iki dizgide aynı konumlardadır; yalnız 2. ve 4. harfler farklıdır. Bir çözüm iki değiştirmedir: i → a (katap), a → i (katip).

7. “ABCBDAB” ile “BDCABA” için LCS uzunluğu, yalnız ekleme ve silmeyle uzaklık ve Levenshtein uzaklığı kaçtır?

   Cevap

   LCS uzunluğu 4'tür (ör. BCBA). Yalnız ekleme ve silmeyle uzaklık 7 + 6 − 2 · 4 = 5'tir. Levenshtein uzaklığı da 5'tir; bu çiftte değiştirmeler daha kısa bir yol sağlamaz.

8. “abaab” dizgisinin sonek dizisi nedir? “ab” ile başlayan sonekler hangi sıralardadır ve örüntü metinde hangi konumlarda geçer?

   Cevap

   Sıralı sonekler aab, ab, abaab, b, baab'dır; SA = [2, 3, 0, 4, 1]. “ab” ile başlayanlar sıra 1 (ab) ve sıra 2'dir (abaab). SA değerleri 3 ve 0 olduğu için “ab” metinde 0 ve 3 konumlarında geçer.

9. “abab$” dizgisinin BWT'si nedir ve LF eşlemesiyle nasıl geri çevrilir?

   Cevap

   Sıralı döndürmeler $abab, ab$ab, abab$, b$aba, bab$a'dır; L = “bb$aa”. F = “$aabb”, C[$] = 0, C[a] = 1, C[b] = 3; sıra sayıları 0, 1, 0, 0, 1'dir. Yürüyüş 0'dan başlar: L[0] = b, LF = 3; L[3] = a, LF = 1; L[1] = b, LF = 4; L[4] = a, LF = 2. 2 numaralı satırın L karakteri $'dır ve yürüyüş durur. Okunanlar b, a, b, a'dır; başa eklenerek “abab” elde edilir.

10. İkili dizgilerde “00” ile bitenleri kabul eden bir DFA nasıl kurulur? “10100” girdisi hangi durumlardan geçer?

    Cevap

    Üç durum yeter: q₀ (son sembol 0 değil ya da girdi boş; başlangıç), q₁ (son sembol tek bir 0) ve q₂ (son iki sembol 00; kabul). Geçişler: q₀: 0 → q₁, 1 → q₀; q₁: 0 → q₂, 1 → q₀; q₂: 0 → q₂, 1 → q₀. “10100” için yol q₀ → q₀ → q₁ → q₀ → q₁ → q₂'dir ve dizgi kabul edilir.

5.2.13İleri okuma

• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Bölüm 5: dizgi sıralama (LSD, MSD, üç yollu hızlı sıralama), alt dizgi arama, düzenli ifadeler ve veri sıkıştırmayı Java koduyla ve deneysel ölçümlerle anlatır.
• D. Gusfield, Algorithms on Strings, Trees, and Sequences (Cambridge University Press, 1997): sonek ağaçları, düzenleme uzaklığı ve hizalama algoritmalarını hesaplamalı biyoloji örnekleriyle derinlemesine işler.
• J. E. Hopcroft, R. Motwani ve J. D. Ullman, Introduction to Automata Theory, Languages, and Computation (3. baskı, 2006): DFA, NFA, alt küme kurulumu ve Kleene teoreminin ispatlı anlatımı.
• R. Cox, “Regular Expression Matching Can Be Simple And Fast” (2007, swtch.com): Thompson yapısıyla otomat tabanlı eşlemeyi geri izlemeli motorlarla karşılaştıran, üstel yavaşlamayı ölçümlerle gösteren makale.

5.2.14Kaynaklar

1. M. Burrows, D. J. Wheeler, “A Block-sorting Lossless Data Compression Algorithm”, DEC SRC Research Report 124, 1994.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (dizgi eşleştirme otomatları).
3. R. Cox, “Regular Expression Matching Can Be Simple And Fast”, 2007, https://swtch.com/~rsc/regexp/regexp1.html.
4. J. E. F. Friedl, Mastering Regular Expressions, 3. baskı, O'Reilly, 2006; Java java.util.regex.Pattern belgeleri.
5. D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
6. J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3. baskı, 2006.
7. V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Soviet Physics Doklady 10(8), 1966.
8. U. Manber, G. Myers, “Suffix Arrays: A New Method for On-Line String Searches”, SIAM Journal on Computing 22(5), 1993.
9. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (5.1 String Sorts, 5.4 Regular Expressions).
10. R. A. Wagner, M. J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM 21(1), 1974.

İlgili sayfalar: Dizgi Algoritmaları (2) sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.