Low-Complexity Compression with Random Access

Kamparaju, Srikanth and Mastan, Shaik and Vatedka, Shashank (2022) Low-Complexity Compression with Random Access. In: 14th IEEE International Conference on Signal Processing and Communications, SPCOM 2022, 11 July 2022 through 15 July 2022, Bangalore.

Text
SPCOM_2022.pdf - Published Version
Restricted to Registered users only
Download (331kB) | Request a copy

Abstract

We investigate the problem of variable-length compression with random access for stationary and ergodic sources, wherein short substrings of the raw file can be extracted from the compressed file without decompressing the entire file. It is possible to design compressors for sequences of length n that achieve compression rates close to the entropy rate of the source, and still be able to extract individual source symbols in time θ(1) under the word-RAM model. In this article, we analyze a simple well-known approach used for compression with random access. We theoretically show that this is suboptimal, and design two simple compressors that simultaneously achieve entropy rate and constant-time random access. We then propose dictionary compression as a means to further improve performance, and experimentally validate this on various datasets. © 2022 IEEE.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Vatedka, Shashank	https://orcid.org/0000-0003-2384-9392

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

The work of S. Vatedka was supported by a seed grant from IIT Hyderabad and and a Start-up Research Grant (SRG/2020/000910) from SERB, India.

Uncontrolled Keywords:

Compressed files; Compression rates; Entropy rates; Ergodic sources; Lower complexity; Random access; Simple++; Stationary sources; Sub-strings; Variable length

Subjects:

Electrical Engineering

Divisions:

Department of Electrical Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

01 Sep 2022 10:19

Last Modified:

01 Sep 2022 10:19

URI:

http://raiithold.iith.ac.in/id/eprint/10380