[Kinh nghiệm]Làm việc với mã Huffman

Admin · 1 [Kinh nghiệm]Làm việc với mã Huffman Sat Jun 04, 2011 10:04 pm

Admin

Quản trị viên

Bài gửi : 785
Điểm : 14388
Được cảm ơn : 10454
Ngày gia nhập : 11/05/2011

Mã Huffman

1. Cây Huffman
- Lá là các ký tự
- Mỗi nút lưu:
                    + Ký tự
                    + Số lần xuất hiện
- Đường đi từ gốc đến lá là mã của ký tự.
2. Giải thuật mã hoá văn bản sử dụng cây huffman
- Đạt n ký tự của văn bản vào n nút lá.
- Tạo danh sách gồm n ký tự và số lần xuất hiện.
- Lặp lại quá trình sau, cho đến khi trong danh sách chỉ còn 1 phần tử.
                    + Chọn 2 phần tử có tần số (số lần) xuất hiện ít nhất.
                    + tạo nút mới:
                                        * Số lần xuất hiện bằng tổng số lần xuất hiện 2 phàn tử đã chọn.
                                        * Con trái: Là nút ứng với phần tử có số lần xuất hiện nhỏ
                                        * Con phải: Là nút ứng với phần tử có số lần xuất hiện lớn
                    + Thay 2 phần tử đã chọn trong danh sách bằng 1 phần tử có số lần xuất hiện bằng tổng.
- Xác định đường đi từ gốc tới lá biểu diễn nó bằng xâu nhị phân theo quy tắc:
                              + Sang trái: bit 0
                              + sang phải: bit 1
Xâu nhị phân thu được chính là mã tương ứng với ký tự ở lá đó.
- Tính tổng số bít cần để mã hoá văn bản
[You must be registered and logged in to see this image.] số bit mã hoá x số lần xuất hiện

Admin · 2 Các đề thi liên quan đến mã Huffman Sat Jun 18, 2011 9:43 am

Admin

Quản trị viên

Bài gửi : 785
Điểm : 14388
Được cảm ơn : 10454
Ngày gia nhập : 11/05/2011

Đây là các câu trong đề thi liên quan đến mã này:

Câu 2. Đề thi năm 2009
a. Cho cây nhị phân T. Viết hàm tính chiều cao của cây.
b. Văn bản T chỉ gồm các ký tự a, b, c, d, e, f, g, h với số lần xuất hiện như sau:

Ký tự	a	b	c	d	e	f	g	h
Số lần xuất hiện	43	28	21	12	20	18	16	39

Xây dựng bộ mã Huffman tối ưu và vẽ cây nhị phân Huffman tương ứng. Cho biết số bit của văn bản mã hoá.

Câu 2. Đề thi năm 2008
a. Danh sách D lưu trữ các ký tự và tần suất xuất hiện của chúng trong văn bản T có n ký tự:
List = ^Words;
Words = Record;
w: Char;
t: Integer;
End;
D[1..n] of List;
Viết giải thuật xây dựng cây nhị phân Huffman mã hoá văn bản T.

b. Văn bản T chỉ gồm các ký tự a, b, c, d, e, f, g, h với số lần xuất hiện như sau:

Ký tự	a	b	c	d	e	f	g	h
Số lần xuất hiện	30	20	20	13	7	5	3	2

Xây dựng bộ mã Huffman tối ưu và vẽ cây nhị phân Huffman tương ứng. Cho biết số bit của văn bản mã hoá và hiệu suất mã hoá.

Khách viếng thăm có thể giải và gửi bài để chúng ta xây dựng một đáp án chuẩn cho câu hỏi dạng này.

Admin

Admin

Quản trị viên

Bài gửi : 785
Điểm : 14388
Được cảm ơn : 10454
Ngày gia nhập : 11/05/2011

Giải đề 2008:
1) Đầu tiên phải sắp xếp lại theo thứ tự giảm dần về tần suất, nhưng ở đây đã sắp xếp rồi, chỉ việc viết lại, nếu đề mà chưa sắp xếp, Khách viếng thăm nhớ sắp xếp lại đó nha:
[You must be registered and logged in to see this image.]

b₁) Ta thấy g và h là 2 ký tự có tần suất ít nhất nên:
[You must be registered and logged in to see this image.]
b₂) Làm tiếp f và M₁ do lớn hơn e nên xếp lên trên:
[You must be registered and logged in to see this image.]
b₃)Làm tiếp cứ theo nguyên tắc tần suất lớn hơn xếp lên trên để được:
[You must be registered and logged in to see this image.]
b₄)Tiếp tục:
[You must be registered and logged in to see this image.]
b₅)Tiếp tục:
[You must be registered and logged in to see this image.]
b₆)Tiếp tục:
[You must be registered and logged in to see this image.]
b₇)Tiếp tục:
[You must be registered and logged in to see this image.]

Điền các giá trị theo cây, nhánh bên trái là 0, nhánh bên phải là 1:
[You must be registered and logged in to see this image.]
Ta có bảng mã hóa Huffman, lấy từ gốc xuống:
a = 00
b = 10
c = 11
d = 011
e = 0101
f = 01000
g = 010010
h = 010011

Số bit mã hóa văn bản là:
2.30 + 2.20 + 2.20 + 3.13 + 4.7 + 5.5 + 6.3 + 6.2
= 60 + 40 + 40 + 39 + 28 + 25 + 18 + 12 = 262
Hiệu suất mã hóa văn bản là:
[You must be registered and logged in to see this image.]

= 0,3275

Admin · 4 [Kinh nghiệm] Thu Jul 07, 2011 9:30 am

Admin

Quản trị viên

Bài gửi : 785
Điểm : 14388
Được cảm ơn : 10454
Ngày gia nhập : 11/05/2011

Tổng hợp thêm những dạng câu hỏi trong đề thi.
Cho văn bản T gồm n ký tự lưu trữ bằng mảng sau:
KT = ARRAY (1..n) of record
                    c: ký tự;
                    s: số lần xuất hiện;
                              end;
a) Xây dựng cấu trúc cây nhị phân Huffman
b) Viết giải thuật mã hóa cây Huffman để mã hóa văn bản trên

Giải
a)

Cấu trúc cây nhị phân Huffman:

b)

Giải thuật xây dựng cây nhị phân Huffman để mã hóa văn bản trên:

sangminh2009 · 5 Re: [Kinh nghiệm]Làm việc với mã Huffman Fri Jul 15, 2011 5:05 pm

sangminh2009

Thành viên chưa phát huy chia sẻ
Thành viên chưa phát huy chia sẻ

Bài gửi : 5
Điểm : 61
Được cảm ơn : 20
Ngày gia nhập : 08/07/2011

em có ý kiến. cách xây dựng mã huffman nhu thế này có đúng như trong sách của thầy tĩnh không?
em đọc ví dụ của thầy và làm theo cách này nhưng kết quả không giống nhau?
anh chị coi lại nhé.
vì em nhớ không nhầm thì có sách nào đó viết là : sắp xếp dãy ban đầu theo thứ tự giảm dần thì lại có kết quả hoàn toàn khác đó? → bạn cho rằng cách làm trên là sắp xếp tăng dần?

BanQT: Khách viếng thăm thấy ở đâu đúng hơn thì theo. Có nhiều sách ghi tên Thầy, nhưng không phải do Thầy viết, mà do học trò của Thầy viết, Thầy chỉ đứng tên. Đó là những sách tham khảo, không thông qua hội đồng, nên nhiều khi kiểm soát nội dung nhiều khi còn thiếu chặt chẽ, → khi dạy so với sách sẽ khác, như rất nhiều bài trên diễn đàn đã đề cập và giải quyết mâu thuẫn này rồi. Còn đúng hay sai thì phải hỏi người dạy, chứ những người đi học thì thấy thế là đúng. Khách viếng thăm thấy sai thì cần chỉ ra chỗ sai, các đề TEST thầy cho, chấm điểm thấy phần lớn là điểm 1, 2, 3, 4... nên bản thân nhiều member siêu sao cũng chẳng dám nói là đúng hay sai nữa, cho nên mới cần nhận xét để làm Bài chuẩn. Còn việc nói chung chung không đưa ra một căn cứ cụ thể thì đến thánh cũng chịu, huống chi là Khách viếng thăm và chúng ta.

HaiYen · 6 Re: [Kinh nghiệm]Làm việc với mã Huffman Sun Jul 17, 2011 10:56 pm

HaiYen

Thành viên cao cấp

Bài gửi : 137
Điểm : 4239
Được cảm ơn : 1440
Ngày gia nhập : 13/05/2011

Giải thuật duyệt cây Huffman để đưa ra bảng mã, thủ tục này nhiều người biết, nhưng cũng nên đưa ra làm chuẩn:
PROC Tai_Ma(P: Next; X: String)
          IF P^.L = Ø THEN OUTPUT (P^.C, X);
                    ELSE
                              Tai_Ma(P^.L, X & "0")
                              Tai_Ma(P^.R, X & "1")

abc · 7 Re: [Kinh nghiệm]Làm việc với mã Huffman Fri Jul 22, 2011 1:14 am

abc

Thành viên bắt đầu chia sẻ

Bài gửi : 32
Điểm : 182
Được cảm ơn : 30
Ngày gia nhập : 13/07/2011

+ tạo nút mới:
* Số lần xuất hiện bằng tổng số lần xuất hiện 2 phàn tử đã chọn.
* Con trái: Là nút ứng với phần tử có số lần xuất hiện nhỏ
* Con phải: Là nút ứng với phần tử có số lần xuất hiện lớn
Nhưng như lời giải trên em thấy Con trái > Con Phải mà

Mục đích của mã Huffman, vừa mã hóa, vừa giảm dung lượng. Còn việc đặt trái hay phải là do qui ước, là cách bạn mã hóa. Điều đó không ảnh hưởng đến kết quả của bạn. Đừng lo lắng nhiều quá mà quẫn trí. He he.

fitppro · 8 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Jul 25, 2011 2:51 pm

fitppro

Thành viên ít chịu khó

Bài gửi : 4
Điểm : 35
Được cảm ơn : 0
Ngày gia nhập : 22/07/2011

Mình cũng thắc mắc giống abc, ko thấy ai trả lời giúp nhỉ?

HaiYen · 9 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Jul 25, 2011 3:09 pm

HaiYen

Thành viên cao cấp

Bài gửi : 137
Điểm : 4239
Được cảm ơn : 1440
Ngày gia nhập : 13/05/2011

fitppro đã viết:Mình cũng thắc mắc giống abc, ko thấy ai trả lời giúp nhỉ?

Có lẽ bạn không đọc được bài viết ở thư mục Bài chuẩn? những bài này đã đóng dấu TEST?

TuanNghia

TuanNghia

Thành viên bắt đầu chia sẻ

Bài gửi : 10
Điểm : 115
Được cảm ơn : 19
Ngày gia nhập : 24/07/2011

Chọn nút trái hay nút phải mặc dù đưa ra các bộ mã khác nhau nhưng độ nén vẫn không đổi.

AutoAdd:
Có ai biết viết hàm tính chiều cao cậy nhị phân Huffman? Không biết có câu hỏi nào như thế không nhỉ?

[You must be registered and logged in to see this link.]

Tongmanhcuong · 11 Re: [Kinh nghiệm]Làm việc với mã Huffman Thu Aug 04, 2011 4:28 pm

Tongmanhcuong

Quản trị viên

Bài gửi : 127
Điểm : 866
Được cảm ơn : 221
Ngày gia nhập : 16/05/2011

Nếu các bạn trả lời được câu hỏi này thì vấn đề coi như được giải quyết. "Mục đích của mã Huffman để làm gì?"

Còn về tính chiều cao vấn đề đã được giải quyết trên diễn này. Mình nghĩ thời điểm này không phải đi giải quyết những vấn đề quá cơ bản.

nhattan · 12 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Nov 07, 2011 9:35 pm

nhattan

Thành viên ít chịu khó

Bài gửi : 1
Điểm : 10
Được cảm ơn : 0
Ngày gia nhập : 07/11/2011

thank nha, bài viết rất hay, dễ hiểu.

thong · 13 Re: [Kinh nghiệm]Làm việc với mã Huffman Thu Nov 10, 2011 6:02 pm

thong

Thành viên ít chịu khó

Bài gửi : 2
Điểm : 20
Được cảm ơn : 0
Ngày gia nhập : 10/11/2011

Admin hãy giải dùm bài này: bản tin cần truyền: QWERQWERQTWER.......
Tính ra:
Q=30
W=11
E=14
R=20
T=5
Y=12
U=8
a) hãy mã hóa các kí tự trên
b) Số bit trung bình trong 1 từ mã là bao nhiêu?
thank trước nha.

Ban QT: Admin vừa đi phẫu thuật, bạn đố Admin thì hãy để cho Admin khỏi đã nhé... cứ chờ đấy!...

thong · 14 Re: [Kinh nghiệm]Làm việc với mã Huffman Tue Nov 22, 2011 10:56 am

thong

Thành viên ít chịu khó

Bài gửi : 2
Điểm : 20
Được cảm ơn : 0
Ngày gia nhập : 10/11/2011

Mình giải bài này như sau, không biết đúng không. Mong các bạn góp ý.
a) ta có bảng mã hoá Huffman như sau:
Q=00
R=11
E=010
Y=100
W=101
U=0110
T=0111
số bit mã hoá văn bản: 2*30+2*20+3*14+3*12+3*11+4*8+4*5=263
b)Theo công thức Shannon
Ta tính Entropy:
H=-(0,3log2(0,3)+0,2log2(0,2)+0,14log2(0,14)+0,12log2(0,12)+0,11log2(0,11)+0,08log2(0,08)+0,05log2(0,05))
= 0,521+0,464+0,397+0,367+0,35+0,292+0,216
= 2,607bit/từ mã
*Số bit trung bình trong 1 từ mã dùng mã Huffman là:
2*0,3+2*0,2+3*0,14+3*0,12+3*0,11+4*0,08+4*0,05=2,63bit/từ mã

thvinh · 15 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Oct 22, 2012 9:36 am

thvinh

Thành viên ít chịu khó

Bài gửi : 2
Điểm : 20
Được cảm ơn : 0
Ngày gia nhập : 21/10/2012

vi du 1
0.2 0.2 0.15 0.15 0.1 0.1 0.05 0.05
vi du 2
A(0.2) B(0.2) C(0.2) D(0.2) E(0.1) F(0.1)
moi nguoi giup đỡ,có thể vẽ cây ra cho dễ hiểu ko,nhiều giá trị có giá trị bằng nhau thì góp như thế nào ,góp bên trái trước hay bên phải trước,ở giữa hay 2 biên ...

trungttnd · 16 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Oct 22, 2012 1:26 pm

trungttnd

Thành viên cao cấp

Bài gửi : 56
Điểm : 262
Được cảm ơn : 111
Ngày gia nhập : 15/07/2011

Sắp theo giá trị giảm dần từ trái qua phải, sau đó gộp từ phải sang trái. giá trị mới chèn vào theo đúng thứ tự giảm dần từ trái sang phải.

thvinh · 17 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Oct 22, 2012 5:05 pm

thvinh

Thành viên ít chịu khó

Bài gửi : 2
Điểm : 20
Được cảm ơn : 0
Ngày gia nhập : 21/10/2012

trungttnd đã viết:Sắp theo giá trị giảm dần từ trái qua phải, sau đó gộp từ phải sang trái. giá trị mới chèn vào theo đúng thứ tự giảm dần từ trái sang phải.

bạn thử làm giúp mih 2 bài kia,làm ví dụ dễ hiểu hơn mà,cảm ơn nhiều [You must be registered and logged in to see this image.]

anhnoon0410 · 18 tính không gian lưu trữ Thu Jan 17, 2013 4:23 pm

anhnoon0410

Thành viên ít chịu khó

Bài gửi : 1
Điểm : 10
Được cảm ơn : 0
Ngày gia nhập : 17/01/2013

Thực hiện việc nén dữ liệu bằng giải thuật nén Huffman tĩnh trên 1 chuỗi gồm 2 triệu ký tự A, 1
triệu ký tự B, và 1 triệu ký tự C. Hãy cho biết việc nén chuỗi đã giúp tiết kiệm được không gian
lưu trữ như thế nào trong các trường hợp:
a. Các cụm ký tự AB, AC xen kẽ nhau (ABAC..ABAC…ABAC)
b. Toàn bộ ký tự A xuất hiện liên tục rồi đến toàn bộ ký tự B rồi đến toàn bộ ký tự C.
(AA…A..ABB…B..BBCC..C..C)

phamhuynhit · 19 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon May 20, 2013 4:34 am

phamhuynhit

Thành viên chưa phát huy chia sẻ
Thành viên chưa phát huy chia sẻ

Bài gửi : 5
Điểm : 30
Được cảm ơn : 0
Ngày gia nhập : 08/05/2013

thnak admin

Minto Trầm · 20 Re: [Kinh nghiệm]Làm việc với mã Huffman Wed Sep 17, 2014 11:09 pm

Minto Trầm

Thành viên ít chịu khó

Bài gửi : 4
Điểm : 40
Được cảm ơn : 0
Ngày gia nhập : 13/09/2014

Có lẽ bạn nhầm lẫn ở chỗ nào đấy chứ mình học môn xử lý ảnh của thầy Tĩnh có học về Huffman thì kết quả sẽ tương tự như bài giải ở trên.

sangminh2009 đã viết:em có ý kiến. cách xây dựng mã huffman nhu thế này có đúng như trong sách của thầy tĩnh không?
em đọc ví dụ của thầy và làm theo cách này nhưng kết quả không giống nhau?
anh chị coi lại nhé.
vì em nhớ không nhầm thì có sách nào đó viết là : sắp xếp dãy ban đầu theo thứ tự giảm dần thì lại có kết quả hoàn toàn khác đó? → bạn cho rằng cách làm trên là sắp xếp tăng dần?

BanQT: Khách viếng thăm thấy ở đâu đúng hơn thì theo. Có nhiều sách ghi tên Thầy, nhưng không phải do Thầy viết, mà do học trò của Thầy viết, Thầy chỉ đứng tên. Đó là những sách tham khảo, không thông qua hội đồng, nên nhiều khi kiểm soát nội dung nhiều khi còn thiếu chặt chẽ, → khi dạy so với sách sẽ khác, như rất nhiều bài trên diễn đàn đã đề cập và giải quyết mâu thuẫn này rồi. Còn đúng hay sai thì phải hỏi người dạy, chứ những người đi học thì thấy thế là đúng. Khách viếng thăm thấy sai thì cần chỉ ra chỗ sai, các đề TEST thầy cho, chấm điểm thấy phần lớn là điểm 1, 2, 3, 4... nên bản thân nhiều member siêu sao cũng chẳng dám nói là đúng hay sai nữa, cho nên mới cần nhận xét để làm Bài chuẩn. Còn việc nói chung chung không đưa ra một căn cứ cụ thể thì đến thánh cũng chịu, huống chi là Khách viếng thăm và chúng ta.

lovesang · 21 Re: [Kinh nghiệm]Làm việc với mã Huffman Sat Dec 06, 2014 9:33 pm

lovesang

Thành viên ít chịu khó

Bài gửi : 1
Điểm : 10
Được cảm ơn : 0
Ngày gia nhập : 06/12/2014

Mọi người cho mình hỏi cái này với
Thực hiện việc nén dữ liệu bằng giải thuật nén Huffman tĩnh trên 1 chuỗi gồm 2 triệu ký tự A, 1
triệu ký tự B, và 1 triệu ký tự C. Hãy cho biết việc nén chuỗi đã giúp tiết kiệm được không gian
lưu trữ như thế nào trong các trường hợp:
a. Các cụm ký tự AB, AC xen kẽ nhau (ABAC..ABAC…ABAC)
b. Toàn bộ ký tự A xuất hiện liên tục rồi đến toàn bộ ký tự B rồi đến toàn bộ ký tự C.
(AA…A..ABB…B..BBCC..C..C)

Sponsored content

1 [Kinh nghiệm]Làm việc với mã Huffman Sat Jun 04, 2011 10:04 pm

Admin

2 Các đề thi liên quan đến mã Huffman Sat Jun 18, 2011 9:43 am

Admin

3 [Lời giải]Bài mẫu về cây nhị phân Huffman Tue Jul 05, 2011 8:51 am

Admin

4 [Kinh nghiệm] Thu Jul 07, 2011 9:30 am

Admin

5 Re: [Kinh nghiệm]Làm việc với mã Huffman Fri Jul 15, 2011 5:05 pm

sangminh2009

6 Re: [Kinh nghiệm]Làm việc với mã Huffman Sun Jul 17, 2011 10:56 pm

HaiYen

7 Re: [Kinh nghiệm]Làm việc với mã Huffman Fri Jul 22, 2011 1:14 am

abc

8 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Jul 25, 2011 2:51 pm

fitppro

9 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Jul 25, 2011 3:09 pm

HaiYen

10 [Ý kiến]Có ai biết viết hàm tính chiều cao cậy nhị phân Huffman Thu Aug 04, 2011 12:04 am

TuanNghia

11 Re: [Kinh nghiệm]Làm việc với mã Huffman Thu Aug 04, 2011 4:28 pm

Tongmanhcuong

12 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Nov 07, 2011 9:35 pm

nhattan

13 Re: [Kinh nghiệm]Làm việc với mã Huffman Thu Nov 10, 2011 6:02 pm

thong

14 Re: [Kinh nghiệm]Làm việc với mã Huffman Tue Nov 22, 2011 10:56 am

thong

15 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Oct 22, 2012 9:36 am

thvinh

16 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Oct 22, 2012 1:26 pm

trungttnd

17 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon Oct 22, 2012 5:05 pm

thvinh

18 tính không gian lưu trữ Thu Jan 17, 2013 4:23 pm

anhnoon0410

19 Re: [Kinh nghiệm]Làm việc với mã Huffman Mon May 20, 2013 4:34 am

phamhuynhit

20 Re: [Kinh nghiệm]Làm việc với mã Huffman Wed Sep 17, 2014 11:09 pm

Minto Trầm

21 Re: [Kinh nghiệm]Làm việc với mã Huffman Sat Dec 06, 2014 9:33 pm

lovesang

22 Re: [Kinh nghiệm]Làm việc với mã Huffman

Sponsored content