Prefix fonksiyonu

Prefix 

     Merhaba, bugün string algoritmalarının temeli olan prefix fonksiyonu ile stringteki prefix leri bulmayı anlatacağım bu basit ve temel yöntemden sonra, uzun string text içinde kelime gruplarının hızlıca bulunmasını sağlayan algoritmalar'a geçeceğim. Buradaki notlar daha çok kendime notlar silsilesi olarak devam edecek hem de ihtiyaç duyan arkadaşlar için anlaşılır bir Türkçe kaynak oluşturmaya çalışacağım.

 




               Prefix fonksiyonu basitce bir string içinde soldan sağa arama yapıp prefix değerini bulmayı sağlamaktadır. Basitçe söylemek gerekirse 'aabcaabaa' gibi bir string için :

indisler	0	1	2	3	4	5	6	7	8
Karakterler	a	a	b	c	a	a	b	a	a
Prefix değerleri	0	1	0	0	1	2	3	1	2

              Tablo üzerinden anlatalım: ilk karakter a 0 ile nitelendirilir. 2.karakter (indis 1) a ilk karakterle kontrol edilir ve aynı olduğundan 1 değeri atanır böylece sıra sıra her karakter başlangıç karakteri ile kontrol edilerek prefix değerleri bulunur. 4. 5. ve 6. indislerdeki aab değerleri 0. 1. ve 2. ile aynı olduğundan sıra ile 1, 2, 3 prefix değerlerini alır.

örnek kod ve sonuçları üzerinden detaya inecek olursak:

     public static int[] PrefixFunction(string s)
        {
            int[] prefixes = new int[s.Length]; // prefix fonksiyon sonuçlarını gösteren dizi

            int prefix = 0; // prefix değerleri tutulur
            prefixes[0] = 0; //ilk değer daima 0 olarak başlar

            for (int i = 1; i < s.Length; i++)
            {
                
                while (prefix > 0 && s[i] != s[prefix])
                {
                    prefix = prefixes[prefix - 1];
                }

                if (s[prefix] == s[i]) // prefix 0 dan başlanıp kontrolden geçtikçe arttırılarak baştan karakterler kontrol edilmiş olur.
                {
                    prefix++;
                } 

                prefixes[i] = prefix; 
            }

            return prefixes;
        }

      Örnek olarak 'abrakadabra' verdiğimiz durumda sonuç olarak

          Böyle bir görüntü karşımıza gelecektir. kodu anlatmak gerekirse: for döngüsü tüm string karakterleri içinde gezmemizi sağlamakta, prefix integer'ı 0 dan başladığı için ilk karakterle 'i' indisinin geldiği karakteri kontrol eder, aynı ise prefix integer'ı nı 1 arttırıp prefixies dizisinin i indisli elemanına yazar böylede 's' dizisinin 'i' indisli karakterinin prefix değeri prefixies dizisinde 'i' indisinde tutulur. en güzeli olan While döngüsü ise eğer karakterimiz prefix değil ise ve prefix değeri 0 dan büyük iken kontrolü prefixler içerisinde yapmakta, yani prefix 6 iken 7. karakter kontrol edilir ama karakter eşit değil ise prefix sıfırlanmaz içinde bulunduğumuz karakter belki 7. indisli prefix değil ama 2.,3. veya 4. olabilir. bunun kontrolü ise içinde bulunduğumuz değer yani 7. indisli ye kontrol karakterim eşit değil ise stringteki 7. indisli karakterin prefix olup olmadığı kontrol edilir eğer ki bu değer prefix ise sonraki değeri de şuan kontrol ettiğim karaktere eşitse kontrol karakterim başka bir prefix olmuş olur.

        Bunu daha anlaşılır kılmak için 'aaabcfgaaabctklaaabcfgaaabcf' bu stringi kullanacağım.

 


   

indisler

   

0

   

1

   

2

   

3

   

4

   

5

   

6

   

7

   

8

   



9

   



10

   



11

   



12

   



13

   



14

   



15

   



16

   



17

   



18

   



19

   



20

   



21

   



22

   



23

   



24

   



25

   



26

   



27

  

 


  

karakterler

  

a

  

a

  

a

  

b

  

c

  

f

  

g

  

a

  

a

  



 a

  



 b

  



 c

  



 t

  



 k

  



 l

  



 a

  



 a

  



 a

  



 b

  



 c

  



 f

  



 g

  



 a

  



a

  



a

  



b

  



c

  



 f

 

  

prefix değerleri

  

0

  

1

  

2

  

0

  

0

  

0

  

0

  

1

  

2

  



3

  



4

  



5

  



0

  



0

  



0

  



1

  



2

  



3

  



4

  



5

  



6

  



7

  



8

  



9

  



10

  



11

  



12

  



6

                          Bu örnekten yola çıkarsak i=26 için c kontrolü yapıldığında 12 indisli prefix olduğu belirlendikten sonra kontrol edilem 27. indisteki f 12. indisteki string değeri olan 'k' ye eşit değil, bu durumda prefix 1 azltırılır 11 olur, stringin 11. değeri yani 'c'nin prefix değeri kontrol edilir eğer c prefix ise ondan sonraki değer kontrol edilir eğer eşitse bu prefix değeri yazılır. Bu durumda 'c' nin prefix değeri 5 prefix integeri'ı  5'e eşitlenir, stringin 5. değeri kontrol edilir bu değer bizim 27. değere eşit 'f' bu durumda 27. karakterin prefix'i 6 olmakta. Çünkü 22. 23. 24. 25. 26. ve 27. değerler aaabcf 0.1.2.3.4.5. değerler olan aaabcf ye eşir olduğundan 'f' nin prefix değeri 6 olmakta.



             Elimden geldiğince açıklamaya anlaşılır olmaya çalıştım umarım faydalı olmuştur.