`

[实例]利用霍夫曼树获得霍夫曼编码并进行加密和解密

 
阅读更多
 




    奋战一个晚上把基本功能实现了 
//HuffmanTree.h

#ifndef HUFFMAN_TREE_H
#define HUFFMAN_TREE_H

#include <Windows.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

namespace HuffmanTreeSpace
{
    struct HuffmanTreeNode
    {
        int nData;
        string strData;
        string strHuffmanCodeing;
        HuffmanTreeNode* pRoot;
        HuffmanTreeNode* pLeftChild;
        HuffmanTreeNode* pRightChild;

        HuffmanTreeNode()
        {
            nData = 0;

            pRoot = NULL;
            pLeftChild = NULL;
            pRightChild = NULL;
        }

//         bool operator < (const HuffmanTreeNode& rhs) const // 升序排序时必须写的函数
//         {
//             return nData < rhs.nData;
//         }
//         bool operator > (const HuffmanTreeNode& rhs) const // 降序排序时必须写的函数
//         {
//             return nData > rhs.nData;
//         }
    };

    typedef struct tag_SingleCode
    {
        int nData;
        string strData;
        string strCoding;
    }SingleCode, *PSingleCode;

    typedef vector<HuffmanTreeNode*> TreeNodeArray;
    typedef vector<SingleCode> HuffmanCodingTable;

    enum  EM_HUFFMAN_ORDER
    {
        EM_HUFFMAN_DLR = 0,
        EM_HUFFMAN_LDR = 1,
        EM_HUFFMAN_LRD = 2
    };

    class HuffmanTree
    {
    public:
        HuffmanTree();

        void AddRawDataToNode(string strData);
        void AddNode(int nData, string strData);
        void MySort();

        void Gnenerate();
        void PrintTreeNode();

        void PrintNode(EM_HUFFMAN_ORDER emType, const HuffmanTreeNode* pNode);
        void GetHuffmanNode(const HuffmanTreeNode* pNode, int nData, string strData);
        string PrintHuffmanCode(int nData, string strData);

        HuffmanTreeNode* GetRoot()
        {
            return m_pRootNode;
        }

        void GenerateCodingTable();
        string HuffmanEncoding(const string& strRaw);
        string HuffmanDecoding(const string& strEncoded);

    public:
        string m_strTemp;
        const HuffmanTreeNode* m_pTemp;

        HuffmanCodingTable m_CodingTable;

    private:
        TreeNodeArray m_TreeNodes; //本示例没有考虑内存的释放，后续可以改进
        HuffmanTreeNode* m_pRootNode;
        string strHuffCode;
    };

    //////////////////////////////////////////////////////////////////////////
    void HuffmanTree_Test1();
    void HuffmanTree_Test2();
    void HuffmanTree_Test3();
}

#endif



#include "HuffmanTree.h"

namespace HuffmanTreeSpace
{
    HuffmanTree::HuffmanTree()
        :m_pRootNode(NULL)
    {
    }

    bool less_second(char char1, char char2)
    {
        return char1 < char2;
    }

    void HuffmanTree::AddRawDataToNode(string strData)
    {
        m_CodingTable.clear();

        //统计字符出现的频率
        string strTemp = strData;
        sort(strTemp.begin(), strTemp.end()/*, less_second*/);

        while (strTemp.size() > 0)
        {
            string strData;
            const char* ptr = strTemp.c_str();
            int nSize = count(strTemp.begin(), strTemp.end(), *ptr);
            strData = *ptr;

            AddNode(nSize, strData);

            strTemp = strTemp.substr(nSize, strTemp.size()-nSize);
        }
    }

    void HuffmanTree::AddNode(int nData, string strData)
    {
        HuffmanTreeNode* pNode = new HuffmanTreeNode();
        pNode->nData = nData;
        pNode->strData = strData;
        m_TreeNodes.push_back(pNode);

        SingleCode singleCode;
        singleCode.nData = nData;
        singleCode.strData = strData;
        m_CodingTable.push_back(singleCode);
    }

    //升序排序
    bool lessmark(const HuffmanTreeNode* treeNode1, const HuffmanTreeNode* treeNode2)
    {
        return (treeNode1->nData < treeNode2->nData);
    }

    //降序排序
    bool greatermark(const HuffmanTreeNode* treeNode1, const HuffmanTreeNode* treeNode2)
    {
        return treeNode1->nData > treeNode2->nData;
    }


    void HuffmanTree::MySort()
    {
        sort(m_TreeNodes.begin(), m_TreeNodes.end(), lessmark);
    }

    void HuffmanTree::Gnenerate()
    {
        MySort();

        while (m_TreeNodes.size() > 1)
        {
            //PrintTreeNode();

            int nsize = m_TreeNodes.size();
            TreeNodeArray::iterator iter = m_TreeNodes.begin();
            TreeNodeArray::iterator iter2 = m_TreeNodes.begin();
            ++iter2;

            HuffmanTreeNode* pNode = new HuffmanTreeNode();

            pNode->nData = (*iter)->nData + (*iter2)->nData;
            pNode->strData = (*iter)->strData + (*iter2)->strData;
            (*iter)->strHuffmanCodeing = "0";
            (*iter2)->strHuffmanCodeing = "1";

            (*iter)->pRoot = pNode;
            (*iter2)->pRoot = pNode;

            pNode->pLeftChild = *iter;
            pNode->pRightChild = *iter2;

            m_TreeNodes.erase(iter2);
            m_TreeNodes.erase(iter);

            m_TreeNodes.push_back(pNode);

            MySort();
        }

        m_pRootNode = *m_TreeNodes.begin();

        GenerateCodingTable();
    }

    void HuffmanTree::PrintTreeNode()
    {
        TreeNodeArray::iterator iter = m_TreeNodes.begin();
        TreeNodeArray::iterator end = m_TreeNodes.end();

        for(; iter != end; ++iter)
        {
            cout << "Val = " << (*iter)->nData << "str = " << (*iter)->strData << " address = "  <<(*iter)->pLeftChild << ", " <<(*iter)->pRightChild << endl;
        }
    }

    void HuffmanTree::PrintNode(EM_HUFFMAN_ORDER emType, const HuffmanTreeNode* pNode)
    {
        if (pNode != NULL)
        {
            if (EM_HUFFMAN_DLR == emType)
            {
                cout << " " << pNode->nData << "(" << pNode->strData << "," << pNode->strHuffmanCodeing << ")";
            }

            //Get Left Leaf
            if (pNode->pLeftChild != NULL)
            {
                PrintNode(emType, pNode->pLeftChild);
            }

            if (EM_HUFFMAN_LDR == emType)
            {
                cout << " " << pNode->nData << "(" << pNode->strData << "," << pNode->strHuffmanCodeing << ")";
            }

            //Get Right Leaf
            if (pNode->pRightChild != NULL)
            {
                PrintNode(emType, pNode->pRightChild);
            }

            if (EM_HUFFMAN_LRD == emType)
            {
                cout << " " << pNode->nData << "(" << pNode->strData << "," << pNode->strHuffmanCodeing << ")";
            }
        }
    }

    void HuffmanTree::GetHuffmanNode(const HuffmanTreeNode* pNode, int nData, string strData)
    {
        if (pNode != NULL)
        {
            if (pNode->nData==nData
             && pNode->strData==strData)
            {
                if (NULL == m_pTemp)
                {
                    m_pTemp = pNode;
                }
                return;
            }
            else
            {
                m_strTemp = m_strTemp.substr(0, m_strTemp.length()-1);
            }

            //Get Left Leaf
            if (pNode->pLeftChild != NULL)
            {
                if (pNode->pLeftChild->nData==nData
                 && pNode->pLeftChild->strData==strData)
                {
                    if (NULL == m_pTemp)
                    {
                        m_pTemp = pNode->pLeftChild;
                    }

                    m_strTemp = m_strTemp.substr(0, m_strTemp.length()-1);
                    return;
                }
                else
                {
                    GetHuffmanNode(pNode->pLeftChild, nData, strData);
                    //cout << "0";
                    //m_strTemp = "0" + m_strTemp;
                }
            }
            else
            {
                m_strTemp = m_strTemp.substr(0, m_strTemp.length()-1);
            }

            //Get Right Leaf
            if (pNode->pRightChild != NULL)
            {
                if (pNode->pRightChild->nData==nData
                    && pNode->pRightChild->strData==strData)
                {
                    if (NULL == m_pTemp)
                    {
                        m_pTemp = pNode->pRightChild;
                    }

                    m_strTemp = m_strTemp.substr(0, m_strTemp.length()-1);
                    return;
                }
                else
                {
                    GetHuffmanNode(pNode->pRightChild, nData, strData);
                    //cout << "1";
                    //m_strTemp = "1" + m_strTemp;
                }
            }
            else
            {
                m_strTemp = m_strTemp.substr(0, m_strTemp.length()-1);
            }
        }
    }

    string HuffmanTree::PrintHuffmanCode(int nData, string strData)
    {
        string strHuffmanCode;

        m_strTemp = "";
        m_pTemp = NULL;

        //cout << "---------------------------------------------------" << endl;
        GetHuffmanNode(m_pRootNode, nData, strData);
        //cout << "Temp=" << m_strTemp  << "\n" << strData << "(" << nData << ") = ";

        const HuffmanTreeNode* ptr = m_pTemp;
        while (ptr != NULL)
        {
            strHuffmanCode = ptr->strHuffmanCodeing + strHuffmanCode;
            //cout << " " << ptr->nData << "(" << ptr->strHuffmanCodeing << ")";
            ptr = ptr->pRoot;
        }
        cout << strData << " = " << strHuffmanCode << endl;
        //cout << "---------------------------------------------------" << endl;

        return strHuffmanCode;
    }

    void HuffmanTree::GenerateCodingTable()
    {
        HuffmanCodingTable::iterator iter= m_CodingTable.begin();
        HuffmanCodingTable::iterator end= m_CodingTable.end();

        for ( ; iter != end; ++iter)
        {
            iter->strCoding = PrintHuffmanCode(iter->nData, iter->strData);
        }
    }

    string& replace_all_distinct(string& str,const   string&   old_value,const   string&   new_value)
    {
        for(string::size_type   pos(0);   pos!=string::npos;   pos+=new_value.length())
        {
            if ((pos=str.find(old_value,pos))!=string::npos)
            {
                str.replace(pos,old_value.length(),new_value);
            }
            else
            {
                break;
            }
        }

        return str;
    }

    string HuffmanTree::HuffmanEncoding(const string& strRaw)
    {
        HuffmanCodingTable::const_iterator iter= m_CodingTable.begin();
        HuffmanCodingTable::const_iterator end= m_CodingTable.end();
        string strTemp = strRaw;

        for ( ; iter != end; ++iter)
        {
            replace_all_distinct(strTemp, iter->strData, iter->strCoding);
        }

        return strTemp;
    }

    string HuffmanTree::HuffmanDecoding(const string& strEncoded)
    {
        string strTemp = strEncoded;
        string strNew;

        while (strTemp.length() > 0)
        {
            HuffmanCodingTable::const_iterator iter= m_CodingTable.begin();
            HuffmanCodingTable::const_iterator end= m_CodingTable.end();
            for ( ; iter != end; ++iter)
            {
                //replace_all_distinct(strTemp, iter->strData, iter->strCoding);
                size_t nPos = strTemp.find(iter->strCoding);

                if (0 == nPos)
                {
                    //cout << "\n" << strTemp << " ==> \n";
                    strTemp = strTemp.substr(iter->strCoding.length(), strTemp.size()-iter->strCoding.length());
                    //cout << strTemp << endl;
                    strNew += iter->strData;
                    //cout << "\n" << strNew << endl;
                    break;
                }
            }
        }

        return strNew;
    }

    //////////////////////////////////////////////////////////////////////////
    void HuffmanTree_Test1()
    {
        string strRawData = "abdacdcdBAdCCCCdCDdDD";
        string strEncoding;
        string strDecoding;
        HuffmanTree huffmanTree;

        cout << "------------------HuffmanTree_Test1-----------------------\n";
        cout << "Pliantext = "  << strRawData << endl;

        huffmanTree.AddNode(2, "a");
        huffmanTree.AddNode(1, "b");
        huffmanTree.AddNode(2, "c");
        huffmanTree.AddNode(6, "d");
        huffmanTree.AddNode(1, "A");
        huffmanTree.AddNode(1, "B");
        huffmanTree.AddNode(5, "C");
        huffmanTree.AddNode(3, "D");

        huffmanTree.Gnenerate();

        strEncoding = huffmanTree.HuffmanEncoding(strRawData);
        cout << "Encoding = "  << strEncoding << endl;

        strDecoding = huffmanTree.HuffmanDecoding(strEncoding); //
        cout << "Decoding = "  << strDecoding << endl;
        cout << "----------------------------------------------------------\n";

    }

    void HuffmanTree_Test2()
    {
        string strRawData = "abdacdcdBAdCCCCdCDdDD";
        string strEncoding;
        string strDecoding;
        HuffmanTree huffmanTree;

        cout << "------------------HuffmanTree_Test2-----------------------\n";
        cout << "Pliantext = "  << strRawData << endl;

        huffmanTree.AddRawDataToNode(strRawData);
        huffmanTree.Gnenerate();

        strEncoding = huffmanTree.HuffmanEncoding(strRawData);
        cout << "Encoding = "  << strEncoding << endl;

        strDecoding = huffmanTree.HuffmanDecoding(strEncoding); //
        cout << "Decoding = "  << strDecoding << endl;
        cout << "----------------------------------------------------------\n";
    }

    void HuffmanTree_Test3()
    {
        string strRawData = "abdacdcdBAdCCCCdCDdDD";
        string strEncoding;
        string strDecoding;
        HuffmanTree huffmanTree;

        cout << "------------------HuffmanTree_Test3-----------------------\n";
        cout << "Pliantext = "  << strRawData << endl;

        huffmanTree.AddNode(1, "A");
        huffmanTree.AddNode(1, "B");
        huffmanTree.AddNode(5, "C");
        huffmanTree.AddNode(3, "D");
        huffmanTree.AddNode(2, "a");
        huffmanTree.AddNode(1, "b");
        huffmanTree.AddNode(2, "c");
        huffmanTree.AddNode(6, "d");

        huffmanTree.Gnenerate();

        strEncoding = huffmanTree.HuffmanEncoding(strRawData);
        cout << "Encoding = "  << strEncoding << endl;

        strDecoding = huffmanTree.HuffmanDecoding(strEncoding); //
        cout << "Decoding = "  << strDecoding << endl;
        cout << "----------------------------------------------------------\n";
    }
}




分享到：
| 哈夫曼树与哈夫曼编码
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    VB6压缩解压缩、加密解密源码大全

    总之，"VB6压缩解压缩、加密解密源码大全"是一个宝贵的资源，它提供了大量实际应用的实例，可以帮助开发者深入理解并实践加密与压缩技术，从而提升软件的安全性和效率。无论是初学者还是经验丰富的程序员，都能从中...

    数据结构与算法-C语言版本

    - **贪心算法**：每次做出局部最优选择，期望达到全局最优，如霍夫曼编码、Prim最小生成树算法、Dijkstra最短路径算法。 - **回溯法**：尝试所有可能的解决方案，一旦发现不满足条件则退回一步重新选择，如八皇后...

    信息与编码，学习信息论与编码技术的很好的课件

    例如，霍夫曼编码利用频率统计进行变字长编码，使得频繁出现的符号占据较少的位数。 2. 信道编码：旨在增加数据的冗余度，以对抗信道噪声和错误。常见的信道编码有奇偶校验码、循环冗余校验（CRC）、汉明码以及更...

    数据结构java版 梁志敏译

    它通过使用变长编码表对源符号进行编码，不同符号的编码长度不同，通常是出现频率较高的符号使用较短的编码。算法的核心是构建一个霍夫曼树，该树根据各个符号出现的频率构建，频率高的符号离树根较近，频率低的离...

    信息与编码讲义

    《信息与编码讲义》是一份深入探讨信息理论与编码技术...《信息与编码讲义》会详细解析以上各知识点，并通过实例和习题帮助学习者理解和应用这些理论。无论是通信工程专业学生还是相关领域的从业者，都能从中受益匪浅。

    信息论与编码学习辅导及习题详解(包含阅读器)

    常见的信源编码方法包括霍夫曼编码、算术编码和游程编码等。 3. **信道编码**：信道编码是在发送端添加冗余信息，以增强信号抵抗信道噪声的能力，确保接收端能够正确解码。常见的信道编码有奇偶校验码、卷积码和...

    zip_utils_src.rar

    通过阅读和理解这些代码，开发者可以更好地理解数据压缩的原理，以及如何在程序中实现这些功能，这对于提升软件性能、优化资源利用和处理跨平台问题等方面都具有重要意义。 总的来说，ZIP格式和其背后的压缩算法是...

    The Laws of Cryptography wiht Java Code

    现代密码学的核心部分之一是《高级加密标准》(AES)，本书也对AES进行了深入分析，包括AES的介绍、有限域GF(256)的概念、S盒的作用、密钥扩展过程、加密操作和解密操作。AES作为目前广泛使用的一种对称加密标准，其...

    The Laws of Cryptography with Java Code.pdf

    讲解了霍夫曼编码这种数据压缩方法的工作原理及其应用。 - **第6章：汉明码用于错误校正** 分析了汉明码如何有效地检测并纠正数据传输过程中的错误。 - **第7章：处理十进制数字** 探讨了如何在密码学中处理非...

    内蒙古工业大学信息论课件PPT

    这套内蒙古工业大学的信息论课件PPT，很可能会涵盖以上提到的各个知识点，并通过实例和图表帮助学生直观理解这些抽象概念。学习者可以通过这些课件深入学习，提升自己在信息处理和通信技术方面的理论素养。

    elements of information theory

    这本教材不仅涵盖了这些基本概念，还包含了大量实例和习题，帮助读者理解并应用信息论原理。无论是对于通信工程、计算机科学还是统计学的学生，或者是从事相关研究的专家，都是不可或缺的参考书籍。

    Algorithm:알고리즘

    5. **算法优化**："Algorithm-master"可能包含一些针对特定问题的优化算法，比如使用位运算进行快速计算，或者利用内存对齐和预读取优化循环性能。理解这些技巧对于编写高性能的C++代码非常重要。 6. **算法分析与...

Magicbox
Global site tag (gtag.js) - Google Analytics