We investigate a type of lossless source code called a grammar-based code, which, in response to any input data string x over a fixed finite alphabet, selects a context-free grammar G/sub x/ representing x in the sense that x is the unique string belonging to the language generated by G/sub x/. Lossless compression of x takes place indirectly via compression of the production rules of the grammar G/sub x/. It is shown that, subject to some mild restrictions, a grammar-based code is a universal code with respect to the family of finite-state information sources over the finite alphabet. Redundancy bounds for grammar-based codes are established. Reduction rules for designing grammar-based codes are presented.
展开▼
机译：我们研究了一种无损源代码，称为基于语法的代码，该代码可响应固定有限字母上的任何输入数据字符串x，从x表示x的意义上选择表示x的无上下文语法G / sub x /属于G / sub x /生成的语言的唯一字符串。 x的无损压缩通过语法G / sub x /的生成规则的压缩间接进行。结果表明，在一些轻微的限制下，基于语法的代码对于有限字母上的有限状态信息源族是通用代码。建立了基于语法的代码的冗余边界。提出了用于设计基于语法的代码的归约规则。
展开▼
