?David A. Huffman

1 哈夫曼編碼簡史（Huffman code）

1951年，哈夫曼和他在MIT信息論的同學(xué)需要選擇是完成學(xué)期報告還是期末考試。導(dǎo)師Robert M. Fano給他們的學(xué)期報告的題目是，尋找最有效的二進制編碼。由于無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉(zhuǎn)向新的探索，最終發(fā)現(xiàn)了基于有序頻率二叉樹編碼的想法，并很快證明了這個方法是最有效的。由于這個算法，學(xué)生終于青出于藍，超過了他那曾經(jīng)和信息論創(chuàng)立者香農(nóng)共同研究過類似編碼的導(dǎo)師。哈夫曼使用自底向上的方法構(gòu)建二叉樹，避免了次優(yōu)算法Shannon-Fano編碼的最大弊端──自頂向下構(gòu)建樹。
1952年，David A. Huffman在麻省理工攻讀博士時發(fā)表了《一種構(gòu)建極小多余編碼的方法》，一文，它一般就叫做Huffman編碼。A Method for the Construction of Minimum-Redundancy Codeshttps://www.ias.ac.in/article/fulltext/reso/011/02/0091-0099
Huffman在1952年根據(jù)香農(nóng)（Shannon）在1948年和范若（Fano）在1949年闡述的這種編碼思想提出了一種不定長編碼的方法，也稱霍夫曼（Huffman）編碼?；舴蚵幋a的基本方法是先對圖像數(shù)據(jù)掃描一遍，計算出各種像素出現(xiàn)的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張該圖像的霍夫曼碼表。編碼后的圖像數(shù)據(jù)記錄的是每個像素的碼字，而碼字與實際像素值的對應(yīng)關(guān)系記錄在碼表中。

2?赫夫曼編碼

赫夫曼編碼是可變字長編碼(VLC)的一種。 Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就稱Huffman編碼。下面引證一個定理，該定理保證了按字符出現(xiàn)概率分配碼長，可使平均碼長最短。

3 源程序

using System;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
? ? /// <summary>
? ? /// 哈夫曼編碼的壓縮與解壓縮
? ? /// </summary>
? ? public class HuffmanCompressor
? ? {
? ? ? ? private HuffmanNode oRootHuffmanNode { get; set; } = null;
? ? ? ? private List<HuffmanNode> oValueHuffmanNodes { get; set; } = null;

? ? ? ? private List<HuffmanNode> BuildBinaryTree(string Value)
? ? ? ? {
? ? ? ? ? ? List<HuffmanNode> oHuffmanNodes = GetInitialNodeList();

? ? ? ? ? ? Value.ToList().ForEach(m => oHuffmanNodes[m].Weight++);

? ? ? ? ? ? oHuffmanNodes = oHuffmanNodes
? ? ? ? ? ? ? ? .Where(m => (m.Weight > 0))
? ? ? ? ? ? ? ? .OrderBy(m => (m.Weight))
? ? ? ? ? ? ? ? .ThenBy(m => (m.Value))
? ? ? ? ? ? ? ? .ToList();

? ? ? ? ? ? oHuffmanNodes = UpdateNodeParents(oHuffmanNodes);

? ? ? ? ? ? oRootHuffmanNode = oHuffmanNodes[0];
? ? ? ? ? ? oHuffmanNodes.Clear();

? ? ? ? ? ? SortNodes(oRootHuffmanNode, oHuffmanNodes);

? ? ? ? ? ? return oHuffmanNodes;
? ? ? ? }

? ? ? ? public void Compress(string FileName)
? ? ? ? {
? ? ? ? ? ? FileInfo oFileInfo = new FileInfo(FileName);

? ? ? ? ? ? if (oFileInfo.Exists == true)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? string sFileContents = "";

? ? ? ? ? ? ? ? using (StreamReader oStreamReader = new StreamReader(File.OpenRead(FileName)))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? sFileContents = oStreamReader.ReadToEnd();
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? List<HuffmanNode> oHuffmanNodes = BuildBinaryTree(sFileContents);

? ? ? ? ? ? ? ? oValueHuffmanNodes = oHuffmanNodes
? ? ? ? ? ? ? ? ? ? .Where(m => (m.Value.HasValue == true))
? ? ? ? ? ? ? ? ? ? .OrderBy(m => (m.BinaryWord))
? ? ? ? ? ? ? ? ? ? .ToList();

? ? ? ? ? ? ? ? Dictionary<char, string> oCharToBinaryWordDictionary = new Dictionary<char, string>();
? ? ? ? ? ? ? ? foreach (HuffmanNode oHuffmanNode in oValueHuffmanNodes)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? oCharToBinaryWordDictionary.Add(oHuffmanNode.Value.Value, oHuffmanNode.BinaryWord);
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? StringBuilder oStringBuilder = new StringBuilder();
? ? ? ? ? ? ? ? List<byte> oByteList = new List<byte>();
? ? ? ? ? ? ? ? for (int i = 0; i < sFileContents.Length; i++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? string sWord = "";

? ? ? ? ? ? ? ? ? ? oStringBuilder.Append(oCharToBinaryWordDictionary[sFileContents[i]]);

? ? ? ? ? ? ? ? ? ? while (oStringBuilder.Length >= 8)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? sWord = oStringBuilder.ToString().Substring(0, 8);

? ? ? ? ? ? ? ? ? ? ? ? oStringBuilder.Remove(0, sWord.Length);
? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? if (String.IsNullOrEmpty(sWord) == false)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? oByteList.Add(Convert.ToByte(sWord, 2));
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if (oStringBuilder.Length > 0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? string sWord = oStringBuilder.ToString();

? ? ? ? ? ? ? ? ? ? if (String.IsNullOrEmpty(sWord) == false)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? oByteList.Add(Convert.ToByte(sWord, 2));
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? string sCompressedFileName = Path.Combine(oFileInfo.Directory.FullName, String.Format("{0}.compressed", oFileInfo.Name.Replace(oFileInfo.Extension, "")));
? ? ? ? ? ? ? ? if (File.Exists(sCompressedFileName) == true)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? File.Delete(sCompressedFileName);
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? using (FileStream oFileStream = File.OpenWrite(sCompressedFileName))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? oFileStream.Write(oByteList.ToArray(), 0, oByteList.Count);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? public void Decompress(string FileName)
? ? ? ? {
? ? ? ? ? ? FileInfo oFileInfo = new FileInfo(FileName);

? ? ? ? ? ? if (oFileInfo.Exists == true)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? string sCompressedFileName = String.Format("{0}.compressed", oFileInfo.FullName.Replace(oFileInfo.Extension, ""));

? ? ? ? ? ? ? ? byte[] oBuffer = null;
? ? ? ? ? ? ? ? using (FileStream oFileStream = File.OpenRead(sCompressedFileName))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? oBuffer = new byte[oFileStream.Length];
? ? ? ? ? ? ? ? ? ? oFileStream.Read(oBuffer, 0, oBuffer.Length);
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? HuffmanNode oZeroHuffmanNode = oRootHuffmanNode;
? ? ? ? ? ? ? ? while (oZeroHuffmanNode.Left != null)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? oZeroHuffmanNode = oZeroHuffmanNode.Left;
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? HuffmanNode oCurrentHuffmanNode = null;
? ? ? ? ? ? ? ? StringBuilder oStringBuilder = new StringBuilder();

? ? ? ? ? ? ? ? for (int i = 0; i < oBuffer.Length; i++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? string sBinaryWord = "";
? ? ? ? ? ? ? ? ? ? byte oByte = oBuffer[i];

? ? ? ? ? ? ? ? ? ? if (oByte == 0)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? sBinaryWord = oZeroHuffmanNode.BinaryWord;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? sBinaryWord = Convert.ToString(oByte, 2);
? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? if ((sBinaryWord.Length < 8) && (i < (oBuffer.Length - 1)))
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? StringBuilder oBinaryStringBuilder = new StringBuilder(sBinaryWord);
? ? ? ? ? ? ? ? ? ? ? ? while (oBinaryStringBuilder.Length < 8)
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? oBinaryStringBuilder.Insert(0, "0");
? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? sBinaryWord = oBinaryStringBuilder.ToString();
? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? for (int j = 0; j < sBinaryWord.Length; j++)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? char cValue = sBinaryWord[j];

? ? ? ? ? ? ? ? ? ? ? ? if (oCurrentHuffmanNode == null)
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? oCurrentHuffmanNode = oRootHuffmanNode;
? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? if (cValue == '0')
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? oCurrentHuffmanNode = oCurrentHuffmanNode.Left;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? oCurrentHuffmanNode = oCurrentHuffmanNode.Right;
? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? if ((oCurrentHuffmanNode.Left == null) && (oCurrentHuffmanNode.Right == null))
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? oStringBuilder.Append(oCurrentHuffmanNode.Value.Value);
? ? ? ? ? ? ? ? ? ? ? ? ? ? oCurrentHuffmanNode = null;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? string sUncompressedFileName = Path.Combine(oFileInfo.Directory.FullName, String.Format("{0}.uncompressed", oFileInfo.Name.Replace(oFileInfo.Extension, "")));

? ? ? ? ? ? ? ? if (File.Exists(sUncompressedFileName) == true)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? File.Delete(sUncompressedFileName);
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? using (StreamWriter oStreamWriter = new StreamWriter(File.OpenWrite(sUncompressedFileName)))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? oStreamWriter.Write(oStringBuilder.ToString());
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? private static List<HuffmanNode> GetInitialNodeList()
? ? ? ? {
? ? ? ? ? ? List<HuffmanNode> oGetInitialNodeList = new List<HuffmanNode>();

? ? ? ? ? ? for (int i = Char.MinValue; i < Char.MaxValue; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? oGetInitialNodeList.Add(new HuffmanNode((char)(i)));
? ? ? ? ? ? }

? ? ? ? ? ? return oGetInitialNodeList;
? ? ? ? }

? ? ? ? private static void SortNodes(HuffmanNode Node, List<HuffmanNode> Nodes)
? ? ? ? {
? ? ? ? ? ? if (Nodes.Contains(Node) == false)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Nodes.Add(Node);
? ? ? ? ? ? }

? ? ? ? ? ? if (Node.Left != null)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? SortNodes(Node.Left, Nodes);
? ? ? ? ? ? }

? ? ? ? ? ? if (Node.Right != null)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? SortNodes(Node.Right, Nodes);
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? private static List<HuffmanNode> UpdateNodeParents(List<HuffmanNode> Nodes)
? ? ? ? {
? ? ? ? ? ? while (Nodes.Count > 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int iOperations = (Nodes.Count / 2);
? ? ? ? ? ? ? ? for (int iOperation = 0, i = 0, j = 1; iOperation < iOperations; iOperation++, i += 2, j += 2)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (j < Nodes.Count)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? HuffmanNode oParentHuffmanNode = new HuffmanNode(Nodes[i], Nodes[j]);
? ? ? ? ? ? ? ? ? ? ? ? Nodes.Add(oParentHuffmanNode);

? ? ? ? ? ? ? ? ? ? ? ? Nodes[i] = null;
? ? ? ? ? ? ? ? ? ? ? ? Nodes[j] = null;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? Nodes = Nodes
? ? ? ? ? ? ? ? ? ? .Where(m => (m != null))
? ? ? ? ? ? ? ? ? ? .OrderBy(m => (m.Weight))
? ? ? ? ? ? ? ? ? ? .ToList();
? ? ? ? ? ? }

? ? ? ? ? ? return Nodes;
? ? ? ? }
? ? }

? ? public class HuffmanNode
? ? {
? ? ? ? private string sBinaryWord { get; set; } = "";
? ? ? ? private bool bIsLeftNode { get; set; } = false;
? ? ? ? private bool bIsRightNode { get; set; } = false;
? ? ? ? private HuffmanNode oLeft { get; set; } = null;
? ? ? ? private HuffmanNode oParent { get; set; } = null;
? ? ? ? private HuffmanNode oRight { get; set; } = null;
? ? ? ? private char? cValue { get; set; } = ' ';
? ? ? ? private int iWeight { get; set; } = 0;

? ? ? ? public HuffmanNode()
? ? ? ? {
? ? ? ? }

? ? ? ? public HuffmanNode(char Value)
? ? ? ? {
? ? ? ? ? ? cValue = Value;
? ? ? ? }

? ? ? ? public HuffmanNode(HuffmanNode Left, HuffmanNode Right)
? ? ? ? {
? ? ? ? ? ? oLeft = Left;
? ? ? ? ? ? oLeft.oParent = this;
? ? ? ? ? ? oLeft.bIsLeftNode = true;

? ? ? ? ? ? oRight = Right;
? ? ? ? ? ? oRight.oParent = this;
? ? ? ? ? ? oRight.bIsRightNode = true;

? ? ? ? ? ? iWeight = (oLeft.Weight + oRight.Weight);
? ? ? ? }

? ? ? ? public string BinaryWord
? ? ? ? {
? ? ? ? ? ? get
? ? ? ? ? ? {
? ? ? ? ? ? ? ? string sReturnValue = "";

? ? ? ? ? ? ? ? if (String.IsNullOrEmpty(sBinaryWord) == true)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? StringBuilder oStringBuilder = new StringBuilder();

? ? ? ? ? ? ? ? ? ? HuffmanNode oHuffmanNode = this;

? ? ? ? ? ? ? ? ? ? while (oHuffmanNode != null)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? if (oHuffmanNode.bIsLeftNode == true)
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? oStringBuilder.Insert(0, "0");
? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? if (oHuffmanNode.bIsRightNode == true)
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? oStringBuilder.Insert(0, "1");
? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? oHuffmanNode = oHuffmanNode.oParent;
? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? sReturnValue = oStringBuilder.ToString();
? ? ? ? ? ? ? ? ? ? sBinaryWord = sReturnValue;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? sReturnValue = sBinaryWord;
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? return sReturnValue;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? public HuffmanNode Left
? ? ? ? {
? ? ? ? ? ? get
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return oLeft;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? public HuffmanNode Parent
? ? ? ? {
? ? ? ? ? ? get
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return oParent;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? public HuffmanNode Right
? ? ? ? {
? ? ? ? ? ? get
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return oRight;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? public char? Value
? ? ? ? {
? ? ? ? ? ? get
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return cValue;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? public int Weight
? ? ? ? {
? ? ? ? ? ? get
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return iWeight;
? ? ? ? ? ? }
? ? ? ? ? ? set
? ? ? ? ? ? {
? ? ? ? ? ? ? ? iWeight = value;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? public static int BinaryStringToInt32(string Value)
? ? ? ? {
? ? ? ? ? ? int iBinaryStringToInt32 = 0;

? ? ? ? ? ? for (int i = (Value.Length - 1), j = 0; i >= 0; i--, j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? iBinaryStringToInt32 += ((Value[j] == '0' ? 0 : 1) * (int)(Math.Pow(2, i)));
? ? ? ? ? ? }

? ? ? ? ? ? return iBinaryStringToInt32;
? ? ? ? }

? ? ? ? public override string ToString()
? ? ? ? {
? ? ? ? ? ? StringBuilder sb = new StringBuilder();

? ? ? ? ? ? if (cValue.HasValue == true)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? sb.AppendFormat("'{0}' ({1}) - {2} ({3})", cValue.Value, iWeight, BinaryWord, BinaryStringToInt32(BinaryWord));
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if ((oLeft != null) && (oRight != null))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if ((oLeft.Value.HasValue == true) && (oRight.Value.HasValue == true))
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? sb.AppendFormat("{0} + {1} ({2})", oLeft.Value, oRight.Value, iWeight);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? sb.AppendFormat("{0}, {1} - ({2})", oLeft, oRight, iWeight);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? sb.Append(iWeight);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }

? ? ? ? ? ? return sb.ToString();
? ? ? ? }
? ? }
}
?

4 源代碼

using System;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{/// <summary>/// 哈夫曼編碼的壓縮與解壓縮/// </summary>public class HuffmanCompressor{private HuffmanNode oRootHuffmanNode { get; set; } = null;private List<HuffmanNode> oValueHuffmanNodes { get; set; } = null;private List<HuffmanNode> BuildBinaryTree(string Value){List<HuffmanNode> oHuffmanNodes = GetInitialNodeList();Value.ToList().ForEach(m => oHuffmanNodes[m].Weight++);oHuffmanNodes = oHuffmanNodes.Where(m => (m.Weight > 0)).OrderBy(m => (m.Weight)).ThenBy(m => (m.Value)).ToList();oHuffmanNodes = UpdateNodeParents(oHuffmanNodes);oRootHuffmanNode = oHuffmanNodes[0];oHuffmanNodes.Clear();SortNodes(oRootHuffmanNode, oHuffmanNodes);return oHuffmanNodes;}public void Compress(string FileName){FileInfo oFileInfo = new FileInfo(FileName);if (oFileInfo.Exists == true){string sFileContents = "";using (StreamReader oStreamReader = new StreamReader(File.OpenRead(FileName))){sFileContents = oStreamReader.ReadToEnd();}List<HuffmanNode> oHuffmanNodes = BuildBinaryTree(sFileContents);oValueHuffmanNodes = oHuffmanNodes.Where(m => (m.Value.HasValue == true)).OrderBy(m => (m.BinaryWord)).ToList();Dictionary<char, string> oCharToBinaryWordDictionary = new Dictionary<char, string>();foreach (HuffmanNode oHuffmanNode in oValueHuffmanNodes){oCharToBinaryWordDictionary.Add(oHuffmanNode.Value.Value, oHuffmanNode.BinaryWord);}StringBuilder oStringBuilder = new StringBuilder();List<byte> oByteList = new List<byte>();for (int i = 0; i < sFileContents.Length; i++){string sWord = "";oStringBuilder.Append(oCharToBinaryWordDictionary[sFileContents[i]]);while (oStringBuilder.Length >= 8){sWord = oStringBuilder.ToString().Substring(0, 8);oStringBuilder.Remove(0, sWord.Length);}if (String.IsNullOrEmpty(sWord) == false){oByteList.Add(Convert.ToByte(sWord, 2));}}if (oStringBuilder.Length > 0){string sWord = oStringBuilder.ToString();if (String.IsNullOrEmpty(sWord) == false){oByteList.Add(Convert.ToByte(sWord, 2));}}string sCompressedFileName = Path.Combine(oFileInfo.Directory.FullName, String.Format("{0}.compressed", oFileInfo.Name.Replace(oFileInfo.Extension, "")));if (File.Exists(sCompressedFileName) == true){File.Delete(sCompressedFileName);}using (FileStream oFileStream = File.OpenWrite(sCompressedFileName)){oFileStream.Write(oByteList.ToArray(), 0, oByteList.Count);}}}public void Decompress(string FileName){FileInfo oFileInfo = new FileInfo(FileName);if (oFileInfo.Exists == true){string sCompressedFileName = String.Format("{0}.compressed", oFileInfo.FullName.Replace(oFileInfo.Extension, ""));byte[] oBuffer = null;using (FileStream oFileStream = File.OpenRead(sCompressedFileName)){oBuffer = new byte[oFileStream.Length];oFileStream.Read(oBuffer, 0, oBuffer.Length);}HuffmanNode oZeroHuffmanNode = oRootHuffmanNode;while (oZeroHuffmanNode.Left != null){oZeroHuffmanNode = oZeroHuffmanNode.Left;}HuffmanNode oCurrentHuffmanNode = null;StringBuilder oStringBuilder = new StringBuilder();for (int i = 0; i < oBuffer.Length; i++){string sBinaryWord = "";byte oByte = oBuffer[i];if (oByte == 0){sBinaryWord = oZeroHuffmanNode.BinaryWord;}else{sBinaryWord = Convert.ToString(oByte, 2);}if ((sBinaryWord.Length < 8) && (i < (oBuffer.Length - 1))){StringBuilder oBinaryStringBuilder = new StringBuilder(sBinaryWord);while (oBinaryStringBuilder.Length < 8){oBinaryStringBuilder.Insert(0, "0");}sBinaryWord = oBinaryStringBuilder.ToString();}for (int j = 0; j < sBinaryWord.Length; j++){char cValue = sBinaryWord[j];if (oCurrentHuffmanNode == null){oCurrentHuffmanNode = oRootHuffmanNode;}if (cValue == '0'){oCurrentHuffmanNode = oCurrentHuffmanNode.Left;}else{oCurrentHuffmanNode = oCurrentHuffmanNode.Right;}if ((oCurrentHuffmanNode.Left == null) && (oCurrentHuffmanNode.Right == null)){oStringBuilder.Append(oCurrentHuffmanNode.Value.Value);oCurrentHuffmanNode = null;}}}string sUncompressedFileName = Path.Combine(oFileInfo.Directory.FullName, String.Format("{0}.uncompressed", oFileInfo.Name.Replace(oFileInfo.Extension, "")));if (File.Exists(sUncompressedFileName) == true){File.Delete(sUncompressedFileName);}using (StreamWriter oStreamWriter = new StreamWriter(File.OpenWrite(sUncompressedFileName))){oStreamWriter.Write(oStringBuilder.ToString());}}}private static List<HuffmanNode> GetInitialNodeList(){List<HuffmanNode> oGetInitialNodeList = new List<HuffmanNode>();for (int i = Char.MinValue; i < Char.MaxValue; i++){oGetInitialNodeList.Add(new HuffmanNode((char)(i)));}return oGetInitialNodeList;}private static void SortNodes(HuffmanNode Node, List<HuffmanNode> Nodes){if (Nodes.Contains(Node) == false){Nodes.Add(Node);}if (Node.Left != null){SortNodes(Node.Left, Nodes);}if (Node.Right != null){SortNodes(Node.Right, Nodes);}}private static List<HuffmanNode> UpdateNodeParents(List<HuffmanNode> Nodes){while (Nodes.Count > 1){int iOperations = (Nodes.Count / 2);for (int iOperation = 0, i = 0, j = 1; iOperation < iOperations; iOperation++, i += 2, j += 2){if (j < Nodes.Count){HuffmanNode oParentHuffmanNode = new HuffmanNode(Nodes[i], Nodes[j]);Nodes.Add(oParentHuffmanNode);Nodes[i] = null;Nodes[j] = null;}}Nodes = Nodes.Where(m => (m != null)).OrderBy(m => (m.Weight)).ToList();}return Nodes;}}public class HuffmanNode{private string sBinaryWord { get; set; } = "";private bool bIsLeftNode { get; set; } = false;private bool bIsRightNode { get; set; } = false;private HuffmanNode oLeft { get; set; } = null;private HuffmanNode oParent { get; set; } = null;private HuffmanNode oRight { get; set; } = null;private char? cValue { get; set; } = ' ';private int iWeight { get; set; } = 0;public HuffmanNode(){}public HuffmanNode(char Value){cValue = Value;}public HuffmanNode(HuffmanNode Left, HuffmanNode Right){oLeft = Left;oLeft.oParent = this;oLeft.bIsLeftNode = true;oRight = Right;oRight.oParent = this;oRight.bIsRightNode = true;iWeight = (oLeft.Weight + oRight.Weight);}public string BinaryWord{get{string sReturnValue = "";if (String.IsNullOrEmpty(sBinaryWord) == true){StringBuilder oStringBuilder = new StringBuilder();HuffmanNode oHuffmanNode = this;while (oHuffmanNode != null){if (oHuffmanNode.bIsLeftNode == true){oStringBuilder.Insert(0, "0");}if (oHuffmanNode.bIsRightNode == true){oStringBuilder.Insert(0, "1");}oHuffmanNode = oHuffmanNode.oParent;}sReturnValue = oStringBuilder.ToString();sBinaryWord = sReturnValue;}else{sReturnValue = sBinaryWord;}return sReturnValue;}}public HuffmanNode Left{get{return oLeft;}}public HuffmanNode Parent{get{return oParent;}}public HuffmanNode Right{get{return oRight;}}public char? Value{get{return cValue;}}public int Weight{get{return iWeight;}set{iWeight = value;}}public static int BinaryStringToInt32(string Value){int iBinaryStringToInt32 = 0;for (int i = (Value.Length - 1), j = 0; i >= 0; i--, j++){iBinaryStringToInt32 += ((Value[j] == '0' ? 0 : 1) * (int)(Math.Pow(2, i)));}return iBinaryStringToInt32;}public override string ToString(){StringBuilder sb = new StringBuilder();if (cValue.HasValue == true){sb.AppendFormat("'{0}' ({1}) - {2} ({3})", cValue.Value, iWeight, BinaryWord, BinaryStringToInt32(BinaryWord));}else{if ((oLeft != null) && (oRight != null)){if ((oLeft.Value.HasValue == true) && (oRight.Value.HasValue == true)){sb.AppendFormat("{0} + {1} ({2})", oLeft.Value, oRight.Value, iWeight);}else{sb.AppendFormat("{0}, {1} - ({2})", oLeft, oRight, iWeight);}}else{sb.Append(iWeight);}}return sb.ToString();}}
}