motionLib/Huffman.cpp at master · songtianyi/motionLib · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include "Huffman.h"

CHuffman::CHuffman()
{
    //ctor
}

CHuffman::~CHuffman()
{
    //dtor
}


void CHuffman::heapsift(int i)
{
    int l=i<<1;
    int r=(i<<1)+1;
    int least=i;
    if(l<=heapCnt && heap[heap[l]]<heap[heap[least]])
    {
        least=l;
    }
    if(r<=heapCnt && heap[heap[r]]<heap[heap[least]])
    {
        least=r;
    }
    if(least!=i)
    {
		//exchange index
        heap[i]^=heap[least];
        heap[least]^=heap[i];
        heap[i]^=heap[least];
        heapsift(least);
    }
}

void CHuffman::simulate(const int *m_nFreqArray)
{

    int la,lb;
    for(int i=0; i<HUFF_S_LEN; ++i)
    {
        heap[i+HUFF_S_LEN+1] = m_nFreqArray[i];
        heap[i+1]=i+HUFF_S_LEN+1;
    }

    heapCnt=HUFF_S_LEN;
	//little heap
    for(int i=heapCnt/2; i>=1; --i)
    {
        heapsift(i);
    }
    while(heapCnt>1)
    {
        la=heap[1];
        heap[1]=heap[heapCnt];
        heapCnt--;
        heapsift(1);
        lb=heap[1];
		//la lb minium value index
        heap[heapCnt+1]=heap[la]+heap[lb];
		//
        heap[1]=heapCnt+1;
        heap[la]=heapCnt+1;
        heap[lb]=heapCnt+1;
        heapsift(1);
    }
}

void CHuffman::generate()
{
    for(int i=1; i<=HUFF_S_LEN; ++i)
    {
        int temp=heap[i+HUFF_S_LEN];
        int len=1;
        while(temp!=2)
        {
            temp=heap[temp];
            len++;
        }
        m_DicArray[i-1].length=len;
    }
    memset(len,0,sizeof(len));
    for(int i=0; i<HUFF_S_LEN; ++i)
    {
        m_DicArray[i].code=len[m_DicArray[i].length];
        len[m_DicArray[i].length]++;
    }
    //cal first
    first[HUFF_S_LEN+1]=0;
    for(int i=HUFF_S_LEN; i>0; --i)
    {
        first[i]=(first[i+1]+len[i+1]+1)/2;
    }
    //cal code
    for(int i=0; i<HUFF_S_LEN; ++i)
    {
        m_DicArray[i].code=m_DicArray[i].code+first[m_DicArray[i].length];
    }
}