Abstrakt. Vi presenterar en ram för att dynamisera koncisa datastrukturer, för att uppmuntra deras användning över icke-succinct versioner inom en mängd olika viktiga tillämpningsområden. Vårt ramverk kan dynamisera de flesta toppmoderna koncisa datastrukturer för ordböcker, ordinära träd, märkta träd och textsamlingar. Av särskild betydelse är dess direkta tillämpning på XML indexering strukturer som besvarar subpath frågor [2]. Vårt ramverk fokuserar på att uppnå informations-teoretiskt optimalt utrymme tillsammans med nära-optimala uppdatering/query gränser. Som huvuddelen av vårt arbete anser vi att följande problem är centralt för textindexering: Med en text T över ett alfabet, konstruera en komprimerad datastruktur som svarar på frågorna char (i), rank s (i) och välj s(i) för en symbol s. Många datastrukturer anser dessa frågor för statisk text T [5, 3, 16, 4]. Vi bygger på dessa resultat och ger de mest kända frågegränser för den dynamiska versionen av detta problem, stödja godtyckliga tillägg och raderingar av symboler i T. Särskilt, med en amorterad uppdateringstid för O (n ), någon statisk koncis datastruktur D för T, tar t (n) tid för frågor, kan omvandlas av vårt ramverk till en dynamisk koncis datastruktur som stöder rank s (i), välj s(i) och char (i) frågor i O (t(n) + log n) tid, för alla konstant > 0. När vi lyckas uppnå O(1) frågetider = polylog(n). Våra uppdaterings-/krävgränser är nästan optimala med avseende på de nedre gränserna från [13].
Det har varit arbete på dynamisering denna struktur REF, där de uppnår samma utrymme plus o(n) bitar, frågetider ökas med O( 1  på log log n), och uppdateringstiderna är O( 1  på n) amortized, för alla konstant 0 <  på < 1.
A Framework for Dynamizing Succinct Data Structures ⋆
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Computer Science']}