Trộn nhiều tệp

Bài 5.6. Trộn nhiều tệp

           Cho n tệp văn bản mã số từ 1 đến n. Tệp thứ i chứa d_i  phần tử được sắp tăng. Hãy lập một lịch chỉ ra trình tự trộn mỗi lần hai tệp để cuối cùng thu được một tệp sắp tăng duy nhất với tổng số lần ghi dữ liệu vào tệp là nhỏ nhất. Biết rằng thủ tục trộn hai tệp chỉ có thể đọc tuần tự hoặc ghi tuần tự mỗi lần một phần tử.

               Dữ liệu vào: Tệp văn bản MF.INP.

-          Dòng đầu tiên là số lượng n các tệp chứa dữ liệu sắp tăng.

-          Tiếp đến là n số tự nhiên d_i, i = 1..n cho biết số phần tử trong tệp thứ i. Mỗi số ghi trên một dòng.

               Dữ liệu ra: Tệp văn bản MF.OUT.

-          Dòng đầu tiên: m là số lần thực hiện trộn hai tệp.

-          Tiếp đến là m dòng, mỗi dòng chứa ba số tự nhiên i, j và k cho biết cần lấy tệp i trộn với tệp j và ghi kết quả vào tệp k. Các số trên cùng một dòng cách nhau qua dấu cách.

               Tệp chứa kết quả trung gian phải có mã số khác với mã số của các tệp tạo lập trước đó.    

Thí dụ:

MF.INP	MF.OUT	Ý nghĩa: Cho 5 tệp sắp tăng với số phần tử lần lượt là 10, 5, 4, 4, 3. Cần thực hiện 4 lần trộn, mỗi lần 2 tệp. Lần thứ nhất: trộn tệp 5 với tệp 3 ghi vào tệp 6. Lần thứ hai: trộn tệp 4 với tệp 2 ghi vào tệp 7. Lần thứ ba: trộn tệp 6 với tệp 7 ghi vào tệp 8. Lần thứ tư: trộn tệp 1 với tệp 8 ghi vào tệp 9. Tổng số lần ghi là 58.
5 10 5 4 4 3	4 5 3 6 4 2 7 6 7 8 1 8 9 58

Thuật toán

Trước hết để ý rằng nếu trộn tệp sắp tăng f gồm n phần tử với tệp sắp tăng g gồm m phần tử để thu được tệp sắp tăng h thì đối với các phần tử trong hai tệp nguồn ta chỉ cần thực hiện thao tác đọc, còn thao tác ghi chỉ thực hiện đối với tệp đích h.  Kí hiệu |f| là số phần tử trong tệp f, ta có:

| f | = n, | g | = m

 Do tổng số các phần tử của hai tệp là m + n nên số phần tử trong tệp đích h sẽ là

| h | = n + m =  | f | + | g |

và do đó số lần ghi (tối thiểu) các phần tử vào tệp h sẽ là n + m.

Ta có nhận xét sau: Muốn xây dựng một quy trình trộn mỗi lần hai tệp cho nhiều tệp ban đầu với yêu cầu tổng số thao tác ghi tệp là tối thiểu thì ta phải tạo ra các tệp trung gian càng ít phần tử càng tốt.

Ta dùng kí hiệu f Å g ® h với ý nghĩa là trộn hai tệp nguồn f và g để thu được tệp h. Ta có

Nếu f  Å g ® h thì | h | =  |f | + | g |

Để ý rằng trộn tệp f với tệp g hay trộn tệp g với tệp f thì số thao tác ghi tệp như nhau và cùng bằng | f | + | g |. Giả sử ta có ba tệp với số phần tử tương ứng là

s[1..3] = (5, 1, 2).

Giả sử ta thực hiện quy trình (j Å k) Å l như sau:

Bước 1: Trộn tệp j với tệp k ghi tạm vào tệp m. Số thao tác ghi sẽ là (5 + 1) = 6 và tệp m có 6 phần tử.

Bước 2: Trộn tệp m với tệp l ghi vào tệp n. Số thao tác ghi sẽ là 6 + 2 = 8 và tệp n có 8 phần tử.

Kết quả thu được tệp n. 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.

Phương án	Quy trình thực hiện	Tổng số thao tác ghi tệp
1	(j Å k) Å l	2(5 + 1) + 2 = 2.6 + 2 = 14
2	(j Å l) Å k	2(5 + 2) + 1 = 2.7 + 1 = 15
3	(k  Å l) Å j	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) s         Lấy hai tệp u và v có số phần tử nhỏ nhất. s         Trộn u Å v ® h. Ta có | h | = | u | + | |v |. s         Loại bỏ u và v khỏi danh sách các tệp cần xử lí. s         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	(j:10,k:5,l:4,m:4,n:3)	n:3 , l:4	n Å l ® o	7
2	(j:10,k:5,m:4,o:7)	k:5 , m:4	k Å m ® p	9
3	(j:10,o:7, p: 9)	o:7 , p:9	o Å p ® q	16
4	(j:10,q: 16)	j:10 , q:16	j Å q ® r	26
Kết quả	(r: 26)			58
Minh hoạ thuật toán Huffman với dữ liệu vào (j:10,k:5,l:4,m:4,n: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.

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 s         Lấy hai đỉnh  u và v có s(u) và s(v) min. s         Đánh dấu u và v là đã xử lí. s         h:= h + 1 s         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:

 

{-----------------------------

   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;

  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}

  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.

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.