Data compression is a form of encoding aimed at representing the message in a compact form. Within this framework, we define a subclass of context-free grammars, referred to as admissible grammars. For each string $w$, we assign an admissible grammar $G_w$, such that its language is $\{ w \}$. We present two classes of assignments of admissible grammars to a string and provide an example for each class. Binary encoding of the production rules of an admissible grammar $G_w$ together with the underlying admissible grammar assignment results in a good redundancy bound. Such data compression constitutes a universal code, generally providing near-optimal compression.
|
