sonek dizisi - Suffix array

sonek dizisi
Tip	Dizi
Tarafından icat edildi	Manber ve Myers (1990)
Zaman karmaşıklığı; içinde büyük Ç gösterimde

Gelen bilgisayar bilimleri , bir sonek dizisi Sıralanmış olan dizi tüm son ekler a dize . Diğerlerinin yanı sıra tam metin indekslerinde, veri sıkıştırma algoritmalarında ve bibliyometri alanında kullanılan bir veri yapısıdır .

Sonek dizileri, Manber & Myers (1990) tarafından sonek ağaçlarına basit, alan açısından verimli bir alternatif olarak tanıtıldı . Bunlar bağımsız olarak 1987'de Gaston Gonnet tarafından PAT dizisi adı altında keşfedilmişti ( Gonnet, Baeza-Yates & Snider 1992 ).

Li, Li ve Huo (2016) , hem zaman hem de uzayda optimal olan ilk yerinde zaman eki dizisi oluşturma algoritmasını verdi; burada yerinde , algoritmanın yalnızca giriş dizesi ve çıkış eki dizisinin ötesinde ek alana ihtiyaç duyduğu anlamına gelir . ${\görüntüleme stili {\matematiksel {O}}(n)}$ ${\ Displaystyle {\Mathcal {O}}(1)}$

Gelişmiş son ek dizileri (ESA'lar), aynı zamanı ve bellek karmaşıklığını koruyarak son ek ağaçlarının tam işlevselliğini yeniden üreten ek tablolara sahip son ek dizileridir. Bir dizgenin tüm son eklerinin bir alt kümesi için sonek dizisine seyrek sonek dizisi denir . Optimum zaman ve bellek algoritması dahil olmak üzere ek bellek kullanımını en aza indirmek için çoklu olasılık algoritmaları geliştirilmiştir.

Tanım

Let bir -dize olsun ve ile kapsayıcı arasında değişen alt dizeyi belirtelim . $S=S[1]S[2]...S[n]$ ${\metin stili n}$ ${\görüntüleme stili S[i,j]}$ ${\görüntüleme stili S}$ ${\görüntüleme stili ben}$ ${\görüntüleme stili j}$

Eki dizisi içinde tanımlanmakta olup başlangıç pozisyonları sağlamaya tamsayı dizisi olmak üzere son ekler arasında içinde sözlük sırasını . Bu, bir girdinin -th en küçük son ekinin başlangıç konumunu içerdiği ve dolayısıyla tümü için : anlamına gelir . ${\görüntüleme stili A}$ ${\görüntüleme stili S}$ ${\görüntüleme stili S}$ ${\ Displaystyle A[i]}$ ${\görüntüleme stili ben}$ ${\görüntüleme stili S}$ $1<i\leq n$ $S[A[i-1],n]<S[A[i],n]$

Her eki arasında yukarı gösterileri tam olarak bir kez. Son ekler basit dizelerdir. Bu diziler (kağıt sözlükte olduğu gibi), başlangıç konumları (tamsayı indeksleri) içine kaydedilmeden önce sıralanır . ${\görüntüleme stili S}$ ${\görüntüleme stili A}$ ${\görüntüleme stili A}$

Örnek

Dizine alınacak = metnini düşünün : ${\görüntüleme stili S}$ banana$

ben	1	2	3	4	5	6	7
${\ Displaystyle S[i]}$	B	a	n	a	n	a	$

Metin $, benzersiz ve sözlükbilimsel olarak diğer herhangi bir karakterden daha küçük olan özel nöbetçi harfle sona erer . Metin aşağıdaki eklere sahiptir:

son ek	ben
muz$	1
anana$	2
büyükanne$	3
ana$	4
na$	5
bir$	6
$	7

Bu son ekler artan düzende sıralanabilir:

son ek	ben
$	7
bir$	6
ana$	4
anana$	2
muz$	1
na$	5
büyükanne$	3

Sonek dizisi , bu sıralanmış son eklerin başlangıç konumlarını içerir: ${\görüntüleme stili A}$

ben =	1	2	3	4	5	6	7
${\ Displaystyle A[i]}$ =	7	6	4	2	1	5	3

Açıklık sağlamak için altına dikey olarak yazılan son ekleri olan sonek dizisi:

ben =	1	2	3	4	5	6	7
${\ Displaystyle A[i]}$ =	7	6	4	2	1	5	3
1	$	a	a	a	B	n	n
2		$	n	n	a	a	a
3			a	a	n	$	n
4			$	n	a		a
5				a	n		$
6				$	a
7					$

Örneğin, 4 değerini içerir ve bu nedenle sonek olan içinde 4 konumundan başlayan son eki ifade eder . ${\görüntüleme stili A[3]}$ ${\görüntüleme stili S}$ ana$

Ağaçların son ekine karşılık

Sonek dizileri, sonek ağaçlarıyla yakından ilişkilidir :

Sonek dizileri, bir sonek ağacının derinlik öncelikli geçişi gerçekleştirilerek oluşturulabilir. Kenarlar ilk karakterlerinin sözlükbilimsel sırasına göre ziyaret edilirse, sonek dizisi, geçiş sırasında bunların ziyaret edildiği sırayla verilen yaprak etiketlere karşılık gelir.
Bir sonek ağacı, sonek dizisi ve LCP dizisinin bir kombinasyonu kullanılarak doğrusal zamanda oluşturulabilir . Algoritmanın açıklaması için LCP dizisi makalesindeki ilgili bölüme bakın.

Her sonek ağacı algoritmasının, ek bilgilerle ( LCP dizisi gibi) geliştirilmiş bir sonek dizisi kullanan ve aynı problemi aynı zamanda karmaşıklıkta çözen bir algoritma ile sistematik olarak değiştirilebileceği gösterilmiştir . Son ek ağaçlarına göre son ek dizilerinin avantajları arasında iyileştirilmiş alan gereksinimleri, daha basit doğrusal zaman oluşturma algoritmaları (örneğin, Ukkonen'in algoritması ile karşılaştırıldığında ) ve geliştirilmiş önbellek yeri bulunur.

Alan verimliliği

Sonek dizileri , sonek ağaçlarının alan gereksinimlerini iyileştirmek için Manber & Myers (1990) tarafından tanıtıldı : Sonek dizileri tamsayıları depolar . Bir tamsayının bayt gerektirdiğini varsayarsak , bir sonek dizisi toplamda bayt gerektirir . Bu, dikkatli bir sonek ağacı uygulamasının gerektirdiği baytlardan önemli ölçüde daha azdır . ${\görüntüleme stili n}$ ${\görüntüleme stili 4}$ ${\görüntüleme stili 4n}$ ${\görüntüleme stili 20n}$

Ancak, bazı uygulamalarda, sonek dizilerinin alan gereksinimleri yine de engelleyici olabilir. Bit cinsinden analiz edildiğinde, bir sonek dizisi boşluk gerektirirken , alfabe boyutundaki orijinal metin yalnızca bit gerektirir . Olan bir insan genomu için ve ek dizisinden nedenle genomun kendisine göre 16 kat daha fazla bellek hakkında kaplar. ${\görüntüleme stili {\matematiksel {O}}(n\log n)}$ ${\görüntüleme stili \sigma }$ ${\mathcal {O}}(n\log \sigma )$ ${\görüntüleme stili \sigma =4}$ ${\görüntüleme stili n=3.4\kez 10^{9}}$

Bu tür tutarsızlıklar, sıkıştırılmış son ek dizilerine ve FM-endeksi gibi BWT tabanlı sıkıştırılmış tam metin dizinlerine yönelik bir eğilimi motive etti . Bu veri yapıları, yalnızca metin boyutunda veya daha az boşluk gerektirir.

İnşaat algoritmaları

Bir sonek ağacı oluşturulabilir ve ağaç derinliğini -önce 'de de geçerek bir sonek dizisine dönüştürülebilir , bu nedenle . ${\görüntüleme stili {\matematiksel {O}}(n)}$ ${\görüntüleme stili {\matematiksel {O}}(n)}$ ${\görüntüleme stili {\matematiksel {O}}(n)}$

Bir sonek dizisi oluşturmak için naif bir yaklaşım, karşılaştırmaya dayalı bir sıralama algoritması kullanmaktır . Bu algoritmalar son ek karşılaştırmaları gerektirir , ancak bir son ek karşılaştırması zamanında çalışır , dolayısıyla bu yaklaşımın genel çalışma zamanı . ${\görüntüleme stili {\matematiksel {O}}(n\log n)}$ ${\görüntüleme stili {\matematiksel {O}}(n)}$ ${\mathcal {O}}(n^{2}\log n)$

Daha gelişmiş algoritmalar, sıralanacak eklerin rastgele diziler olmayıp birbiriyle ilişkili olması gerçeğinden yararlanır. Bu algoritmalar aşağıdaki hedeflere ulaşmaya çalışır:

minimum asimptotik karmaşıklık ${\görüntüleme stili \Teta (n)}$
uzayda hafif, yani metnin yanında çok az veya hiç çalışma belleği yok ve sonek dizisinin kendisine ihtiyaç var
pratikte hızlı

Tüm hedeflere ulaşmak için ilk algoritmalardan biri Nong, Zhang & Chan'ın (2009) SA-IS algoritmasıdır . Algoritma da oldukça basittir (< 100 LOC ) ve aynı anda LCP dizisini oluşturmak için geliştirilebilir . SA-IS algoritması, bilinen en hızlı sonek dizisi oluşturma algoritmalarından biridir. Yuta Mori'nin dikkatli bir uygulaması, diğer doğrusal veya süper doğrusal inşaat yaklaşımlarının çoğundan daha iyi performans gösterir.

Zaman ve mekan şartlarına yanında eki dizisi inşaat algoritmaları ayrıca desteklenmektedir birbirlerinden ayrılırlar alfabenin : sabit alfabe alfabe boyutu sabit bağlı olan, alfabelere tamsayı karakterler bağlı olarak bir aralığın içinde tam sayılardır ve genel harfleri tek karakter karşılaştırmalar izin verilir . ${\görüntüleme stili n}$

Çoğu sonek dizisi oluşturma algoritması, aşağıdaki yaklaşımlardan birine dayanır:

Önek ikiye katlama algoritmaları, Karp, Miller & Rosenberg'in (1972) stratejisine dayanmaktadır . Buradaki fikir, son eklerin sözlükbilimsel sıralamasını onurlandıran önekleri bulmaktır. Değerlendirilen önek uzunluğu, bir önek benzersiz olana ve ilgili son ekin sırasını sağlayana kadar algoritmanın her yinelemesinde iki katına çıkar.
Özyinelemeli algoritmalar, bir ek alt kümesini özyinelemeli olarak sıralamak için Farach (1997) tarafından sonek ağacı oluşturma algoritmasının yaklaşımını takip eder . Bu alt küme daha sonra kalan son eklerin bir sonek dizisini çıkarmak için kullanılır. Bu son ek dizilerinin her ikisi de daha sonra son ek dizisini hesaplamak için birleştirilir.
Uyarılmış kopyalama algoritmaları, geri kalan son eklerin hızlı bir şekilde sıralanmasını sağlamak için zaten sıralanmış bir alt kümeyi kullanmaları bakımından özyinelemeli algoritmalara benzer. Aradaki fark, bu algoritmaların, seçilen son ek alt kümesini sıralamak için yinelemeyi yinelemeye tercih etmesidir. Bu çeşitli algoritmalar grubunun bir araştırması Puglisi, Smyth & Turpin (2007) tarafından bir araya getirilmiştir .

Tamsayılı alfabeler için iyi bilinen bir özyinelemeli algoritma, Kärkkäinen & Sanders'ın (2003) DC3/skew algoritmasıdır . Doğrusal zamanda çalışır ve paralel ve harici bellek soneki dizisi oluşturma algoritmalarının temeli olarak başarıyla kullanılmıştır .

Tarafından yapılan son çalışmalar Salson ve arkadaşları. (2010) , yeni bir sonek dizisini sıfırdan yeniden oluşturmak yerine, düzenlenmiş bir metnin sonek dizisini güncellemek için bir algoritma önermektedir. Teorik olarak en kötü durum zaman karmaşıklığı olsa bile , pratikte iyi performans gösteriyor gibi görünüyor: yazarlardan elde edilen deneysel sonuçlar, dinamik sonek dizilerinin uygulanmasının, içine makul sayıda harf eklenmesi düşünüldüğünde, genellikle yeniden oluşturmaktan daha verimli olduğunu gösterdi. orjinal metin. ${\görüntüleme stili {\matematiksel {O}}(n\log n)}$

Pratik açık kaynak çalışmasında, son ek dizisi yapımı için yaygın olarak kullanılan bir rutin, 1999 Larsson-Sadakane algoritmasına dayanan qsufsort idi. Bu rutinin yerini, 2017 itibariyle "ana bellekte bilinen en hızlı son ek sıralama algoritması" olan Yuta Mori'nin DivSufSort'u almıştır. O da bir LCP dizisini hesaplamak için değiştirilebilir. Itoh-Tanaka ile birlikte uyarılmış bir kopyalama kullanır. 2021'de Ilya Grebnov, Silesia Corpus'ta DivSufSort uygulamasına göre ortalama %65 performans artışı gösteren algoritmanın daha hızlı bir uygulamasını sundu.

Genelleştirilmiş Sonek Dizisi

Bir sonek dizisi kavramı birden fazla dizgeye genişletilebilir. Buna genelleştirilmiş son ek dizisi (veya GSA), bir dizi dize için tüm son ekleri içeren bir son ek dizisi denir (örneğin, ve her dizenin tüm son ekleriyle sözlükbilimsel olarak sıralanır. $S=S_{1},S_{2},S_{3},...,S_{k}$

Uygulamalar

Bir dizgenin sonek dizisi, dizge içinde bir alt dizgi modelinin her oluşumunu hızlı bir şekilde bulmak için bir dizin olarak kullanılabilir . Modelin her oluşumunu bulmak, alt dize ile başlayan her son eki bulmaya eşdeğerdir. Sözlüksel sıralama sayesinde bu ekler sonek dizisinde birlikte gruplandırılacak ve iki ikili arama ile verimli bir şekilde bulunabilecektir . İlk arama aralığın başlangıç konumunu, ikincisi ise bitiş konumunu belirler: ${\görüntüleme stili P}$ ${\görüntüleme stili S}$

n = len(S)
def search(P: str) -> Tuple[int, int]:
    """
    Return indices (s, r) such that the interval A[s:r] (including the end
    index) represents all suffixes of S that start with the pattern P.
    """
    # Find starting position of interval
    l = 0  # in Python, arrays are indexed starting at 0
    r = n
    while l < r:
        mid = (l + r) // 2  # division rounding down to nearest integer
        # suffixAt(A[i]) is the ith smallest suffix
        if P > suffixAt(A[mid]):
            l = mid + 1
        else:
            r = mid
    s = l
    
    # Find ending position of interval
    r = n
    while l < r:
        mid = (l + r) // 2
        if suffixAt(A[mid]).startswith(P):
            l = mid + 1
        else:
            r = mid
    return (s, r)

Tek bir son ek karşılaştırmasının karakterleri karşılaştırması gerektiğinden, uzunluk dizesinde uzunluğun alt dize modelini bulmak zaman alır . Manber & Myers (1990) , bu sınırın LCP bilgisi kullanılarak zamana nasıl iyileştirilebileceğini açıklar . Buradaki fikir, bunların kalıbın ve mevcut arama aralığının en uzun ortak önekinin parçası olduğu zaten bilindiğinde, bir kalıp karşılaştırmasının belirli karakterleri yeniden karşılaştırmasına gerek olmamasıdır. Abouelhoda, Kurtz ve Ohlebusch (2004) , sınırı daha da geliştirmiş ve sonek ağaçlarından bilinen bir arama süresi elde etmiştir . ${\görüntüleme stili P}$ ${\görüntüleme stili m}$ ${\görüntüleme stili S}$ ${\görüntüleme stili n}$ ${\görüntüleme stili {\matematiksel {O}}(m\log n)}$ ${\görüntüleme stili m}$ ${\görüntüleme stili {\matematiksel {O}}(m+\log n)}$ ${\görüntüleme stili {\matematiksel {O}}(m)}$

Burrows-Wheeler dönüşümünü (BWT) hesaplamak için sonek sıralama algoritmaları kullanılabilir . MDK bir dizenin tüm döngüsel permütasyon sıralama gerektirir. Bu dize, diğer tüm karakterlerden (yani, $) sözlükbilimsel olarak daha küçük olan özel bir dize sonu karakteriyle bitiyorsa, sıralanmış döndürülmüş BWT matrisinin sırası, bir sonek dizisindeki son eklerin sırasına karşılık gelir. Bu nedenle BWT , önce metnin bir sonek dizisi oluşturularak ve ardından BWT dizesini çıkararak doğrusal zamanda hesaplanabilir : . $BWT[i]=S[A[i]-1]$

Son ek dizileri, örnek tabanlı makine çevirisinde alt dizeleri aramak için de kullanılabilir, bu da İstatistiksel makine çevirisinde kullanılan tam bir tümcecik tablosundan çok daha az depolama gerektirir .

Son ek dizisinin birçok ek uygulaması LCP dizisini gerektirir . Bunlardan bazıları , ikincisinin uygulama bölümünde detaylandırılmıştır .

Notlar

Referanslar

Manber, Udi ; Myers, Gene (1990). Son ek dizileri: çevrimiçi dizi aramaları için yeni bir yöntem . Ayrık Algoritmalar üzerine Birinci Yıllık ACM-SIAM Sempozyumu. s. 319-327.
Manber, Udi ; Myers, Gene (1993). "Sonek dizileri: çevrimiçi dize aramaları için yeni bir yöntem" . SIAM Journal on Computing . 22 (5): 935-948. doi : 10.1137/0222058 . S2CID 5074629 .
Gawrychowski, Pawel; Kociumaka, Tomasz (Ocak 2017). "Optimum Zaman ve Mekanda Seyrek Sonek Ağacı Yapımı". Ayrık Algoritmalar Üzerine Yirmi Sekizinci Yıllık ACM-SIAM Sempozyumu Tutanakları . Philadelphia, PA: Endüstriyel ve Uygulamalı Matematik Derneği: 425-439. arXiv : 1608.00865 . doi : 10.1137/1.9781611974782.27 . ISBN'si 9781611974782. S2CID 6608776 .
Li, Zize; Li, Jian; Huo, Hongwei (2016). Optimal Yerinde Sonek Sıralaması . 25. Uluslararası Dizi İşleme ve Bilgi Erişimi Sempozyumu (SPIRE) Tutanakları. Bilgisayar Bilimleri Ders Notları. 11147 . Springer. s. 268–284. arXiv : 1610.08305 . doi : 10.1007/978-3-030-00479-8_22 . ISBN'si 978-3-030-00478-1.
Shi, Fei (1996). Birden çok dize için son ek dizileri: Çevrimiçi birden çok dize araması için bir yöntem . Bilgisayar Bilimleri Ders Notları. 1179 . Springer Berlin Heidelberg. s. 11–22. doi : 10.1007/BFb0027775 . ISBN'si 978-3-540-62031-0.
Abouelhoda, Mohamed İbrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). Gelişmiş Sonek Dizisi ve Genom Analizine Uygulamaları . Biyoinformatikte Algoritmalar. Bilgisayar Bilimleri Ders Notları . 2452 . doi : 10.1007/3-540-45784-4_35 . ISBN'si 978-3-540-44211-0.
Abouelhoda, Mohamed İbrahim; Kurtz, Stefan; Ohlebusch, Enno (Mart 2004). "Gelişmiş sonek dizileri ile sonek ağaçlarının değiştirilmesi" . Ayrık Algoritmalar Dergisi . 2 (1): 53–86. doi : 10.1016/S1570-8667(03)00065-0 . ISSN 1570-8667 .
Gonnet, GH; Baeza-Yates, RA; Snider, T (1992). "Metin için yeni dizinler: PAT ağaçları ve PAT dizileri" . Bilgi Erişimi: Veri Yapıları ve Algoritmalar .
Kurtz, S (1999). "Son ek ağaçlarının alan gereksinimini azaltmak". Yazılım-Uygulama ve Deneyim . 29 (13): 1149-1171. doi : 10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-0 . hdl : 10338.dmlcz/135448 .
Puglisi, Simon J.; Smyth, WF; Turpin, Andrew H. (2007). "Son ek dizisi oluşturma algoritmalarının bir taksonomisi" . ACM Bilgi İşlem Anketleri . 39 (2): 4. doi : 10.1145/1242471.1242472 . S2CID 2653529 .
Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Neredeyse Saf İndüklenmiş Sıralama ile Doğrusal Sonek Dizisi Yapısı . 2009 Veri Sıkıştırma Konferansı. P. 193. doi : 10.1109/DCC.2009.42 . ISBN'si 978-0-7695-3592-0.
Fischer, Johannes (2011). LCP-Array'i indükleme . Algoritmalar ve Veri Yapıları. Bilgisayar Bilimleri Ders Notları. 6844 . P. 374. arXiv : 1101.3448 . doi : 10.1007/978-3-642-22300-6_32 . ISBN'si 978-3-642-22299-3.
Salson, M.; Lecroq, T.; Leonard, M.; Mouchard, L. (2010). "Dinamik genişletilmiş son ek dizileri" . Ayrık Algoritmalar Dergisi . 8 (2): 241. doi : 10.1016/j.jda.2009.02.07 .
Burkhardt, Stefan; Kärkkäinen, Juha (2003). Hızlı Hafif Sonek Dizisi Oluşturma ve Kontrol Etme . Kombinatoryal Model Eşleştirme. Bilgisayar Bilimleri Ders Notları. 2676 . P. 55. doi : 10.1007/3-540-44888-8_5 . ISBN'si 978-3-540-40311-1.
Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). Dizelerde, ağaçlarda ve dizilerde tekrarlanan kalıpların hızlı tanımlanması . Bilgisayar Teorisi üzerine dördüncü yıllık ACM sempozyumunun bildirileri - STOC '72. P. 125. doi : 10.1145/800152.804905 .
Farach, M. (1997). Büyük alfabelerle en uygun son ek ağaç yapısı . Bildiriler 38. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu. doi : 10.1109/SFCS.1997.646102 . ISBN'si 0-8186-8197-7.
Kärkkäinen, Juha; Ukkonen, Esko (1996). Seyrek sonek ağaçları . Bilgisayar Bilimleri Ders Notları. 1090 . Springer Berlin Heidelberg. s. 219–230. doi : 10.1007/3-540-61332-3_155 . ISBN'si 978-3-540-61332-9.
Kärkkäinen, Juha; Sanders, Peter (2003). Basit Doğrusal İş Soneki Dizi Yapısı . Otomatlar, Diller ve Programlama. Bilgisayar Bilimleri Ders Notları. 2719 . doi : 10.1007/3-540-45061-0_73 . ISBN'si 978-3-540-40493-4.
Dementyev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). "Daha iyi harici bellek son eki dizisi yapısı" . Deneysel Algoritmik Dergisi . 12 : 1–24. doi : 10.1145/1227161.1402296 . S2CID 12296500 .
Kulla, Fabian; Sanders, Peter (2007). "Ölçeklenebilir paralel son ek dizi yapısı". Paralel Hesaplama . 33 (9). doi : 10.1016/j.parco.2007.06.004 .

Languages

In other projects