DFA Metin Arama Algoritması (DFA Text Search)

Yazan : Şadi Evren ŞEKER

1. Otomatın İnşası
2. Algoritmanın arama aşaması
3. Algoritmanın çalışması
4. Algoritmanın kodlanması

Bilgisayar bilimlerinde, bir metnin içerisinde farklı bir metnin veya bir kelimenin aranması sırasında kullanılan algoritmalardan birisidir. Algoritma, aranan kelime için bir otomat (automaton) oluşturur ve hedef metin içerisinde bu otomata göre arama işlemi yapar.

Oluşturulana otomatın DFA (deterministic finite automaton, belirli sonlu otomat) olması gerekmektedir.

Algoritmanın çalışması iki aşamada incelenebilir:

• Aranan kelimeye özgü bir otomatın inşa edilmesi
• İnşa edilen bu otomatın bir metin içerisinde arama işlemi için kullanılması

Yukarıdaki bu adımları sırasıyla anlatmaya çalışalım ve ayrıca performanslarını inceleyelim.

Otomatın inşası

Bilindiği üzere bir DFA ifade edilirken şu dört terimden faydalanılır: A(x) =(Q, q₀, T, E). Bu tanımın üzerinde arama yapacağı dili x harfleri kümesinden oluşan bir dil (language) (^*x) olarak tanımlarsak, otomatı oluşturan bu terimlerin metin arama işlemi için uyarlanmış hallerini şöyle açıklayabiliriz.

• Q kümesi x harflerinden oluşan ve bütün olasılıkları ifade eden kümedir ve Q={, x[0], x[0 .. 1], … , x[0 .. m-2], x} olarak gösterilebilir.
• q₀, otomatın başlangıç terimidir ve başlangıçta otomatta boş küme olduğunu düşünürsek q₀=; olarak gösterilebilir.
• T, otomatın üzerinde tanımlı olduğu dili oluşturan sembolleri gösterir. Bu örnekte dilimizin ^*x şeklinde tanımlı olmasından dolayı T = {x} olarak gösterilebilir.
• Son olarak E teriminin tanımını Q kümesinde tanımlı bütün “q” değerleri ve dilinde tanımlı herhangi bir “a” terimi için (q, a, qa) şeklinde tanımlayabiliriz. Bu tanımın doğruluğu, “a” değerinin “x” değerinin bir ön eki olması şartına bağlayabiliriz. Şayet bir ön ek olarak kabul edilmezse, yine (q,a,p) üçlüsünün E kümesinde olması şartıyla, p değeri x’in bir ön eki olan qa için en uzun ek olur.

Yukarıdaki otomat inşa edilirken m uzunluğunda bir kelime olduğu kabul edilirse (ki yukarıdaki Q kümesinin elemanları bu uzunlukta verilmiştir) inşa için gereken süre O( m + r) ve inşa için gereken hafıza ise O(mr) olarak hesaplanabilir.

Algoritmanın araması

Algoritma, yukarıdaki şekilde bir DFA inşa ettikten sonra bu DFA’i kullanarak hedef metin içerisinde arama yapar. Bu arama işlemi n boyutundaki bir metin için O(n) zamanda yapılabilir.

Bu arama işleminin çalışmasını bir örnek üzerinden inceleyelim.

Algoritmanın çalışması

Örnek olarak “bilgi” kelimesini “bilbilgisayarkavramlari” metninin içerisinde aramaya çalışalım.

Öncelikle kelimemiz için bir belirli otomat (DFA) oluşturmamız gerekiyor.

Dilimizdeki (^*x) alfabemizi tanımlayacak olursak:

{a,b,g,i,k,l,m,r,s,v,y} harflerinden oluşan bir dil olarak tanımlanabilir.

Bu dil üzerinde belirli bir sonlu otomat “bilgi” kelimesi için aşağıdaki şekilde inşa edilebilir:

d 0 { a -> 0 b -> 1 g -> 0 i -> 0 k -> 0 l -> 0 m -> 0 r -> 0 s -> 0 v -> 0 y -> 0 }

d 1 { a -> 0 b -> 1 g -> 0 i -> 2 k -> 0 l -> 0 m -> 0 r -> 0 s -> 0 v -> 0 y -> 0 }

d 2 { a -> 0 b -> 1 g -> 0 i -> 0 k -> 0 l -> 3 m -> 0 r -> 0 s -> 0 v -> 0 y -> 0 }

d 3 { a -> 0 b -> 1 g -> 4 i -> 0 k -> 0 l -> 0 m -> 0 r -> 0 s -> 0 v -> 0 y -> 0 }

d 4 { a -> 0 b -> 1 g -> 0 i -> 5 k -> 0 l -> 0 m -> 0 r -> 0 s -> 0 v -> 0 y -> 0 }

d 5 { a -> 0 b -> 1 g -> 0 i -> 0 k -> 0 l -> 0 m -> 0 r -> 0 s -> 0 v -> 0 y -> 0 }

Yukarıda verilen durumlar için gidilecek durumlar listelenmiştir. Bu otomatı daha iyi anlayabilmek için aşağıdaki şekilde çizebiliriz:

Yukarıdaki otomatta, 0. Durum başlangıç durumu olmaktadır. Ayrıca 5. Duruma her ulaşılmasında aranan metin bulunmuş demektir.

Yukarıdaki otomatın örnek metin üzerindeki çalışmasını adım adım açıklamaya çalışalım:

bilbilgisayarkavramlari

  |

İlk olarak hedef metinden b harfi alınıyor. Bu harf otomatımızın ilk geçişine tekabül ediyor ve dolayısıyla 0. Durumdan 1. Duruma geçiyoruz.

Geçiş: 0.b -> b

1. durumdayken ikinci harfi hedef metinden okuyoruz:

  Bilbilgisayarkavramlari

   |

Şu anda 1. Durumdan 2. Duruma geçmek için şartımız oluştu

Geçiş: b.i -> bi

Bu işlem aşağıdaki şekilde devam ettirilir:

  BIlbilgisayarkavramlari

    |

  Geçiş: bi.l -> bil

  BILbilgisayarkavramlari

     |

  Geçiş: bil.b -> b

Yeni gelen harf, otomattaki 3. Durumdan 1. Duruma dönmeyi gerektiren b harfidir. Dolayısıyla aradığımız kelimenin ilk 3 harfi bulunmasına karşılık kelimenin tamamı bulunamamış ve başa dönülmüştür.

  bilBilgisayarkavramlari

      |

  Geçiş: b.i -> bi

  bilBIlgisayarkavramlari

       |

  Geçiş: bi.l -> bil

  bilBILgisayarkavramlari

        |

  Geçiş: bil.g -> bilg

  bilBILGisayarkavramlari

         |

  Geçiş: bilg.i -> bilgi

  bilBILGIsayarkavramlari

          |

  Geçiş: bilgi.s -> 0

  bilBILGIsayarkavramlari

           |

  Geçiş: 0.a -> 0

  bilBILGIsayarkavramlari

            |

  Geçiş: 0.y -> 0

  bilBILGIsayarkavramlari

             |

  Geçiş: 0.a -> 0

  bilBILGIsayarkavramlari

              |

  Geçiş: 0.r -> 0

  bilBILGIsayarkavramlari

               |

  Geçiş: 0.k -> 0

  bilBILGIsayarkavramlari

                |

  Geçiş: 0.a -> 0

  bilBILGIsayarkavramlari

                 |

  Geçiş: 0.v -> 0

  bilBILGIsayarkavramlari

                  |

  Geçiş: 0.r -> 0

  bilBILGIsayarkavramlari

                   |

  Geçiş: 0.a -> 0

  bilBILGIsayarkavramlari

                    |

  Geçiş: 0.m -> 0

  bilBILGIsayarkavramlari

                     |

  Geçiş: 0.l -> 0

  bilBILGIsayarkavramlari

                      |

  Geçiş: 0.a -> 0

  bilBILGIsayarkavramlari

                       |

  Geçiş: 0.r -> 0

  bilBILGIsayarkavramlari

                        |

  Geçiş: 0.i -> 0

Sonuç olarak, yukarıdaki büyük harfle gösterilen alanda, aranan kelime bulunmuştur.

Algoritmanın kodlanması

Algoritmanın kodu C dili için aşağıdaki şekilde yazılabilir.

Yukarıdaki kodda, arama işlemini yapan ana fonksiyon, otomat fonksiyonudur. Arama işlemi sırasında bu fonksiyon çağrılarak işlem başlatılır. Bu fonksiyonun otomatı inşa etmek için kullandığı inşa fonksiyonu, kodun 27. Satırında çağrılmıştır. Bu çağırma işleminden önce bir otomaton oluşturulmuş ve atıf ile çağırma (call by reference) kullanılarak inşa fonksiyonuna geçirilmiştir.

Kod, 8 ile 14. Satırlar arasında bir DFA inşa etmekte ve 30 ile 33. Satırlar arasında ise bu otomatı kullanarak hedef metin içerisinde arama yapmaktadır.