之前用Huffman编码做过一个压缩小程序。当时的Huffman树半自适应的,需要对源文件扫描两遍。这次是完全自适应的,只需要对源文件扫描一次就可以生成压缩文件,并且压缩文件中不会含编码表。具体关于原理的东西实在网上搜的文档(附件中有),C++的源代码网上也有。
以下是我的代码:(代码有错,代码有错,我是按那个文档并且参照C++的源代码做的,杯具杯具,路漫漫……)
package cn.cls.greedy;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import javax.print.DocFlavor.CHAR_ARRAY;
import cn.cls.bean.HNode;
public class Huffman {
// 常量--------------------------------------------------------------
/**
* 编码的最大值
*/
private final int MAX_VALUE = 255;
/**
* 首次出现数据的代替码
*/
private final int CODE_ESCAPE = 256;
/**
* 用于扩展新节点
*/
private final int CODE_EXTAND = 257;
/**
* 节点列表的大小
*/
private final int LIST_LENGTH = 258;
/**
* 非叶子节点
*/
private final int NOT_DATA = -1;
/**
* 字节最低位
*/
private final int BOTTOM_BIT = 0;
/**
* 字节最高位
*/
private final int TOP_BIT = 7;
/**
* 输出缓存区的大小
*/
private final int BUFFER_SIZE = 10240;
/**
* 节点初始count值的左移量(加倍)
*/
private final int INIT_RATIO = 2;
/**
* 每次重构树是节点count值右移量(减小)
*/
private final int SHRINK_RATIO = 1;
// 变量--------------------------------------------------------------
/**
* 源文件、目标文件
*/
private File src, des;
/**
* 文件输入、输出流
*/
private FileInputStream ins;
private FileOutputStream ous;
/**
* 树的根节点、解压时当前指向的节点
*/
private HNode root, current;
/**
* 输出流位指针、缓冲区指针
*/
private int bit_pointer, buffer_pointer;
/**
* 输出缓冲区
*/
private byte[] outputBuffer;
/**
* 节点列表
*/
private HNode[] list;
// 构造器、初始化-------------------------------------------------------
public Huffman(File src, File des) {
this.src = src;
this.des = des;
}
/**
* 初始化
*/
public int init() {
// 初始化文件输入、输出流
try {
ins = new FileInputStream(src);
ous = new FileOutputStream(des);
} catch (FileNotFoundException e) {
e.printStackTrace();
return -1;
}
// 初始化节点列表
list = new HNode[LIST_LENGTH];
for (int i = 0; i < list.length; i++)
list[i] = null;
// 初始化树
HNode tmp, tmp2;
root = newHNode(NOT_DATA, true, null);
tmp = newHNode(CODE_ESCAPE, false, root);
tmp2 = newHNode(CODE_EXTAND, true, root);
root.lchild = tmp2;
root.rchild = tmp;
root.count = tmp.count + tmp2.count;
current = root;
// 初始化输出缓存区
outputBuffer = new byte[BUFFER_SIZE];
outputBuffer[0] = 0;
buffer_pointer = 0;
bit_pointer = TOP_BIT;
return 0;
}
// 外部接口-----------------------------------------------------------
/**
* 读取源文件并压缩
*
* @return 0:操作成功
*/
public int encode() {
// 初始化
if (init() == -1) {
return -1;
}
// 初始化输入缓存区
int[] buffer = new int[BUFFER_SIZE];
// 循环读取入缓存区
int available = 0;
try {
while ((available = ins.available()) > 0) {
// 如果剩余字节不足以填满缓存区,则新建最小缓存区
if (available < BUFFER_SIZE) {
buffer = new int[available];
}
// 读入缓存区
int tmp;
for (int i = 0; i < buffer.length; i++) {
tmp = ins.read();
buffer[i] = (tmp > 0) ? tmp : (tmp + 256);
}
// 对缓存区的数据编码
int data;
for (int i = 0; i < buffer.length; i++) {
data = buffer[i];
/*
* 如果该数据不在树中,则输出CODE_ESCAPE对应的编码(其实就是1),输出数据
* 并且在树中新建该字符的节点;如果在数据已存在与树中,则输出其对应的编码,
* 而且由于对树节点自底向上count加一,还需要对树进行必要的调整。
*/
if (list[data] == null) {
encodeData(CODE_ESCAPE);
for (int j = 7; j > 0; j--)
writeBit(data & (int) Math.pow(2, j));
enlargeHTree(data);
} else {
encodeData(data);
balanceHTree(list[data].parent);
}
/*
* 对树进行瘦身,这一步是不要的,可以使你的压缩文件更小
* (源文件越大,效果越明显。但如果源文件数据变态,也不一定的哦!)
*/
shrinkHTree();
}
}
flush();
} catch (IOException e) {
e.printStackTrace();
return -1;
}
return 0;
}
/**
* 读取压缩文件并压缩
*
* @return 0:操作成功
*/
public int decode() {
return 0;
}
// 输入输出------------------------------------------------------------
/**
* 输出一位,如果缓存区满了,就输出到文件
*
* @param bit
* 位数据
* @return 0:操作成功
*/
private int writeBit(int bit) {
// 写入一位数据
if (bit != 0)
outputBuffer[buffer_pointer] |= (int) Math.pow(2, bit_pointer);
// 位指针向低位移动
bit_pointer--;
// 如果位指针越过字节最低位,则回归最高位,同时将缓冲区指针向后移动
if (bit_pointer < BOTTOM_BIT) {
bit_pointer = TOP_BIT;
buffer_pointer++;
// 如果缓存区指针越过缓存区,则输出缓存区,指针归零,清零缓存区第一个字节
if (buffer_pointer == BUFFER_SIZE) {
try {
ous.write(outputBuffer);
ous.flush();
} catch (IOException e) {
e.printStackTrace();
return -1;
}
buffer_pointer = 0;
outputBuffer[0] = 0;
}
// 清零缓存区下一字节
outputBuffer[buffer_pointer] = 0;
}
return 0;
}
/**
* 输出缓存区
*/
private void flush() {
try {
ous.write(outputBuffer, 0, buffer_pointer);
ous.flush();
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* 自底向上遍历树,并将编码输出
*
* @param data
* 数据
* @return 0:操作成功
*/
private int encodeData(int data) {
if (data > CODE_ESCAPE) {
System.out.println("编码时遇到未知数据!");
return -1;
}
// 自底向上编码,并输出
HNode tmp = list[data];
do {
writeBit((tmp.isleft ? 0 : 1));
tmp.count++;
} while ((tmp = tmp.parent) != root);
return 0;
}
// 树操作------------------------------------------------------------
/**
* 新建一个节点,并指定其父节点;同时初始化节点的count,并将节点放入节点列表
*
* @param data
* 节点数据
* @param isleft
* true:左节点
* @param parent
* 父节点
* @return 新建的节点
*/
private HNode newHNode(int data, boolean isleft, HNode parent) {
HNode tmp = new HNode();
tmp.data = data;
tmp.isleft = isleft;
tmp.parent = parent;
// 对编码数据count赋初始值
if (data <= MAX_VALUE)
tmp.count = (int) Math.pow(2, INIT_RATIO) - 1;
// 加入叶节点列表
if (data != NOT_DATA)
list[data] = tmp;
return tmp;
}
/**
* 当出现的数据是树中没有的数据时,扩展树
*
* @param data
* 节点数据
* @return 0:操作成功
*/
private int enlargeHTree(int data) {
// 取出扩展节点
HNode tmp = list[CODE_EXTAND].parent;
// 生成非叶子节点,以扩展节点的父节点为父节点;将扩展节点接到此节点后
HNode tmp2 = newHNode(NOT_DATA, true, tmp);
tmp.lchild = tmp2;
tmp2.lchild = list[CODE_EXTAND];
list[CODE_EXTAND].parent = tmp2;
// 生成数据节点,此节点为扩展节点的兄弟节点
tmp = newHNode(data, false, tmp2);
tmp2.rchild = tmp;
// 自底向上调整count
tmp2.count = 0;
int tmp3 = tmp.count;
do {
tmp2.count += tmp3;
} while ((tmp2 = tmp2.parent) != root);
// 调整树
balanceHTree(tmp.parent);
return 0;
}
/**
* 当计数器由某个根节点的更新到根节点后,需要考虑调整部分树节点
*
* @param node
* 调整的范围是node的父节点到node的子节点,深度范围为3
* @return 0:操作成功
*/
private int balanceHTree(HNode node) {
HNode parent = node.parent;
// 如果父节点为根节点则不调整
if (parent == root) {
return 0;
}
// 找出node的兄弟节点
HNode brother = node.isleft ? parent.rchild : parent.lchild;
// 找出node下count较大的子节点
HNode child = node.lchild.count > node.rchild.count ? node.lchild
: node.rchild;
// 如果node的兄弟节点的count小于child的count,则交换
if (child.count > parent.count - brother.count) {
boolean isleft = child.isleft;
if (node.isleft) {
parent.rchild = child;
child.isleft = false;
} else {
parent.lchild = child;
child.isleft = true;
}
if (isleft) {
node.lchild = brother;
brother.isleft = true;
} else {
node.rchild = brother;
brother.isleft = false;
}
}
// 递归向上调整
balanceHTree(parent);
return 0;
}
/**
* 为了是树尽可能的小(编码尽可能的短),对树进行瘦身是必要的,删除出现频率很小的节点
*
* @return 0:操作成功
*/
private int shrinkHTree() {
HNode tmp, parent, brother;
// 将所有数据节点count减倍,删除count为零的节点
for (int i = 0; i <= MAX_VALUE; i++) {
tmp = list[i];
if (tmp!=null) {
tmp.count >>= SHRINK_RATIO;
if (tmp.count==0) {
parent = tmp.parent;
if (tmp.isleft) {
brother = parent.rchild;
} else {
brother = parent.lchild;
}
brother.parent = parent.parent;
if (parent.isleft) {
parent.parent.lchild = brother;
brother.isleft = true;
} else {
tmp.parent.rchild = brother;
brother.isleft = false;
}
tmp = null;
parent = null;
list[i] = null;
}
}
}
return 0;
}
}
Hnode:
package cn.cls.bean;
public class HNode {
public int data; //数据
public int count; //频率
public HNode parent; //父节点
public HNode lchild; //左子节点
public HNode rchild; //右子节点
public boolean isleft; //0为左节点,1为右节点
}
最后说明一下,解压的方法还没写,稍等,1h以后在下一篇日志里见。。。
分享到:
相关推荐
开关重定义。 你可以在同一命令行指定普通文件名和列表文件。如果文件和列表 文件都未被指定,那么 RAR 将默认是 *.*,来处理所有文件。 许多 RAR 命令,例如解压、测试和列表,都允许在压缩文件名中使用...
同的短时能量自适应调整引入回声的衰减系数,具有抵抗加噪、滤波、重采样以及MP3 压缩等攻击的良好鲁棒性和更高的不可感知性。 在详细分析纠错编码对隐藏信息检测误码率影响的基础上,将CBH编码技术引入到 回声隐藏...
其它参数是压缩文件名和被压缩的文件或要从压缩文件 中被解压文件。 列表文件是一个包括处理的文件名的纯文本文件。第一列应该以文件名开始。可以 在//字符后添加注释。例如,你可以创建包含下列字符串的 backup...
12.10.3 选择多播环回:IP_MULTICAST_ LOOP 281 12.11 加入一个IP多播组 282 12.11.1 in_addmulti函数 285 12.11.2 slioctl和loioctl函数:SIOCADDMULTI和SIOCDELMULTI 287 12.11.3 leioctl函数:SIOCADDMULTI和 ...
with支持名称空间和多重获取/设置和删除的stoor本地和会话存储包装目录关于安装:...它提供:值的解析和字符串化可插入的回退(默认为内存中)名称空间多值获取,设置和删除值安装方式软件包管理器:$ npm install-
将气囊缓冲过程分解为绝热压缩和排气释能2个过程,从热力学和运动学方程出发,建立考虑降落伞阻力影响的缓冲气囊的解析分析模型。基于该模型,对立式气囊的缓冲特性进行研究。结果表明:降落伞阻力对缓冲性能有微小...
提出了一种基于离散小波变换(DWT) 和离散余弦变换(DCT) 的音频信息隐藏的新算法。 首先,对载体音频信号...噪、低通滤波、重采样、重量化、回声、MP3 压缩、样点裁剪、时域线性延伸和缩短等的攻击具有很强的 鲁棒性。
在分析"箱式混凝土墙+承重岩层"承载体受力压缩变形机理的基础上,建立了二次岩层移动力学模型,并推导出了该条件下评价混凝土稳定性的安全系数。根据煤层地质条件,确定了混凝土墙的间距、宽度及抗压强度。该技术在花园...
所得气凝胶的物理性质通过热重分析,扫描电子显微镜,氮吸附-解吸,接触角,热导率测量,压缩测试和傅里叶变换红外光谱来表征。 制成的气凝胶显示出高柔韧性,杨氏压缩模量为0.33 MPa,密度为0.132 g / cm3。 它们...
恢复因磁盘格式化,或是重装操作系统后丢失的数据文件。 分区恢复 恢复因分区表被破坏而丢失的分区里面的数据文件。 其他恢复 恢复因磁盘崩溃无法读取的数据文件; 恢复文档,照片,电影...
利用人耳听觉掩蔽特性,采用小波变换和幅度调制的方式,实现了一种新的复杂度低、...实验结果表明,该算法具有很好的不可感知性,且能够抵抗诸如低通滤波、加噪、重采样、回声、A/μ率转换、MP3压缩及各种去同步攻击。
★个别版本windows7系统插入USB录音盒后无法正常自动加载驱动,一般这种情况是由系统声卡驱动不匹配等原因造成,请下载:驱动精灵软件,对您系统的声卡驱动进行更新,然后再重插USB录音盒可以解决驱动问题。
2019年中央经济会议提出“财政政策要大力提质增效”、“压缩一般性支出”,从表述上看, 2020年政府部门将“控制杠杆增速”、逐步进入“稳杠杆阶段”,那么相应的居民部门杠杆增速将企稳并在未来重回 上升通道。...
实验表明,嵌入秘密信息后的音频文件不仅具有良好的不可感知性,而且能够抵抗诸如低通滤波、加噪声、回声、重采样、Mp3解压缩等攻击,特别还能抵抗DA/AD转换和各种去同步攻击,具有很强的鲁棒性。
如从格式从改变的数据源加回。 更新2020.10.6 该存储库每天提供由以下人员提供的数据集的存档: https://covid19-dashboard.ages.at/ 每小时从 https://covid19-dashboard.ages.at/data/data.zip 提取并承诺。 ...
它的重量大约为 2kb 压缩和 gzip 压缩以及 4.5kb 压缩。 Mousetrap 已经过测试,应该可以在 Internet Explorer 6+、Safari、Firefox 和 Chrome 中使用。 bind 方法是您将进行的主要调用。 这会将指定的键盘命令绑定...
5、弹出输赢提示,提示用户退出或重玩。 课题要求: 1、设计良好的人机交互GUI界面; 2、程序要求有注释。 在此基础上还改变了控件背景,添加了最高分纪录。当游戏胜利或者游戏失败时都会有弹窗提醒。 下载解压缩后...
HTTP路径反向代理,将远端HTTP服务反向代理到本地HTTP子目录下,解析修改HTTP请求头与响应头并修改链接位置,重定义Content-Length,遇到HTTP响应gzip压缩编码时解压后进行修改并可以重新gzip压缩发回用户,用户可以...
等,这样做的好处是你重装系统之后你加密的文件夹资料依旧存在。 3.现在版本软件可以多用户使用。即:在不同的目录设置不同的密码。但是请你务必记住口令! 4.可以对优盘数据进行加密处理。 5.警告:试用期间...