Abstrakt. Vi ger nya lösningar på de SÖKBARA PARTIELLA SUMMEN med IndeLS problem. Med tanke på en sekvens av n k-bit nummer, presenterar vi en struktur som tar kn +o(kn) bitar av utrymme, kan utföra transaktioner summa, söka, infoga, och ta bort, allt i O(log n) värsta fall tid, för alla k = O(log n). Detta utökar tidigare resultat genom Hon et al. [2003c] uppnå samma mellanslag och O(log n/ log log n) tid komplexitet för frågorna, men erbjuder komplexiteter för infoga och ta bort som är amortized och värre än vår, och stöds endast för k = O(1). Vårt resultat matchar en befintlig lägre gräns för stora värden på k. Vi ger också nya lösningar på problemet DYNAMIC SEQUENCE. Med tanke på en sekvens av n symboler i intervallet [1, σ ] med binär noll-order entropi H 0, presenterar vi en dynamisk datastruktur som kräver n H 0 + o(n log σ ) bitar av utrymme, som kan utföra rang och välja, samt infoga och ta bort symboler på godtyckliga positioner, i O(log n log σ ) tid. Vårt resultat är den första entropibundna dynamiska datastrukturen för rankning och välja över allmänna sekvenser. I fallet σ = 2, där båda tidigare problem sammanfaller, förbättrar vi den dynamiska lösningen av Hon et al. [2003c] i det att vi komprimerar sekvensen. Det enda tidigare resultatet med entropi-bundet utrymme för dynamiska binära sekvenser är av Blandford och Blelloch [2004], som har samma komplexitet som vår struktur, men inte uppnår konstant 1 multiplicera entropy termen i rymden komplexitet. Slutligen presenterar vi en ny dynamisk komprimerad full-text själv-index, för en samling texter över ett alfabet av storlek σ, av övergripande längd n och hth ordning empirisk entropi H h.
Ett wavelet träd med dynamiska bitmappar ger en dynamisk sekvens representation som tar nH 0 (T) + o(n log σ) bitar och löser alla operationer i tid O(log n log σ) REF.
Dynamic entropy-compressed sequences and full-text indexes
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}