LCP dizisi - LCP array

LCP dizisi
Tür	Dizi
Tarafından icat edildi	Manber ve Myers (1990)harvtxt hatası: hedef yok: CITEREFManberMyers1990 ( yardım )
Zaman karmaşıklığı ve uzay karmaşıklığı içinde büyük Ç gösterimde
	Ortalama	En kötü durumda
Uzay	${\görüntüleme stili {\matematiksel {O}}(n)}$	${\görüntüleme stili {\matematiksel {O}}(n)}$
İnşaat	${\görüntüleme stili {\matematiksel {O}}(n)}$	${\görüntüleme stili {\matematiksel {O}}(n)}$

Olarak bilgisayar biliminin , uzun ortak ön ek dizi ( LCP dizisi ), bir yardımcı olan veri yapısı için eki dizisi . Sıralanmış bir sonek dizisindeki tüm ardışık son ek çiftleri arasındaki en uzun ortak öneklerin (LCP'ler) uzunluklarını saklar.

Örneğin, eğer A  := [aab, ab, abaab, b, baab] bir sonek dizisidir, A [1] = arasındaki en uzun ortak önekaabve A [2] =ab dır-dir birbu uzunluk 1, bu nedenle H [2] LCP dizi 1 '= H . Aynı şekilde, A [2]' nin LCP'si =abve A [3] =abaab dır-dir ab, yani H [3] = 2.

LCP dizisi ile eki dizisi Augmenting verimli benzetmek yukarıdan aşağıya ve aşağıdan yukarıya bir verir geçişleri arasında eki ağacının , eki dizisinde desen denk hızlandırır ve sıkıştırılmış eki ağaçlar için bir ön koşuldur.

Tarih

LCP dizisi 1993 yılında Udi Manber ve Gene Myers tarafından dizi arama algoritmalarının çalışma süresini iyileştirmek için sonek dizisinin yanında tanıtıldı .

Tanım

Izin olmak eki dizisi dizesinin uzunluğu , benzersiz ve bir gözcü mektubu sözlük sırasında başka bir karakter daha küçük. Let sonuna kadar olan alt göstermektedirler arasında değişen için . Böylece, ' nin en küçük inci ekidir . ${\görüntüleme stili A}$${\displaystyle S=s_{1},s_{2},\ldots s_{n-1}\$}$${\görüntüleme stili n}$${\görüntüleme stili \$}$${\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}$${\ Displaystyle S[A[i],n]}$${\görüntüleme stili ben}$${\görüntüleme stili S}$

Let iki dizeleri arasındaki en uzun ortak önek uzunluğunu göstermektedirler ve . Daha sonra LCP dizi büyüklüğü arasında bir tamsayıdır dizi gibi tanımlanmamış ve her için . Böylece sözlükbilimsel olarak en küçük son ekin en uzun ortak önekinin uzunluğunu ve sonek dizisinde onun öncülünü saklar . ${\displaystyle \operatöradı {lcp} (v,w)}$${\görüntüleme stili v}$${\görüntüleme stili w}$${\ Displaystyle H[1,n]}$${\görüntüleme stili n}$${\ Displaystyle H[1]}$${\displaystyle H[i]=\operatöradı {lcp} (S[A[i-1],n],S[A[i],n])}$${\displaystyle 1<i\leq n}$${\ Displaystyle H[i]}$${\görüntüleme stili ben}$

LCP dizisi ve sonek dizisi arasındaki fark:

• Sonek dizisi: Bir dizinin her son ekinin sözlük sıralamasını temsil eder.
• LCP dizisi: Ardışık iki sonek arasındaki maksimum uzunluk önek eşleşmesini, bunlar sözlükbilimsel olarak sıralandıktan sonra içerir.

Misal

Dizeyi düşünün : ${\displaystyle S={\textrm {muz\$}}}$

ve karşılık gelen sıralı sonek dizisi  : ${\görüntüleme stili A}$

Son eklerin altına dikey olarak yazıldığı sonek dizisi:

Daha sonra LCP dizisi , en uzun ortak öneklerini belirlemek için sözlükbilimsel olarak ardışık ekleri karşılaştırarak oluşturulur: ${\görüntüleme stili H}$

Yani, örneğin, en uzun ortak önek uzunluğudur soneklerinin tarafından paylaşılan ve . Bunun tanımsız olduğuna dikkat edin , çünkü sözlükbilimsel olarak daha küçük bir sonek yoktur. ${\ Displaystyle H[3]=3}$${\displaystyle {\metin{ana}}}$${\displaystyle A[3]=S[4,7]={\textrm {ana\$}}}$${\displaystyle A[4]=S[2,7]={\textrm {anana\$}}}$${\ Displaystyle H[1]}$

Verimli inşaat algoritmaları

LCP dizisi oluşturma algoritmaları iki farklı kategoriye ayrılabilir: LCP dizisini sonek dizisinin bir yan ürünü olarak hesaplayan algoritmalar ve LCP değerlerini hesaplamak için önceden oluşturulmuş bir sonek dizisini kullanan algoritmalar.

Manber & Myers (1993) , zaman içinde sonek dizisinin yanında LCP dizisini hesaplamak için bir algoritma sağlar . Kärkkäinen & Sanders (2003) , zaman algoritmalarını LCP dizisini de hesaplayacak şekilde değiştirmenin mümkün olduğunu göstermektedir . Kasai et al. (2001) , metin ve sonek dizisi verilen LCP dizisini hesaplayan ilk zaman algoritmasını (FLAAP) sunar. ${\ Displaystyle O(n\log n)}$${\görüntüleme stili O(n)}$${\görüntüleme stili O(n)}$

Her metin sembolünün bir bayt aldığını ve sonek veya LCP dizisinin her girişinin 4 bayt aldığını varsayarsak, algoritmalarının en büyük dezavantajı , orijinal çıktı (metin, sonek dizisi, LCP dizisi) yalnızca yer kaplarken, büyük bir bayt alanı kaplamasıdır. bayt. Bu nedenle, Manzini (2004) , Kasai ve diğerlerinin algoritmasının rafine bir versiyonunu oluşturmuştur . (2001) (lcp9) ve alan doluluğunu baytlara indirdi . Kärkkäinen, Manzini & Puglisi (2009) , Kasai'nin algoritmasında ( -algoritma) çalışma süresini iyileştiren başka bir iyileştirme sağlar . Bunun yerine, gerçek LCP dizisi yerine, bu algoritma oluşturur sırası büyük değerler metin düzenine yerine sözlük sırasını göründükleri LCP (PLCP) dizisi. ${\görüntüleme stili 13n}$${\görüntüleme stili 9n}$${\görüntüleme stili 9n}$${\görüntüleme stili\Phi }$

Gog ve Ohlebusch (2011) , teorik olarak yavaş olmasına rağmen ( ) pratikte yukarıda bahsedilen algoritmalardan daha hızlı olan iki algoritma sunar . ${\ Displaystyle O(n^{2})}$

2012 itibariyle, şu anda en hızlı lineer zamanlı LCP dizi oluşturma algoritması, Nong, Zhang & Chan (2009) tarafından geliştirilen en hızlı sonek dizi oluşturma algoritmalarından (SA-IS) birine dayanan Fischer'e (2011) dayanmaktadır. . Yuta Mori'nin DivSufSort'unu temel alan Fischer & Kurpicz (2017) daha da hızlı.

Uygulamalar

Abouelhoda, Kurtz ve Ohlebusch (2004) tarafından belirtildiği gibi , birkaç dizi işleme problemi aşağıdaki ağaç geçişleri ile çözülebilir :

• tam sonek ağacının aşağıdan yukarıya geçişi
• sonek ağacının bir alt ağacının yukarıdan aşağıya geçişi
• sonek bağlantılarını kullanarak ağaç geçişini ekleyin.

Kasai et al. (2001) , yalnızca sonek dizisini ve LCP dizisini kullanarak sonek ağacının aşağıdan yukarıya geçişinin nasıl simüle edileceğini gösterir . Abouelhoda, Kurtz ve Ohlebusch (2004) , sonek dizisini LCP dizisi ve ek veri yapıları ile geliştirir ve bu geliştirilmiş sonek dizisinin üç tür sonek ağacı geçişini simüle etmek için nasıl kullanılabileceğini açıklar . Fischer & Heun (2007) , minimum aralık sorguları için LCP dizisini ön işleme tabi tutarak gelişmiş sonek dizisinin alan gereksinimlerini azaltır . Böylece, sonek ağacı algoritmaları ile çözülebilen her problem, geliştirilmiş sonek dizisi kullanılarak da çözülebilir .

Yalnızca sonek dizisi kullanılıyorsa , bir uzunluk kalıbının bir uzunluk dizisinin alt dizisi olup olmadığına karar vermek zaman alır . Ek olarak LCP bilgisi kullanılarak bu sınır zamana göre iyileştirilebilir . Abouelhoda, Kurtz ve Ohlebusch (2004) optimum süreye ulaşmak için bu çalışma süresinin nasıl daha da iyileştirilebileceğini göstermektedir . Böylece, sonek dizisi ve LCP dizisi bilgisi kullanılarak, karar sorgusu sonek ağacını kullanmak kadar hızlı cevaplanabilir . ${\görüntüleme stili P}$${\görüntüleme stili m}$${\görüntüleme stili S}$${\görüntüleme stili n}$${\ Displaystyle O(m\log n)}$${\ Displaystyle O(m+\log n)}$${\görüntüleme stili O(m)}$

LCP dizisi ayrıca, sonek bağlantıları ve en düşük ortak ata sorguları gibi tam sonek ağacı işlevselliği sağlayan sıkıştırılmış sonek ağaçlarının önemli bir parçasıdır . Ayrıca, zaman içinde Lempel-Ziv LZ77 çarpanlarına ayırmasını hesaplamak için sonek dizisi ile birlikte kullanılabilir . ${\görüntüleme stili O(n)}$

Bir uzunluk dizisi için en uzun tekrarlanan alt dizi problemi , hem sonek dizisi hem de LCP dizisi kullanılarak zamanla çözülebilir . Maksimum değer bulmak için LCP dizi boyunca lineer tarama gerçekleştirmek için yeterli olan ve karşılık gelen dizin depolanır. En az iki kez oluşan en uzun alt dize daha sonra tarafından verilir . ${\görüntüleme stili S}$${\görüntüleme stili n}$${\görüntüleme stili \Teta (n)}$${\görüntüleme stili A}$${\displaystyle v_{maks}}$${\görüntüleme stili ben}$${\displaystyle v_{maks}}$${\displaystyle S[A[i],A[i]+v_{max}-1]}$

Bu bölümün geri kalanında, LCP dizisinin iki uygulaması daha ayrıntılı olarak açıklanmaktadır: Bir dizenin sonek dizisi ve LCP dizisi, karşılık gelen sonek ağacını oluşturmak için nasıl kullanılabilir ve aralık kullanılarak rasgele son ekler için LCP sorgularının nasıl yanıtlanabileceği LCP dizisindeki minimum sorgular.

Bir desenin oluşum sayısını bulun

Bir metinde (uzunluk ) belirli bir dizenin (uzunluk ) tekrarlanma sayısını bulmak için , ${\görüntüleme stili P}$${\görüntüleme stili m}$${\görüntüleme stili T}$${\görüntüleme stili N}$

• Tüm oluşumlarının başlangıç ​​ve bitiş konumunu bulmak için sonek dizisine karşı ikili arama kullanırız .${\görüntüleme stili T}$${\görüntüleme stili P}$
• Şimdi aramayı hızlandırmak için LCP dizisini, özellikle LCP dizisinin özel bir versiyonunu kullanıyoruz (aşağıda LCP-LR).

Standart ikili aramanın (LCP bilgisi olmadan) kullanılmasıyla ilgili sorun, yapılması gereken karşılaştırmaların her birinde, P'yi sonek dizisinin geçerli girişiyle karşılaştırmamızdır, bu da m karaktere kadar tam dize karşılaştırması anlamına gelir. Yani karmaşıklık . ${\ Displaystyle O(\log N)}$${\ Displaystyle O(m\log N)}$

LCP-LR dizisi bunu şu şekilde geliştirmeye yardımcı olur : ${\ Displaystyle O(m+\log N)}$

İkili arama algoritması sırasında herhangi bir noktada, her zamanki gibi, sonek dizisinin bir aralığını ve onun merkez noktasını dikkate alırız ve aramamıza sol alt aralıkta mı yoksa sağ alt aralıkta mı devam edeceğimize karar veririz . Kararı vermek için, adresindeki dizeyle karşılaştırırız . Eğer özdeş olduğunu , arama tamamlandı. Ama değilse, zaten ilk karakterlerini karşılaştırdık ve sonra sözlükbilimsel olarak daha küçük veya daha büyük olup olmadığına karar verdik . Sonucun ' den daha büyük olduğunu varsayalım . Bu nedenle, bir sonraki adımda, ortada yeni bir merkezi noktayı ele alıyoruz : ${\görüntüleme stili (L,\noktalar,R)}$${\görüntüleme stili M}$${\görüntüleme stili (L,\noktalar,M)}$${\görüntüleme stili (M,\noktalar,R)}$${\görüntüleme stili P}$${\görüntüleme stili M}$${\görüntüleme stili P}$${\görüntüleme stili M}$${\görüntüleme stili k}$${\görüntüleme stili P}$${\görüntüleme stili P}$${\görüntüleme stili M}$${\görüntüleme stili P}$${\görüntüleme stili M}$${\görüntüleme stili (M,\noktalar,R)}$${\ Displaystyle M'}$

             M ...... M' ...... R
             |
      we know:
         lcp(P,M)==k

Şimdi işin püf noktası, LCP-LR'nin önceden hesaplanmış olmasıdır, öyle ki bir -lookup bize en uzun ortak önekini söyler ve , . ${\görüntüleme stili O(1)}$${\görüntüleme stili M}$${\ Displaystyle M'}$${\görüntüleme stili \mathrm {lcp} (E,M')}$

Biz zaten (önceki adımdan) kendisinin : ile ortak bir karakter önekine sahip olduğunu biliyoruz . Şimdi üç olasılık var: ${\görüntüleme stili M}$${\görüntüleme stili k}$${\görüntüleme stili P}$${\displaystyle \mathrm {lcp} (P,M)=k}$

• Durum 1: , yani M ile ortak olan, M' ile ortak olandan daha az önek karakterine sahip. Bu, M'nin (k+1)-inci karakterinin M'ninkiyle aynı olduğu ve P'nin sözlükbilimsel olarak M'den daha büyük olduğu için, sözlükbilimsel olarak da M''den daha büyük olması gerektiği anlamına gelir. Böylece sağ yarıdan devam ediyoruz (M',...,R).${\displaystyle k<\mathrm {lcp} (E,M')}$${\görüntüleme stili P}$
• Durum 2: , yani ile ortak olandan daha fazla önek karakterine sahip . Biz karşılaştırmak olsaydı Dolayısıyla üzere , ortak önek daha küçük olacağını ve daha sözlük sırasında büyük olurdu aslında karşılaştırma yapmadan, bu nedenle, biz sol yarısında devam .${\displaystyle k>\mathrm {lcp} (E,M')}$${\görüntüleme stili P}$${\görüntüleme stili M}$${\görüntüleme stili M}$${\ Displaystyle M'}$${\görüntüleme stili P}$${\ Displaystyle M'}$${\görüntüleme stili k}$${\ Displaystyle M'}$${\görüntüleme stili P}$${\görüntüleme stili (M,\noktalar,M')}$
• Durum 3: . Yani M ve M' her ikisi de ilk karakterlerde aynıdır . Biz sol veya sağ yarısında devam karar için, karşılaştırmak yeterli üzere başlayarak inci karakteri.${\displaystyle k=\mathrm {lcp} (M,M')}$${\görüntüleme stili P}$${\görüntüleme stili k}$${\görüntüleme stili P}$${\ Displaystyle M'}$${\ Displaystyle (k+1)}$
• Yinelemeli olarak devam ediyoruz.

Genel etki, hiçbir karakterinin metnin herhangi bir karakteriyle birden fazla kez karşılaştırılmamasıdır. Toplam karakter karşılaştırma sayısı ile sınırlıdır , dolayısıyla toplam karmaşıklık gerçekten de öyledir . ${\görüntüleme stili P}$${\görüntüleme stili m}$${\ Displaystyle O(m+logN)}$

Sonek dizisinin herhangi iki girişi arasındaki lcp'yi zamanında bize söyleyebilmesi için hala LCP- LR'yi önceden hesaplamamız gerekiyor . Standart LCP dizisinin bize yalnızca ardışık girişlerin lcp'sini verdiğini biliyoruz, yani herhangi bir . Ancak ve açıklamasında yukarıda ille ardışık girişleri değildir. ${\görüntüleme stili O(1)}$${\displaystyle \mathrm {lcp} (i-1,i)}$${\görüntüleme stili ben}$${\görüntüleme stili M}$${\ Displaystyle M'}$

Bunun anahtarı , ikili arama sırasında yalnızca belirli aralıkların gerçekleşeceğini anlamaktır: Her zaman ile başlar ve bunu merkezde böler ve sonra sola veya sağa devam eder ve bu yarıyı tekrar böler ve böyle devam eder. Buna bakmanın başka bir yolu şudur: sonek dizisinin her girişi, ikili arama sırasında tam olarak bir olası aralığın merkezi noktası olarak gerçekleşir. Dolayısıyla , ikili arama sırasında muhtemelen bir rol oynayabilecek tam olarak N farklı aralık vardır ve bu olası aralıklar için önceden hesaplamak yeterlidir . Bu, farklı önceden hesaplanmış değerlerdir, dolayısıyla LCP-LR boyuttadır. ${\görüntüleme stili (L,\noktalar,R)}$${\görüntüleme stili (0,\noktalar,N)}$${\ Displaystyle (L\dots M\dots R)}$${\görüntüleme stili \mathrm {lcp} (L,M)}$${\görüntüleme stili \mathrm {lcp} (M,R)}$${\görüntüleme stili N}$${\görüntüleme stili 2N}$${\görüntüleme stili O(N)}$

Ayrıca, standart LCP dizisinden zaman içinde LCP-LR değerlerini hesaplamak için basit bir özyinelemeli algoritma vardır . ${\görüntüleme stili 2N}$${\görüntüleme stili O(N)}$

Özetle:

• LCP'den zaman ve uzayda LCP-LR'yi hesaplamak mümkündür .${\görüntüleme stili O(N)}$${\görüntüleme stili O(2N)=O(N)}$
• İkili arama sırasında LCP-LR'nin kullanılması, arama prosedürünün 'den ' ye hızlandırılmasına yardımcı olur .${\ Displaystyle O(M\log N)}$${\ Displaystyle O(M+logN)}$
• için eşleşme aralığının sol ve sağ ucunu belirlemek için iki ikili arama kullanabiliriz ve eşleşme aralığının uzunluğu P için tekrarlama sayısına karşılık gelir.${\görüntüleme stili P}$

Son ek ağaç yapımı

Sonek dizisi ve bir uzunluk dizisinin LCP dizisi göz önüne alındığında, sonek ağacı aşağıdaki fikre dayalı olarak zaman içinde oluşturulabilir : Sözlükbilimsel olarak en küçük sonek için kısmi sonek ağacıyla başlayın ve diğer son ekleri tarafından verilen sıraya göre tekrar tekrar ekleyin. sonek dizisi. ${\görüntüleme stili A}$${\görüntüleme stili H}$${\displaystyle S=s_{1},s_{2},\ldots s_{n}\$}$${\ Displaystyle n+1}$${\ Displaystyle ST}$${\görüntüleme stili O(n)}$

için kısmi sonek ağacı olsun . Ayrıca , kökten düğüme tüm yol etiketlerinin birleştirilmesinin uzunluğu olsun . ${\displaystyle ST_{i}}$${\displaystyle 0\leq i\leq n}$${\görüntüleme stili d(v)}$${\displaystyle ST_{i}}$${\görüntüleme stili v}$

Durum 1 ( ): Dizenin , , ve soneklerinin sonek ağacına zaten eklendiğini varsayalım . Daha sonra ağaca resimdeki gibi son ek eklenir. En sağdaki yol kırmızıyla vurgulanır.${\displaystyle d(v)=H[i+1]}$${\görüntüleme stili bir\$}$${\görüntüleme stili ana\$}$${\görüntüleme stili anana\$}$${\ Displaystyle muz\$}$${\displaystyle S=muz\$}$${\görüntüleme stili yok\$}$

Sadece kökten oluşan ağaç ile başlayın . Takmak için içine , yürümek en sağdaki son zamanlarda eklenen yaprak başlayan yolunu en derin düğüm kadar köküne ile ulaşılır. ${\ Displaystyle ST_{0}}$${\ Displaystyle A[i+1]}$${\displaystyle ST_{i}}$${\ Displaystyle A[i]}$${\görüntüleme stili v}$${\displaystyle d(v)\leq H[i+1]}$

İki durumu ayırt etmemiz gerekiyor:

• ${\displaystyle d(v)=H[i+1]}$: Kök-to-etiketlerin birleştirme olduğunu bu araçlar yolu soneklerinin en uzun ortak öneki eşittir ve . Bu durumda, düğümün yeni bir yaprağı olarak ekleyin ve kenarı ile etiketleyin . Bu nedenle, kenar etiketi , kök- yolun etiketlerinin birleştirilmesiyle halihazırda temsil edilmeyen kalan son ek karakterlerinden oluşur . Bu, kısmi sonek ağacını oluşturur .${\görüntüleme stili v}$${\ Displaystyle A[i]}$${\ Displaystyle A[i+1]}$
  ${\ Displaystyle A[i+1]}$${\görüntüleme stili x}$${\görüntüleme stili v}$${\görüntüleme stili (v,x)}$${\displaystyle S[A[i+1]+H[i+1],n]}$${\ Displaystyle A[i+1]}$${\görüntüleme stili v}$
  ${\displaystyle ST_{i+1}}$
  

  Durum 2 ( ): Son ek eklemek için daha önce eklenen son ekin kenarının ayrılması gerekir. Yeni bir iç düğüme yeni kenar soneklerinin uzun ortak önek ile etiketlenir ve . İki yaprağı birbirine bağlayan kenarlar , önekin parçası olmayan kalan son ek karakterleriyle etiketlenir .${\displaystyle d(v)<H[i+1]}$${\görüntüleme stili büyük\$}$${\görüntüleme stili yok\$}$${\görüntüleme stili yok\$}$${\görüntüleme stili büyük\$}$
• ${\displaystyle d(v)<H[i+1]}$: Kök-to-etiketlerin birleştirme olduğunu bu araçlar yolu görüntüler daha az karakterden uzun ortak soneklerin önek daha ve ve eksik karakterlerin kenar etiketinde içerdiği 'ın en sağdaki kenarına. Bu nedenle, gerek bölmek aşağıdaki gibi bu kenarı: Let çocuğu olmanın üzerinde bireyin en sağdaki yolu.${\görüntüleme stili v}$${\ Displaystyle A[i]}$${\ Displaystyle A[i+1]}$${\görüntüleme stili v}$
  ${\görüntüleme stili w}$${\görüntüleme stili v}$${\displaystyle ST_{i}}$

1. Kenarı silin .${\görüntüleme stili (v,w)}$
2. Yeni bir dahili düğüm ve etiketli yeni bir kenar ekleyin . Yeni etiket oluşur eksik en uzun ortak bir önek karakter ve . Böylece, kök- yolun etiketlerinin sıralanması artık en uzun ortak ön eki ve 'yi görüntüler .${\görüntüleme stili y}$${\görüntüleme stili (v,y)}$${\displaystyle S[A[i]+d(v),A[i]+H[i+1]-1]}$${\ Displaystyle A[i]}$${\ Displaystyle A[i+1]}$${\görüntüleme stili y}$${\ Displaystyle A[i]}$${\ Displaystyle A[i+1]}$
3. etiketli bir kenar ile yeni oluşturulan dahili düğüme bağlanın . Yeni etiket , silinen kenarın , kenar etiketi olarak kullanılmayan kalan karakterlerinden oluşur .${\görüntüleme stili w}$${\görüntüleme stili y}$${\görüntüleme stili (y,w)}$${\displaystyle S[A[i]+H[i+1],A[i]+d(w)-1]}$${\görüntüleme stili (v,w)}$${\görüntüleme stili (v,y)}$
4. Yeni bir yaprak olarak ekleyin ve etiketli bir kenar ile yeni dahili düğüme bağlayın . Böylece kenar etiketi , kök- yolun etiketlerinin birleştirilmesiyle halihazırda temsil edilmeyen kalan son ek karakterlerinden oluşur .${\ Displaystyle A[i+1]}$${\görüntüleme stili x}$${\görüntüleme stili y}$${\görüntüleme stili (y,x)}$${\displaystyle S[A[i+1]+H[i+1],n]}$${\ Displaystyle A[i+1]}$${\görüntüleme stili v}$
5. Bu, kısmi sonek ağacını oluşturur .${\displaystyle ST_{i+1}}$

Basit bir amortisman argümanı, bu algoritmanın çalışma süresinin aşağıdakilerle sınırlı olduğunu gösterir : ${\görüntüleme stili O(n)}$

En sağdaki yoldan yukarı yürüyerek adım adım gidilen düğümler (son düğüm dışında ) ağaca yeni bir yaprak olarak eklendiğinde en sağdaki yoldan çıkarılır . Bu düğümler, sonraki tüm adımlar için bir daha asla geçilmeyecektir . Bu nedenle, toplamda en fazla düğüm geçilecektir. ${\görüntüleme stili ben}$${\displaystyle ST_{i}}$${\görüntüleme stili v}$${\ Displaystyle A[i+1]}$${\displaystyle j>i}$${\ Displaystyle 2n}$

İsteğe bağlı son ekler için LCP sorguları

LCP dizisi, yalnızca sonek dizisindeki her ardışık son ek çiftinin en uzun ortak önekinin uzunluğunu içerir . Bununla birlikte, ters eki dizisinin yardımı ile ( örneğin, eki, konumunda başlar bu olarak bir pozisyonda muhafaza edilir olarak ve sabit zaman) aralığı en az bir sorgu ile , keyfi eklerinden en uzun ortak prefiks uzunluğunu belirlemek mümkündür içinde zaman. ${\görüntüleme stili H}$${\görüntüleme stili A}$${\görüntüleme stili A^{-1}}$${\displaystyle A[i]=j\Leftrightarrow A^{-1}[j]=i}$${\görüntüleme stili S[j,n]}$${\görüntüleme stili j}$${\görüntüleme stili S}$${\ Displaystyle A^{-1}[j]}$${\görüntüleme stili A}$${\görüntüleme stili H}$${\görüntüleme stili O(1)}$

Çünkü eki dizisinin lexicographic düzenin, soneklerinin her ortak öneki ve arasındaki tüm eklerinden ortak bir ön ek olarak var 'soneki dizideki s konumuna ve ' soneki dizideki s konumu . Bu nedenle, tüm bu eklerin paylaştığı en uzun ön ekin uzunluğu , aralıktaki minimum değerdir . Bu değer, aralık minimum sorguları için önceden işlenmişse sabit zamanda bulunabilir . ${\ Displaystyle S[i,n]}$${\görüntüleme stili S[j,n]}$${\görüntüleme stili ben}$${\ Displaystyle A^{-1}[i]}$${\görüntüleme stili j}$${\ Displaystyle A^{-1}[j]}$${\displaystyle H[A^{-1}[i]+1,A^{-1}[j]]}$${\görüntüleme stili H}$

Bu nedenle, bir dizge uzunlukta ve rasgele iki pozisyon dizede ile , soneklerinin uzun ortak önek uzunluğunu ve aşağıdaki gibi hesaplanır: . ${\görüntüleme stili S}$${\görüntüleme stili n}$${\görüntüleme stili ben,j}$${\görüntüleme stili S}$${\displaystyle A^{-1}[i]<A^{-1}[j]}$${\ Displaystyle S[i,n]}$${\görüntüleme stili S[j,n]}$${\displaystyle \operatöradı {LCP} (i,j)=H[\operatöradı {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])]}$

Notlar

Referanslar

• Abouelhoda, Mohamed İbrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). "Gelişmiş sonek dizileri ile sonek ağaçlarının değiştirilmesi" . Ayrık Algoritmalar Dergisi . 2 : 53–86. doi : 10.1016/S1570-8667(03)00065-0 .
• Manber, Udi; Myers, Gene (1993). "Son Ek Dizileri: Çevrimiçi Dizi Aramaları İçin Yeni Bir Yöntem". SIAM Journal on Computing . 22 (5): 935. CiteSeerX  10.1.1.105.6571 . doi : 10.1137/0222058 . S2CID  5074629 .
• Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K. (2001). Sonek Dizilerinde Doğrusal Zamanlı En Uzun Ortak Önek Hesaplaması ve Uygulamaları . 12. Yıllık Kombinatoryal Model Eşleştirme Sempozyumu Tutanakları. Bilgisayar Bilimleri Ders Notları. 2089 . s. 181–192. doi : 10.1007/3-540-48194-X_17 . ISBN'si 978-3-540-42271-6.
• Ohlebusch, Enno; Fischer, Johannes; Gog, Simon (2010). CST++ . Dize İşleme ve Bilgi Alma. Bilgisayar Bilimleri Ders Notları. 6393 . s. 322. doi : 10.1007/978-3-642-16321-0_34 . ISBN'si 978-3-642-16320-3.
• Kärkkäinen, Juha; Sanders, Peter (2003). Basit doğrusal çalışma eki dizi yapısı . Otomatlar, diller ve programlama üzerine 30. uluslararası konferansın bildirileri. s. 943–955 . 2012-08-28 alındı .
• Fischer, Johannes (2011). LCP-Array'i indükleme . Algoritmalar ve Veri Yapıları. Bilgisayar Bilimleri Ders Notları. 6844 . s. 374–385. arXiv : 1101.3448 . doi : 10.1007/978-3-642-22300-6_32 . ISBN'si 978-3-642-22299-3.
• Manzini, Giovanni (2004). Doğrusal Zaman LCP Dizisi Hesaplaması için Yerden Tasarruf Sağlayan İki Hile . Algoritma Teorisi - SWAT 2004. Bilgisayar Bilimleri Ders Notları. 3111 . s. 372. doi : 10.1007/978-3-540-27810-8_32 . ISBN'si 978-3-540-22339-9.
• Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J. (2009). İzin Verilen En Uzun-Ortak Önek Dizisi . Kombinatoryal Model Eşleştirme. Bilgisayar Bilimleri Ders Notları. 5577 . s. 181. doi : 10.1007/978-3-642-02441-2_17 . ISBN'si 978-3-642-02440-5.
• Puglisi, Simon J.; Turpin, Andrew (2008). En Uzun-Ortak-Önek Dizi Hesaplaması için Uzay-Zaman Tazminatları . Algoritmalar ve Hesaplama. Bilgisayar Bilimleri Ders Notları. 5369 . s. 124. doi : 10.1007/978-3-540-92182-0_14 . ISBN'si 978-3-540-92181-3.
• Gog, Simon; Ohlebusch, Enno (2011). Hızlı ve Hafif LCP-Dizi Yapı Algoritmaları (PDF) . Algoritma Mühendisliği ve Deneyleri Çalıştayının Tutanakları, ALENEX 2011. s. 25–34 . 2012-08-28 alındı .
• 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ı. s. 193. doi : 10.1109/DCC.2009.42 . ISBN'si 978-0-7695-3592-0.
• Fischer, Johannes; Heun, Volker (2007). Gelişmiş Sonek Dizisindeki RMQ-Bilgisinin ve İyileştirmelerin Yeni Kısa Bir Temsili . Kombinatorik, Algoritmalar, Olasılıksal ve Deneysel Metodolojiler. Bilgisayar Bilimleri Ders Notları. 4614 . s. 459. doi : 10.1007/978-3-540-74450-4_41 . ISBN'si 978-3-540-74449-8.
• Chen, G.; Puglisi, SJ; Smyth, WF (2008). "Daha Az Zaman ve Mekan Kullanarak Lempel–Ziv Çarpanlara ayırma". Bilgisayar Bilimlerinde Matematik . 1 (4): 605. doi : 10.1007/s11786-007-0024-4 . S2CID  1721891 .
• Crochemore, M.; Ilie, L. (2008). "Doğrusal zaman ve uygulamalarda En Uzun Önceki Faktörü Hesaplama". Bilgi İşlem Mektupları . 106 (2): 75. CiteSeerX  10.1.1.70.5720 . doi : 10.1016/j.ipl.2007.100.06 .
• Crochemore, M.; Ilie, L.; Smyth, WF (2008). Lempel Ziv Faktorizasyonunu Hesaplamak İçin Basit Bir Algoritma . Veri Sıkıştırma Konferansı (dcc 2008). s. 482. doi : 10.1109/DCC.2008.36 . hdl : 20.500.11937/5907 . ISBN'si 978-0-7695-3121-2.
• Sadakane, K. (2007). "Tam İşlevselliğe Sahip Sıkıştırılmış Sonek Ağaçları". Hesaplama Sistemleri Teorisi . 41 (4): 589-607. CiteSeerX  10.1.1.224.4152 . doi : 10.1007/s00224-006-1198-x . S2CID  263130 .
• Fischer, Johannes; Makinen, Veli; Navarro, Gonzalo (2009). "Daha hızlı entropi-sınırlı sıkıştırılmış sonek ağaçları". Teorik Bilgisayar Bilimi . 410 (51): 5354. doi : 10.1016/j.tcs.2009.09.012 .
• Fischer, Johannes; Kurpicz, Florian (5 Ekim 2017). "DivSufSort'un Sökülmesi". Prag Stringology Konferansı 2017 Bildiriler Kitabı . arXiv : 1710.01896 .

Dış bağlantılar

• Fischer'de (2011) açıklanan kodun geçici uygulamasının aynası
• SDSL: Kısa Veri Yapısı Kitaplığı - Çeşitli LCP dizi uygulamaları, Minimum Aralık Sorgusu (RMQ) destek yapıları ve daha birçok kısa ve öz veri yapısı sağlar
• Son ek dizisi ve LCP dizisi (Java) kullanılarak öykünülmüş aşağıdan yukarıya son ek ağacı geçişi
• Metin-İndeksleme projesi (sonek ağaçlarının, sonek dizilerinin, LCP dizisinin ve Burrows-Wheeler Transform'un doğrusal zamanlı inşası )