Operationer ranka och välja över en sekvens av symboler har många tillämpningar för utformningen av koncisa och komprimerade datastrukturer som hanterar textsamlingar, strukturerad text, binära relationer, träd, grafer, och så vidare. Vi är intresserade av det fall där samlingarna kan uppdateras via tillägg och raderingar av symboler. Två aktuella lösningar framstår som de bästa i avvägningen mellan rum och tid (när man överväger alla operationer). En lösning, av Mäkinen och Navarro, uppnår komprimerat utrymme (dvs. nH 0 + o(n log σ) bits) och O(log n log σ) värsta fall tid för alla operationer, där n är sekvenslängd, σ är alfabetet storlek, och H 0 är noll-ordning entropi av sekvensen. Den andra lösningen, av Lee och Park, uppnår O(log n(1 + log σ log n )) amorterad tid och okomprimerat utrymme, dvs. n log 2 σ + O(n) + o(n log σ) bitar. I detta dokument visar vi att det bästa av båda världarna kan uppnås. Vi kombinerar lösningarna för att erhålla nH 0 + o(n log σ) bitar av utrymme och O(log n(1 + log σ log n )) värsta fall tid för alla operationer. Bortsett från den bästa nuvarande lösningen på problemet får vi flera biprodukter av oberoende intresse som gäller för delbelopp, textindex, suffixmatriser, Burrows-Wheelertransform med flera.
Slutligen förbättrade González och Navarro Ref de två ovannämnda resultaten genom att utforma en struktur på nH 0 + o(n) · lg σ bits för att stödja all verksamhet i O(lg σ lg ng n + 1)) värsta fall tid.
Rank/Select on Dynamic Compressed Sequences and Applications
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}