Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Thuật toán Huffman trong việc nén ảnh như thế nào?

  1. #1
    Ngày gia nhập
    11 2011
    Bài viết
    29

    Mặc định Thuật toán Huffman trong việc nén ảnh như thế nào?

    Chào các bạn. Ai biết về thuật toán nén ảnh Huffman tư vấn giúp mình với. Mình đang làm demo về bài này nhưng bí quá. Mình vẫn chưa tìm ra cách đọc file ảnh thế nào để thông kê được nó. Các bạn tư vấn cho mình với. Cảm ơn các bạn nha.

  2. #2
    Ngày gia nhập
    05 2011
    Bài viết
    16

    Code huffman nén mọi loại file
    C Code:
    1. #include <stdio.h>
    2.  
    3. #pragma pack(1)
    4.  
    5. struct NODE {
    6.     unsigned char   c;      // ky tu
    7.     int     freq;   // so lan xuat hien
    8.     bool    used;   // danh dau node da xu ly chua
    9.     int     nLeft;  // chi so nut con nam ben trai
    10.     int     nRight; // chi so nut con nam ben phai
    11. };
    12.  
    13. struct MABIT {
    14.     char*   bits;
    15.     int     soBit;
    16. };
    17.  
    18. const int MAX_NODE = 256*9;
    19. const int MAX_BIT_LEN = 10000;
    20. NODE    huffTree[MAX_NODE];
    21. MABIT   bangMaBit[256];
    22.  
    23. int soNodeTrongCay = 0;
    24.  
    25. void KhoiTao() {
    26.     for (int i = 0; i < MAX_NODE; i++) {
    27.         huffTree[i].c = i;
    28.         huffTree[i].freq = 0;
    29.         huffTree[i].used = false;
    30.         huffTree[i].nLeft = -1;
    31.         huffTree[i].nRight = -1;
    32.     }
    33. }
    34.  
    35. void ThongKeTanSoXuatHien(char* tenFile) { 
    36.     FILE* fi = fopen(tenFile, "rb");
    37.     unsigned char c;
    38.  
    39.     while (1)   {
    40.         fread(&c, 1, sizeof(char), fi);
    41.         if (feof(fi)) {
    42.             break;
    43.         }
    44.         huffTree[c].freq ++; // Ghi chú: Thao tác này để làm gì (nghĩa là gì)?      
    45.     }
    46.  
    47.     fclose(fi);
    48. }
    49.  
    50. void XuatBangThongKe() {
    51.     printf("Bang thong ke tan suat: \n");
    52.     for (int i = 0; i < 256; i++) {
    53.         if (huffTree[i].freq > 0)
    54.         {// Ghi chú: tại sao cần kiểm tra điều kiện này?
    55.             printf("%c: %d\n",i, huffTree[i].freq);
    56.             soNodeTrongCay++;
    57.         }
    58.     }
    59. }
    60.  
    61. bool Tim2PhanTuMin(int &i, int &j, int nNode) {
    62.     i = -1;
    63.     j = -1;
    64.  
    65.     // tim 2 phan tu co trong so nho nhat
    66.     for (int k = 0; k < nNode; k++)
    67.         if (huffTree[k].used == false && huffTree[k].freq > 0)      { // Ghi chú: Tại sao cần kiểm tra 2 điều kiện này
    68.             if (i == -1) {
    69.                 i = k;
    70.             }
    71.             else if (j == -1) {
    72.                 j = k;
    73.             }
    74.             else {
    75.                 if (huffTree[i].freq > huffTree[j].freq) {
    76.                     if (huffTree[k].freq < huffTree[i].freq) {
    77.                         i = k;
    78.                     }
    79.                 }
    80.                 else {
    81.                     if (huffTree[k].freq < huffTree[j].freq) {
    82.                         j = k;
    83.                     }
    84.                 }
    85.             }
    86.         }
    87.         // sap xep lai 2 phan tu de co i: phan tu co trong so nho nhat, j: phan tu co trong so nho nhi 
    88.         // co 2 truong hop can doi i,j:
    89.         // huffTree[i].freq > huffTree[j].freq
    90.         // huffTree[i].freq == huffTree[j].freq va (huffTree[i].c > huffTree[j].c)
    91.         if (i != -1 && j!= -1) {
    92.             if ( (huffTree[i].freq > huffTree[j].freq) || ((huffTree[i].freq > huffTree[j].freq) && (huffTree[i].c > huffTree[j].c))) {
    93.                 int t = i;
    94.                 i = j;
    95.                 j = t;
    96.             }
    97.             return true;
    98.         }
    99.         else {
    100.             return false;
    101.         }
    102. }
    103.  
    104.  
    105. int TaoCayHuffman() {
    106.     int nNode = 256;
    107.     int i, j;
    108.     bool timThay = false;
    109.     while (true)    {
    110.  
    111.         // Ghi chú: bước này để làm gì
    112.         timThay = Tim2PhanTuMin(i, j, nNode);
    113.         if (!timThay) {
    114.             break;
    115.         }
    116.  
    117.         // Ghi chú: bước này để làm gì
    118.         huffTree[nNode].c = (huffTree[i].c < huffTree[j].c) ? huffTree[i].c : huffTree[j].c;
    119.         huffTree[nNode].freq = huffTree[i].freq + huffTree[j].freq;
    120.         huffTree[nNode].nLeft = i;
    121.         huffTree[nNode].nRight = j;
    122.  
    123.         // Ghi chú: bước này để làm gì
    124.         huffTree[i].used = true;
    125.         huffTree[j].used = true;
    126.  
    127.         // Ghi chú: bước này để làm gì
    128.         huffTree[nNode].used = false;
    129.         nNode++;
    130.  
    131.     }
    132.     return nNode - 1; // Ghi chú: ý nghĩa của giá trị trả về?
    133.  
    134. }
    135.  
    136. void XuatCayHuffman(int node, int tab) {
    137.     if (node == -1) {
    138.         return;
    139.     }
    140.     for (int i = 0; i < tab; i++) {
    141.         printf("\t");
    142.     }
    143.     if (huffTree[node].nLeft == -1 && huffTree[node].nRight == -1)  {
    144.         printf("%c\n", huffTree[node].c);
    145.     }
    146.     else    {
    147.         printf("%c..\n", huffTree[node].c);
    148.         XuatCayHuffman(huffTree[node].nLeft, tab + 1);
    149.         XuatCayHuffman(huffTree[node].nRight, tab + 1);
    150.     }
    151. }
    152.  
    153. void DuyetCayHuffman(int node, char maBit[], int nMaBit) {
    154.     if (node == -1) {
    155.         return;
    156.     }
    157.     if (huffTree[node].nLeft == -1 && huffTree[node].nRight == -1) {    //Ghi chú: ý nghĩa của điều kiện kiểm tra là gì? 
    158.         bangMaBit[node].soBit = nMaBit;
    159.         bangMaBit[node].bits = new char[nMaBit];
    160.         for (int i = 0; i < nMaBit; i++) {
    161.             bangMaBit[node].bits[i] = maBit[i];
    162.         }
    163.         return;
    164.     }
    165.     else {
    166.         //Ghi chú: ý nghĩa của 2 dòng lệnh bên dưới là gì?
    167.         maBit[nMaBit] = 0;     
    168.         DuyetCayHuffman(huffTree[node].nLeft, maBit, nMaBit + 1);
    169.  
    170.         //Ghi chú: ý nghĩa của 2 dòng lệnh bên dưới là gì?
    171.         maBit[nMaBit] = 1;
    172.         DuyetCayHuffman(huffTree[node].nRight, maBit, nMaBit + 1);
    173.     }
    174. }
    175.  
    176. void PhatSinhMaBit(int nRoot) { // Ghi chú: ý nghĩa của tham số nRoot?
    177.     for (int i = 0; i < 256; i++) {
    178.         bangMaBit[i].soBit = 0;
    179.         bangMaBit[i].bits = NULL;
    180.     };
    181.     char maBit[MAX_BIT_LEN/8];
    182.     int nMaBit = 0;
    183.  
    184.     DuyetCayHuffman(nRoot, maBit, nMaBit);
    185. }
    186.  
    187. void XuatBangMaBit() {
    188.     for (int i = 0; i < 256; i++)
    189.         if (bangMaBit[i].soBit > 0) {
    190.             printf("%c: ", i);
    191.             for (int j = 0; j < bangMaBit[i].soBit; j++)
    192.                 printf("%d", bangMaBit[i].bits[j]);
    193.             printf("\n");
    194.         }
    195. }
    196.  
    197. void XuatByte(unsigned char out, int soBitCoNghia) {
    198.     for (int i = 7; i >= 7 - soBitCoNghia + 1; i--) {
    199.         if ((out >> i) & 1) {// Ghi chú: Thao tác này để làm gì?
    200.             printf("1");
    201.         }
    202.         else {
    203.             printf("0");       
    204.         }
    205.     }
    206.     printf(" ");
    207. }
    208.  
    209.  
    210.  
    211. //So node trong cay -> ki tu -> tan so -> ki tu -> tan so -> ..... day cac bit da ma hoa
    212. void GhiBangThongKe(FILE *&fpwrite) {
    213.     //printf("Ghi bang thong ke tan suat: \n");
    214.  
    215.     fwrite( &soNodeTrongCay, sizeof( int ), 1, fpwrite );
    216.     for (int i = 0; i < 256; i++)
    217.     {
    218.         if (huffTree[i].freq > 0)
    219.         {
    220.             char c = i;
    221.             fwrite(&c, 1, sizeof(char), fpwrite);
    222.             int n = huffTree[i].freq;
    223.             fwrite(&n, 1, sizeof(int), fpwrite);
    224.             //printf("%c: %d\n",i, huffTree[i].freq);
    225.         }
    226.     }
    227.  
    228.     //fclose(fpwrite);
    229.  
    230. }
    231.  
    232.  
    233. void MaHoa1KyTu(FILE *&fpwrite, unsigned char c, unsigned char &out, unsigned char &viTriBit) { //Ghi chú: ý nghĩa của các tham số truyền vào?
    234.  
    235.     for (int i = 0; i < bangMaBit[c].soBit; i++) {
    236.         if (bangMaBit[c].bits[i] == 1) {
    237.             out = out | (1 << viTriBit); // Ghi chú: Thao tác này để làm gì?
    238.         }
    239.         if (viTriBit == 0) { // da du 1 byte, ghi byte do ra file
    240.             viTriBit = 7;
    241.  
    242.             //XuatByte(out, 8);
    243.  
    244.             fwrite(&out, 1, sizeof(char), fpwrite); //Ghi ma ra file ma nhi phan theo tung block byte
    245.             out = 0;
    246.         }
    247.         else {
    248.             viTriBit--;
    249.         }
    250.     }
    251. }
    252.  
    253.  
    254. void NenHuffman(char* inputFile, char *outputFile) {
    255.  
    256.     FILE *fpwrite = fopen(outputFile, "wb");
    257.  
    258.     // BUOC 1: thong ke tan suat xuat hien cua cac ki tu
    259.     KhoiTao();
    260.  
    261.     ThongKeTanSoXuatHien(inputFile);   
    262.  
    263.     XuatBangThongKe();
    264.  
    265.     GhiBangThongKe(fpwrite); //Ghi ban thong ke
    266.  
    267.     // BUOC 2: tao cay Huffman
    268.  
    269.     int nRoot = TaoCayHuffman();
    270.  
    271.     XuatCayHuffman(nRoot, 0);
    272.  
    273.     // BUOC 3: phat sinh ma bit
    274.  
    275.     PhatSinhMaBit(nRoot);
    276.  
    277.     XuatBangMaBit();
    278.  
    279.     // BUOC 4: thay the cac ky tu bang ma bit tuong ung
    280.     unsigned char out = 0;              // ky tu se xuat ra
    281.     unsigned char soBitCoNghia = 0;     // byte cuoi co the ko su dung het cac bit nen can luu so bit co nghia cua byte cuoi
    282.  
    283.     unsigned char c;
    284.     unsigned char viTriBit = 7;         //Ghi chú: ý nghĩa của biến viTriBit?
    285.     FILE* fi = fopen(inputFile, "rb");
    286.     while (true) { 
    287.         fread(&c, 1, sizeof(char), fi);
    288.         if (feof(fi)) {
    289.             break;
    290.         }
    291.         MaHoa1KyTu(fpwrite, c, out, viTriBit);
    292.         //fwrite(&out, 1, sizeof(char), fpwrite); //Ghi ma ra file ma nhi phan theo tung block byte
    293.     }
    294.     soBitCoNghia = 7 - viTriBit;
    295.     if (soBitCoNghia == 0) {               
    296.         soBitCoNghia = 8;
    297.     }
    298.     else {
    299.         //XuatByte(out, soBitCoNghia);
    300.         fwrite(&out, 1, sizeof(char), fpwrite); //Ghi ma ra file ma nhi phan theo tung block byte
    301.     }
    302.  
    303.     fclose(fi);
    304.     fclose(fpwrite);
    305. }
    306.  
    307. //Decompress:
    308. void LoadHuffmanTree(FILE *&fpread)
    309. {
    310.     KhoiTao(); //Reset lai cay Huffman va load lai
    311.     unsigned char c;
    312.     unsigned int n;
    313.  
    314.     int soNode;
    315.     fread( &soNode, sizeof( int ), 1, fpread );
    316.  
    317.     for(int i=0; i<soNode; i++)
    318.     {
    319.         fread( &c, sizeof( char ), 1, fpread );
    320.         fread( &n, sizeof( int ), 1, fpread );
    321.         huffTree[c].freq = n;
    322.     }
    323. }
    324.  
    325. int DemSoKiTu()
    326. {
    327.     int sum = 0;
    328.     for (int i = 0; i < 256; i++) {
    329.         if (huffTree[i].freq > 0) {// Ghi chú: tại sao cần kiểm tra điều kiện này?
    330.             //printf("%c: %d\n",i, huffTree[i].freq);
    331.             sum += huffTree[i].freq;
    332.         }
    333.     }
    334.     return sum;
    335. }
    336.  
    337. int getbit(unsigned char n, int i)
    338. {
    339.     return (n >> i) & 0x1;
    340. }
    341.  
    342. void onbit(char unsigned &n, int i) //Ham bat bit
    343. {
    344.     n = n | (0x1 << i);
    345. }
    346.  
    347. void DeCompress(int nRoot, FILE *& fpread)
    348. {
    349.  
    350.     FILE *fdecode = fopen("decode.txt", "wb");
    351.  
    352.     int nCurrent = nRoot;
    353.     int soKiTu = DemSoKiTu(); //Dem so ki tu de ko bi du bit (vi doc theo bloc 8 bit)
    354.     int isoKiTu = 0;
    355.     //Doc block 8 bit:
    356.     unsigned char c;
    357.  
    358.     while (1)   {
    359.         fread( &c, sizeof( char ), 1, fpread );
    360.         for(int i=7; i>=0; i--)
    361.         {
    362.             int ibit = getbit(c, i);
    363.             //printf("%d", ibit);
    364.             if(ibit == 1)
    365.                 nCurrent = huffTree[nCurrent].nRight;
    366.             else
    367.                 nCurrent = huffTree[nCurrent].nLeft;
    368.  
    369.             if(huffTree[nCurrent].nLeft == -1 && huffTree[nCurrent].nRight == -1)
    370.             {
    371.  
    372.                 fwrite( &huffTree[nCurrent].c, sizeof( char ), 1, fdecode );
    373.    
    374.  
    375.            
    376.                 isoKiTu++;
    377.                 if(isoKiTu == soKiTu)
    378.                 {
    379.                     fclose(fdecode);
    380.                     return;
    381.                 }
    382.                
    383.                
    384.                 nCurrent = nRoot;
    385.             }
    386.  
    387.         }
    388.  
    389.         if (feof(fpread)) {
    390.             break;
    391.         }
    392.     }
    393.  
    394.     fclose(fdecode);
    395. }
    396.  
    397. void main() {
    398.     // nen
    399.     NenHuffman("test.jpg", "output.txt");
    400.  
    401.     printf("______________________________\nThao tac giai nen: ");
    402.  
    403.     KhoiTao(); //Reset lai cau Huffman
    404.  
    405.     //Doc file da nen va giai nen:
    406.     FILE *fpread = fopen("output.txt", "rb");
    407.     LoadHuffmanTree(fpread);
    408.     XuatBangThongKe();
    409.  
    410.     int nRoot = TaoCayHuffman(); //Tao cay huffman tu du lieu vua load
    411.     XuatCayHuffman(nRoot, 0);
    412.     PhatSinhMaBit(nRoot);
    413.     XuatBangMaBit();
    414.  
    415.     DeCompress(nRoot, fpread);
    416.  
    417.     fclose(fpread);
    418.  
    419. }

    thuật toán thì xem tại đính kèm
    Attached Files Attached Files

  3. #3
    Ngày gia nhập
    05 2013
    Bài viết
    1

    Mặc định thuật toán huffman

    mình cũng đang tìm hiểu vấn đề này, hi vọng bạn y5k72pk có thể giải đáp những câu hỏi trong phần chú thích code của bạn để mình có thể hiểu rõ code của bạn hơn. cảm ơn

  4. #4
    Ngày gia nhập
    08 2008
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    192

    Thank pro.
    Đào mộ đôi khi cũng rất tốt bởi vì nó đưa những kiến thức bỏ quên từ lâu lên cho mọi người đùng đào xới.

    Fb-Skype-Mail : leemanhj916 [@gmail.com]

Các đề tài tương tự

  1. Nén dữ liệu - Thuật toán Huffman - ĐHKHTN TP.HCM
    Gửi bởi vitbau1412 trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 4
    Bài viết cuối: 02-01-2017, 01:11 AM
  2. Nén thư mục với thuật toán Huffman như thế nào?
    Gửi bởi koutarou trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 20-12-2012, 12:27 PM
  3. Thuật toán nén adaptive huffman như thế nào?
    Gửi bởi nhiepphong200 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 4
    Bài viết cuối: 11-06-2012, 03:35 AM
  4. Thuật toán Huffman.
    Gửi bởi HUMG.ThongIT trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 0
    Bài viết cuối: 24-11-2011, 09:07 PM
  5. Hướng dẫn sơ qua về thuật toán nén file Huffman
    Gửi bởi Cpro trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 02-12-2008, 06:25 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn