Suffix array (sonek dizisi)

Kısaca: Suffix array, bir metnin tüm soneklerinin sıralı listesidir. Onunla her alt dize ikili aramayla bulunabilir.

Biraz daha ayrıntılı: banana metni için sonekler banana, anana, nana, ana, na, a’dır. Yalnızca başlangıç konumları alfabetik sırayla saklanır: [5, 3, 1, 0, 4, 2].

Ayrıntılı

• Arama: m uzunluğunda bir desen, soneklerin üzerinde ikili arama ile O(m log n)‘de bulunur.
• Kuruluş: Naif olarak sıralamayla O(n² log n). İyi algoritmalar (SA-IS, prefix doubling) O(n) ila O(n log n)‘e ulaşır.
• Sonek ağaçlarına karşı: Biraz daha yavaş ama çok daha az bellek.
• LCP dizisi eki: Komşu soneklerin ortak önek uzunluğunu saklar ve en uzun tekrarlanan alt dize gibi başka sorgulara izin verir.
• Kullanım: Biyoinformatik (genom araması), bzip2’deki Burrows-Wheeler dönüşümü, intihal tespiti, tam metin indeksleri.
• Karşılaştırma: Aynı metinde tekrarlanan aramalar için indeks karşılığını verir. Tek seferlik aramayı KMP veya Boyer-Moore halleder.

Ayrıca bak: Ters çevrilmiş indeks