Question

C++对一长度为22的数字字符串，无损压缩为16位字符串，并且可逆。有什么好的算法？

Answer 1

长度22的数字字符串表示的应该是0至10^23-1
即0到9999....9 （22个9）

一个字符串占一个字节8位，理论上最多表示2^8-1,0~255个状态，
或者说一个字节无符号整数范围是0~255

要无损压缩0至10^23-1范围内的整数，至少需要二进制77位（23/log10(2)）

你所说的16位字符串是只16个字符串把，也就是16字节，128位吧，
如果是的话，压缩还是很有冗余的，要是小于77为二进制数，就不可能无损压缩了

最简单的就是用4位二进制码表示1个十进制数
4位二进制码有16中可能，取其中的10中可能表示十进制0~1
那么每两位十进制数就用一个字节表示，22位，只需要11个字节就够了

数字字符0~9的ascii码是48~57（十六进制30~39），只保留低四位就是0~9
两个10进制数给占4位，占一个字节

压缩编码的时候，从十进制低位起，每两个数字一组（个位和十位，百位和千位.....)
（低位的ascii-48） +（高位的ascii-48）*16 获得一个字节
22位的数字，能够获得11个字节的数据，如果要16个字节的话，就有5个字节的冗余

解码的时候，从低到高获得每个字节
字节数据/16的商+48 就是高位的ascii码
字节数据/16的余数+48 就是地位的ascii码

当然乘除可以用移位运算代替，速度更快

追问

16位字符串织的是长度为16的字符串。即把长度22 -> 16 字符串。
你好，有这方面的程序吗？对位操作不是很熟悉。不剩感激。

追答

#include "stdafx.h"
#include<stdio.h>

unsigned char a[23]="798654390";
void code(unsigned char* in, unsigned char* out);
void decode(unsigned char* in, unsigned char* out);

int main()
{
unsigned char b[16];
unsigned char c[23];
printf("%s\n",a);
code(a,b);
decode(b,c);
printf("%s\n",c);
}

void code(unsigned char* in, unsigned char* out)
{
unsigned char temp[32];
int i,l=0;
for(i=0;in[i];i++)l=l++;
for(i=0;i<l;i++)temp[i]=in[l-i-1];//倒序数字串
for(;i<32;i++)temp[i]='0';//不足位添'0'补至32位
for(i=0;i<16;i++)out[i]=(temp[2*i]-48)|((temp[2*i+1]-48)<<4);//将两字节数字编码成1字节 ******
}

void decode(unsigned char* in, unsigned char* out)
{
int i;
unsigned char temp[32];
for(i=0;i<16;i++)//将1字节解码成两字节 ********
{
temp[2*i+1]=(in[i]>>4)+48;
temp[2*i]=(in[i]&15)+48;
}
    for(i=0;i<22;i++)out[i]=temp[21-i];//倒序输出低22位
out[22]='\0';//第23位补'\0'作为结束
}

这是随便写的，

输入的数字是a，存在一个长23的字符数组里（最后有'\0'终结）

编码后是b，长16的字符数组，最后没有'\0’终结,内容也是乱码，所以没有打印出来

解码后是c，长23的字符数组，22位数字（不足的前面补了'0'，加一位‘\0'终结位）

其实关键的语句就是注释中带有*******的两个for循环

一个编码，一个解码，看懂了就好