NDLI: Universal lossless data compression with side information by using a conditional MPM grammar transform

Content Provider	IEEE Xplore Digital Library
Author	En-Hui Yang Kaltchenko, A. Kieffer, J.C.
Copyright Year	1963
Abstract	A grammar transform is a transformation that converts any data sequence to be compressed into a grammar from which the original data sequence can be fully reconstructed. In a grammar-based code, a data sequence is first converted into a grammar by a grammar transform and then losslessly encoded. Among several previously proposed grammar transforms is the multilevel pattern matching (MPM) grammar transform. In this paper, the MPM grammar transform is first extended to the case of side information known to both the encoder and decoder, yielding a conditional MPM (CMPM) grammar transform. A new simple linear-time and space complexity algorithm is then proposed to implement the MPM and CMPM grammar transforms. Based on the CMPM grammar transform, a universal lossless data compression algorithm with side information is developed, which can achieve asymptotically the conditional entropy rate of any stationary, ergodic source pair. It is shown that the algorithm's worst case redundancy/sample against the k-contest conditional empirical entropy among all individual sequences of length n is upper-bounded by c(1/logn), where c is a constant. The proposed algorithm with side information is the first in the coming family of conditional grammar-based codes, whose expected high efficiency is due to the efficiency of the corresponding unconditional codes.
Sponsorship	IEEE Information Theory Society
Starting Page	2130
Ending Page	2150
Page Count	21
File Size	642643
File Format	PDF
ISSN	00189448
Volume Number	47
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-09-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Data compression
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Universal lossless data compression with side information by using a conditional MPM grammar transform

Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models

Universal lossless compression via multilevel pattern matching

Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform .2. With context models

An Algorithm for Universal Lossless Compression With Side Information

A Universal Grammar-Based Code for Lossless Compression of Binary Trees

Universal Lossless Compression of Erased Symbols

Universal lossless source coding with the Burrows Wheeler transform

Lossless sliding-block compression of constrained systems

Universal lossless data compression with side information by using a conditional MPM grammar transform

Similar Documents

Universal lossless data compression with side information by using a conditional MPM grammar transform

Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models

Universal lossless compression via multilevel pattern matching

Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform .2. With context models

An Algorithm for Universal Lossless Compression With Side Information

A Universal Grammar-Based Code for Lossless Compression of Binary Trees

Universal Lossless Compression of Erased Symbols

Universal lossless source coding with the Burrows Wheeler transform

Lossless sliding-block compression of constrained systems

Universal lossless data compression with side information by using a conditional MPM grammar transform