データ構造とアルゴリズム実験‐(付加実験)テキスト列のハフマン符号化と復号化

テキスト列のハフマン符号化と復号化

ハフマン符号化は最も基本的な文字圧縮符号化である.テキストをハフマン符号化してから情報通信を行うことで、チャネル利用率を大幅に向上させ、情報伝送時間を短縮し、伝送コストを低減することができる.しかしながら、これは、送信側で1つの符号化システムを介して伝送データを予め符号化することを要求する.受信側では、送信されたデータを復号(復元)する.プログラムを設計し、1行の文字列(最大長さ10000文字)を入力し、ハフマン符号化を構築してください.必要に応じて(転送前に)文字テキストを符号化(文字テキストをハフマン0-1符号化に変換)するか、符号化されたデータ(受信後)を復号(0-1符号化を文字テキストに復元)するかを選択します.具体的には、(1)初期化(I):1行のテキストを読み込み、文字分布に基づいてハフマンツリーを構築し、文字のハフマン符号化(符号化と復号化に用いる)を構築し、「Huffman code established!」を出力する.(2)符号化(C):得られたハフマン符号化を用いて元の文字テキストを符号化し、出力する.(3)デコード(D):符号化後の0-1テキストをデコード(元の文字テキストに復元)、出力;(4)退出(X):終了;注意:符号化または復号時にハフマン符号化が確立されていない場合は、ヒント「Huffman code does not exist!」例:サンプル入力:I Welcome to the school of computer science and technology.C D 1100110010010010010000010001010111011100100100100100000110111011101000001001001000001011001101111010001011111001001001011111001001011011010101110100100100100101110100100100110110010010110010010010011111111101010 Xサンプル出力:Huffman code established!11011011001100100001000101101110111001001011100001101110111010000001110010000101011001101111010001000101111100011100111000111110101011101000011101101101000000111011111000100111101101110001100000110100100001010011111011111101010 Welcome to the school of computer science and technology.
注意:stringはmallocできません.newを使います.stringはmallocできない、newを使う!stringはmallocできない、newを使う!そのため、codeblocks上で実行できます.OJ上ではだめです.2日間のセグメントエラーですね.ハフマンツリーを作成する方法:1.2つの重み値が最も小さい点(重み値が同じであれば前を選択)を見つけて、この2つの点を1つのルート(ルートの重み値は2つのポイントの重み値の和)に接続し、「ルート」を元のシーケンスの最後に配置します.選択した2つの点を元のシーケンスから削除します(元のシーケンスは重複文字を削除した後の所定のシーケンスを指します).2.元のシーケンスの残りの点がルートノードとしてマークされるまで、上記の操作を繰り返します.
スペースを含む文字列を入力します.

getchar();
char c;
scanf("%c",&c);
int i=0;
while(c!='
')
{
    str[i]=c;
    i++;
    scanf("%c",&c);
    }
len=i;

完全なコードは次のとおりです.

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef queue<int> q_i;
typedef queue<string> q_s;
typedef queue<double> q_d;
typedef queue<ll> q_ll;
typedef queue<char> q_c;
typedef priority_queue<int> pq_i;
typedef priority_queue<string> pq_s;
typedef priority_queue<double> pq_d;
typedef priority_queue<ll> pq_ll;
typedef stack<int> s_i;
typedef stack<string> s_s;
typedef stack<double> s_d;
typedef stack<ll> s_ll;
typedef stack<char> s_c;
typedef map<ll,ll> m_ll_ll;
typedef map<int,ll> m_i_ll;
typedef map<string,ll> m_s_ll;
typedef map<char,int> m_c_i;
typedef map<char,ll> m_c_ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define per(i,l,r) for(ll i=r;i>=l;i--)
#define eif else if
#define N 3005
#define mm(dp) memset(dp,0,sizeof(dp))
#define mm1(dp) memset(dp,-1,sizeof(dp))
#define mm2(dp) memset(dp,0x3f,sizeof(dp))
#define IT set::iterator
#define fs(n) fixed<< setprecision(n)
#define inf 0x3f3f3f3f
const double e=2.71828182845;
const double pi = acos(-1.0);
map<char,int>mapp;
map<char,string>mapp1;
typedef struct
{
    string s1;
    int num;
}STU;
typedef struct
{
    string s1,s0;
    int num;
}STU1;
bool cmp(STU x,STU y)
{
    return x.num>y.num;
}
typedef struct node
{
    string data;
    struct node *left,*right;
}HuffmanTreeNode,*PtrHuffman;
class Haffman
{
    public:
    PtrHuffman head=NULL;
    PtrHuffman p[100005];
    void create1(int nm,STU *stu)
    {
        int u=0;
        rep(i,1,nm)
        {
            PtrHuffman t=new HuffmanTreeNode;
            t->data = stu[i].s1;
            t->left = t->right = NULL;
            p[i]= t;
        }
        rep(i,1,nm-1)
        {
            int fi=inf,se=inf;
            int fi1=0,se1=0;
            rep(j,1,nm+u)
            {
                if(stu[j].num>0&&stu[j].num<fi)
                {
                    fi=stu[j].num;
                    fi1=j;
                }
            }
            rep(j,1,nm+u)
            {
                if(stu[j].num>0&&stu[j].num<se&&j!=fi1)
                {
                    se=stu[j].num;
                    se1=j;
                }
            }
            PtrHuffman q=new HuffmanTreeNode;
            q->data=p[fi1]->data+p[se1]->data;
            q->left=p[fi1];
            q->right=p[se1];
            u++;
            stu[nm+u].s1=stu[fi1].s1+stu[se1].s1;
            stu[nm+u].num=stu[fi1].num+stu[se1].num;
            p[nm+u]=q;
            stu[fi1].num=-1;
            stu[se1].num=-1;
            head=q;
        }
    }
    void bianli(struct node *t1,int u)
    {
        if(t1==NULL)
            return;
        if(u==0)
            cout<<t1->data<<endl;
        else
        {
            cout<<u<<" ";
            cout<<t1->data<<endl;
        }
        bianli(t1->left,u+1);
        bianli(t1->right,u+1);
    }

    void bianli1(struct node *t1,char ch,string str)
    {
        if(t1==NULL)
            return;
        string s1="";
        s1+=ch;
        string ss=t1->data;
        if(ss==s1)
        {
            mapp1[ch]=str;
            return;
        }
        else
        {
            string s=t1->data;
            int len=s.size();
            int flag=0;
            rep(i,0,len)
            {
                if(s[i]==ch)
                {
                    flag=1;
                    break;
                }
            }
            if(flag==0)
                return;
            else
            {
                bianli1(t1->left,ch,str+"0");
                bianli1(t1->right,ch,str+"1");
            }
        }
    }
    STU1 bianli2(struct node *t1,string str)
    {
        if(t1->data.size()==1)
        {
            STU1 stu;
            stu.s1=t1->data;
            int len=str.size();
            stu.s0=str;
            return stu;
        }
        char ch=str[0];
        int len=str.size();
        str=str.substr(1,len-1);
        if(ch=='0')
        {
            return bianli2(t1->left,str);
        }
        if(ch=='1')
        {
            return bianli2(t1->right,str);
        }
    }
};
int len;
int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    Haffman ha;
    char str[10005];
    int uu=0;
    while(1)
    {
        char ch;
        cin>>ch;
        if(ch=='X')
            break;
        eif(ch=='I')
        {
            getchar();
            char c;
            scanf("%c",&c);
            int i=0;
            while(c!='
')
            {
                str[i]=c;
                i++;
                scanf("%c",&c);
            }
            len=i;
            string ss="";
            rep(i,0,len-1)
            {
                if(mapp[str[i]]==0)
                {
                    mapp[str[i]]=1;
                    ss+=str[i];
                }
                eif(mapp[str[i]]!=0)
                {
                    mapp[str[i]]++;
                }
            }
            int len1=ss.size();
            STU stu[10005];
            rep(i,0,len1-1)
            {
                string s0="";
                char c=ss[i];
                s0+=c;
                stu[i+1].s1=s0;
                stu[i+1].num=mapp[c];
            }
            ha.create1(len1,stu);
            cout<<"Huffman code established!"<<endl;
            uu=1;
        }
        eif(ch=='C')
        {
            if(uu==0)
            {
                cout<<"Huffman code does not exist!"<<endl;
            }
            else{
            rep(i,0,len-1)
            {
                char cc=str[i];
                ha.bianli1(ha.head,cc,"");
                cout<<mapp1[str[i]];
            }
            cout<<endl;
        }}
        eif(ch=='D')
        {
            if(uu==0)
            {
                cout<<"Huffman code does not exist!"<<endl;
            }
            else{

            string s2;
            cin>>s2;
            while(1)
            {
                if(s2=="")
                    break;
                STU1 huan=ha.bianli2(ha.head,s2);
                cout<<huan.s1;
                s2=huan.s0;
            }
            cout<<endl;
        }}
    }
    return 0;
}