一道很难的有关算法的测试题，写逆算法
最近在学习压缩算法，刚学懂了一个压缩算法，把它加以改造，做成了一道测试题．
这道题很难，这个算法很巧．如果不知道答案，我都没有把握能做出来.
如果你自信算法方面很强，可以试一试．如果你做不出来，又想知道答案，联系我．
以下已经给出了完整的 Decode 代码，Encode 代码有几处空，填入代码，使算法工作．
这个算法可以广泛地应用于注册机，网络传输等方面．
如果你做出来了，我愿高薪聘你
#include <Windows.h>
#include <stdio.h>
class CBitEncoder
{
PBYTE m_pbuf;
UINT m_len;
UINT Prob;
UINT _cacheSize;
BYTE _cache;
UINT64 Low;
UINT uiSom;
void WriteByte(BYTE b) { m_pbuf[m_len++] = b; }
void Init()
{
Prob = (1 << 10);
Low = 0;
uiSom = 0xFFFFFFFF;
_cacheSize = 0;
_cache = 0;
}
void ShiftLow()
{
此处空１３行代码;
}
public:
void SetOutputBufPtr(PBYTE buf)
{
Init();
m_pbuf = buf;
m_len = 0;
}
int GetLength() { return m_len; }
void FlushData()
{
此处空２行代码;
}
void bEncode(UINT symbol)
{
此处空１７行代码;
}
};
//---------------以上是 Encoder 以下是 Decoder
class CBitDecoder
{
PBYTE m_psrc;
int m_srclen;
UINT uiSom;
UINT uiAny;
UINT Prob;
BYTE ReadByte()
{
m_srclen--;
return *m_psrc++;
}
void Init()
{
Prob = (1 << 10);
uiAny = 0;
uiSom = 0xFFFFFFFF;
for(int i = 0; i < 4; i++)
uiAny = (uiAny << 8) | this->ReadByte();
}
public:
void SetSrcBuf(PBYTE psrc, int srclen)
{
m_psrc = psrc;
m_srclen = srclen;
Init();
}
int GetRemainByte() { return m_srclen; }
bool bDecode()
{
bool b;
UINT u = (this->uiSom >> 11) * this->Prob;
if (this->uiAny < u)
{
this->uiSom = u;
this->Prob += ((1 << 11) - this->Prob) >> 5;
b = false;
}
else
{
this->uiSom -= u;
this->uiAny -= u;
this->Prob -= (this->Prob) >> 5;
b = true;
}
if (this->uiSom < (1 << 24))
{
this->uiAny = (this->uiAny << 8) | this->ReadByte();
this->uiSom <<= 8;
}
return b;
}
};
int Test_Encode(PBYTE psrc, int srclen, PBYTE buf)
{
CBitEncoder bitEncoder;
bitEncoder.SetOutputBufPtr(buf);
for (int i=0;i<srclen;i++)
{
BYTE b = psrc[i];
for (int j=0;j<8;j++)
{
bitEncoder.bEncode((b>>j) & 1);
}
}
bitEncoder.FlushData();
return bitEncoder.GetLength();
}
int Test_Decode(PBYTE psrc, int srclen, PBYTE buf)
{
CBitDecoder bitDecoder;
bitDecoder.SetSrcBuf(psrc, srclen);
int totallen = 0;
for (;;)
{
BYTE b = 0;
for (int i=0;i<8;i++)
{
b += (bitDecoder.bDecode() << i);
if (bitDecoder.GetRemainByte() < 0)
return totallen;
}
*buf++ = b;
totallen++;
}
return totallen;
}
void main()
{
char* psrc = "exam by LiuTaoTao 20070728";
int srclen = strlen(psrc);
BYTE buf[3000];
int len = Test_Encode((PBYTE)psrc, srclen, buf);
printf("Srclen = %d Encode len = %d \n", srclen, len);
BYTE outbuf[3000];
int len2 = Test_Decode(buf, len, outbuf);
printf("Decode len from %d to %d \n", len, len2);
if (len2 >= srclen && !memcmp(psrc, outbuf, srclen))
printf("OK\n");
else
printf("Error\n");
}
// 这种压缩算法，代码简单，速度快．最差的情况，是增长4个字节
// 还有一个缺点,就是不能很有效地判断是否已经解码结束,有时候会多解几个字节出来
