[发明专利]VLSI高效霍夫曼编码设备和方法

摘要

本发明揭示了一种基于霍夫曼译码的压缩算法，其适于容易使用VLSI设计来实施。可以处理数据文件以例如根据述LV算法用包含偏移和长度的复制命令替换重复数据。接着可对于所述文件的一些部分生成霍夫曼码。所述霍夫曼码生成用于数据文件中的文字的霍夫曼码长度，而无需首先将文字统计数据排序。可以将所述霍夫曼码长度限制为不比最大长度长，并且可以修改所述霍夫曼码以提供可接受的溢流概率并且所述霍夫曼码可以采用规范次序。可以将文字、偏移和长度分别编码。可以向有限数目的二进制数指派用于这些数据集的不同值以生成用于生成霍夫曼码的使用统计数据。

主权项

1.一种用于压缩的方法(300，400)，其包括通过计算机系统执行：/n接收多个计数P(i)，i＝1到N，每个计数P(i)对应于数据集中的多个符号中的一个符号S(i)，所述多个计数P(i)未排序；/n通过以下方式，根据所述计数P(i)向N个中的每个符号S(i)，i＝1到N指派位长度而无需首先将所述计数P(i)排序，以获得第一规范霍夫曼码：/n向每个符号S(i)指派映射值I(i)，所述映射值是依次向所述数据集中的每个符号S(i)指派的；/n确定所述多个计数P(i)，i＝1到N，每个计数对应于不同的符号S(i)；/n寻找所述多个符号S(i)中具有多个频率量度P(i)中的最低对应计数P(a)和P(b)的两个符号S(a)和S(b)；/n将所述计数P(a)和P(b)求和以获得总和Pt；/n确定指派给符号S(a)和S(b)的映射值I(a)和I(b)中的较小映射值I(min)以及所述映射值I(a)和I(b)中的较大映射值I(max)；/n将I(max)中的一者改变成等于所述较小映射值I(min)；/n将对应于所述较小映射值I(min)的计数P(min)设置成等于Pt；/n将对应于I(max)的计数P(max)设置成等于零；/n递增对应于符号S(a)和S(b)的位长度L(a)和L(b)；以及/n通过所述递增动作重复所述寻找动作，直到所有映射值I(i)等于零为止；/n使用所述第一规范霍夫曼码对所述数据集进行规范霍夫曼译码；以及/n将所有大于阈值的代码长度L(i)设置成等于所述阈值以获得第二规范霍夫曼码。/n