LCP-array - LCP array

LCP-array
Typ	Array
Uppfunnet av	Manber & Myers (1990)harvtxt-fel: inget mål: CITEREFManberMyers1990 ( hjälp )
Tidskomplexitet och rymdkomplexitet i stor O-notation
	Genomsnitt	Värsta fall
Plats	${\ displaystyle {\ mathcal {O}} (n)}$	${\ displaystyle {\ mathcal {O}} (n)}$
Konstruktion	${\ displaystyle {\ mathcal {O}} (n)}$	${\ displaystyle {\ mathcal {O}} (n)}$

Inom datavetenskap är den längsta vanliga prefixmatrisen ( LCP- array ) en hjälpdatastruktur för suffixmatrisen . Den lagrar längderna på de längsta vanliga prefixen (LCP) mellan alla par av på varandra följande suffix i en sorterad suffixmatris.

Till exempel, om A  : = [aab, ab, abaab, b, baab] är en suffixmatris, det längsta vanliga prefixet mellan A [1] =aaboch A [2] =ab är asom har längden 1, så H [2] = 1 i LCP array H . Likaså LCP för A [2] =aboch A [3] =abaab är ab, så H [3] = 2.

Genom att förstärka suffixmatrisen med LCP-matrisen kan man effektivt simulera över- och nedåt-upp- traverser av suffixträdet , påskyndar mönstermatchning på suffixmatrisen och är en förutsättning för komprimerade suffixträd.

Historia

LCP-matrisen introducerades 1993 av Udi Manber och Gene Myers vid sidan av suffixmatrisen för att förbättra körtiden för deras strängsökalgoritm.

Definition

Låta vara suffix utbud av strängen längd , där är en vaktpost brev som är unikt och lexikografiskt mindre än någon annan karaktär. Låt beteckna substringen från allt till . Således är det minsta suffixet av . ${\ displaystyle A}$${\ displaystyle S = s_ {1}, s_ {2}, \ ldots s_ {n-1} \ $}$${\ displaystyle n}$${\ displaystyle \ $}$${\ displaystyle S [i, j]}$${\ displaystyle S}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle S [A [i], n]}$${\ displaystyle i}$${\ displaystyle S}$

Låt beteckna längden på det längsta vanliga prefixet mellan två strängar och . Då är LCP-arrayen ett heltal-array med en sådan storlek som är odefinierad och för alla . Lagrar således längden på det längsta gemensamma prefixet för det lexikografiskt minsta suffixet och dess föregångare i suffixmatrisen. ${\ displaystyle \ operatorname {lcp} (v, w)}$${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle H [1, n]}$${\ displaystyle n}$${\ displaystyle H [1]}$${\ displaystyle H [i] = \ operatorname {lcp} (S [A [i-1], n], S [A [i], n])}$${\ displaystyle 1 <i \ leq n}$${\ displaystyle H [i]}$${\ displaystyle i}$

Skillnad mellan LCP-array och suffix-array:

• Suffix array: Representerar den leksikografiska rangordningen för varje suffix i en array.
• LCP-array: Innehåller den maximala längdens prefixmatchning mellan två efterföljande suffix efter att de har sorterats lexikografiskt.

Exempel

Tänk på strängen : ${\ displaystyle S = {\ textrm {banan \ $}}}$

och dess motsvarande sorterade suffixmatris  : ${\ displaystyle A}$

Suffix array med suffix skrivna ut vertikalt nedan:

Sedan konstrueras LCP-arrayen genom att jämföra lexikografiskt på varandra följande suffix för att bestämma deras längsta gemensamma prefix: ${\ displaystyle H}$

Så, till exempel, är längden på det längsta vanliga prefixet som delas av suffixen och . Observera att det är odefinierat, eftersom det inte finns något lexikografiskt mindre suffix. ${\ displaystyle H [3] = 3}$${\ displaystyle {\ text {ana}}}$${\ displaystyle A [3] = S [4,7] = {\ textrm {ana \ $}}}$${\ displaystyle A [4] = S [2,7] = {\ textrm {anana \ $}}}$${\ displaystyle H [1]}$

Effektiva konstruktionsalgoritmer

LCP-arraykonstruktionsalgoritmer kan delas in i två olika kategorier: algoritmer som beräknar LCP-arrayen som en biprodukt till suffixmatrisen och algoritmer som använder en redan konstruerad suffixmatris för att beräkna LCP-värdena.

Manber & Myers (1993) tillhandahåller en algoritm för att beräkna LCP-matrisen tillsammans med suffixmatrisen i tid. Kärkkäinen & Sanders (2003) visar att det också är möjligt att ändra deras tidsalgoritm så att den också beräknar LCP-matrisen. Kasai et al. (2001) presenterar första gången algoritmen (FLAAP) som beräknar LCP-matrisen med tanke på texten och suffixmatrisen. ${\ displaystyle O (n \ log n)}$${\ displaystyle O (n)}$${\ displaystyle O (n)}$

Förutsatt att varje textsymbol tar en byte och varje inmatning av suffixet eller LCP-matrisen tar 4 byte, är den största nackdelen med deras algoritm en stor utrymmesbeläggning av byte, medan originalutmatningen (text, suffixmatris, LCP-array) endast upptar byte. Därför, Manzini (2004) skapade en förfinad version av algoritmen enligt Kasai et al. (2001) (lcp9) och minskade rymdbeläggningen till byte. Kärkkäinen, Manzini & Puglisi (2009) ger ytterligare en förfining av Kasais algoritm ( -algoritm) som förbättrar körtiden. I stället för den faktiska LCP-matrisen bygger denna algoritm den permuterade LCP (PLCP) -matrisen, där värdena visas i textordning snarare än i lexikografisk ordning. ${\ displaystyle 13n}$${\ displaystyle 9n}$${\ displaystyle 9n}$${\ displaystyle \ Phi}$

Gog & Ohlebusch (2011) tillhandahåller två algoritmer som trots att de var teoretiskt långsamma ( ) var snabbare än de ovan nämnda algoritmerna i praktiken. ${\ displaystyle O (n ^ {2})}$

Från och med 2012 beror den för närvarande snabbaste linjära LCP-array-konstruktionsalgoritmen på Fischer (2011) , som i sin tur baseras på en av de snabbaste suffix-array-konstruktionsalgoritmerna (SA-IS) av Nong, Zhang & Chan (2009). . Fischer & Kurpicz (2017) baserad på Yuta Moris DivSufSort är ännu snabbare.

Applikationer

Som noterats av Abouelhoda, Kurtz & Ohlebusch (2004) kan flera strängbearbetningsproblem lösas med följande typer av trädkorsningar :

• nedifrån och upp-traversering av hela suffixträdet
• uppifrån och ner genomkorsning av en subtree av suffixträdet
• suffix trädkorsning med hjälp av suffixlänkarna.

Kasai et al. (2001) visar hur man simulerar en nedifrån och upp-genomgång av suffixträdet med endast suffixmatrisen och LCP-matrisen. Abouelhoda, Kurtz & Ohlebusch (2004) förbättrar suffixmatrisen med LCP-arrayen och ytterligare datastrukturer och beskriver hur denna förbättrade suffixmatris kan användas för att simulera alla tre typer av suffixträdkorsningar. Fischer & Heun (2007) minskar utrymmeskraven för den förbättrade suffixmatrisen genom att förbehandla LCP-matrisen för intervallminsta frågor . Således kan alla problem som kan lösas med suffixträdalgoritmer också lösas med hjälp av den förbättrade suffixmatrisen .

Att avgöra om ett mönster med längden är en delsträng av en sträng med längden tar tid om endast suffixet arrayen används. Genom att dessutom använda LCP-informationen kan denna gräns förbättras med tiden. Abouelhoda, Kurtz & Ohlebusch (2004) visar hur man kan förbättra den här körtiden ytterligare för att uppnå optimal tid. Således, med hjälp av suffixmatris och LCP-matrisinformation, kan beslutsfrågan besvaras lika snabbt som att använda suffixträdet . ${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle S}$${\ displaystyle n}$${\ displaystyle O (m \ log n)}$${\ displaystyle O (m + \ log n)}$${\ displaystyle O (m)}$

LCP-arrayen är också en väsentlig del av komprimerade suffixträd som ger full suffixträdfunktionalitet som suffixlänkar och lägsta vanliga förfäderfrågor . Dessutom kan den användas tillsammans med suffixmatrisen för att beräkna Lempel-Ziv LZ77- faktorisering i tid. ${\ displaystyle O (n)}$

Den längsta upprepad träng problem för en sträng av längd kan lösas i tid med användning av både suffixet arrayen och LCP array. Det räcker att utföra en linjär genomsökning genom LCP-matrisen för att hitta dess maximala värde och motsvarande index där lagras. Det längsta underlaget som inträffar minst två gånger ges sedan av . ${\ displaystyle S}$${\ displaystyle n}$${\ displaystyle \ Theta (n)}$${\ displaystyle A}$${\ displaystyle v_ {max}}$${\ displaystyle i}$${\ displaystyle v_ {max}}$${\ displaystyle S [A [i], A [i] + v_ {max} -1]}$

Resten av detta avsnitt förklarar två tillämpningar av LCP-arrayen mer detaljerat: Hur suffixmatrisen och LCP-matrisen för en sträng kan användas för att konstruera motsvarande suffixträd och hur det är möjligt att svara på LCP-frågor för godtyckliga suffix med intervall minimifrågor på LCP-matrisen.

Hitta antalet förekomster av ett mönster

För att hitta antalet förekomster av en given sträng (längd ) i en text (längd ), ${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle T}$${\ displaystyle N}$

• Vi använder binär sökning mot suffixmatrisen för att hitta start- och slutposition för alla förekomster av .${\ displaystyle T}$${\ displaystyle P}$
• Nu för att påskynda sökningen använder vi LCP-array, specifikt en specialversion av LCP-array (LCP-LR nedan).

Problemet med att använda standard binär sökning (utan LCP-information) är att i var och en av de jämförelser som behövs görs, jämför vi P med den aktuella posten i suffixmatrisen, vilket innebär en fullständig strängjämförelse på upp till m tecken. Så komplexiteten är . ${\ displaystyle O (\ log N)}$${\ displaystyle O (m \ log N)}$

LCP-LR-arrayen hjälper till att förbättra detta på följande sätt: ${\ displaystyle O (m + \ log N)}$

När som helst under den binära sökalgoritmen överväger vi, som vanligt, ett intervall för suffixmatrisen och dess centrala punkt , och beslutar om vi fortsätter vår sökning i det vänstra delområdet eller i det högra delområdet . För att fatta beslutet jämför vi med strängen på . Om är identiskt med , är vår sökning klar. Men om inte, har vi redan jämfört de första tecknen i och sedan bestämt oss för om det är lexikografiskt mindre eller större än . Låt oss anta att resultatet blir större än . Så i nästa steg överväger vi och en ny central punkt i mitten: ${\ displaystyle (L, \ dots, R)}$${\ displaystyle M}$${\ displaystyle (L, \ dots, M)}$${\ displaystyle (M, \ dots, R)}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle k}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle (M, \ dots, R)}$${\ displaystyle M '}$

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

Tricket är nu att LCP-LR förberäknas så att en -lookup berättar den längsta gemensamma prefix och , . ${\ displaystyle O (1)}$${\ displaystyle M}$${\ displaystyle M '}$${\ displaystyle \ mathrm {lcp} (M, M ')}$

Vi vet redan (från föregående steg) som själv har ett prefix av tecken gemensamma med : . Nu finns det tre möjligheter: ${\ displaystyle M}$${\ displaystyle k}$${\ displaystyle P}$${\ displaystyle \ mathrm {lcp} (P, M) = k}$

• Fall 1:, dvs har färre prefix tecken gemensamt med M än M har gemensamt med M '. Detta betyder att (k + 1) -teckenet för M 'är detsamma som för M, och eftersom P är lexikografiskt större än M, måste det också vara lexikografiskt större än M'. Så vi fortsätter i högra halvan (M ', ..., R).${\ displaystyle k <\ mathrm {lcp} (M, M ')}$${\ displaystyle P}$
• Fall 2:, dvs har fler prefix tecken gemensamt med än har gemensamt med . Följaktligen, om vi skulle jämföra med , skulle det gemensamma prefixet vara mindre än och vara lexikografiskt större än , så utan att faktiskt göra jämförelsen, fortsätter vi i vänstra halvan .${\ displaystyle k> \ mathrm {lcp} (M, M ')}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle M}$${\ displaystyle M '}$${\ displaystyle P}$${\ displaystyle M '}$${\ displaystyle k}$${\ displaystyle M '}$${\ displaystyle P}$${\ displaystyle (M, \ dots, M ')}$
• Fall 3: . Så M och M 'är båda identiska med i de första tecknen. För att avgöra om vi fortsätter i vänstra eller högra halvan räcker det med att jämföra med utgångspunkt från den th karaktären.${\ displaystyle k = \ mathrm {lcp} (M, M ')}$${\ displaystyle P}$${\ displaystyle k}$${\ displaystyle P}$${\ displaystyle M '}$${\ displaystyle (k + 1)}$
• Vi fortsätter rekursivt.

Den totala effekten är att ingen karaktär av jämförs med någon karaktär i texten mer än en gång. Det totala antalet teckenjämförelser begränsas av , så den totala komplexiteten är verkligen . ${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle O (m + logN)}$

Vi behöver fortfarande förberäkna LCP-LR så att det i tid kan berätta lcp mellan två poster i suffixmatrisen. Vi vet att LCP: s standardmatris endast ger oss lcp för på varandra följande poster, dvs för alla . Men, och i beskrivningen ovan är inte nödvändigtvis på varandra följande poster. ${\ displaystyle O (1)}$${\ displaystyle \ mathrm {lcp} (i-1, i)}$${\ displaystyle i}$${\ displaystyle M}$${\ displaystyle M '}$

Nyckeln till detta är att inse att endast vissa områden någonsin kommer att inträffa under den binära sökningen: Det börjar alltid med och delar upp det i mitten, och fortsätter sedan antingen till vänster eller höger och dela den halva igen och så vidare. Ett annat sätt att titta på det är: varje post i suffixmatrisen sker som en central punkt i exakt ett möjligt intervall under binär sökning. Så det finns exakt N distinkta områden som möjligen kan spela en roll under binär sökning, och det räcker att förberäkna och för de möjliga intervallen. Så det är distinkta förberäknade värden, därför är LCP-LR i storlek. ${\ displaystyle (L, \ dots, R)}$${\ displaystyle (0, \ dots, N)}$${\ displaystyle (L \ dots M \ dots R)}$${\ displaystyle \ mathrm {lcp} (L, M)}$${\ displaystyle \ mathrm {lcp} (M, R)}$${\ displaystyle N}$${\ displaystyle 2N}$${\ displaystyle O (N)}$

Dessutom finns det en rak rekursiv algoritm för att beräkna värdena för LCP-LR i tid från standard LCP-matrisen. ${\ displaystyle 2N}$${\ displaystyle O (N)}$

För att sammanfatta:

• Det är möjligt att beräkna LCP-LR i tid och rum från LCP.${\ displaystyle O (N)}$${\ displaystyle O (2N) = O (N)}$
• Användning av LCP-LR under binär sökning hjälper till att påskynda sökproceduren från till .${\ displaystyle O (M \ log N)}$${\ displaystyle O (M + logN)}$
• Vi kan använda två binära sökningar för att bestämma vänster och höger ände för matchningsområdet för , och längden på matchningsområdet motsvarar antalet förekomster för P.${\ displaystyle P}$

Suffix trädkonstruktion

Med tanke på suffix array och LCP matrisen av en sträng av längd , dess suffix träd kan konstrueras i tid baserat på följande idé: Börja med den partiella suffix träd för lexikografiskt minsta suffix och upprepade gånger insatsen andra suffix i den ordning som ges av suffixmatrisen. ${\ displaystyle A}$${\ displaystyle H}$${\ displaystyle S = s_ {1}, s_ {2}, \ ldots s_ {n} \ $}$${\ displaystyle n + 1}$${\ displaystyle ST}$${\ displaystyle O (n)}$

Låt vara det partiella suffixträdet för . Låt oss dessutom vara längden på sammanfogningen av alla banetiketter från roten till noden . ${\ displaystyle ST_ {i}}$${\ displaystyle 0 \ leq i \ leq n}$${\ displaystyle d (v)}$${\ displaystyle ST_ {i}}$${\ displaystyle v}$

Fall 1 ( ): Antag suffixen , , och av strängen är redan lagts till suffixet trädet. Sedan läggs suffixet till trädet som visas på bilden. Den högra banan markeras i rött.${\ displaystyle d (v) = H [i + 1]}$${\ displaystyle a \ $}$${\ displaystyle ana \ $}$${\ displaystyle anana \ $}$${\ displaystyle banan \ $}$${\ displaystyle S = banan \ $}$${\ displaystyle na \ $}$

Börja med , trädet består endast av roten. För att infoga i , gå upp längst till höger med början på det nyligen infogade bladet till roten tills den djupaste noden med nås. ${\ displaystyle ST_ {0}}$${\ displaystyle A [i + 1]}$${\ displaystyle ST_ {i}}$${\ displaystyle A [i]}$${\ displaystyle v}$${\ displaystyle d (v) \ leq H [i + 1]}$

Vi måste skilja mellan två fall:

• ${\ displaystyle d (v) = H [i + 1]}$: Detta innebär att sammanfogningen av etiketterna på root-to- path är lika med det längsta vanliga prefixet för suffix och . I det här fallet infogar du som ett nytt blad av noden och märker kanten med . Kantetiketten består alltså av de återstående tecknen på suffixet som inte redan representeras av sammankopplingen av etiketterna från rot-till- sökvägen. Detta skapar trädets partiella suffix .${\ displaystyle v}$${\ displaystyle A [i]}$${\ displaystyle A [i + 1]}$
  ${\ displaystyle A [i + 1]}$${\ displaystyle x}$${\ displaystyle v}$${\ displaystyle (v, x)}$${\ displaystyle S [A [i + 1] + H [i + 1], n]}$${\ displaystyle A [i + 1]}$${\ displaystyle v}$
  ${\ displaystyle ST_ {i + 1}}$
  

  Fall 2 ( ): För att lägga till suffix måste kanten på det tidigare infogade suffixet delas upp. Den nya kanten till den nya interna noden är märkt med det längsta vanliga prefixet för suffixen och . Kanterna som förbinder de två bladen är märkta med de återstående suffikstecknen som inte ingår i prefixet.${\ displaystyle d (v) <H [i + 1]}$${\ displaystyle nana \ $}$${\ displaystyle na \ $}$${\ displaystyle na \ $}$${\ displaystyle nana \ $}$
• ${\ displaystyle d (v) <H [i + 1]}$: Detta innebär att sammanlänkningen av etiketterna om grund-till path displayer färre tecken än den längsta gemensamma prefixet av suffix och och de saknade tecken ingår i kant etikett s högra kant. Därför måste vi dela upp den kanten på följande sätt: Låt vara barnet på vägen längst till höger.${\ displaystyle v}$${\ displaystyle A [i]}$${\ displaystyle A [i + 1]}$${\ displaystyle v}$
  ${\ displaystyle w}$${\ displaystyle v}$${\ displaystyle ST_ {i}}$

1. Ta bort kanten .${\ displaystyle (v, w)}$
2. Lägg till en ny intern nod och en ny kant med etikett . Den nya etiketten består av saknade tecken i det längsta vanliga prefixet av och . Sammankopplingen av etiketterna från rot-till- sökvägen visar nu det längsta vanliga prefixet för och .${\ displaystyle y}$${\ displaystyle (v, y)}$${\ displaystyle S [A [i] + d (v), A [i] + H [i + 1] -1]}$${\ displaystyle A [i]}$${\ displaystyle A [i + 1]}$${\ displaystyle y}$${\ displaystyle A [i]}$${\ displaystyle A [i + 1]}$
3. Anslut till den nyligen skapade interna noden med en kant som är märkt . Den nya etiketten består av de återstående tecknen i den borttagna kanten som inte användes som etiketten på kanten .${\ displaystyle w}$${\ displaystyle y}$${\ displaystyle (y, w)}$${\ displaystyle S [A [i] + H [i + 1], A [i] + d (w) -1]}$${\ displaystyle (v, w)}$${\ displaystyle (v, y)}$
4. Lägg till som ett nytt blad och anslut det till den nya interna noden med en kant som är märkt . Således består kantetiketten av de återstående tecknen på suffixet som inte redan representeras av sammankopplingen av etiketterna från root-to- path.${\ displaystyle A [i + 1]}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (y, x)}$${\ displaystyle S [A [i + 1] + H [i + 1], n]}$${\ displaystyle A [i + 1]}$${\ displaystyle v}$
5. Detta skapar trädets partiella suffix .${\ displaystyle ST_ {i + 1}}$

Ett enkelt amorteringsargument visar att algoritmens körtid begränsas av : ${\ displaystyle O (n)}$

Noderna som passeras i steg genom att gå upp längst till höger (förutom den sista noden ) tas bort från den längst till höger när de läggs till i trädet som ett nytt blad. Dessa noder kommer aldrig att passeras igen för alla efterföljande steg . Därför kommer högst noder att passeras totalt. ${\ displaystyle i}$${\ displaystyle ST_ {i}}$${\ displaystyle v}$${\ displaystyle A [i + 1]}$${\ displaystyle j> i}$${\ displaystyle 2n}$

LCP-frågor för godtyckliga suffix

LCP-matrisen innehåller endast längden på det längsta gemensamma prefixet för varje par på varandra följande suffix i suffixmatrisen . Men med hjälp av den inversa suffixmatrisen ( dvs. suffixet som börjar vid position in lagras i position i ) och konstant tidsintervall minimifrågor på , är det möjligt att bestämma längden på det längsta vanliga prefixet för godtyckliga suffix. i tid. ${\ displaystyle H}$${\ displaystyle A}$${\ displaystyle A ^ {- 1}}$${\ displaystyle A [i] = j \ Vänsterstråk A ^ {- 1} [j] = i}$${\ displaystyle S [j, n]}$${\ displaystyle j}$${\ displaystyle S}$${\ displaystyle A ^ {- 1} [j]}$${\ displaystyle A}$${\ displaystyle H}$${\ displaystyle O (1)}$

På grund av den lexikografisk ordning suffixet array, varje gemensam prefix suffixen och måste vara ett gemensamt prefix för alla suffix mellan position i suffixet array och ställning i suffixet array . Därför är längden på det längsta prefixet som delas av alla dessa suffix det minsta värdet i intervallet . Detta värde kan hittas i konstant tid om det är förbehandlat för intervallminsta frågor. ${\ displaystyle S [i, n]}$${\ displaystyle S [j, n]}$${\ displaystyle i}$${\ displaystyle A ^ {- 1} [i]}$${\ displaystyle j}$${\ displaystyle A ^ {- 1} [j]}$${\ displaystyle H [A ^ {- 1} [i] + 1, A ^ {- 1} [j]]}$${\ displaystyle H}$

Således ges en sträng av längd och två godtyckliga positioner i strängen med , längden hos den längsta gemensamma prefixet av suffixen och kan beräknas enligt följande: . ${\ displaystyle S}$${\ displaystyle n}$${\ displaystyle i, j}$${\ displaystyle S}$${\ displaystyle A ^ {- 1} [i] <A ^ {- 1} [j]}$${\ displaystyle S [i, n]}$${\ displaystyle S [j, n]}$${\ displaystyle \ operatorname {LCP} (i, j) = H [\ operatorname {RMQ} _ {H} (A ^ {- 1} [i] + 1, A ^ {- 1} [j])]}$

Anteckningar

Referenser

• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). Msgstr "Ersätter suffixträd med förbättrade suffixmatriser" . Journal of Discrete Algorithms . 2 : 53–86. doi : 10.1016 / S1570-8667 (03) 00065-0 .
• Manber, Udi; Myers, Gene (1993). "Suffix arrays: En ny metod för on-line strängsökningar". 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). Beräkning av linjär tid längst-vanliga prefix i suffixarrayer och dess tillämpningar . Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. Föreläsningsanteckningar inom datavetenskap. 2089 . s. 181–192. doi : 10.1007 / 3-540-48194-X_17 . ISBN 978-3-540-42271-6.
• Ohlebusch, Enno; Fischer, Johannes; Gog, Simon (2010). CST ++ . Strängbehandling och informationshämtning. Föreläsningsanteckningar inom datavetenskap. 6393 . sid. 322. doi : 10.1007 / 978-3-642-16321-0_34 . ISBN 978-3-642-16320-3.
• Kärkkäinen, Juha; Sanders, Peter (2003). Enkel linjär arbetssuffix array konstruktion . Fortsättningar från den 30: e internationella konferensen om automata, språk och programmering. s. 943–955 . Hämtad 28.08.2012 .
• Fischer, Johannes (2011). Framkallar LCP-Array . Algoritmer och datastrukturer. Föreläsningsanteckningar inom datavetenskap. 6844 . s. 374–385. arXiv : 1101.3448 . doi : 10.1007 / 978-3-642-22300-6_32 . ISBN 978-3-642-22299-3.
• Manzini, Giovanni (2004). Två rymdbesparande knep för beräkning av linjär tids LCP-matris . Algoritmteori - SWAT 2004. Föreläsningsanteckningar inom datavetenskap. 3111 . sid. 372. doi : 10.1007 / 978-3-540-27810-8_32 . ISBN 978-3-540-22339-9.
• Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J. (2009). Tillåtna längsta-gemensamma prefixmatriser . Combinatorial Pattern Matching. Föreläsningsanteckningar inom datavetenskap. 5577 . sid. 181. doi : 10.1007 / 978-3-642-02441-2_17 . ISBN 978-3-642-02440-5.
• Puglisi, Simon J .; Turpin, Andrew (2008). Space-Time avvägningar för längsta-Common-Prefix Array Beräkning . Algoritmer och beräkning. Föreläsningsanteckningar inom datavetenskap. 5369 . sid. 124. doi : 10.1007 / 978-3-540-92182-0_14 . ISBN 978-3-540-92181-3.
• Gog, Simon; Ohlebusch, Enno (2011). Snabba och lätta LCP-Array-konstruktionsalgoritmer (PDF) . Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2011. s. 25–34 . Hämtad 28.08.2012 .
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Linjär Suffix Array Construction av nästan ren inducerad sortering . 2009 datakomprimeringskonferens. sid. 193. doi : 10.1109 / DCC.2009.42 . ISBN 978-0-7695-3592-0.
• Fischer, Johannes; Heun, Volker (2007). En ny kortfattad representation av RMQ-information och förbättringar i den förbättrade suffixmatrisen . Kombinatorik, algoritmer, probabilistiska och experimentella metoder. Föreläsningsanteckningar inom datavetenskap. 4614 . sid. 459. doi : 10.1007 / 978-3-540-74450-4_41 . ISBN 978-3-540-74449-8.
• Chen, G .; Puglisi, SJ; Smyth, WF (2008). "Lempel – Ziv-faktorisering med mindre tid och utrymme". Matematik i datavetenskap . 1 (4): 605. doi : 10.1007 / s11786-007-0024-4 . S2CID  1721891 .
• Crochemore, M .; Ilie, L. (2008). "Beräknar längsta tidigare faktor i linjär tid och applikationer". Informationsbehandlingsbrev . 106 (2): 75. CiteSeerX  10.1.1.70.5720 . doi : 10.1016 / j.ipl.2007.10.006 .
• Crochemore, M .; Ilie, L .; Smyth, WF (2008). En enkel algoritm för beräkning av Lempel Ziv-faktorisering . Datakomprimeringskonferens (dcc 2008). sid. 482. doi : 10.1109 / DCC.2008.36 . hdl : 20.500.11937 / 5907 . ISBN 978-0-7695-3121-2.
• Sadakane, K. (2007). "Komprimerade suffixsträd med full funktionalitet". Teori om datorsystem . 41 (4): 589–607. CiteSeerX  10.1.1.224.4152 . doi : 10.1007 / s00224-006-1198-x . S2CID  263130 .
• Fischer, Johannes; Mäkinen, Veli; Navarro, Gonzalo (2009). "Snabbare entropibegränsade komprimerade suffixträd". Teoretisk datavetenskap . 410 (51): 5354. doi : 10.1016 / j.tcs.2009.09.012 .
• Fischer, Johannes; Kurpicz, Florian (5 oktober 2017). "Demontering av DivSufSort". Proceedings of the Prague Stringology Conference 2017 . arXiv : 1710.01896 .

externa länkar

• Spegel av ad hoc-implementeringen av koden som beskrivs i Fischer (2011)
• SDSL: Succinct Data Structure Library - Tillhandahåller olika LCP-arrayimplementeringar, Range Minimum Query (RMQ) -stödstrukturer och många fler kortfattade datastrukturer
• Längst ner-upp-suffixträdkorsning emulerad med hjälp av suffixmatris och LCP-matris (Java)
• Textindexeringsprojekt (linjär tidskonstruktion av suffixträd, suffixmatriser, LCP-array och Burrows-Wheeler Transform )