跪求数字压缩算法

Question

背景：

身份证号码的前 17 位,是数字类型的字符串：比如 "53010119870615158", 现在书写的时候占了 17 个字符, 有没有办法将其压缩短一些，比如 10 位之类的。

需求:

1. 可以采用十六进制, 或者 10 进制, 或者数字和字母的组合
2. 不易区分的数字字母除外, 比如: I 和 1， O 和 0 .
3. 需要生成的新字符, 可以转换为原来的值(即无损).
4. 需要有稳定的生成的位数，可以在最开始补 0 之类的。

请各位大神提供解决方案，或者思路，或者链接都可以。

Answer 1

先从理论上计算一下：

0-9 共 10 个数字，表示 17 位字符串，一共是 10^17 个。

ASCII 码中的可显示字符一共是 96 个，除去那些容易混淆的。

• 我们使用数字 1，不使用 l、I，使用数字 0，不是有 O（小写的 o 应该没有问题，可以使用）
• 我们使用单引号 '，不使用 ```（键盘最左上角），为了保险起见我们连双引号 " 也不使用了

这样一共还剩 96-5=91 个。（PS：小数点和运算符号 +-*/ 会不会引起混淆啊？）

因为 10^2 等于 100，比 91 要大，因此，理论上字符串长度无法缩小一半。

计算 log(10^17)/log(91) 得到 8.67771353205 因此，17 位长度的字符串可以缩短为 9 位的长度。

*********** 分割线 ****************

还能不能压缩的更短呢？

当然可以。

得换个思路：我们从信息论的角度考虑，这个字符串所携带的信息远没有它表示的那么多，冗余太大了。

@felix021 大大也太快了吧。本来打算下午谢谢身份证的格式，发现 felix021 已经写了。http://segmentfault.com/q/1010000000332003#a-1020000000332093

******* 再次更新 ********

我的第一个算法把长度压缩到了 9 位，第二个算法没写完，被 @felix 大大抢先了，结果他压缩到了 6 位，OMG，直接导致题主采纳了他的回答。（本来题主已经采纳我的了）

于是，心有不甘，那我就再接再厉，把这个号码压缩到 5 位。哈哈哈哈哈！

众所周知，身份证是国人的一个代码，那么中国有多少人呢？我们姑且以 20 亿来计算。那么我们的问题就变成了，如何用最短的字符串表示 2000000000 个字符串呢？

回到第一个算法，我们找到了可以显示的 91 个 ascii 字符。OK。那么我们再计算一个公式

og(2000000000)/log(91) = 4.747745520907

可见，我们如果用 6 位来表示的话，应该有点儿浪费，其实，5 位就绰绰有余了。

通过计算我们还可以算出，用 5 位的 91 个字符，可以表示 91^5 = 6 240 321 451 个字符串，62亿多，当前全球才 70 多亿的人口。所以全中国的身份证压缩到 5 位是绰绰有余的。

==OVER

Answer 2

补充几点：

居民身份证号码，根据〖中华人民共和国国家标准 GB 11643-1999〗中有关公民身份号码的规定，公民身份号码是特征组合码，由十七位数字本体码和一位数字校验码组成。排列顺序从左至右依次为：六位数字地址码，八位数字出生日期码，三位数字顺序码和一位数字校验码。 居民身份证是国家法定的证明公民个人身份的有效证件

1. 6位地址码并没有用到完整的000000-999999, 虽然编码规则比较复杂，但是网上可以找到完整的列表，不超过4000条。

2. 生日占了8位，但是实际上完全不需要这么多。假定中国最老的人也是20世纪的，那么可以用从1900年1月1号开始的天数来记录，用16bit整数就可以差不多把2080年前的生日都表示完了。

3. 最后一位是校验码， 可以直接省略掉。

所以可以把信息先映射到 [0, 4000 * 1000 * 2^16) （262,144,000,000，减少了5.x个十进制位）， 然后再压缩，按照@justjavac的编码方法，应该可以压缩到6位以内。

Answer 3

楼上各位都是比较理论化的，我就来个实用的吧。由于 lz 没说用什么语言，就用 Java 吧：

import java.math.BigInteger;
BigInteger bi = new BigInteger("53010119870615158");
System.out.println(bi.toString(36));

输出：ehyiovm88dy

思路：把这个数转换成 36 进制。因为，原来的 10 进制，每位只有 0 - 9 这 9 种状态，36 进制中每位有 0-9A-Za-z 36 种状态，每位利用率高了，所以所需的位数就短了。

还原的话可以用 new BigInteger(String, int radix)

其他语言，只要有高精度运算库的都可以这么做。