Komprimert suffiks array - Compressed suffix array

I informatikk er et komprimert suffiksarray en komprimert datastruktur for mønstermatching . Komprimerte suffiksarrayer er en generell klasse av datastruktur som forbedrer suffiksarrayen . Disse datastrukturene muliggjør raskt søk etter en vilkårlig streng med en relativt liten indeks.

Gitt en tekst T av n tegn fra et alfabet Σ, en komprimert suffiks rekke Støtter søker etter vilkårlige mønstre i T . For et inndatamønster P med m- tegn er søketiden typisk O ( m ) eller O ( m + log ( n )). Den plass som brukes er vanligvis , der er den k-te ordens entropi empirisk av teksten T . Tid og rom for å konstruere et komprimert suffiks-array er normalt .

Den opprinnelige instantieringen av det komprimerte suffiksarrayet løste et langvarig åpent problem ved å vise at rask mønsterinnpassing var mulig ved bare å bruke en lineær-romdatastruktur, nemlig en proporsjonal med størrelsen på teksten T , som tar bit. Den konvensjonelle suffikset array og suffikset tre bruker biter, som er vesentlig større. Grunnlaget for datastrukturen er en rekursiv nedbrytning ved bruk av "nabofunksjonen", som gjør at et suffiks-array kan bli representert med en av halvparten av dens lengde. Konstruksjonen gjentas flere ganger til den resulterende suffiks-gruppen bruker et lineært antall biter. Etterfølgende arbeid viste at den faktiske lagringsplassen var relatert til entropien med null rekkefølge og at indeksen støtter selvindeksering. Plassen som ble bundet ble ytterligere forbedret for å oppnå det endelige målet om entropi med høyere orden; komprimeringen oppnås ved å partisjonere nabofunksjonen ved høye ordens kontekster, og komprimere hver partisjon med et wavelet-tre . Plassbruken er ekstremt konkurransedyktig i praksis med andre moderne kompressorer, og den støtter også rask mønstermatching.

Minnetilgangene som er gjort av komprimerte suffiks-matriser og andre komprimerte datastrukturer for mønstermatching er vanligvis ikke lokaliserte, og derfor har disse datastrukturene vært notorisk vanskelig å utforme effektivt for bruk i eksternt minne . Nyere fremskritt ved bruk av geometrisk dualitet drar fordel av blokkeringstilgangen levert av disker for å øke hastigheten på I / O-tiden betydelig. I tillegg er det demonstrert potensielt praktisk søkeytelse for et komprimert suffiksarray i eksternt minne.

Implementeringer av åpen kildekode

Det er flere åpen kildekodeimplementeringer av komprimerte suffiks-matriser tilgjengelig (se eksterne koblinger nedenfor). Bowtie og Bowtie2 er open-source komprimert suffiks gruppe implementeringer av lese oppstilling for bruk i bioinformatikk . The Succinct Data Structure Library (SDSL) er et bibliotek som inneholder en rekke komprimerte datastrukturer inkludert komprimerte suffiksarrays. FEMTO er en implementering av komprimerte suffiksarrays for eksternt minne. I tillegg er en rekke implementeringer, inkludert de originale FM-indeks implementeringene, tilgjengelige fra Pizza & Chili nettstedet (se eksterne lenker).

Se også

referanser

  1. ^ a b c R. Grossi og JS Vitter, Compression Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 35 (2), 2005, 378-407. En tidligere versjon dukket opp i Proceedings of the 32nd ACM Symposium on Theory of Computing, mai 2000, 397-406.
  2. ^ a b Paolo Ferragina og Giovanni Manzini (2000). "Opportunistiske datastrukturer med applikasjoner". Fortsettelser av det 41. årlige symposiet om grunnlegger av informatikk. p.390.
  3. ^ a b R. Grossi, A. Gupta og JS Vitter, indekser med høy orden entropi-komprimert tekst, Proceedings of the 14th SIAM / ACM Symposium on Discrete Algorithms, January 2003, 841-850.
  4. ^ K. Sadakane, komprimerte tekstdatabaser med effektive spørringsalgoritmer basert på komprimerte suffiks-arrays, Proceedings of the International Symposium on Algorithms and Computation , Lecture Notes in Computer Science, vol. 1969, Springer, desember 2000, 410-421.
  5. ^ L. Foschini, R. Grossi, A. Gupta, og JS Vitter, indekserer lik kompressjon: eksperimenter på suffiksarrays og trær , ACM-transaksjoner på algoritmer , 2 (4), 2006, 611-639.
  6. ^ W.-K. Hon, R. Shah, SV Thankachan og JS Vitter, om entropisk komprimert tekstindeksering i eksternt minne, Fortsettelse av konferansen om stresebehandling og henting av informasjon , august 2009.
  7. ^ MP Ferguson, FEMTO: raskt søk i samlinger med stor sekvens , Proceedings of the 23.rd Conference on Combinatorial Pattern Matching , juli 2012

Eksterne linker

implementeringer: