Hỏi các cao thủ về mã hóa

[hieusua]

Em vừa mới học mã hóa Shannon, Fano và Huffman, nhưng ko biết cách viết giải thuật cho máy tính, mong các cao thủ giúp đỡ.
À, em làm bằng Java, vậy có cao thủ nào biết Java thì chỉ luôn cách nào tối ưu để làm mã hóa 3 cách trên nghen.

[thailehuy]

Qua đây chỉ cho, viết trên mạng mệt lắm

[hieusua]

hic, chơi vậy ko được àh nghen, bíêt ông lúc nào ở đâu đâu mà kiếm.
Thôi, nếu viết mấy thứ đó mệt, thì chỉ tui cách chia nhóm này giùm cái: Cho n xác suất xếp theo thứ tự giảm dần p1>=p2>=p3...>=pn, chia làm 3 nhóm sao cho tổng của các xác suất trong từng nhóm ít chênh lệch với nhau nhất. Điều kiện là 1 nhóm fải gồm các xác suất liền kề nhau (vd như trường hợp 1 nhóm gồm p1,p2,p4 là ko hợp lệ.).

[thailehuy]

Đại loại là :
-Tính tổng n xác suất S(n)
-Chia S(n)cho 3, nếu không chia hết thì chia 2 số làm tròn lên, 1 số làm tròn xuống.(gọi là a, a, b với b < a)
-Chạy 1 dòng WHILE loop lấy các xác suất từ 1 trở đi cho đến khi tổng các xác suất đó bằng hoặc vừa lớn hơn b (giả sử tới p(i)) -> nhóm 1
-Chạy tiếp 1 dòng WHILE loop từ p(i+1) cho tới khi lấy được tổng = a -> nhóm 2
-Còn lại là nhóm 3.
*chú ý là nếu S(n) chia hết cho 3 (giả sử được a) thì 2 dòng WHILE trên phải chỉnh đôi chút: nếu dòng 1 lấy đến khi tổng lớn hơn a thì dòng 2 phải lấy đến khi tổng gần bằng a nhất.
Ông viết bằng C hay Java vậy ?

[hieusua]

Đã nói rồi, Java, và không biết viết giao diện, hè hè, kóc biết xài JBuilder. Nếu ông biết thì chỉ tui luôn đê.
Còn một thắc mắc nữa, về việc chia nhóm ấy, biết là phải sử dụng đệ qui để mã hóa theo Fano, nhưng vẫn chưa mường tượng được fải làm như thế nào, hic hic.
Rồi làm sao tạo ra một bộ mã free prefix với các chiều dài cho trước thỏa mãn kraft's inequality?

[thailehuy]

Ông nói tui chả hiểu gì cả !!!! Nói tiếng Việt đi.(mấy cái ông nói tui quên sạch rồi, học tuốt 3 tháng trước )
Tui trước giờ viết Java trong textpad không hà. Nếu ông khôn biết xài thì ra mua cái dĩa JCreator mà xài, vừa nhẹ vừa dễ hiểu, JBuilder nặng lắm.

[hieusua]

Hê hê, máy ông dỏm, nên mới xài JCreator. Tui có đủ cả, EditPlus là nhẹ nhất, sau đó là JCreator Pro, và JBuilder. Nhưng tui khoái xài JBuilder tại nó đẹp
Hic, tui sợ nói tiếng Việt ông ko hiểu mới ráng dịch ra tiếng Anh đó chứ, mỗi sách dịch 1 cách khác nhau, chả biết đâu mà lần. Bất đẳng thức Kraft là: tổng(D^-ni)<=1, với D là kích thước bảng kí hiệu mã (vd như nhị phân thì D = 2), ni là các chiều dài của các từ mã.
PS: Nếu có nhu cầu đổi CPU thì cho tui con Celeron 1.7GHz đó nha, đang cần gấp.

[Nuhutu]

thường muốn viết giải thuật thì hieusua phải biết các cấu trúc cơ bản của lập trình hướng đối tượng như : Stack, Queue, Tree AVL Tree.... và một số thuật giải thì mới có thể tối ưu hóa được mã để tạo mã Shannon, huffman...
Thường thì tránh dùng lệnh rẽ nhánh (như if, case switch...)thì sẽ nhanh hơn.

[hieusua]

Hihi, cứ koi như tui đã bít mấy thứ đấy đi Pác có thể gợi ý, phác thảo thử ý tưởng để mã hóa theo Huffman cho em được không? Với lại, nếu xài Huffman cho nguồn X^3 (X có khoảng 10 tin -> X^3 tới 1000 tin) thì giải thuật bình thường rất lâu, có thể nào làm nhanh hơn được không ?

[Nuhutu]

Nuhutu tui đây cũng ko phải cao thủ gì nhưng cũng giúp được 1 tí.
Chọn giải thuật sắp xếp thật tốt tập X(Quick sort, Head sort, ...)
C1:-> đổ vào Link List (dùng list 2 chiều thì tốt) -> bắt đầu lấy 2 tin một để mã hóa.
C2:-> vừa sắp vừa bỏ vào Tree -> qúet cây mã hóa
còn nhiều cách khác nữa, tự làm tiếp nhé.