我目前正在嘗試編寫一個讀取文本文件并通過創(chuàng)建 HuffmanTree 對其進行編碼的程序。我在優(yōu)先隊列的二叉堆中使用并行數(shù)組并跟蹤我的霍夫曼樹。我知道從堆中取出兩分鐘，合并它們，然后將它們插回堆中直到只剩下一個的原理，但是我無法將該邏輯/算法轉(zhuǎn)換為代碼。這是我的 HuffmanEncode 類：public class HuffmanEncode { public HuffmanEncode(String in, String out) { // Implements the Huffman encoding algorithm // Add private methods and instance variables as needed int[] freqs = new int[128]; // character counts char[] chars = new char[128]; //characters freqs = countFrequencies(in); HuffmanTree[] trees = new HuffmanTree[128]; //single node trees for(int i= 0; i < freqs.length; i++) { chars[i] = (char)i; trees[i] = new HuffmanTree(chars[i]); } BinaryHeap heap = new BinaryHeap(128); // create a binary heap for(int i = 0; i < 128; i++) { heap.insert(freqs[i], trees[i]); } // STUCK HERE buildTree(heap); HuffmanTree root = new HuffmanTree(); // STUCK HERE } private void buildTree(BinaryHeap h) { // grab two smallest while (h.getSize() > 1) { //repeat until there is only one left int temp1, temp2; HuffmanTree t1, t2; temp1 = h.getMinPriority(); temp2 = h.getMinPriority(); // add their frequency to create new single node tree with char 128 int sum = temp1 + temp2; HuffmanTree node = new HuffmanTree((char)128); // insert it back into the heap h.insert(sum, node); } }
2 回答
天涯盡頭無女友
TA貢獻1831條經(jīng)驗 獲得超9個贊
我已經(jīng)使用最小堆實現(xiàn)了霍夫曼編碼。你可能會從中得到一些想法。
internal class HuffmanTree
{
internal HuffmanTreeNode rootNode;
private Dictionary<char, int> dictFrequencies;
HuffmanPriorityQueue huffmanPriorityQueue;
internal void Build(string input)
{
dictFrequencies = input.GroupBy(x => x).ToDictionary(k => k.Key, v => v.Count());
huffmanPriorityQueue = new HuffmanPriorityQueue(dictFrequencies.Count);
foreach (var item in dictFrequencies)
{
huffmanPriorityQueue.Push(new HuffmanTreeNode { Symbol = item.Key, Frequency = item.Value, Left = null, Right = null });
}
while(huffmanPriorityQueue.Count() >= 2)
{
HuffmanTreeNode leftNode = huffmanPriorityQueue.Pop();
HuffmanTreeNode rightNode = huffmanPriorityQueue.Pop();
HuffmanTreeNode parentNode = new HuffmanTreeNode
{
Frequency = leftNode.Frequency + rightNode.Frequency,
Symbol = '*',
Left = leftNode,
Right = rightNode
};
this.rootNode = parentNode;
huffmanPriorityQueue.Push(parentNode);
}
}
internal class HuffmanPriorityQueue
{
HuffmanTreeNode[] items;
int top = 0;
public HuffmanPriorityQueue(int size)
{
items = new HuffmanTreeNode[size + 1];
}
internal void Push(HuffmanTreeNode node)
{
int i = ++top;
while (i > 1 && items[i / 2].Frequency > node.Frequency)
{
items[i] = items[i / 2];
i = i / 2;
}
items[i] = node;
}
internal HuffmanTreeNode Pop()
{
HuffmanTreeNode data = items[1];
items[1] = items[top];
items[top--] = null;
int i = 1;
int j = i * 2;
while (j <= top)
{
if ((j + 1) <= top && items[j + 1].Frequency < items[j].Frequency)
{
j += 1;
}
if (items[j].Frequency < items[i].Frequency)
{
HuffmanTreeNode temp = items[j];
items[j] = items[i];
items[i] = temp;
i = j;
j = i * 2;
}
else
break;
}
return data;
}
internal int Count()
{
return top;
}
}
internal class HuffmanTreeNode
{
internal char Symbol { get; set; }
internal int Frequency { get; set; }
internal HuffmanTreeNode Right { get; set; }
internal HuffmanTreeNode Left { get; set; }
}
添加回答
舉報
0/150
提交
取消