C# 霍夫曼二叉树压缩算法实现

知道有的人比较懒,直接贴全部代码.
一开始一次性Code完了压缩部分代码.只调试了2,3次就成功了.
一次性写150行代码,没遇到什么bug的感觉还是蛮爽的.
写解压代码,才发现压缩代码有些细节问题.
对最后一个字符处理问题.
遇到比较折腾点:构建二叉树时,把原本应该是(叶结点的有值的)节点放在了左节点,正确应该放在右节点,导致生成的编码序列不满足(任意编码不是其他编码的前缀).导致解码失败.
使用方法:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO; namespace 霍夫曼二叉树压缩
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
var s=GetCode();
var b= GetByteByCode(s);
} private void button1_Click(object sender, EventArgs e)
{
var srcData = Encoding.UTF8.GetBytes(textBox1.Text);
var cpsData = Compress(srcData);
treeView1.ExpandAll();
var depData = DeCompress(cpsData);
var depStr = Encoding.UTF8.GetString(depData );
} Dictionary<int, string> dicCode = new Dictionary<int, string>();
byte[] Compress(byte[] data)
{
Dictionary<byte, int> everyCount = new Dictionary<byte, int>();
foreach (var d in data)
{
if(everyCount.ContainsKey(d)==false )
everyCount.Add(d,);
everyCount[d]++;
}
var orderAscCounts = everyCount.OrderBy(a=>a.Value);
Queue<Count> queCouts = new Queue<Count>();
orderAscCounts.ToList().ForEach(d => {
queCouts.Enqueue(new Count { key=d.Key, count=d.Value });
});
BuildTree(ref queCouts);
foreach (var a in BNode.nodes)
{
var code = new string(GetCode(a).Reverse().ToArray());
dicCode.Add(a.key,code);
}
BNode root = BNode.nodes[];
while(root.parent!=null){
root = root.parent;
}
CreateTreeView(root,treeView1.Nodes);
string curCode = "";
List<byte> outData = new List<byte>();
foreach (var d in data)
{
curCode += dicCode[d];
if (curCode.Length >= )
{
byte curBit = GetByteByCode(curCode.Substring(,));
outData.Add(curBit);
curCode = curCode.Length > ? curCode.Substring(, curCode.Length - ) : "";
}
}
if (curCode != "")
{
curCode = curCode.PadRight(,'');
byte curBit = GetByteByCode(curCode);
outData.Add(curBit);
} return outData.ToArray();
} byte[] DeCompress(byte[] data)
{
string codes = "";
for (int i = ; i < data.Length - ;i++ )
{
codes += GetCode(data[i]);
}
codes += GetCode(data[data.Length-]).TrimEnd('');
var bdata = GetCode(codes); return bdata;
} byte GetByteByCode(string curCode)
{
return Convert.ToByte(curCode, );
}
byte[] GetCode(string code)
{
List<byte> datas = new List<byte>();
int pos = ;
var orderDicCode=dicCode.OrderByDescending(a=>a.Value.Length);
do{
int p=-;
foreach (var vCode in orderDicCode)
{
p = code.IndexOf(vCode.Value);
if (p == )
{
datas.Add((byte)vCode.Key);
code = code.Substring(vCode.Value.Length , code.Length-vCode.Value.Length );
break;
}
}
if (p == -)
{
throw new Exception("解压出错:发现未能识别的编码,编码表或数据已被破坏!");
}
}while(code.Length>); /* for (int i = 1; pos + i < code.Length ; i++)
{
var firstCode = code.Substring(pos, i);
var secondCode = code.Substring(pos, i + 1); var first = dicCode.Where(a => a.Value == firstCode);
var second = dicCode.Where(a => a.Value == secondCode);
if (first.Count() > 0 && second.Count() == 0 ){
datas.Add( (byte)first.First().Key);
pos = pos+i;
i = 1;
} else if (pos + i == code.Length - 1 && second.Count() > 0)
datas.Add( (byte)second.First().Key );
}*/
return datas.ToArray();
}
string GetCode(byte b )
{
return Convert.ToString(b, ).PadLeft(, '');//Convert.ToString(b, 2) ;//:
}
string GetCode(BNode a)
{
if (a.parent!=null)
return (a.isLeft ? "" : "")+GetCode(a.parent);
return "" ;
} BNode BuildTree(ref Queue<Count> queCouts )
{
var first = queCouts.Dequeue();
var second = queCouts.Dequeue(); var lft =first.node==null? new BNode { key=first.key, count=first.count } : first.node; var rgt = second.node == null ? new BNode { key = second.key, count = second.count } : second.node; if (rgt.key == -)
{
var temp = lft;
lft = rgt;
rgt = temp; } var pnode = new BNode
{
key = -, count = first.count + second.count
};
lft.isLeft = true;
rgt.isLeft = false;
pnode.left = lft;
pnode.right = rgt;
lft.parent = pnode; rgt.parent = pnode;
if (lft.key != -)
BNode.nodes.Add(lft);
if (rgt.key != -)
BNode.nodes.Add(rgt);
if (queCouts.Count > ){
queCouts.Enqueue(new Count { count=pnode.count, key=pnode.key, node=pnode });
var orderQue = queCouts.OrderBy(q => q.count).ToList();
queCouts.Clear();
foreach (var a in orderQue)
queCouts.Enqueue(a);
return BuildTree(ref queCouts);
}
else
return pnode;
} void CreateTreeView(BNode node , TreeNodeCollection tnc)
{
if (node == null) return;
var newNode = tnc.Add((node.isLeft ? "" : "") + (node.key!=-?"-"+node.key + ":" + node.count:""));
CreateTreeView(node.left,newNode.Nodes);
CreateTreeView(node.right, newNode.Nodes);
} class Count
{
public int key;
public int count;
public BNode node;
} class BNode{
public int key;
public int count;
public BNode left;
public BNode right;
public BNode parent;
public bool isLeft = false;
public static List<BNode> nodes = new List< BNode>(); }
}
}