Vakti zamanında ara ara da olsa algoritma çalışmaları yapardım blog için. Bir soruyu alır ve programatik olarak nasıl çözüleceğini anlatmaya çalışırdım. Böyle aktivitelere pek işten güçten fırsat bulamıyorum sanırım. En son iki yıla yakın bir zaman olmuş onu farkettim.
Neyse efendim girişi toparlayalım; mors alfabesi üzerine ufak bir algoritma çalışması yapacağız. Problemimiz şu; bir arkadaşınız facebook iletisi olarak mors alfabesinde bir metin girdi ancak metni karakterlerine ayırmadı (ayıramadı da denebilir). Mors alfabesi ile az bir süre bile haşır neşir olduysanız her karakter için aynı sayıda ses kullanılmadığını bilirsiniz. Aslında bu anda mors alfabesinden kısaca bir bahsetmek gerekli sanırım. Mors alfabesi 1800 lerden beri kullanılan bir tür iletişim kodlamasıdır. Uzun ve kısa olmak üzere iki tip eleman barındırır. Tüm alfanümerik karakterler bu iki elemanın kombinasyonları şeklinde oluşturulmuş bir sistemde alfabeye aktarılmıştır. (Genel standart olarak metin dilinde uzun ses için – kısa ses için . karakteri kullanılmakta olduğundan bende bu yazıda bu iki karakteri kullanacağım) Örnek vermek gerekirse M karakteri – - , T karakteri – , ? karakteri . . – - . . E karakteri ise . olarak gösterilir.
Şimdi bu noktada soruna bir kez daha göz atarsak olayın boyutunu daha iyi anlayabiliriz. Mors alfabesinde her karakter için aynı sayıda eleman kullanılmadığından karakter ayrımları (normal şartlarda / olarak gösterilen) belli olmayan bir kodlamanın sağlam bir sorun oluşturduğunu anlayabiliriz. Örnek olarak size . . – - . . olarak verilmiş bir kodlama “?” anlamına gelebileceği gibi mesela EETTEE anlamına da gayet gelebilmekte. O zaman yapacaklarımız, algoritmamızın yöntemi şu şekilde olacak, öncelikle verilen kodlamaya ait olan tüm alt ayrım gruplarını oluşturacağız. Sonra her bir grup için alfabenin doğrulanması işlemini yapacağız, en son olarak da doğrulanan kelimeler için anlamlılık testi yapacağız. Aynı örnek üzerinden gidersek, birinci olarak . ./- -/. . ve ya . . – / – . . gibi tüm bölünme olasılıklarını çıkarıp, sonra bu ayrımlardan alfabede bulunmayanları eledikten sonra oluşan kelimeleri anlamlılık testine sokacağız.
Birinci aşama için ufak bir hesap yapmamız lazım. 3 elemanlı bir kodlama verildiğini düşünelim. “.-.” olsun örneğin. Bu kodlama için “./-/.” “.-/.” “./-.” ve “.-.” olmak üzere 4 farklı bölüm olasılığımız var bunu nasıl hesaplarız. Her bir eleman için sonrasına boşluk gelme ya da gelmeme olanağı bulunduğuna göre formülümüz; (n kodlamadaki eleman sayısı) 2 ^(n-1) olur. Burada ki örnekte n=3 için 2^(3-1) = 4 adet olasılık mevcut oldu. Benim üzerimde çalıştığım örnekte n=17 olmak üzere 2^16 = 65536 adet toplam bölüm olasılığı mevcut idi.
Sonra bu olasılıkların herbiri için, bölümlerin alfabe doğrulamasını yapmalıyız. Eğer bölümlerden herhangi birisi mors alfabesinde tanımlanmamış ise o olasılığı elemeliyiz. Bu işlemin sonucunda oluşacak sayı için birşey söylemek imkansız. Girdiye göre değişebilir sadece en fazla 2^(n-1) kadar olacağını söyleyebiliyoruz. Bendeki örnekte sayı 41190 adet oluştu.
Son olarak her bir eşleşme için anlamlılık testi yapmaya geldi sıra. Bunun için bir kaç yöntem mevcut, eğer metnin dilini tahmin edebiliyorsanız bir veritabanından eşleştirme yapabilirsiniz. Ya da benim gibi gözle tarayabilirsiniz. Sonuçta oluşan kelimeler oldukça fazla olmasına rağmen belli kalıpları defalarca kez tekrarladığı için dikkatlice bakmanız gereken adet oldukça düşük oluyor. Mesela T harfi – olarak tanımlandığından sonuçlar içerisinde iki ve daha fazla arka arkaya gelmiş olan T karakterini defalarca kez görmeniz mümkün. Bu durumu ikinci aşamada ufak bir değişiklikle bertaraf edebiliriz mutlaka. Çünkü hiç bir dilde iki kereden fazla kez aynı karakterin yanyana gelme durumu yoktur sanıyorum.
Bu durumu ikinci adıma eklediğimiz de sonuç sayısı 26780′e inmekte. Eğer bir veritabanı taraması yapacaksanız önemli bir düşüş bu sayı. Benim üzerinde çalıştığım kodlamadaki karakter ve sonuç sayısı fazla olmadığı için algoritmayı burada bırakabildim. Ama örneğin 50 karakterlik bir kodlama verilmiş olması demek yaklaşık bir kaç katrilyon olasılığı hesaplamanız demektir. Bu yüzden ikinci adım bu algoritmanın en önemli noktasıdır. İkinci aşamada yapılacak optimizasyonlar direkt olarak sonuca ulaşım zamanını etkiler.
Post a Comment