skip etiketine sahip kayıtlar gösteriliyor. Tüm kayıtları göster
skip etiketine sahip kayıtlar gösteriliyor. Tüm kayıtları göster

14 Aralık 2016 Çarşamba

Alpha Skip Search Algoritması

  • Skip Search algoritmasının iyileştirilmiş halidir 
  • Dizginin logσ(m) uzunluğundaki her elemanı için konumlarını kullanır 
  • Önişlem safhası O(m) zaman ve alan karmaşıklığı
  • Arama safhası O(mn) zaman karmaşıklığı 
  • Beklenen karakter karşılaştırması O(logσ (m).(n / (m-logσ (m)))) 
TANIM:
Alpha Skip Search algoritmasının önişlem safhası x kelimesi içersin de uyuşan bütün ℓ=logσm uzunluğundaki bütün elemanların, T(x) ağacının inşasını içerir. T(x) nin yaprakları x in ℓ uzunluğundaki bütün elemanlarını temsil etmektedir.  x içersin de bulunan, yaprak ile birleşmiş, eleman konumlarının listesinin saklandığı, T(x) içersin deki her yaprak için bir kova vardır. Alfabe uzunluğu sabit olarak dikkate alındığında algoritmanın önişlem safhası en kötü durumda doğrusaldır. Algoritmanın arama safhası y[1, (n- ℓ) / m ] aralık içersin de  k sayı değeri ile bütün j = k.(m- ℓ +1)-1 için y[j .. j+ ℓ -1] metin elemanlarının kovalarına bakmayı içerir. En kötü durumda arama safhasının zaman karmaşıklığı kuadratik dir fakat beklenen metin karakter karşılaştırması O(logσ (m).(n / (m-logσ (m)))) .