Komprimerad suffixarray

Inom datavetenskap är en komprimerad suffixarray en komprimerad datastruktur för mönstermatchning . Komprimerade suffixarrayer är en allmän klass av datastrukturer som förbättrar suffixarrayen . Dessa datastrukturer möjliggör snabb sökning efter en godtycklig sträng med ett jämförelsevis litet index.

Givet en text T med n tecken från ett alfabet Σ, stöder en komprimerad suffixarray sökning efter godtyckliga mönster i T . För ett inmatningsmönster P med m tecken är söktiden vanligtvis O( m ) eller O( m + log( n )). Det utrymme som används är typiskt $O(nH_{k}(T))+o(n)$ , där $H_{ k}(T)$ är den k-te ordningens empiriska entropin i texten T . Tiden och utrymmet för att konstruera en komprimerad suffixarray är normalt $O(n)$ .

Den ursprungliga instansieringen av den komprimerade suffixarrayen löste ett långvarigt öppet problem genom att visa att snabb mönstermatchning var möjlig med endast en linjär-rymddatastruktur, nämligen en proportionell mot storleken på texten T , som tar $O(n\,{\log |\Sigma |})$ bitar. Den konventionella suffixmatrisen och suffixträdet använder $\Omega (n\,{\log n})$ bitar, vilket är väsentligt större. Grunden för datastrukturen är en rekursiv nedbrytning med hjälp av "grannfunktionen", som gör att en suffixarray kan representeras av en av halva dess längd. Konstruktionen upprepas flera gånger tills den resulterande suffixmatrisen använder ett linjärt antal bitar. Följande arbete visade att det faktiska lagringsutrymmet var relaterat till nollordningens entropin och att indexet stöder självindexering. Det bundna utrymmet förbättrades ytterligare för att uppnå det slutliga målet med högre ordningens entropi; komprimeringen erhålls genom att partitionera grannfunktionen med högordningskontexter och komprimera varje partition med ett waveletträd . Utrymmesanvändningen är extremt konkurrenskraftig i praktiken med andra toppmoderna kompressorer, och den stöder även snabb mönstermatchning.

Minnesåtkomsterna som görs av komprimerade suffixarrayer och andra komprimerade datastrukturer för mönstermatchning är vanligtvis inte lokaliserade, och därför har dessa datastrukturer varit notoriskt svåra att designa effektivt för användning i externt minne . Nya framsteg med användning av geometrisk dualitet drar fördel av blockåtkomsten från diskar för att snabba upp I/O-tiden avsevärt. Dessutom har potentiellt praktiska sökprestanda för en komprimerad suffixarray i externt minne demonstrerats.

Implementeringar med öppen källkod

Det finns flera implementeringar av öppen källkod av komprimerade suffixarrayer tillgängliga (se Externa länkar nedan). Bowtie och Bowtie2 är öppen källkod för komprimerade suffixarrayimplementeringar av läsjustering för användning inom bioinformatik . Succinct Data Structure Library (SDSL) är ett bibliotek som innehåller en mängd olika komprimerade datastrukturer inklusive komprimerade suffixarrayer. FEMTO är en implementering av komprimerade suffixarrayer för externt minne. Dessutom finns en mängd olika implementeringar, inklusive de ursprungliga FM-indeximplementeringarna , tillgängliga från Pizza & Chilis webbplats (se externa länkar).

Se även

^ ^a ^b ^c R. Grossi och JS Vitter, komprimerade suffixarrayer och suffixträd, med applikationer till textindexering och strängmatchning, SIAM Journal on Computing, 35(2), 2005, 378-407. En tidigare version dök upp i Proceedings of the 32nd ACM Symposium on Theory of Computing, maj 2000, 397-406.
^ ^a ^b Paolo Ferragina och Giovanni Manzini (2000). "Opportunistiska datastrukturer med applikationer". Proceedings of the 41st Annual Symposium on Foundations of Computer Science. s. 390.
^ ^a ^b R. Grossi, A. Gupta och JS Vitter, Entropi-komprimerade textindex av hög ordning, handlingar från det 14:e årliga SIAM/ACM-symposiet om diskreta algoritmer, januari 2003, 841-850.
^ K. Sadakane, komprimerade textdatabaser med effektiva frågealgoritmer baserade på de komprimerade suffixmatriserna, förfaranden för det internationella symposiet om algoritmer och beräkningar, föreläsningsanteckningar i datavetenskap, vol. 1969, Springer, december 2000, 410-421.
^ L. Foschini, R. Grossi, A. Gupta och JS Vitter, Indexering är lika med komprimering: Experiment på suffixmatriser och träd, ACM-transaktioner på algoritmer , 2(4), 2006, 611-639.
^ W.-K. Hon, R. Shah, SV Thankachan och JS Vitter, On Entropy-Compressed Text Indexing in External Memory, Proceedings of the Conference on String Processing and Information Retrieval , augusti 2009.
^ MP Ferguson, FEMTO: snabb sökning av stora sekvenssamlingar , Proceedings of the 23th Annual Conference on Combinatorial Pattern Matching, juli 2012

externa länkar

Implementeringar:

[GV00-1] R. Grossi och JS Vitter, komprimerade suffixarrayer och suffixträd, med applikationer till textindexering och strängmatchning, SIAM Journal on Computing, 35(2), 2005, 378-407. En tidigare version dök upp i Proceedings of the 32nd ACM Symposium on Theory of Computing, maj 2000, 397-406.

[opportunistic_2000-2] Paolo Ferragina och Giovanni Manzini (2000). "Opportunistiska datastrukturer med applikationer". Proceedings of the 41st Annual Symposium on Foundations of Computer Science. s. 390.

[GGV03-3] R. Grossi, A. Gupta och JS Vitter, Entropi-komprimerade textindex av hög ordning, handlingar från det 14:e årliga SIAM/ACM-symposiet om diskreta algoritmer, januari 2003, 841-850.

[4] K. Sadakane, komprimerade textdatabaser med effektiva frågealgoritmer baserade på de komprimerade suffixmatriserna, förfaranden för det internationella symposiet om algoritmer och beräkningar, föreläsningsanteckningar i datavetenskap, vol. 1969, Springer, december 2000, 410-421.

[5] L. Foschini, R. Grossi, A. Gupta och JS Vitter, Indexering är lika med komprimering: Experiment på suffixmatriser och träd, ACM-transaktioner på algoritmer , 2(4), 2006, 611-639.

[6] W.-K. Hon, R. Shah, SV Thankachan och JS Vitter, On Entropy-Compressed Text Indexing in External Memory, Proceedings of the Conference on String Processing and Information Retrieval , augusti 2009.

[7] MP Ferguson, FEMTO: snabb sökning av stora sekvenssamlingar , Proceedings of the 23th Annual Conference on Combinatorial Pattern Matching, juli 2012