NDLI: Improved antidictionary based compression

Content Provider	IEEE Xplore Digital Library
Author	Crochemore, M. Navarro, G.
Copyright Year	2002
Description	Author affiliation: Inst. Gaspard-Monge, King's Coll., London, UK (Crochemore, M.)
Abstract	The compression of binary texts using antidictionaries is a novel technique based on the fact that some substrings (called "antifactors") never appear in the text. Let sb be an antifactor where b is its last bit. Every time s appears in the text we know that the next bit is b~ and hence omit its representation. Since building the set of all antifactors is space consuming at compression time, it is customary to limit the maximum length of antifactors considered up to a constant k. Larger k yields better compression of the text but requires more space at compression time. In this paper we introduce the notion of almost antifactors, which are strings that rarely appear in the text. More formally, almost antifactors are strings that, if we consider them as antifactors and separately code their occurrences as exceptions, the compression ratio improves. We show that almost antifactors permit improving compression with a limited amount of main memory to compress. Our experiments show that they obtain the same compression of the classical algorithm using only 30%-55% of its memory space.
Starting Page	7
Ending Page	13
File Size	320606
Page Count	7
File Format	PDF
ISBN	0769518672
ISSN	15224902
DOI	10.1109/SCCC.2002.1173168
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-11-06
Publisher Place	Chile
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer science Educational institutions Data structures Societies
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

On antidictionary coding based on compacted substring automaton

Relationship between antidictionary automata and compacted substring automata

On a universal antidictionary coding for stationary ergodic sources with finite alphabet

Relationship between antidictionary automata and compacted substring automata.

Compact Data Structures for Temporal Graphs

Improved antidictionary based compression.

A Scalable Grid-Based Clustering Algorithm for Very Large Spatial Databases

Algorithms for Compressed Inputs

Move-to-front and permutation based inversion coding

Improved antidictionary based compression

Similar Documents

On antidictionary coding based on compacted substring automaton

Relationship between antidictionary automata and compacted substring automata

On a universal antidictionary coding for stationary ergodic sources with finite alphabet

Relationship between antidictionary automata and compacted substring automata.

Compact Data Structures for Temporal Graphs

Improved antidictionary based compression.

A Scalable Grid-Based Clustering Algorithm for Very Large Spatial Databases

Algorithms for Compressed Inputs

Move-to-front and permutation based inversion coding

Improved antidictionary based compression