huffman 인코딩 c# 구현
21562 단어 Huffman
1 using System;
2 using System.Collections.Generic;
3 using System.ComponentModel;
4 using System.Data;
5 using System.Drawing;
6 using System.Text;
7 using System.Windows.Forms;
8 using System.Collections.Specialized;
9 namespace HuffmanCode
10 {
11 public partial class Form1 : Form
12 {
13 class Node //
14 {
15 public char code;
16 public uint prioirry; //
17 public Node lchild; //
18 public Node rchild; //
19 }
20 public Form1()
21 {
22 InitializeComponent();
23
24 }
25
26 private Dictionary<char, string> dictcode = new Dictionary<char, string>();
27 private Node huffTree;
28
29 private int comparisonNode(Node n1, Node n2)
30 {
31 return (int)(n1.prioirry - n2.prioirry);
32 }
33
34 private string encode(string str)
35 {
36 dictcode.Clear();
37 huffTree = null;
38 if (string.IsNullOrEmpty(str))
39 {
40 return "";
41 }
42 Dictionary<char, uint> priorityQueue = new Dictionary<char, uint>();
43
44 for (int i = 0; i < str.Length; i++)
45 {
46 if (priorityQueue.ContainsKey(str[i]))
47 {
48 priorityQueue[str[i]]++;
49 }
50 else
51 {
52 priorityQueue.Add(str[i], 1);
53 }
54 }
55 List<Node> listpc = new List<Node>();
56 foreach (var item in priorityQueue)
57 {
58 listpc.Add(new Node() { prioirry = item.Value, lchild = null, rchild = null, code = item.Key });
59 }
60
61 listpc.Sort(comparisonNode);
62
63 while (listpc.Count > 1)
64 {
65 Node n = new Node();
66 n.prioirry = listpc[0].prioirry + listpc[1].prioirry;
67 n.lchild = listpc[0];
68 n.rchild = listpc[1];
69 listpc.RemoveAt(0);
70 listpc.RemoveAt(0);
71 int index = -1;
72 for (int i = 0; i < listpc.Count; i++)
73 {
74 if (n.prioirry <= listpc[i].prioirry)
75 {
76 index = i;
77 break;
78 }
79 }
80 if (index == -1) { index = listpc.Count; }
81 listpc.Insert(index, n);
82 }
83 string encodestr = "";
84 viewTree(listpc[0], "");
85 huffTree = listpc[0];
86 for (int i = 0; i < str.Length; i++)
87 {
88 encodestr += dictcode[str[i]];
89 }
90 return encodestr;
91 }
92
93
94 private void viewTree(Node n, string v)
95 {
96 if (n.code != '\0')
97 {
98 dictcode.Add(n.code, v);
99 }
100 else
101 {
102 if (n.lchild != null)
103 {
104 string vl = v + "0";
105 viewTree(n.lchild, vl);
106 }
107 if (n.rchild != null)
108 {
109 string vr = v + "1";
110 viewTree(n.rchild, vr);
111 }
112 }
113 }
114
115 private string decode(string str)
116 {
117 Node root = huffTree;
118 string result = "";
119 for (int i = 0; i < str.Length; i++)
120 {
121 if (root.code != '\0')
122 {
123 result += root.code.ToString();
124 root = huffTree;
125 }
126
127 if (str[i] == '0')
128 {
129 root = root.lchild;
130 }
131 else
132 {
133 root = root.rchild;
134 }
135 }
136 if (root.code != '\0')
137 {
138 result += root.code.ToString();
139 }
140 return result;
141 }
142
143 private void button1_Click(object sender, EventArgs e)
144 {
145 textBox2.Text = encode(textBox1.Text);
146 }
147
148 private void button2_Click(object sender, EventArgs e)
149 {
150 textBox3.Text = decode(textBox2.Text);
151 }
152 }
153 }