Yazan: Şadi Evren ŞEKER
Algoritma, bilgisayar programlama veya bilgisayar bilimlerinde genelde derleyici tasarımı (compiler design) gibi dizgi (string) işlemenin yoğun olduğu alanlarda büyük lokma (maximal munch) veya en uzun eşleşme (longest match) olarak geçmektedir. Buradaki amaç, anlık olarak en büyük lokmayı oluşturmak ve yutmak veya aranan koşulları sağlayan en uzun yapıyı koparmak olarak düşünülebilir. Tam olarak aynı olmasa da aç gözlü yaklaşımına (greedy approach) yakın bir yapıdır.
Örneğin sözcük analizi sırasında (lexical analysis), programlama dilinde gelen yazıların anlamlı kelimelere bölünmesi gerekmektedir. Diyelim ki aşağıdaki şekilde verilmiş bir satır olsun:
int a=b+c;
Bu satırı insan olarak biz okuduğumuz zaman, bu satırın içeriğinin a isimli bir değişkene b ve c değişkenlerinin toplamını koymak amacında olduğunu anlıyoruz. Ancak bilgisayar açısından henüz işlenmemiş olan bu dizgi (string) aslında bir boşlukla ayrılmış ve birisi 3 diğeri 6 karakter uzunluğunda iki kelimeden oluşan bir satırdır. Buradaki sembollerin taşıyabileceği çok sayıda anlam bulunduğundan derleyici (compiler) bu kelimeleri sözcük analiziden geçirmek zorundadır.
İlk harfi ele alalım ve soldan sağa işlemeye çalışalım. İlk kelimenin ilk harfi i harfi ve bu harf C dilinde farklı anlamdaki komutların başlangıcına işaret ediyor olabilir. Örneğin if, int gibi komutlar olabileceği gibi bir değişken veya fonksiyon ismi de olabilir. Demek ki ilk harften sonra bir anlam çıkarmaya çalışıyoruz ancak ihtimalleri azaltarak sonuna kadar gitmek zorundayız. Ardından gelen n harfi ihtimalleri azaltıyor nihayetinde gelen t harfi ile kelime tamam oluyor. Böylelikle bir kelimeyi analiz etmiş oluyoruz. Benzer durum ikinci kelime için de geçerli ancak ikinci gelime 3 değişken ve 3 sembolden oluşmakta ve kelime bunlara teker teker bölünecek.
Algoritmanın çalışmasını daha iyi anlayabilmek için, sözcük analizinde (lexical analysis) algoritmanın nasıl kullanıldığını anlatalım.
Örneğin bize sözcük analizinde kullanılmak üzere düzenli ifadeler(regular expressions) verilmiş olsun. Bunları kullanarak sözcükleri analiz etmemiz istniyor ki, LEX (flex) gibi diller için de durum tam olarak bundan ibarettir.
Yaklaşımımız öncelikle düzenli ifadeleri (regular expressions), birer sonlu durum otomatı (finite state automaton) şekline çevirmek ve ardından gelen girdi cümlesini bu otomatlarda en fazla yolu gidecek şekilde parçalamak olacaktır.
Örneğin kullandığımı 3 adet düzenli ifade aşağıdaki şekilde verilsin:
T_Do do
T_Double double
T_Mystery [A-Za-z]
Buna göre bir kelime, do, double veya tek harfli herhanbi başka bir kelime olma ihtimaline sahiptir.
Yukarıdaki şekilde, 3 farklı ihtimali de içeren ayrı birer sonlu durum makinesi çizilmiştir. Bu makineleri kullanarak aşağıdaki örnek cümleyi analiz edelim:
“DOUBDOUBLE”
Bu kelimeyi yukarıdaki kurallara göre parçalamak istiyoruz:
Öncelikle, bütün makinelerimizde başlangıç durumuna gidiyoruz ve ardından gelen ilk harfe göre makinelerimiz çalışmaya başlıyor:
Yukarıda görüldüğü üzere, ilk harf olan d harfi bütün makineler için kabul edilir bir harftir. Bu durumda bütün makinelerdeki ilk geçiş, geçilmiş ve başlangıç durumundan, bir durum ileri gidilmiştir. Burada dikkat edilecek diğer bir nokta, makinelerimizden birisinin kabul durumuna (final state) gelmiş olmasıdır. Bu durumda son makinemiz, bize bu harfi yani “d” harfini kabul ettiğini söylüyor. Öyleyse biz d harfine bir gösterici koyarak bu harfi kabul ettiğimizi söyleyebiliriz ve bu gösterici bir sonraki güncellemeye kadar bekliyor. Şimdilik lokmamızda sadece “d” harfi var.
İkinci harf olan “o” harfi işlendiğinde ise sadece ilk iki makinede ilerleme sağlanmıştır. Son sırada yer alan ve 1 harf uzunluğundaki kelimeleri parçalamaya yarayan makine, kelime uzunluğu 1’den fazla olduğu için ilerleyemeden kalır. Tam bu noktada büyük lokma (maximal munch) algoritmasının anlamı ortaya çıkar. Buna göre artık son makineden bir sonuç çıkma ihtimali yoktur çünkü ilk iki makine her durumda, son makineye göre daha büyük bir lokma işleyecektir.
Ayrıca ilk makinemiz son durumuna (final state) ulaştığı için bir önceki adımda, lokmamızda olan “d” harfini güncelliyoruz, çünkü iki harfli daha uzun bir lokmayı kabul eden bir durum ile karşılaştık ve yeni lokmamız “do” oluyor.
Ardından gelen u harfi için işleme devam etmektedir. Tek alternatif olan ikinci makinemizi çalıştırıyoruz. Şu ana kadar bitiş durumuna eriştiğimiz en uzun lokmamız “do” kelimesi.
Girdi olarak aldığımız kelimeden bir harf daha ilerleyerek b harfine kadar işlemiş oluyoruz. Girdi kelimemizin “DOUBDOUBLE” olduğunu hatırlarsak, şu anda 4. harfe kadar gelmişiz demektir. Ayrıca en büyük lokmamız henüz “do” kelimesi.
Bu aşamadan sonra ne yazık ki hiçbir makinemiz ilerleyemeyecek. Bunun sebebi şu ana kadar işlediğimiz kelimenin “DOUBD” olması ve bu kelimeyi kabul eden makinemizin bulunmaması.
Elimizde şimdiye kadar işlediğimiz en büyük lokma olan “do” kelimesini, ilk çıktı olarak basıyoruz. Ardından bu kelimenin devamı olan girdimizdeki 3. harfe yani u harfine geri dönerek işlemeye devam ediyoruz.
Kelimenin yeni başlangıç değeri için U kabul edilecek ve bu harf sadece 3. makineye uygun bulunacak. Bu durumda ikinci kelimemiz U olmuş oluyor. Benzer durum B için de geçerli ve üçüncü kelime olarak B harfini çıkarıyoruz:
DO+U+B
şeklinde şimdiye kadar parçalama işlemini tamamladık. Girdimiz “DOUBDOUBLE” kelimesiydi, bu kelimenin ilk 4 harfi böylece işlenmiş oldu gelelim diğer harflere.
Diğer harfler yeniden makineye girecek ve en büyük lokma oluşana kadar işlenecek.
Kısacası, geriye kalan harflerin 3 makine için işlenmesi sonucunda ikinci makine tarafından kabul edilmesi söz konusudur. Bu durumda parçalama işlemi aşğaıdaki şekilde sonuçlanacaktır:
DO+U+B+DOUBLE
görüldüğü üzere en büyük lokma (maximal munch) algoritmasını basit bir girdi ve 3 makine üzerinde çalıştırdık ve bize, bu makineler tarafından üretilebilecek en uzun alternatifleri döndürdü.