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

清疚 2022-04-11 05:49 186阅读 0赞

\[align=center\]\[img\]https://api5.yunpan.360.cn/intf.php?method=Share.getPublicThumbByNid&qid=108635719&nid=14671735779402431&size=800\_600&devtype=web&v=1.0.1&rtick=14671736103546&share\_qid=108635719&sign=954b8f2ce796ba5572c7812499ac61f8&\[/img\] \[/align\]  
  
\[align=center\]\[img\]https://api5.yunpan.360.cn/intf.php?method=Share.getPublicThumbByNid&qid=108635719&nid=14671798239497213&size=800\_600&devtype=web&v=1.0.1&rtick=14671798308044&share\_qid=108635719&sign=dc6e95501416aeaa4c6e13b685de7e89&\[/img\]\[/align\]  
  
奋战一个晚上把基本功能实现了

//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";
        }
    }

\[align=center\]\[img\]https://api5.yunpan.360.cn/intf.php?method=Share.getPublicThumbByNid&qid=108635719&nid=14671735789406227&size=800\_600&devtype=web&v=1.0.1&rtick=14671736108716&share\_qid=108635719&sign=f9b614324624a36f7c013bf10acad51b&\[/img\]\[/align\]  
\[align=center\]\[img\]https://api5.yunpan.360.cn/intf.php?method=Share.getPublicThumbByNid&qid=108635719&nid=14671735789410839&size=800\_600&devtype=web&v=1.0.1&rtick=14671736109530&share\_qid=108635719&sign=3faaeea3a846bc8220039b195cafa811&\[/img\]\[/align\]  
\[align=center\]\[img\]https://api5.yunpan.360.cn/intf.php?method=Share.getPublicThumbByNid&qid=108635719&nid=14671735799417092&size=800\_600&devtype=web&v=1.0.1&rtick=14671736108316&share\_qid=108635719&sign=4d07d228dcad16ae37be0eefb456c274&\[/img\]\[/align\]