Suffix array

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.

Örnek çözümü göster

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"))

Kendini test et

sonek listesi

suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[____])

Cevabı göster

suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[0])

Suffix array kavramları

sonek

i'den başlayan alt dize
sıralı

Alfabetik düzen
ikili arama

O(m log n)
indeks

Başlangıç konumu
Suffix array neyi saklar?
```
sa = [5, 3, 1, 0, 4, 2]
```
- Dizenin karakter kodlarını
- Sıralı soneklerin başlangıç indekslerini
- Sonek dizesinin kendisini
- Soneklerin uzunluklarını
Cevabı göster

Sıralı soneklerin başlangıç indekslerini — Suffix array sıralı soneklerin başlangıç indekslerini saklar.

Sıradaki ders: Özet - String matching

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler