使用贪婪的顺序上下文相关文法变换的改进的无损耗数据压缩方法

摘要

本发明提供了一种无损耗数据压缩方法，它使用文法变换顺序地构造一个贪婪的上下文相关文法的序列，可以从该序列中逐步恢复原始数据序列。使用顺序上下文相关方法、改进的顺序上下文相关方法和等级式上下文相关方法中的任意一种，对该数据序列进行编码。

主权项

1、一种将原始数据序列顺序地变换为不可约上下文相关文法的方法，所述原始数据序列包括多个符号且与已知上下文模型相关联，根据所述不可约上下文相关文法可完全恢复所述原始数据，其中，所述不可约上下文相关文法是由产生规则集合表示的，这些产生规则是使用表示所述数据序列中的不重叠重复模式和上下文的变量和上下文的对的集合所形成的，所述方法适用于任何可数上下文模型，并包括以下步骤：(a)从所述序列中解析子串，其中，如果所述序列以前未解析的符号的字符串的最长前缀存在，则所述子串是所述最长前缀，否则，所述子串是所述序列以前未解析的符号的字符串的第一个符号，其中，在当前时间点的上下文时，所述序列以前未解析的符号的字符串用前一个不可约上下文相关文法的变量集合中的变量、而不是变量和上下文对的集合的初始对中的初始变量来表示；(b)根据所述子串、当前上下文和所述前一个不可约上下文相关文法，产生容许的上下文相关文法；(c)将至少一个约简规则集合应用于所述容许的上下文相关文法，以产生新的不可约上下文相关文法；(d)重复步骤(a)至(c)，直到用最终不可约上下文相关文法表示所述序列的所有符号。