Asymptotic Optimality of Antidictionary Codes

MaRDI QIDQ5485307zbMATH OpenFDO

Authors Hiroyoshi Morita, Takahiro Ota

Publication date 29 August 2006

Full work available at URL https://arxiv.org/abs/1006.0284

zbMATH Keywords

antidictionarydata compressionECGminimum forbidden wordssuffix trees

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: An antidictionary code is a lossless compression algorithm using an antidictionary which is a set of minimal words that do not occur as substrings in an input string. The code was proposed by Crochemore et al. in 2000, and its asymptotic optimality has been proved with respect to only a specific information source, called balanced binary source that is a binary Markov source in which a state transition occurs with probability 1/2 or 1. In this paper, we prove the optimality of both static and dynamic antidictionary codes with respect to a stationary ergodic Markov source on finite alphabet such that a state transition occurs with probability $p(0<pleq1)$.

Recommendations

• scientific article; zbMATH DE number 4062630
• Efficient computation of maximal anti-exponent in palindrome-free strings
• Upper and lower bounds for dynamic data structures on strings
• A length bound for binary equality words
• A note on the number of N-bit strings with maximum complexity
• Tighter Upper Bounds on the Exact Complexity of String Matching
• Dynamic construction of an antidictionary with linear complexity
• Approximating the Anticover of a String
• Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings
• Tight bounds for searching a sorted array of strings

Cited in

(1)

• Analysis of the Size of Antidictionary in DCA

This page was built for publication: Asymptotic Optimality of Antidictionary Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5485307)