Có ai biết Thuật Toán mã hoá Huffman không ?

[Tiếnsĩđiên]

Bạn nào biết thuật toán mã hoá của huffman làm ơn giời thiệu hay chỉ cho mình được không ? hopặc có thể email tới tiensidien@fptnet.com.vn

[bete]

tiensidien coi thử chỗ này:
http://www.programmersheaven.com/2/Art_Huffman_p1

lưu ý là họ trình bày cả 2 thuật tóan: static lẫn dynamic (adaptive)

Bạn đọc xong thì thử viết chương trình xem sao (tuy 0 phải là thuật toán nhanh nhứt & lục trên Internet thế nào cũng có người cho mã nguồn; nhưng tự mình viềt thử cũng thú lắm !)

[Tiếnsĩđiên]

Cam on ban nhe. Minh se doc xem coi the nao.

[anhunsw]

Lau qua toi khong vao, nen co the Ban khong can nua. Nhung tai trang web nay, co giai thich rat ro ve Huffmann (Plus illustrating by animation...) Ngay xua, khi lam Assignment viet WinZip cho mon Data Structure, toi search nhieu noi lam, nhung o day, co ve OK .

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/huffman.html

Anh

[Xmen]

dung roi, trang cua ong Morris la trinh bay huffman de hieu nhat do, co java applet demo dep mat nua

[whitepenguin]

Các bá chỉ hộ em thuật toán Sunderland Hogdman (xén các cạnh bởi một đa giác)
em cám ơn nhiều

[bete]

thân gửi whitepenguin: bạn thử coi ở đây (tiếng Anh):

http://www.cs.rit.edu/~icss571/clipTrans/PolyClipBack.html

http://www.cs.fit.edu/wds/classes/cse5255/thesis/polyClipSH/intro.html

http://www.hh.se/stud/d01toku/polygon.htm

http://www.google.com/search?q=sutherland+hodgman+clipping&hl=en&lr=&ie=UTF-8&start=20&sa=N

[bete]

Thân gửi whitepenguin: hình bạn đã có giải thuật nhưng còn vướng mắc ?
Nếu vậy thì tui xin nói thử coi sao:

Giải thuật Sutherland-Hogdman là để cắt 1 đa giác cho vừa với 1 hình chữ nhựt (tui nghĩ nếu là hình đa giác lồi cũng không sao - nhưng trong đồ họa máy tính mình hay có cửa sổ hình chữ nhựt).

Cách thức: gọi 4 cạnh của cửa sổ là cạnh1, cạnh2, cạnh3 và cạnh4. Cắt đa giác 4 lần liên tiếp: lần thứ nhứt xài cạnh1, lần thứ 2 xài cạnh2, ......, lần thứ 4 xài cạnh4.

Để cắt 1 đa giác theo 1 cạnh nào đó của cửa sổ: chia mặt phẳng 2 chiều thành 2 miền (chia bởi cạnh đó kéo dài): miền cùng phía cửa sổ và miền khác phía:



đây là miền khác phía

----------+---------------+----- <--- đang cắt theo cạnh này (đường d)
miền | miền |
cùng | cùng phía | miền cùng phía
phía | |
+---------------+

đây là miền cùng phía

Gọi đường thẳng chứa cạnh đang xét của cửa sổ là đường d
Xét 1 cạnh a của đa giác, nói chung mình có 4 trường hợp:

a) 2 đầu của cạnh a thuộc cùng 1 miền (2 đầu đều nằm cùng phía cửa sổ, hoặc 2 đầu đều nằm khác phía cửa sổ): cạnh a sẽ không cắt đường d



x------------------------------x (cạnh a)
----------+---------------+----- <--- đang cắt theo cạnh này (đường d)
| | x
| | |
| | | (cạnh a)
+---------------+ x
x------------------------------x (cạnh a)

b) 2 đầu của cạnh a không thuộc cùng 1 miền (1 đầu nằm cùng phía cửa sổ, đầu còn lại nằm khác phía): cạnh a sẽ cắt đường d tại điểm p


x (cạnh a)
|
--p-------+---------------+----- <--- đang cắt theo cạnh này (đường d)
| | |
| | |
x | |
+---------------+

c) 1 đầu của cạnh a nằm trên đường d, đầu còn lại không nằm trên đường d

d) 2 đầu của cạnh a đều nằm trên đường d

Mình đánh số các đỉnh của đa giác P1 ban đầu theo thứ tự các đỉnh liên tiếp từ v1 tới v_n. Khi mình cắt đa giác P1 này với 1 cạnh của cửa sổ => mình sẽ có được 1 đa giác mới P2 (chính là 1 phần của đa giác ban đầu). Mình phải tìm các đỉnh của đa giác kết quả P2. Đặt mảng R: R chứa các đỉnh của đa giác P2. Lúc mới đầu mình chưa tìm được đỉnh nào của P2 => mảng R là trống

Mình xét đỉnh v1 của P1 => có 3 trường hợp:

a) v1 nằm cùng phía với cửa sổ (lấy đường d làm mốc) => v1 là 1 đỉnh của P2 => bỏ v1 vô mảng R

a) v1 nằm trên đường d => v1 là 1 đỉnh của P2 => bỏ v1 vô mảng R

b) v1 nằm khác phía với cửa sổ (lấy đường d làm mốc) => v1 không là 1 đỉnh của P2 => không bỏ v1 vô mảng R



Lần lượt xét các đỉnh v2, ..., v_n của P2 theo thứ tự. Với mỗi lần xét mình làm như sau:

Mình đang xét đỉnh p_j; đỉnh trước đó mình vừa xét là đỉnh p_i (i+1 = j) => làm 2 bước con:

1) nếu (p_i cùng phía với cửa sổ và p_j ngược phía với cửa sổ; hay đảo lại (p_i ngược, p_j cùng)) => bỏ giao điểm p vô R.

2) nếu (p_j cùng phía với cửa sổ hoặc p_j nằm trên đường d) => bỏ p_j vô R.


Giải thích dài dòng cho luật trên là:

Mình đang xét đỉnh p_j; đỉnh trước đó mình vừa xét là đỉnh p_i (i+1 = j) => có 9 trường hợp con:

1) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j cũng nằm cùng phía với cửa sổ => p_j là 1 đỉnh của P2 => bỏ p_j vô R

2) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j nằm trên đường thẳng d => p_j là 1 đỉnh của P2 => bỏ p_j vô R

3) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j nằm khác phía với cửa sổ => cạnh (p_i, p_j) cắt đường d tại điểm p => p_j không là 1 đỉnh của P2; nhưng p là 1 đỉnh của P2 => bỏ p vô R

4) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j nằm cùng phía với cửa sổ => p_j là 1 đỉnh của P2 => bỏ p_j vô R

5) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j cũng nằm trên đường thẳng d => p_j là 1 đỉnh của P2 => bỏ p_j vô R

6) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j nằm khác phía với cửa sổ => p_j không là 1 đỉnh của P2 => không bỏ p_j vô R

7) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j nằm cùng phía với cửa sổ => cạnh (p_i, p_j) cắt đường d tại điểm p => p và p_j là 1 đỉnh của P2 => bỏ p và p_j vô R (theo thứ tự đó)

8) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j nằm trên đường thẳng d => p_j là 1 đỉnh của P2 => bỏ p_j vô R

9) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j cũng nằm khác phía với cửa sổ => p_j không là 1 đỉnh của P2 => không bỏ p_j vô R


Sau khi mình xét hết v2, ..., v_n (theo thứ tự) thì R sẽ chứa các đỉnh (theo thứ tự) của P2. Mình cắt tiếp P2 (xài cạnh thứ 2 của cửa sổ) => được đa giác mới P3. Mình cắt tiếp P3 (xài cạnh thứ 3 của cửa sổ) => được đa giác mới P4. Mình cắt tiếp P4 (xài cạnh thứ 4 của cửa sổ) => được đa giác mới P5. Đa giác P5 chính là kết quả cuối cùng mà mình cần tìm


(tui nghĩ có thể xài cùng một lúc 4 cạnh để cắt; nhưng hơi rắc rối 1 chút)

(9 trường hợp con trên kia bạn vẽ cái hình ra là thấy rõ liền, tui hơi lười 1 chút. Nếu nhóm lại:

a) Nhóm thứ 1:
3) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j nằm khác phía với cửa sổ => bỏ giao điểm p vô R

b) Nhóm thứ 2:
1) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j cũng nằm cùng phía với cửa sổ => bỏ p_j vô R

2) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j nằm trên đường thẳng d => bỏ p_j vô R

4) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j nằm cùng phía với cửa sổ => bỏ p_j vô R

5) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j cũng nằm trên đường thẳng d => bỏ p_j vô R

8) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j nằm trên đường thẳng d => bỏ p_j vô R

c) Nhóm thứ 3:
7) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j nằm cùng phía với cửa sổ => bỏ giao điểm p và p_j vô R (theo thứ tự đó)

d) Nhóm thứ 4:
6) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j nằm khác phía với cửa sổ => không bỏ p_j vô R

9) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j cũng nằm khác phía với cửa sổ => không bỏ p_j vô R


Nhóm lại lần nữa:

a) Nhóm thứ 1:
3) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j nằm khác phía với cửa sổ => bỏ giao điểm p vô R

7) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j nằm cùng phía với cửa sổ => bỏ giao điểm p vô R

b) Nhóm thứ 2:
1) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j cũng nằm cùng phía với cửa sổ => bỏ p_j vô R

2) p_i nằm cùng phía với cửa sổ (p_i là 1 đỉnh của P2), p_j nằm trên đường thẳng d => bỏ p_j vô R

4) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j nằm cùng phía với cửa sổ => bỏ p_j vô R

5) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j cũng nằm trên đường thẳng d => bỏ p_j vô R

8) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j nằm trên đường thẳng d => bỏ p_j vô R

7) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j nằm cùng phía với cửa sổ => bỏ p_j vô R

c) Nhóm thứ 3:
6) p_i nằm trên đường d (p_i là 1 đỉnh của P2), p_j nằm khác phía với cửa sổ => không bỏ p_j vô R

9) p_i nằm khác phía với cửa sổ (p_i không là 1 đỉnh của P2), p_j cũng nằm khác phía với cửa sổ => không bỏ p_j vô R

=> Lý luận rút gọn sẽ là:
nếu thuộc nhóm 1 (p_i cùng phía với cửa sổ và p_j ngược phía với cửa sổ; hay đảo lại (p_i ngược, p_j cùng)) => bỏ giao điểm p vô R.
nếu thuộc nhóm 2 (p_j cùng phía với cửa sổ hoặc p_j nằm trên đường d) => bỏ p_j vô R.
)

(nếu có gì sai sót mong các bạn sửa giúp cho, xin cám ơn trước)

-thân

[whitepenguin]

Cám ơn bác Pete ,khi xem xong mấy cái link và bài của bác tui hiểu rùi ,ngoài ra tui cũng còn học thêm được giải thuật Cyrus Beck và Suntherland chia mã vùng nữa ,thanks for your post

[whitepenguin]

To pete :Bác có thể giải thích và chỉ tui cách tạo ra màu trong C++ 3.0 được không ,tui không biết xài cái lệnh setrgb và không hiểu cơ chế hoạt động và nạp bằng màu của nó như thế nào ,và bác có thể nói rõ cho tui biết hơn về vùng đệm khung không (Frame Buffer) ,tui đọc sách nó nói chả kỹ gì cả ,kể cà phần lý thuyết màu ,chỉ nói về mô hỉnh màu và cách chuyển đổi mô hình màu ,không có nói rõ cách thiết lập màu trong máy tinh và chả có một code víu dụ nào hết ,và ngay cả thiết kế các thang xám (LUT) cũng nói hờ hờ.Chính vì vậy mà phần fill Color tui bỏ wa để học sáng phần khác đóa, hiện giờ các mô hình wireFrame do tui thiết kế bằng C++ chỉ có là lưới thui chả có màu gì hết ,bác chỉ giùm tui nhá ! thanks

[ninjaru]

Mình có làm một project về nén Huffman tĩnh hồi năm ngoái chạy khá nhanh (tuy ko bằng WinZIP he... he...) upload cho anh em xem thử nè.
Code bằng VC chịu khó lọc ra source code phần thuật toán nhé

[bete]

thân gửi whitepenguin:

tui cách tạo ra màu trong C++ 3.0 được không ,tui không biết xài cái lệnh setrgb và không hiểu cơ chế hoạt động và nạp bằng màu của nó như thế nào ,và bác có thể nói rõ cho tui biết hơn về vùng đệm khung không (Frame Buffer) ,tui đọc sách nó nói chả kỹ gì cả ,kể cà phần lý thuyết màu ,chỉ nói về mô hỉnh màu và cách chuyển đổi mô hình màu ,không có nói rõ cách thiết lập màu trong máy tinh và chả có một code víu dụ nào hết ,và ngay cả thiết kế các thang xám (LUT) cũng nói hờ hờ

=> bạn viết bằng Borland C++, hay VC++ ? VC thì tui không rành. Borland C++ thì chỉ có 16 màu ở DOS mode thôi => không có setgrb. Nếu mình làm ở Windows mode thì may ra mới có red/green/blue. Tui có thấy vài cái thư viện đồ họa (svga256 gì gì đó) cho lam tới 256 màu hay hơn => cần nạp bảng màu như bạn nói. Làm 16 màu ở DOS mode thì tương đối dễ; làm 256 màu hay hơn thì tui chưa làm ra bao giờ :) Nếu bạn xài Borland C++ (3.1) như tui thì tui sẽ ráng thử lại coi sao. Có lẽ làm Windows mode là sướng nhứt (nhưng mình phải biết lập trình Windows)

(tui nghĩ các sách đồ họa ít cho code về thiết lập bảng màu là vì mỗi cái một khác (Borland, VC, DOS mode, Windows mode, ...) => họ chỉ nói ý chính để mình muốn áp dụng vô đâu cũng được; vài cuốn sách cho luôn thư viện đồ họa thì họ có thể cho code ví dụ)

(tui sẽ coi lại Frame Buffer & thang màu coi sao. Thiệt tình tui không phải là dân đồ họa chuyên nghiệp, chỉ được cái lục trong sách & trên mạng thôi :))

-thân

[bete]

Thân gửi whitepenguin: bạn thử vô

http://garbo.uwasa.fi/pc/turbopas.html

=> download vga256.zip => có ví dụ mẫu bằng pascal (tuy 256 màu nhưng độ phân giải là 320x200: hơi thấp)

(HSI2RGB.PAS: chuyển đổi thang màu HSI qua RGB, có thang xám nữa thì phải)

Từ Pascal, bạn có thể thử đổi qua C/C++ (tui thấy Pascal mà chạy cũng lẹ lắm)

(nếu có được độ phân giải cao hơn; 640x400 chẳng hạn thì tốt => để tui kiếm tiếp :))

-thân

[sqlhung]

dung roi, trang cua ong Morris la trinh bay huffman de hieu nhat do, co java applet demo dep mat nua
Minh vao trang web ma cac ban goi ma ko vao duoc ,ban co the goi co minh code cung nhu tai lieu lien quan ve nen va giai nen du lieu duoc ko ??neu duoc ,goi cho minh theo :
nguyen1hung2@gmail.com
Cam on ban nhieu !!!

[hxt57]

Có ai có mã thuật toán nén và giải nén huffman bằng java không cho mình xin với. Cứu với. Sắp chết đuối về cái này rồi.

[dungbinh=khanh]

Xác định chuỗi bit truyền khi dùng thuật toán nén Huffman động để truyền từ tiếng Anh sau:
institute
cho mã gốc là ASCII.

[hoangnt174]

Có ai hỗ trợ cho dungbinh=khanh không ???
Tôi cũng đang khát khao bài tập này đây - Mang ơn các bạn rất nhiều!

[nkm]

cám ơn tất cả các bác .

[vancuongk6b]

Mình có làm một project về nén Huffman tĩnh hồi năm ngoái chạy khá nhanh (tuy ko bằng WinZIP he... he...) upload cho anh em xem thử nè.
Code bằng VC chịu khó lọc ra source code phần thuật toán nhé

Bạn ơi post lại link down đi mình không down được !