Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




    • Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội » Các môn thi đầu vào cao học » Môn CSDL và giải thuật » [Kinh nghiệm]Làm việc với mã Huffman

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    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


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.

    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 133 Vương Thừa Vũ

    [You must be registered and logged in to see this link.]
    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Đâ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.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.

    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 133 Vương Thừa Vũ

    [You must be registered and logged in to see this link.]
    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    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.]

    b1) 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.]
    b2) Làm tiếp f và M1 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.]
    b3)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.]
    b4)Tiếp tục:
    [You must be registered and logged in to see this image.]
    b5)Tiếp tục:
    [You must be registered and logged in to see this image.]
    b6)Tiếp tục:
    [You must be registered and logged in to see this image.]
    b7)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


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.

    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 133 Vương Thừa Vũ

    [You must be registered and logged in to see this link.]
    https://khmt.123.st

    4[Kinh nghiệm]Làm việc với mã Huffman Empty [Kinh nghiệm] Thu Jul 07, 2011 9:30 am

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    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:


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.

    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 133 Vương Thừa Vũ

    [You must be registered and logged in to see this link.]
    https://khmt.123.st

    sangminh2009

    sangminh2009
    Thành viên chưa phát huy chia sẻ
    Thành viên chưa phát huy chia sẻ
    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

    HaiYen
    Thành viên cao cấp
    Thành viên cao cấp
    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")


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...
    [You must be registered and logged in to see this link.]

    abc

    abc
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    + 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.


    ================

    http://www.cafetuoitre.com

    fitppro

    fitppro
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Mình cũng thắc mắc giống abc, ko thấy ai trả lời giúp nhỉ?

    HaiYen

    HaiYen
    Thành viên cao cấp
    Thành viên cao cấp
    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?


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...
    [You must be registered and logged in to see this link.]

    TuanNghia

    TuanNghia
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    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

    avatar
    Quản trị viên
    Quản trị viên
    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

    nhattan
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    thank nha, bài viết rất hay, dễ hiểu.

    thong

    thong
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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

    thong
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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

    thvinh
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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

    trungttnd
    Thành viên cao cấp
    Thành viên cao cấp
    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

    thvinh
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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.]

    18[Kinh nghiệm]Làm việc với mã Huffman Empty tính không gian lưu trữ Thu Jan 17, 2013 4:23 pm

    anhnoon0410

    anhnoon0410
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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

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

    Minto Trầm

    Minto Trầm
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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

    lovesang
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội » Các môn thi đầu vào cao học » Môn CSDL và giải thuật » [Kinh nghiệm]Làm việc với mã Huffman

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of https://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Báo cáo lạm dụng | Thảo luận mới nhất