Vi presenterar ett effektivt genomförande av en skrivskyddad top-down konstruktion för suffixträd. Vårt genomförande bygger på en ny, rymdeffektiv representation av suffixträd som endast kräver 12 byte per inmatningstecken i värsta fall, och 8,5 byte per inmatningstecken i genomsnitt för en samling filer av olika typ. Vi visar hur man effektivt genomför den lata utvärderingen av suffixträd så att ett underträd utvärderas först när det korsas för första gången. Våra experiment visar att för problemet med att söka många exakta mönster i en fast ingång sträng, den lata top-down konstruktion är ofta snabbare och mer utrymme effektiv än andra metoder. Konstruktionen av suffixmatrisen [12] och den linjära konstruktionen av suffixträdet [13] har inte heller alfabetfaktorn i sin körtid. För den linjära tiden suffix träd konstruktioner av [4-6] alfabetet faktorn kan undvikas genom att använda hashing tekniker, se [5]; dock, till priset av att använda betydligt mer utrymme, se [10].
I REF, Giegerich, Kurtz och Stoye utforska fördelarna med att använda en lat genomförande av suffix träd.
Efficient Implementation of Lazy Suffix Trees
{'venue': 'Lecture Notes in Computer Science', 'journal': 'Lecture Notes in Computer Science', 'mag_field_of_study': ['Computer Science']}