Suffix array
- Algoritmalar kursu
- Uzman seviye
- Ders 17/41
- 4 dk
Suffix array ile sıralı sonek tablosu öğrenirsin.
Suffix array
Suffix array, bir dizenin tüm soneklerinin alfabetik olarak sıralanmış başlangıç indeksleridir. Örneğin "banana" için sonekler sıralandığında [5, 3, 1, 0, 4, 2] elde edilir.
Suffix array, büyük metinlerde arama, en uzun tekrar eden alt dize ve sıkıştırma gibi görevlerde kullanılır. İkili arama ile bir örüntü O(m log n)'de aranır.
Doğrudan sıralama O(n² log n)'dir; verimli algoritmalar O(n log n)'ye kadar iner.
Suffix array kurulumu
En basit kurulum, tüm sonekleri oluşturup Python'ın sort işleviyle sıralamaktır. Her sonek bir demet (dize, indeks) olarak saklanır.
Sıralamadan sonra yalnızca indeksleri alırız. Bu yöntem O(n² log n)'dir; küçük diziler için yeterlidir.
İleri seviyede bu işlemi ön ek çiftleriyle karşılaştırarak O(n log² n)'ye düşürebiliriz.
Uygulama build_suffix_array fonksiyonu
build_suffix_array(s) yaz. Sıralı sonek indekslerini döndür. print(build_suffix_array("banana")) ile [5, 3, 1, 0, 4, 2] yazdır.
Başlangıç kodu
def build_suffix_array(s):
# Sıralı sonek indeksleriÖrnek çözüm
def build_suffix_array(s):
# Sıralı sonek indeksleri
suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[0])
return [idx for _, idx in suffixes]
print(build_suffix_array("banana"))Beklenen çıktı
[5, 3, 1, 0, 4, 2]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 sonek listesi
suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[____])suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[0])Açıklama: Sonek dizesine göre sıralanır.
2 Suffix array kavramları
| Kavram | Anlamı |
|---|---|
sonek |
i'den başlayan alt dize |
sıralı |
Alfabetik düzen |
ikili arama |
O(m log n) |
indeks |
Başlangıç konumu |
3 Suffix array neyi saklar?
sa = [5, 3, 1, 0, 4, 2]- Dizenin karakter kodlarını
- Sıralı soneklerin başlangıç indekslerini Doğru cevap
- Sonek dizesinin kendisini
- Soneklerin uzunluklarını
Açıklama: Suffix array sıralı soneklerin başlangıç indekslerini saklar.