On random-access data compaction

摘要

Consider a binary i.i.d. sequence that consists of K=2Jblocks of length T. We are looking for a universal compaction methodthat allows us to decode a certain block by looking only at certainsegments in the code sequence. We have investigated a hierarchicalmethod that encodes the source sequence into a code sequence thatconsists of 2J+1 variable-length segments. For decoding acertain block only J+2 segments need to be accessed. During decoding itis always clear where the next segment that needs to be accessed appearsin the code sequence. The cumulative individual redundancy that isachieved by this method, is optimal in the sense that ½ log₂ N behavior is obtained where N=2JT. An additionalincrease of at most one bit per code-segment is possible however