hanhthien2
New Member
2. Giải thuật
a. Phát biểu bài toán
Giả sử ta có một thông báo là một chuỗi các ký tự, trong đó mỗi ký tự xuất hiện độc lập với cùng một xác suất tại bất kỳ vị trí nào trong thông báo. Yêu cầu đặt ra là mã hóa thông báo này thành một chuỗi các ký tự 0, 1.
b. Phân tích bài toán
Cho trước một tập hợp các ký tự: c1, c2, ..., cn mà xác xuất xuất hiện trong thông báo lần lượt là w1, w2, ..., wn.
Ta sẽ mã hóa mỗi ký tự trong chuỗi thông báo vừa cho, sao cho:
• Không có ký tự nào được mã hóa thành chuỗi là tiền tố của chuỗi mã hóa ký tự
khác (tính chất này được gọi là tính chất tiền tố).
• Ðộ dài của bộ mã là ngắn nhất.
3. Thiết kế thuật toán
Input: tập hợp các ký tự: c1, c2, ..., cn∈C và w1, w2, ..., wn.
Output: mã nhị phân của thông báo C
Mô tả:
Bước 1: đếm số lần xuất hiện của mỗi kí tự trong tập tin sẽ được mã hoá.
Bước 2: tiếp theo là xây dựng một cây nhị phân với các tần số được chứa trong các
nút. Hai nút có tấn số bé nhất được tìm thấy và một nút mới được tạo ra với hai nút con là
các nút đó với giá trị tần số của nút mới bằng tổng tần suất của hai nút con. Tiếp theo hai
nút mới với tần số nhỏ nhất lại được tìm thấy và một nút mới nữa lại được tao ra theo
cách trên.
Lặp lại như vậy cho đến khi tất cả các nút được tổ hợp thành một cây duy nhất.
Cài đặt chương trình:
program huffman; uses crt;
const max=255;
type str=string[1];
btree=^node;
node= record
info:longint;
ch:str;
left,right:btree;
end;
mang=array[0..max] of btree;
maso=array[1..max] of '0'..'1'; var n:-1..max;
c:maso; a:mang;
freq:array[0..max] of longint;
codech:array[0..max] of string[16];
f:text;
procedure deletetree(var t:btree);
begin
if t<> nil then
begin
deletetree(t^.left);
deletetree(t^.right);
dispose(t);
end;
end;
function extract_min(q:mang):btree;
begin
extract_min:=q[n];
n:=n-1;
end;
procedure insertq(var q:mang;z:btree);
var d,g,c:-1..max;
stop:boolean;
i:byte;
begin
if q[0]=nil then q[0]:=z
else
begin
d:=0; c:=n; stop:=false; while not(stop) do
begin
g:=(d+c) div 2;
if (q[g]^.info>z^.info) then
d:=g+1
else
c:=g-1;
if (d>=c) then
stop:=true;
end;
for i:=n downto c do
q[i+1]:=q;
q[c]:=z;
end;
n:=n+1;
end;
procedure assigncode(var t:btree;k:byte);
var i:byte;
begin
if (t^.left=nil) and (t^.right=nil) then
begin
write(f,t^.ch,':');
for i:=1 to k do
begin
write(f,c);
codech[ord(t^.ch[1])]:=codech[ord(t^.ch[1])]+c;
end;
writeln(f);
end
else
begin
inc(k);
c[k]:='0';
assigncode(t^.left,k);
c[k]:='1';
assigncode(t^.right,k);
end;
end;
procedure createarr;
var i:byte;z:btree;
begin
n:=-1;
for i:=0 to max do
if (freq<>0) then
begin
new(z);
z^.info:=freq;
z^.ch:=chr(i);
insertq(a,z);
end;
end;
procedure createHuffmancode;
var z:btree; i:byte;
begin
f or i:=1 to n - 1 do
begin
new(z);
z^.left:=EXTRACT_MIN(a);
z^.right:=EXTRACT_MIN(a);
z^.info:=z^.left^.info + z^.right^.info; INSERTq(a,z);
end;
end;
procedure count;
var f1:text; i:byte; st:string;
begin
assign(f1,'vanban.txt'); reset(f1);
for i:=0 to max do
freq:=0;
while (not eof(f1)) do
begin
readln(f1,st);
for i:=1 to length(st) do
inc(freq[ord(st)]);
end;
close(f1);
end;
procedure inkq1;
begin
assign(f,'cayhman.txt'); rewrite(f);
assigncode(a[0],0);
close(f)
end;
procedure inkq2;
var f1,f2:text; st1:string; i,j:byte;
st2:string[16];
begin
assign(f1,'vanban.txt'); reset(f1);
assign(f2,'mahoa.txt'); rewrite(f2);
while (not eof(f1)) do
begin
read(f1,st1);
for i:=1 to length(st1) do
begin
st2:=codech[ord(st1)]; for j:=1 to length(st2) do
write(f2,st2[j]);
end;
end;
close(f1);
close(f2);
end;
BEGIN
clrscr;
{đếm tần suất các kí tự}
count;
{tạo hàng đợi cho các ký tự phụ thuộc trên tần suất dược sắp xếp không giảm dần}
createarr;
{xây dựng cây mã hóa Huffman}
createhuffmancode;
{in cây Huffman}
inkq1;
{in bảng mã hóa của thông báo}
inkq2;
write('Da xu ly xong!...');
readln;
deletetree(a[0]);
END.
a. Phát biểu bài toán
Giả sử ta có một thông báo là một chuỗi các ký tự, trong đó mỗi ký tự xuất hiện độc lập với cùng một xác suất tại bất kỳ vị trí nào trong thông báo. Yêu cầu đặt ra là mã hóa thông báo này thành một chuỗi các ký tự 0, 1.
b. Phân tích bài toán
Cho trước một tập hợp các ký tự: c1, c2, ..., cn mà xác xuất xuất hiện trong thông báo lần lượt là w1, w2, ..., wn.
Ta sẽ mã hóa mỗi ký tự trong chuỗi thông báo vừa cho, sao cho:
• Không có ký tự nào được mã hóa thành chuỗi là tiền tố của chuỗi mã hóa ký tự
khác (tính chất này được gọi là tính chất tiền tố).
• Ðộ dài của bộ mã là ngắn nhất.
3. Thiết kế thuật toán
Input: tập hợp các ký tự: c1, c2, ..., cn∈C và w1, w2, ..., wn.
Output: mã nhị phân của thông báo C
Mô tả:
Bước 1: đếm số lần xuất hiện của mỗi kí tự trong tập tin sẽ được mã hoá.
Bước 2: tiếp theo là xây dựng một cây nhị phân với các tần số được chứa trong các
nút. Hai nút có tấn số bé nhất được tìm thấy và một nút mới được tạo ra với hai nút con là
các nút đó với giá trị tần số của nút mới bằng tổng tần suất của hai nút con. Tiếp theo hai
nút mới với tần số nhỏ nhất lại được tìm thấy và một nút mới nữa lại được tao ra theo
cách trên.
Lặp lại như vậy cho đến khi tất cả các nút được tổ hợp thành một cây duy nhất.
Cài đặt chương trình:
program huffman; uses crt;
const max=255;
type str=string[1];
btree=^node;
node= record
info:longint;
ch:str;
left,right:btree;
end;
mang=array[0..max] of btree;
maso=array[1..max] of '0'..'1'; var n:-1..max;
c:maso; a:mang;
freq:array[0..max] of longint;
codech:array[0..max] of string[16];
f:text;
procedure deletetree(var t:btree);
begin
if t<> nil then
begin
deletetree(t^.left);
deletetree(t^.right);
dispose(t);
end;
end;
function extract_min(q:mang):btree;
begin
extract_min:=q[n];
n:=n-1;
end;
procedure insertq(var q:mang;z:btree);
var d,g,c:-1..max;
stop:boolean;
i:byte;
begin
if q[0]=nil then q[0]:=z
else
begin
d:=0; c:=n; stop:=false; while not(stop) do
begin
g:=(d+c) div 2;
if (q[g]^.info>z^.info) then
d:=g+1
else
c:=g-1;
if (d>=c) then
stop:=true;
end;
for i:=n downto c do
q[i+1]:=q;
q[c]:=z;
end;
n:=n+1;
end;
procedure assigncode(var t:btree;k:byte);
var i:byte;
begin
if (t^.left=nil) and (t^.right=nil) then
begin
write(f,t^.ch,':');
for i:=1 to k do
begin
write(f,c);
codech[ord(t^.ch[1])]:=codech[ord(t^.ch[1])]+c;
end;
writeln(f);
end
else
begin
inc(k);
c[k]:='0';
assigncode(t^.left,k);
c[k]:='1';
assigncode(t^.right,k);
end;
end;
procedure createarr;
var i:byte;z:btree;
begin
n:=-1;
for i:=0 to max do
if (freq<>0) then
begin
new(z);
z^.info:=freq;
z^.ch:=chr(i);
insertq(a,z);
end;
end;
procedure createHuffmancode;
var z:btree; i:byte;
begin
f or i:=1 to n - 1 do
begin
new(z);
z^.left:=EXTRACT_MIN(a);
z^.right:=EXTRACT_MIN(a);
z^.info:=z^.left^.info + z^.right^.info; INSERTq(a,z);
end;
end;
procedure count;
var f1:text; i:byte; st:string;
begin
assign(f1,'vanban.txt'); reset(f1);
for i:=0 to max do
freq:=0;
while (not eof(f1)) do
begin
readln(f1,st);
for i:=1 to length(st) do
inc(freq[ord(st)]);
end;
close(f1);
end;
procedure inkq1;
begin
assign(f,'cayhman.txt'); rewrite(f);
assigncode(a[0],0);
close(f)
end;
procedure inkq2;
var f1,f2:text; st1:string; i,j:byte;
st2:string[16];
begin
assign(f1,'vanban.txt'); reset(f1);
assign(f2,'mahoa.txt'); rewrite(f2);
while (not eof(f1)) do
begin
read(f1,st1);
for i:=1 to length(st1) do
begin
st2:=codech[ord(st1)]; for j:=1 to length(st2) do
write(f2,st2[j]);
end;
end;
close(f1);
close(f2);
end;
BEGIN
clrscr;
{đếm tần suất các kí tự}
count;
{tạo hàng đợi cho các ký tự phụ thuộc trên tần suất dược sắp xếp không giảm dần}
createarr;
{xây dựng cây mã hóa Huffman}
createhuffmancode;
{in cây Huffman}
inkq1;
{in bảng mã hóa của thông báo}
inkq2;
write('Da xu ly xong!...');
readln;
deletetree(a[0]);
END.