NDLI: Grammar-based coding: new perspectives

Content Provider	IEEE Xplore Digital Library
Author	En-hui Yang Da-ke He Kieffer, J.C.
Copyright Year	2004
Description	Author affiliation: Dept. of Electr. & Comput. Eng., Waterloo Univ., Ont., Canada (En-hui Yang; Da-ke He)
Abstract	Grammar-based coding is investigated from three new perspectives. First, we revisit the performance analysis of grammar-based codes by proposing context-based run-length encoding algorithms as new performance benchmarks. A redundancy result stronger than all previous corresponding results is established. We then extend the analysis of grammar-based codes to sources with countably infinite alphabets. Let /spl Lambda/ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any /spl Lambda/ for which there exists a universal code. Moreover, upper bounds on the worst-case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Finally, we propose a new theoretic framework for compression in which grammars rather than sequential stochastic processes are used as source generating models, and point out some open problems in the framework.
Starting Page	105
Ending Page	110
File Size	511113
Page Count	6
File Format	PDF
ISBN	0780387201
DOI	10.1109/ITW.2004.1405283
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-10-24
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Arithmetic Algorithm design and analysis Performance analysis Stochastic processes Data compression Encoding Upper bound Block codes Compression algorithms Pattern matching
Content Type	Text
Resource Type	Article

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