Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 1 - Chương 5: Phương pháp tham lam

là 6 + 2 = 8 và tệp 
 có 8 phần tử. 
Kết quả thu được tệp . Tổng số thao tác ghi trong cả hai bước trên sẽ là: 
6 + 8 = 14. 
 Tổng quát, với ba tệp a, b và c được trộn theo quy trình: 
(a  b)  c 
ta dễ dàng tính được tổng số thao tác ghi tệp cho quy trình trên là 
(| a | + | b |) + (| a | + | b |) + c = 2(| a | + | b |) + c. 
Bảng dưới đây tính toán cho ba phương án để phát hiện ra phương án tối ưu. 
Sáng tạo trong Thuật toán và Lập trình Tập I 
156 
Phương án Quy trình thực hiện Tổng số thao tác ghi tệp 
1 (  )   2(5 + 1) + 2 = 2.6 + 2 = 14 
2 (  )   2(5 + 2) + 1 = 2.7 + 1 = 15 
3 (  )   2(1 + 2) + 5 = 2.3 + 5= 11 
(phương án tối ưu) 
Khảo sát các quy trình trộn ba tệp 
s[1..3] = (5, 1, 2) 
Thuật toán tham lam khi đó sẽ như sau: 
Thuật toán Huffman 
Lặp (đến khi chỉ còn một tệp duy nhất) 
 Lấy hai tệp u và v có số phần tử nhỏ nhất. 
 Trộn u  v  h. Ta có | h | = | u | + | |v |. 
 Loại bỏ u và v khỏi danh sách các tệp cần xử lí. 
 Kết nạp h vào danh sách các tệp cần xử lí 
xong lặp 
Với n tệp ban đầu, dễ thấy rằng mỗi lần lặp ta loại bỏ được hai tệp (u và v có số 
phần tử min) và thêm một tệp (h) tức là mỗi lần lặp ta loại bỏ được một tệp, do đó số 
lần lặp sẽ là n – 1. 
Thuật toán trên mang tên nhà toán học Mĩ Huffman là người đầu tiên đề xuất. 
Ta minh hoạ thuật toán trên với dữ liệu vào như sau: 
s[1..5] = (10, 5, 4, 4, 3). 
Ý nghĩa: Trộn 5 tệp sắp tăng với số phần tử lần lượt là 10, 5, 4, 4 và 3 để thu được 
một tệp sắp tăng duy nhất. 
Lần 
lặp 
Danh sách các tệp 
cần xử lí 
Hai tệp có số 
phần tử min 
Trộn Số thao 
tác 
ghi tệp 
1 (:10,:5,:4,:4,:3) :3 , :4      7 
2 (:10,:5,:4,:7) :5 , :4      9 
3 (:10,:7, : 9) :7 , :9      16 
4 (:10,: 16) :10 , :16      26 
Kết 
quả 
(: 26) 58 
Minh hoạ thuật toán Huffman với dữ liệu vào 
(:10,:5,:4,:4,:3) 
Vì n = 5 nên số lần lặp sẽ là n – 1 = 4. Sau 4 lần lặp ta thu được tệp mã số 9 với 26 
phần tử. Để tính tổng số thao tác ghi ta chỉ cần lấy tổng số phần tử của các tệp tham gia 
trong mỗi lần trộn hai tệp. Tổng đó là: 
tt = (3 + 4) + (5 + 4) + (7 + 9) + (10 + 16) = 7 + 9 + 16 + 26 = 58. 
Sáng tạo trong Thuật toán và Lập trình Tập I 
157 
Ta chọn phương án cài đặt sau đây cho thuật toán Huffman. Phương án này tỏ ra 
tiện lợi trong nhiều ứng dụng. Lợi thế của nó là không xoá đi các đối tượng (tệp) đã xử 
lí mà chỉ đánh dấu chúng để khi cần có thể khôi phục lại và giải trình kết quả. 
Cụ thể là ta sẽ xây dựng một cây nhị phân gồm 2n – 1 đỉnh và gọi là cây Huffman 
như sau. 
Các đỉnh được mã số từ 1..2n – 1. Mỗi đỉnh nhận một giá trị nguyên dương gọi là 
trọng số của đỉnh đó. 
Trên hình vẽ, đỉnh được thể hiện trong hình tròn, cạnh đó là giá trị của trọng số. 
Trong bài toán trộn tệp này mã số của đỉnh chính là mã số của tệp, trọng số của đỉnh 
chính là số phần tử có trong tệp tương ứng. 
Thuật toán tạo cây Huffman 
Khởi tạo: n đỉnh rời nhau 1..n có trọng số s(1),..., s(n). 
h:= n; 
Lặp n – 1 lần 
 Lấy hai đỉnh u và v có s(u) và s(v) min. 
 Đánh dấu u và v là đã xử lí. 
 h:= h + 1 
 Tạo đỉnh mới h trỏ đến u và v và s(h) = s(u) + s(v). 
xong lặp 
Để tổ chức dữ liệu cho cây Huffman chúng ta dùng ba mảng nguyên s, t và p kích 
thước 2n – 1 phần tử. Với mỗi đỉnh i, s[h] cho biết trọng số của đỉnh h, t[h] trỏ đến con trái 
của đỉnh h, p[h] trỏ đến con phải của đỉnh h. Hai con trái t[h] và phải p[h] chính là hai đỉnh 
đạt trọng số min trong mỗi lần lặp, h chính là đỉnh mới được tạo lập từ hai đỉnh có trọng số 
min. Ngoài ra ta dùng một mảng nguyên d để đánh dấu các đỉnh đã xử lí, d[i] = 0 cho biết 
đỉnh i chưa được xử lí, d[i] = 1 cho biết đỉnh i đã xử lí. Các đỉnh mới được tạo lập và thêm 
vào cây lần lượt nhận mã số là n + 1, n + 2,…, 2n – 1, do đó đỉnh cuối cùng sẽ có mã số là 
h = 2n – 1. Thủ tục tạo cây Huffman h khi đó sẽ như sau: 

3 
 
4 
 
4 
 
7 

5 
 
9 
 
16 
 
10 
 Cây Huffman h xây dựng từ 5 nút ban đầu 
s[1..5] = (10,5,4,4,3) 
h =  
d = 7 + 9 + 16 + 26 = 58 
 
26 
Sáng tạo trong Thuật toán và Lập trình Tập I 
158 
{----------------------------- 
 Tao cay Huffman h = 2n-1 
 tu cac trong so s[1..n] 
-----------------------------} 
procedure Huffman; 
var i,u,v: integer; 
begin 
fillchar(d,sizeof(d),0); 
fillchar(t,sizeof(t),0); 
fillchar(p,sizeof(p),0); 
h := n; tt := 0; {tong trong so} 
for i := 1 to n-1 do 
begin 
 min2(u,v); {u,v dat trong so min } 
 h := h+1; {ma so cua dinh moi} 
 s[h] := s[u]+s[v]; {trong so cua dinh moi } 
 tt := tt+s[h]; {tong trog so } 
 t[h] := u; {tro toi con trai } 
 p[h] := v; {tro toi con phai } 
end; 
end; 
Thủ tục min2(u,v) tìm trong số các đỉnh chưa xử lí hai đỉnh u và v đạt trọng số 
min. Thủ tục này gọi hai lần hàm min1, mỗi lần tìm một đỉnh đạt trọng số min trong 
số các đỉnh chưa xử lí và đánh dấu luôn đỉnh tìm được (là đã xử lí). 
{-------------------------------- 
 Tim trong so cac dinh chua xu li 
 hai dinh u va v dat trong so min. 
----------------------------------} 
procedure min2(var u,v: integer); 
begin 
 u := min1; v := min1; 
end; 
{-------------------------------- 
 Tim trong so cac dinh chua xu li 
 mot dinh dat trong so min 
 va danh dau dinh tim duoc. 
----------------------------------} 
function min1: integer; 
 var i, imin, vmin: integer; 
begin 
 vmin := MaxInt; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
159 
 for i := 1 to h do 
 if d[i]=0 then {dinh i chua xu li } 
 if s[i] < vmin then 
 begin 
 vmin := s[i]; imin := i; 
 end; 
 d[imin] := 1; min1 := imin; 
end; 
Sau khi tạo xong cây Huffman, để ghi kết quả, ta chỉ cần duyệt các đỉnh được tạo 
mới, tức là các đỉnh có mã số từ n + 1 đến h = 2n – 1 để lấy hai con trái và phải của 
mỗi đỉnh. 
{--------------------------------- 
Duyet cac dinh tu n+1 den 2n-1, 
ghi thong tin vao tep. 
----------------------------------} 
procedure Ghi; 
var i: integer; 
begin 
 assign(g,gn); 
 rewrite(g); 
 writeln(g,n-1); 
 for i := n+1 to h do 
 writeln(g,t[i],BL,p[i],BL,i); 
 writeln(g,tt); 
 close(g); 
end; 
(* Pascal *) 
(*----------------------------------- 
 Tron nhieu tep 
------------------------------------*) 
uses crt; 
const 
fn = 'MF.INP'; 
gn = 'MF.OUT'; 
MN = 200; 
BL = #32; {Dau cach} 
NL = #13#10; {xuong dong} 
type 
 MI1 = array[0..MN] of integer; 
 MB1 = array[0..MN] of byte; 
var 
 s,t,p: MI1; 
 {s[i] - so phan tu trong tep i} 
 {t[i] - tro trai} 
 {p[i] - tro phai i} 
Sáng tạo trong Thuật toán và Lập trình Tập I 
160 
 d: MB1; {danh dau tep da xu li} 
 n: integer; {so luong tep ban dau} 
 h: integer; {cay Huffman} 
 f,g: text; 
 tt: longint; 
procedure Doc; 
var i: integer; 
begin 
 assign(f,fn); reset(f); read(f,n); 
 for i := 1 to n do read(f,s[i]); 
 close(f); 
end; 
{-------------------------------- 
Tim trong so cac dinh chua xu li 
mot dinh dat trong so min 
va danh dau dinh tim duoc. 
----------------------------------} 
function min1: integer; tự viết 
{-------------------------------- 
Tim trong so cac dinh chua xu li 
hai dinh u va v dat 
trong so min, U < v. 
----------------------------------} 
procedure min2(var u,v: integer); tự viết 
{----------------------------- 
 Tao cay Huffman h = 2n-1 
 tu cac trong so s[1..n] 
-----------------------------} 
procedure Huffman; tự viết 
{------------------------------ 
Duyet cac dinh tu n+1 den 2n-1, 
ghi thong tin vao tep. 
-------------------------------} 
procedure Ghi; tự viết 
BEGIN 
 Doc; Huffman; Ghi; 
END. 
// C# 
using System; 
using System.IO; 
namespace SangTao1 
{ 
 /*---------------------------- 
 * Cay Huffman 
 * Tron n file sap tang 
 * --------------------------*/ 
Sáng tạo trong Thuật toán và Lập trình Tập I 
161 
 class HuffmanTree 
 { 
 static string fn = "MF.inp"; // file ket qua 
 static string gn = "MF.out"; // file ket qua 
 static int[] t; // tro trai 
 static int[] p; // tro phai 
 static int[] v; // trong so dinh 
 static int[] d; // danh dau dinh da xu ly 
 static int n = 0; // so phan tu 
 static int n2; // n2 = 2*n 
 static int h = 0; // Goc cua cay Huffman 
 static int tt = 0; // tong trong so 
 static void Main() 
 { 
 Doc(); Huffman();Ghi(); Test(); 
 Console.WriteLine("\n Fini"); 
 Console.ReadLine(); 
 } // Main 
 static void Ghi() 
 { 
 StreamWriter f = File.CreateText(gn); 
 for (int i = n + 1; i <= h; ++i) 
 f.WriteLine(t[i] + " " + p[i] + " " + i); 
 f.WriteLine(tt); 
 f.Close(); 
 } 
 static void Huffman() 
 { 
 h = n; // goc cay Huffman 
 tt = 0; // tong trong so 
 int m1 = 0, m2 = 0; 
 int x; 
 for (int i = 1; i < n; ++i) 
 { 
 m1 = MinV(); m2 = MinV(); 
 if (m1 > m2) 
 {x = m1; m1 = m2; m2 = x;} 
 // m1 < m2 
 ++h; // them dinh moi 
 v[h] = v[m1] + v[m2]; 
 t[h] = m1; // tro trai 
 p[h] = m2; // tro phai 
 tt += v[h]; 
 } 
 } 
 // Tim dinh chua xu ly co trong so min 
 static int MinV() 
 { 
 int imin = 0; 
 for (int i = 1; i <= h; ++i) 
 if (d[i] == 0) // dinh i chua x li 
 if (v[i] < v[imin]) imin = i; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
162 
 d[imin] = 1; // danh dau dinh i 
 return imin; 
 } 
 static void Doc() 
 { 
 char[] cc = new char[] {'\n',' ','\t','\0','\r'}; 
 int [] a = 
Array.ConvertAll((File.ReadAllText(fn)).Split(cc, 
 StringSplitOptions.RemoveEmptyEntries), 
 new Converter(int.Parse)); 
 n = a[0]; n2 = 2*n; 
 v = new int[n2]; 
 t = new int[n2]; 
 p = new int[n2]; 
 d = new int[n2]; 
 v[0] = int.MaxValue; // linh canh 
 // Khoi tri cac nut cua cay 
 for (int i = 0; i < n2; ++i) 
 t[i] = p[i] = d[i] = 0; 
 for (int i = 1; i <= n; ++i) 
 v[i] = a[i]; 
 } 
 static void Print(int[] a, int n) tự viết 
 static void Test() tự viết 
 } // Huffmantree 
} // SangTao1 
Chú ý 
 Thuật ngữ tham lam không có nghĩa là lấy nhiều nhất mà chỉ là xác định một 
chiến lược xử lí dữ liệu sao cho có hiệu quả nhất.