Suffix träd

Suffixträd för texten BANAN . Varje delsträng avslutas med specialtecknet $ . De sex banorna från roten till bladen (visas som rutor) motsvarar de sex suffixen A$ , NA$ , ANA$ , NANA$ , ANANA$ och BANANA$ . Siffrorna i bladen anger startpositionen för motsvarande suffix. Suffixlänkar, ritade streckade, används under konstruktionen.

Inom datavetenskap är ett suffixträd (även kallat PAT-träd eller, i tidigare form, positionsträd ) ett komprimerat försök som innehåller alla suffixen i den givna texten som deras nycklar och positioner i texten som deras värden. Suffixträd tillåter särskilt snabba implementeringar av många viktiga strängoperationer.

Konstruktionen av ett sådant träd för strängen $S$ tar tid och utrymme linjärt i längden av $S$ . När de har konstruerats kan flera operationer utföras snabbt, till exempel att lokalisera en delsträng i $S$ , lokalisera en delsträng om ett visst antal misstag är tillåtna, hitta matchningar för ett reguljärt uttrycksmönster etc. Suffixträd gav också ett av de första linjära tidslösningarna för det längsta vanliga delsträngsproblemet . Dessa speedups har en kostnad: att lagra en strängs suffixträd kräver vanligtvis betydligt mer utrymme än att lagra själva strängen.

Historia

Konceptet introducerades först av Weiner (1973) . Snarare än suffixet $S[i..n]$ , Weiner lagrade i sin försök prefixidentifieraren för varje position, det vill säga den kortaste strängen som börjar vid $i$ och förekommer endast en gång i $S$ . Hans Algoritm D tar ett okomprimerat försök för $S[k+1..n]$ och utökar det till ett försök för $S[k..n]$ . På detta sätt, med utgångspunkt från det triviala försöket för $S[n..n]$ , ett försök för $S[1..n]$ kan byggas av $n-1$ i följd anrop till Algoritm D; den totala körtiden är dock $O(n^{2})$ . Weiners algoritm B upprätthåller flera extra datastrukturer för att uppnå en överallt linjär körtid i storleken på den konstruerade trie. De senare kan fortfarande vara $O(n^{2})$ noder, t.ex. för $S=a^{n}b^{n}a^{n}b^{n}\$.$ Weiners algoritm C använder slutligen komprimerade försök för att uppnå linjär total lagringsstorlek och körtid. Donald Knuth karakteriserade senare den senare som "Årets algoritm 1973". Läroboken Aho, Hopcroft & Ullman (1974 , avsnitt 9.5) återgav Weiners resultat i en förenklad och mer elegant form, och introducerade termen positionsträd .

McCreight (1976) var den första som byggde ett (komprimerat) försök av alla suffix av $S$ . Även om suffixet som börjar på $i$ vanligtvis är längre än prefixidentifieraren, skiljer sig deras sökvägsrepresentationer i ett komprimerat försök inte i storlek. Å andra sidan kunde McCreight avstå från de flesta av Weiners extra datastrukturer; bara suffixlänkar kvar.

Ukkonen (1995) förenklade konstruktionen ytterligare. Han tillhandahöll den första onlinekonstruktionen av suffixträd, nu känd som Ukkonens algoritm , med körtid som matchade de då snabbaste algoritmerna. Dessa algoritmer är alla linjära tider för ett alfabet av konstant storlek, och har i värsta fall körtid $O(n\log n)$ i allmänhet.

Farach (1997) gav den första suffixträdkonstruktionsalgoritmen som är optimal för alla alfabet. I synnerhet är detta den första linjära tidsalgoritmen för strängar som dras från ett alfabet av heltal i ett polynomområde. Farachs algoritm har blivit grunden för nya algoritmer för att konstruera både suffixträd och suffixarrayer , till exempel i externt minne, komprimerat, kortfattat, etc.

Definition

Suffixträdet för strängen $S$ med längden $n$ definieras som ett träd så att:

• Trädet har exakt n blad numrerade från $1$ till $n$ .
• Förutom roten har varje intern nod minst två barn.
• Varje kant är märkt med en icke-tom delsträng av $S$ .
• Inga två kanter som börjar från en nod kan ha strängetiketter som börjar med samma tecken.
• Strängen som erhålls genom att sammanfoga alla strängetiketter som finns på vägen från roten till bladet $i$ stavar suffixet $S[i..n]$ , för $i$ från $1$ till $n$ .

Eftersom ett sådant träd inte finns för alla strängar, är $S$ vadderad med en terminalsymbol som inte syns i strängen (vanligtvis betecknad $ ). Detta säkerställer att inget suffix är ett prefix till ett annat, och att det kommer att finnas $n$ lövnoder, en för vart och ett av de $n$ suffixen av $S$ . Eftersom alla interna icke-rotnoder är förgrenade, kan det finnas högst n − 1 sådana noder, och n + ( n − 1) + 1 = 2 n noder totalt ( n blad, n − 1 interna icke-rotnoder, 1 rot).

Suffixlänkar är en nyckelfunktion för äldre linjärtidskonstruktionsalgoritmer, även om de flesta nyare algoritmer, som är baserade på Farachs algoritm, avstår från suffixlänkar. I ett komplett suffixträd har alla interna icke-rotnoder en suffixlänk till en annan intern nod. Om sökvägen från roten till en nod stavar strängen $\chi \alpha$ , där $\chi$ är ett enda tecken och $\alpha$ är en sträng (eventuellt tom) , den har en suffixlänk till den interna noden som representerar $\alpha$ . Se till exempel suffixlänken från noden för ANA till noden för NA i figuren ovan. Suffixlänkar används också i vissa algoritmer som körs på trädet.

Ett generaliserat suffixträd är ett suffixträd gjort för en uppsättning strängar istället för en enda sträng. Den representerar alla suffix från denna uppsättning strängar. Varje sträng måste avslutas med en annan avslutningssymbol.

Funktionalitet

Ett suffixträd för en sträng $S$ med längden $n$ kan byggas i $\Theta (n)$ tid, om bokstäverna kommer från ett alfabet med heltal i en polynomområde (i synnerhet gäller detta för alfabet med konstant storlek). För större alfabet domineras speltiden genom att först sortera bokstäverna för att få dem till ett område med storleken $O(n)$ ; i allmänhet tar detta $O(n\log n)$ tid. Kostnaderna nedan anges under antagandet att alfabetet är konstant.

Antag att ett suffixträd har byggts för strängen $S$ med längden ${\displaystyle n} ,$ eller att ett generaliserat suffixträd har byggts för uppsättningen strängar $D=\{S_{1},S_{2},\dots ,S_{K}\}$ av total längd $n =n_{1}+n_{2}+\cdots +n_{K}$ . Du kan:

• Sök efter strängar:
  • Kontrollera om en sträng $P$ med längden $m$ är en delsträng i ${\displaystyle O(m)}-$ tid.
  • Hitta den första förekomsten av mönstren $P_{1},\dots ,P_{q}$ av total längd $m$ som delsträngar i $O (m)$ tid.
  • Hitta alla $z$ förekomster av mönstren $P_{1},\dots ,P_{q}$ av total längd $m$ som delsträngar i $O(m+z)$ tid.
  • Sök efter ett reguljärt uttryck P i förväntad tid sublinjär i $n$ .
  • Hitta för varje suffix av ett mönster $P$ , längden på den längsta matchningen mellan ett prefix av $P[i\dots m]$ och en delsträng i $D$ i $\Theta (m)$ tid. Detta kallas matchningsstatistik för $P$ .
• Hitta egenskaper för strängarna:
  • Hitta de längsta vanliga delsträngarna av strängen $S_{i}$ och $S_{j}$ i $\Theta (n_{i}+n_ {j})$ tid.
  • Hitta alla maximala par , maximala upprepningar eller supermaximala upprepningar i $\Theta (n+z)$ tid.
  • Hitta Lempel–Ziv- nedbrytningen i $\Theta (n)$ tid.
  • Hitta de längsta upprepade delsträngarna i $\Theta (n)$ tid.
  • Hitta de vanligast förekommande delsträngarna med en minsta längd i $\Theta (n)$ tid.
  • Hitta de kortaste strängarna från $\Sigma$ som inte förekommer i $D$ , i $O(n+z)$ tid, om det finns $z$ sådana strängar.
  • Hitta de kortaste delsträngarna som bara förekommer en gång på $\Theta (n)$ tid.
  • Hitta, för varje $i$ , de kortaste delsträngarna av $S_{i}$ som inte förekommer någon annanstans i $D$ i $\Theta (n)$ tid .

Suffixträdet kan förberedas för konstant tid lägsta gemensamma förfaderhämtning mellan noder i $\Theta (n)$ tid. Man kan då också:

• Hitta det längsta vanliga prefixet mellan suffixen $S_{i}[p..n_{i}]$ och $S_{j}[q..n_{j}]$ i $\Theta (1)$ .
• Sök efter ett mönster P med längden m med högst k felmatchningar i $O(kn+z)$ tid, där z är antalet träffar.
• Hitta alla $z$ maximala palindromer i $\Theta (n)$ , eller $\Theta (gn)$ tid om gap med längd $g$ är tillåtna, eller $\Theta (kn)$ om $k$ missmatchningar är tillåtna.
• Hitta alla $z$ tandemupprepningar i $O(n\log n+z)$ , och k -mismatch tandemupprepningar i $O(kn\log(n/k)+z)$ .
• Hitta de längsta vanliga delsträngarna till minst $k$ strängar i $D$ för $k=2,\dots ,K$ i $\Theta (n)$ tid.
• Hitta den längsta palindromiska delsträngen av en given sträng (med hjälp av strängens generaliserade suffixträd och dess baksida) i linjär tid.

Ansökningar

Suffixträd kan användas för att lösa ett stort antal strängproblem som förekommer inom textredigering, fritextsökning, beräkningsbiologi och andra tillämpningsområden. Primära applikationer inkluderar:

• Strängsökning , i O(m) komplexitet, där m är längden på delsträngen (men med initial O(n) tid som krävs för att bygga suffixträdet för strängen)
• Hitta den längsta upprepade delsträngen
• Hitta den längsta gemensamma delsträngen
• Hitta den längsta palindromen i ett snöre

Suffixträd används ofta i bioinformatikapplikationer , för att söka efter mönster i DNA- eller proteinsekvenser (som kan ses som långa teckensträngar). Förmågan att söka effektivt med felmatchningar kan anses vara deras största styrka. Suffixträd används också vid datakomprimering ; de kan användas för att hitta upprepade data och kan användas för sorteringssteget av Burrows–Wheeler-transformen . Varianter av LZW- komprimeringsscheman använder suffixträd ( LZSS ). Ett suffixträd används också i klustring av suffixträd , en dataklustringsalgoritm som används i vissa sökmotorer.

Genomförande

Om varje nod och kant kan representeras i $\Theta (1)$ utrymme, kan hela trädet representeras i $\Theta (n)$ utrymme. Den totala längden av alla strängar på alla kanter i trädet är $O(n^{2})$ , men varje kant kan lagras som positionen och längden på en delsträng av S , vilket ger en total utrymmesanvändning av $\Theta (n)$ datorord. Det värsta tänkbara utrymmesutnyttjandet av ett suffixträd ses med ett fibonacci-ord , vilket ger hela $2n$ -noderna.

Ett viktigt val när man gör en implementering av ett suffixträd är förälder-barn-relationerna mellan noder. Det vanligaste är att använda länkade listor som kallas syskonlistor . Varje nod har en pekare till sitt första underordnade, och till nästa nod i underordnade listan är den en del av. Andra implementeringar med effektiva körtidsegenskaper använder hash-kartor , sorterade eller osorterade arrayer (med array-fördubbling ) eller balanserade sökträd . Vi är intresserade av:

• Kostnaden för att hitta barnet på en given karaktär.
• Kostnaden för att sätta in ett barn.
• Kostnaden för att värva alla barn i en nod (dividerat med antalet barn i tabellen nedan).

Låt σ vara storleken på alfabetet. Då har du följande kostnader:

${\begin{array}{r|lll}&{\text{Lookup}}&{\text{Infogning}}&{\text{Traversal}}\\\hline {\text{Syskon listor / osorterade arrayer}}&O(\sigma )&\Theta (1)&\Theta (1)\\{\text{Bitvisa syskonträd}}&O(\log \sigma )&\Theta (1)&\Theta (1)\\{\text{Hash maps}}&\Theta (1)&\Theta (1)&O(\sigma )\\{\text{Balanserat sökträd}}&O(\log \sigma )&O( \log \sigma )&O(1)\\{\text{Sorterade arrayer}}&O(\log \sigma )&O(\sigma )&O(1)\\{\text{Hashkartor + syskonlistor}}&O( 1)&O(1)&O(1)\end{array}}$

Insättningskostnaden amorteras och att kostnaderna för hash anges för perfekt hashning.

Den stora mängden information i varje kant och nod gör suffixträdet mycket dyrt, och konsumerar cirka 10 till 20 gånger minnesstorleken på källtexten i bra implementeringar. Suffixarrayen reducerar detta krav till en faktor 8 (för array inklusive LCP- värden inbyggda inom 32-bitars adressutrymme och 8-bitars tecken.) Denna faktor beror på egenskaperna och kan nå 2 med användning av 4-byte breda tecken ( behövs för att innehålla vilken symbol som helst i vissa UNIX-liknande system, se wchar_t ) på 32-bitarssystem. Forskare har fortsatt att hitta mindre indexeringsstrukturer.

Parallellkonstruktion

Olika parallella algoritmer för att påskynda konstruktionen av suffixträd har föreslagits. Nyligen har en praktisk parallell algoritm för suffixträdkonstruktion med $O(n)$ arbete (sekventiell tid) och $O(\log ^{2}n)$ span har utvecklats. Algoritmen uppnår god parallell skalbarhet på flerkärniga maskiner med delat minne och kan indexera det mänskliga genomet – cirka 3 GB – på under 3 minuter med en 40-kärnig maskin.

Extern konstruktion

Även om det är linjärt är minnesanvändningen för ett suffixträd betydligt högre än den faktiska storleken på sekvenssamlingen. För en stor text kan konstruktion kräva externa minnesansatser.

Det finns teoretiska resultat för att konstruera suffixträd i externt minne. Algoritmen av Farach-Colton, Ferragina & Muthukrishnan (2000) är teoretiskt optimal, med en I/O-komplexitet som är lika med den för sortering. Men den övergripande intrikata av denna algoritm har hittills förhindrat dess praktiska implementering.

Å andra sidan har det funnits praktiska arbeten för att konstruera diskbaserade suffixträd som skalas till (få) GB/timmar. De senaste metoderna är TDD, TRELLIS, DiGeST och B ² ST.

TDD och TRELLIS skalar upp till hela det mänskliga genomet vilket resulterar i ett diskbaserat suffixträd av en storlek på tiotals gigabyte. Dessa metoder kan dock inte effektivt hantera samlingar av sekvenser som överstiger 3 GB. DiGeST presterar betydligt bättre och klarar av att hantera samlingar av sekvenser i storleksordningen 6GB på cirka 6 timmar.

Alla dessa metoder kan effektivt bygga suffixträd för fallet när trädet inte passar i huvudminnet, men ingången gör det. Den senaste metoden, B ² ST, skalas för att hantera ingångar som inte får plats i huvudminnet. ERA är en ny konstruktionsmetod för parallella suffixträd som är betydligt snabbare. ERA kan indexera hela det mänskliga genomet på 19 minuter på en 8-kärnig stationär dator med 16 GB RAM. På ett enkelt Linux-kluster med 16 noder (4 GB RAM per nod) kan ERA indexera hela det mänskliga genomet på mindre än 9 minuter.

Se även

• Suffix automat

Anteckningar

•   Aho, Alfred V. ; Hopcroft, John E .; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms , Reading/MA: Addison-Wesley, ISBN 0-201-00029-6 .
•   Apostolico, A.; Iliopoulos, C.; Landau, GM; Schieber, B.; Vishkin, U. (1988), "Parallell konstruktion av ett suffixträd med tillämpningar" , Algorithmica , 3 (1–4): 347–365, doi : 10.1007/bf01762122 , S2CID 5024136 .
•   Baeza-Yates, Ricardo A .; Gonnet, Gaston H. (1996), "Fast text searching for regular expressions or automaton searching on tryes", Journal of the ACM , 43 (6): 915–936, doi : 10.1145/235809.235810 , S2CID 1420298 .
• Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2008), "A new method for indexing genomes using on-disk suffix trees", CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management (PDF) , New York, NY, USA: ACM, s. 649–658 .
• Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2009), "Suffix trees for very large genomic sequences", CIKM '09: Proceedings of the 18th ACM Conference on Information and Knowledge Management (PDF) , New York, NY, USA: ACM .
• Farach, Martin (1997), "Optimal Suffix Tree Construction with Large Alphabets" (PDF) , 38:e IEEE Symposium on Foundations of Computer Science (FOCS '97) , s. 137–143 .
• Farach, Martin ; Muthukrishnan, S. (1996), "Optimal Logarithmic Time Randomized Suffix Tree Construction", International Colloquium on Automata Languages ​​and Programming (PDF) .
•   Farach-Colton, Martin ; Ferragina, Paolo; Muthukrishnan, S. (2000), "Om sorteringskomplexiteten för konstruktion av suffixträd." , Journal of the ACM , 47 (6): 987–1011, doi : 10.1145/355541.355547 , S2CID 8164822 .
•   Giegerich, R.; Kurtz, S. (1997), "Från Ukkonen till McCreight och Weiner: A Unifying View of Linear-Time Suffix Tree Construction" ( PDF) , Algorithmica , 19 (3): 331–353, doi : 10.1007 / PL00009177 1803C , arkiverad från originalet (PDF) 2016-03-03 , hämtad 2012-07-13 .
•   Gusfield, Dan (1997), Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology , Cambridge University Press, ISBN 0-521-58519-8 .
• Hariharan, Ramesh (1994), "Optimal Parallell Suffix Tree Construction", ACM Symposium on Theory of Computing (PDF) .
•   Iliopoulos, Costas; Rytter, Wojciech (2004), "On Parallel Transformations of Suffix Arrays into Suffix Trees", 15th Australasian Workshop on Combinatorial Algorithms , CiteSeerX 10.1.1.62.6715 .
•   Mansour, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011), "ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings" (PDF) , Proceedings of the VLDB Endowment , 5 ( 1): 49–60, arXiv : 1109.6884 , Bibcode : 218109ar : 21810M.Xiv . , doi : 10.14778/2047485.2047490 , S2CID 7582116 .
•   McCreight, Edward M. (1976), "A Space-Economical Suffix Tree Construction Algorithm", Journal of the ACM , 23 ( 2 ): 262–272, CiteSeerX 10.1.1.130.8022 , doi : 10.1145 /32194C306.32194026.9219406.9   .
•   Phoophakdee, Benjarath; Zaki, Mohammed J. (2007), "Genome-scale disk-based suffix tree indexing", SIGMOD '07: Proceedings of the ACM SIGMOD International Conference on Management of Data , New York, NY, USA: ACM, s. 833– 844, CiteSeerX 10.1.1.81.6031 .
•   Sahinalp, Cenk; Vishkin, Uzi (1994), "Symmetry breaking for suffix tree construction", ACM Symposium on Theory of Computing , doi : 10.1145/195058.195164 , S2CID 5985171
• Smyth, William (2003), Computing Patterns in Strings , Addison-Wesley .
• Shun, Julian; Blelloch, Guy E. (2014), "A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction" , ACM Transactions on Parallel Computing , 1 : 1–20, doi : 10.1145/2661653 , S123781   .
• Tata, Sandeep; Hankins, Richard A.; Patel, Jignesh M. (2003), "Practical Suffix Tree Construction", VLDB '03: Proceedings of the 30th International Conference on Very Large Data Bases (PDF) , Morgan Kaufmann, s. 36–47 .
•   Ukkonen, E. (1995), "On-line konstruktion av suffixträd" (PDF) , Algorithmica , 14 (3): 249–260, doi : 10.1007/BF01206331 , S2CID 6027556 ​​.
• Weiner, P. (1973), "Linear pattern matching algorithms" (PDF) , 14th Annual IEEE Symposium on Switching and Automata Theory , s. 1–11, doi : 10.1109/SWAT.1973.13 .
•   Zamir, Oren; Etzioni, Oren (1998), "Web document clustering: a feasibility demonstration", SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval , New York, NY, USA: ACM, s. 46 –54, CiteSeerX 10.1.1.36.4719 .

externa länkar

• Suffix Trees av Sartaj Sahni
• NIST:s ordbok över algoritmer och datastrukturer: Suffixträd
• Universell datakomprimering baserad på Burrows-Wheeler-transformationen: teori och praktik, tillämpning av suffixträd i BWT
• Teori och praktik av kortfattade datastrukturer, C++-implementering av ett komprimerat suffixträd
• Ukkonens Suffix Tree Implementation i C Del 1 Del 2 Del 3 Del 4 Del 5 Del 6
• Onlinedemo: Ukkonens Suffix Tree Visualization