ハーバーマンコーディングアルゴリズム
アルゴリズムコードは次のとおりです.
PS:このアルゴリズムは最小スタックの効率が高く、O(nlgn)では、ここのアルゴリズムはO(n^2)であり、挿入ソートアルゴリズムの時間的複雑さに合致する.
public class HuffmanNode
{
public char Char { get; set; }
public int Frequency { get; set; }
//
internal HuffmanNode LeftChild { get; set; }
internal HuffmanNode RightChild { get; set; }
//
internal HuffmanNode NextSibling { get; set; }
public string HuffmanCode {get;set;}
public HuffmanNode(char Char,int Freq)
{
this.Char = Char;
this.Frequency = Freq;
}
}
public class HuffmanAlgorithms
{
/// <summary>
/// , Nodes , 。
/// </summary>
/// <param name="Nodes"></param>
public static void HuffmanCode(HuffmanNode[] Nodes)
{
if (Nodes == null || Nodes.Length == 0)
{
return;
}
#region
if (Nodes.Length == 1)
{
Nodes[0].HuffmanCode = "0";
return;
}
if (Nodes.Length == 2)
{
Nodes[0].HuffmanCode = "0";
Nodes[1].HuffmanCode = "1";
return;
}
#endregion
HuffmanNode theHead = null;
// , O(n^2)
for (int i = 0; i < Nodes.Length;i++ )
{
InsertNode(ref theHead, Nodes[i]);
}
// Huffman , , ( ).
HuffmanNode theTmp1 = null;
HuffmanNode theTmp2 = null;
theTmp1 = theHead;
if (theHead != null)
{
theTmp2 = theHead.NextSibling;
}
// , , , .O(n*lgn)
while (theTmp1 != null && theTmp2 != null)
{
// , .
HuffmanNode theParent = new HuffmanNode('\0', theTmp1.Frequency + theTmp2.Frequency);
theParent.LeftChild = theTmp1;
theParent.RightChild = theTmp2;
// , .
theHead = theTmp2.NextSibling;
// .
InsertNode(ref theHead, theParent);
theTmp1 = theHead;
if (theHead != null)
{
theTmp2 = theHead.NextSibling;
}
}
// . .o(n)
HuffmanCode(theHead, "");
// , .o(n)
foreach (var node in Nodes)
{
node.LeftChild = null;
node.NextSibling = null;
node.RightChild = null;
}
}
/// <summary>
/// , , Nodes 。
/// </summary>
/// <param name="ANode"></param>
/// <param name="StrCode"></param>
private static void HuffmanCode(HuffmanNode ANode, string StrCode)
{
if (ANode != null)
{
ANode.HuffmanCode = StrCode;
if (ANode.LeftChild != null)
{
HuffmanCode(ANode.LeftChild, StrCode + "0");
}
if (ANode.RightChild != null)
{
HuffmanCode(ANode.RightChild, StrCode + "1");
}
}
}
/// <summary>
/// Node AHead , .
/// </summary>
/// <param name="AHead"></param>
/// <param name="Node"></param>
private static void InsertNode(ref HuffmanNode AHead,HuffmanNode Node)
{
HuffmanNode theTmp1 = AHead;
HuffmanNode theTmp2 = null;
while (theTmp1 != null && theTmp1.Frequency < Node.Frequency)
{
theTmp2 = theTmp1;
theTmp1 = theTmp1.NextSibling;
}
if (theTmp2 == null)
{
AHead = Node;
}
else
{
theTmp2.NextSibling = Node;
}
Node.NextSibling = theTmp1;
}
}
PS:このアルゴリズムは最小スタックの効率が高く、O(nlgn)では、ここのアルゴリズムはO(n^2)であり、挿入ソートアルゴリズムの時間的複雑さに合致する.