using System;
|
using System.Collections.Generic;
|
using System.Linq;
|
|
namespace iWareModel
|
{
|
public class Huffman
|
{
|
/// <summary>
|
/// 原始的编码字符的集合
|
/// </summary>
|
private char[] mDict;
|
|
/// <summary>
|
/// 原始编码字符中实际使用到的字符集（用于需要编码的字符串中的字符小于所定义的字符集）
|
/// </summary>
|
private char[] mCntDict;
|
|
/// <summary>
|
/// 无参构造函数
|
/// </summary>
|
public Huffman()
|
{
|
this.mDict = new char[0];
|
mCntDict = mDict;
|
}
|
|
/// <summary>
|
/// 构造函数，给定Haffman字符的字段集合
|
/// </summary>
|
/// <param name="dict"></param>
|
public Huffman(char[] dict)
|
{
|
this.mDict = dict.Distinct().ToArray();
|
mCntDict = mDict;
|
}
|
|
/// <summary>
|
/// 构造函数，给定Haffman字符的字段集合
|
/// </summary>
|
public Huffman(string dict)
|
{
|
this.mDict = dict.ToCharArray().Distinct().ToArray();
|
mCntDict = mDict;
|
}
|
|
/// <summary>
|
/// 将字符串转Huffman码，并且生成字符转换的关键字典集
|
/// </summary>
|
/// <param name="key">导出的关键字字典</param>
|
/// <param name="str">需要编码的huffman集合</param>
|
/// <returns></returns>
|
public string StringToHuffmanCode(out Dictionary<char, string> key, string str)
|
{
|
var tmps = GetWeightArray(str);
|
var tree = CreateHuffmanTree(tmps);
|
key = CreateHuffmanCode("", tree);
|
return ToHuffmanCode(str, key);
|
}
|
|
/// <summary>
|
/// 关键关键字典将编码还原
|
/// </summary>
|
/// <param name="code"></param>
|
/// <param name="key"></param>
|
/// <returns></returns>
|
public string ToText(string code, Dictionary<char, string> key)
|
{
|
string result = "";
|
|
for (int i = 0; i < code.Length; )
|
{
|
foreach (var item in key)
|
{
|
if (code[i] == item.Value[0] && item.Value.Length + i <= code.Length)
|
{
|
char[] tmpArr = new char[item.Value.Length];
|
Array.Copy(code.ToCharArray(), i, tmpArr, 0, tmpArr.Length);
|
if (new string(tmpArr) == item.Value)
|
{
|
result += item.Key;
|
i += item.Value.Length;
|
break;
|
}
|
}
|
}
|
}
|
return result;
|
}
|
|
|
/// <summary>
|
/// 计算每个字符串的权重
|
/// </summary>
|
/// <param name="str"></param>
|
/// <returns></returns>
|
private Node[] GetWeightArray(string str)
|
{
|
var nodes = new List<Node>();
|
var charArr = str.ToCharArray();
|
if (charArr.Length < mDict.Length)
|
{
|
mCntDict = new char[charArr.Length];
|
Array.Copy(mDict, 0, mCntDict, 0, charArr.Length);
|
}
|
while (charArr.Length > 0)
|
{
|
var tmp = charArr.Where(m => m == charArr[0]).ToArray();
|
nodes.Add(new Node(tmp.Length, tmp.First()));
|
charArr = charArr.Where(m => m != tmp.First()).ToArray();
|
}
|
return nodes.ToArray();
|
}
|
|
/// <summary>
|
/// 生成Haffman树的算法
|
/// </summary>
|
/// <param name="nodes">原始的节点集合</param>
|
/// <returns>生成好的Haffman树</returns>
|
private Node CreateHuffmanTree(Node[] nodes)
|
{
|
if (nodes.Length <= mCntDict.Length)
|
{
|
var node = new Node(0, '\0');
|
node.Children = nodes;
|
foreach (var n in nodes) { node.Weight += n.Weight; }
|
return node;
|
}
|
Array.Sort(nodes);
|
var newNode = new Node(0, '\0');
|
newNode.Children = new Node[mCntDict.Length];
|
|
for (int i = nodes.Length - 1, j = 0; i >= 0; i--, j++)
|
{
|
if (j >= mCntDict.Length) { break;}
|
newNode.Weight += nodes[i].Weight;
|
newNode.Children[j] = nodes[i];
|
}
|
|
var newNodes = new Node[nodes.Length - mCntDict.Length + 1];
|
Array.Copy(nodes, 0, newNodes, 0, newNodes.Length - 1);
|
newNodes[newNodes.Length - 1] = newNode;
|
return CreateHuffmanTree(newNodes);
|
}
|
|
/// <summary>
|
/// 生成关键字典集
|
/// </summary>
|
/// <param name="code">默认填充字符</param>
|
/// <param name="hTree"></param>
|
/// <returns></returns>
|
private Dictionary<char, string> CreateHuffmanCode(string code, Node hTree)
|
{
|
var key = new Dictionary<char, string>();
|
if (hTree.Children == null)
|
{
|
key.Add(hTree.Key, code);
|
}
|
else
|
{
|
for (int i = 0; i < hTree.Children.Length; i++)
|
{
|
var tmpDict = CreateHuffmanCode(code + mCntDict[i], hTree.Children[i]);
|
|
foreach (var item in tmpDict)
|
{
|
key.Add(item.Key, item.Value);
|
}
|
}
|
}
|
return key;
|
}
|
|
/// <summary>
|
/// 关键生成的数将字符转出Haffman码
|
/// </summary>
|
/// <param name="source"></param>
|
/// <param name="key"></param>
|
/// <returns></returns>
|
private string ToHuffmanCode(string source, Dictionary<char, string> key)
|
{
|
string result = "";
|
|
for (int i = 0; i < source.Length; i++)
|
{
|
result += key.First(m => m.Key == source[i]).Value;
|
}
|
return result;
|
}
|
}
|
|
public class Node : IComparable
|
{
|
public Node[] Children { get; set; }
|
public int Weight { get; set; }
|
public char Key { get; set; }
|
public Node() { }
|
public Node(int weight, char value)
|
{
|
this.Weight = weight;
|
this.Key = value;
|
}
|
|
/// <summary>
|
/// 关键权重降序排序
|
/// </summary>
|
/// <param name="obj"></param>
|
/// <returns></returns>
|
public int CompareTo(object obj)
|
{
|
var tmp = obj as Node;
|
if (tmp.Weight > this.Weight) { return 1; }
|
if (tmp.Weight < this.Weight) { return -1; }
|
return 0;
|
}
|
}
|
}
|
