这是一个创建于 4150 天前的主题，其中的信息可能已经有所发展或是发生改变。
字串例如："0001100101101110011010110010000001111010"
由0与1组成，首位可能为0，长度不定，大于64位
需要一种针对这种字串的压缩方式，可以以最节约空间的方式储存这堆字串
想听听各位的想法和意见，必定感谢！ ：）
----------------------------------------
我的想法是例如30位一切，前面补个1（防止转为整数时首位0被忽略），作为二进制字串转为十六进制整数，然后用逗号分隔累加出一个新字串
但感觉这个方式挺笨，而且压缩/解压缩的时候并不会很高效
由0与1组成，首位可能为0，长度不定，大于64位
需要一种针对这种字串的压缩方式，可以以最节约空间的方式储存这堆字串
想听听各位的想法和意见，必定感谢！ ：）
----------------------------------------
我的想法是例如30位一切，前面补个1（防止转为整数时首位0被忽略），作为二进制字串转为十六进制整数，然后用逗号分隔累加出一个新字串
但感觉这个方式挺笨，而且压缩/解压缩的时候并不会很高效
 |
1
sNullp 2013-07-12 18:58:10 +08:00  1
就是32位切存unsigned int就是咯。。
首位0有任何问题么，每个unsigned还原的时候都还原成32个字符就是了。 |
|
3
sNullp 2013-07-12 19:04:21 +08:00 1
一个简单的办法是再加一个unsigned int记录字符串总长，然后把原字符串尾部补0到32的整数。
|
 |
4
ETiV 2013-07-12 19:06:29 +08:00 1
char * zero_one = "0001100101101110011010110010000001111010";
|
 |
5
timonwong 2013-07-12 19:07:41 +08:00 1
简单的话使用Run length encoding吧，无论是速度还是压缩率都可以。更高效算法也有，要运算量或实现难度来换。
|
 |
6
andybest OP @sNullp 谢谢！ 转出来得到的多个unsigned int怎么存合适呢？像我想的那样用逗号分隔组合成一个字串？有没有更好的办法呢？
|
|
8
ETiV 2013-07-12 19:17:18 +08:00 1
..........
@andybest QQ里敲代码习惯了, 直接ctrl+回车发了出去...................没敲完啊- - |
 |
12
gracece 2013-07-12 19:29:30 +08:00 1
我本来还想说哈夫曼压缩，不过好像用不上。
|
 |
14
daoluan 2013-07-12 20:06:03 +08:00 1
如果 0 居多的话可以用 《数据库系统实现》中讲到的压缩算法。
|
 |
15
Radeon 2013-07-12 20:26:41 +08:00 1
要想取得好的压缩比必先知道目标数据的特征
如果没有特征（比如随机），那只能用2进制老老实实来编码 |
 |
16
deanguqiang 2013-07-12 20:34:16 +08:00 2
如果码流足够长并且足够随机，最简单的方法当然就是存成unsigned char 或者unsigned int之类的，没有进一步压缩的必要，并且解码也容易。如果一定要进一步压缩的话可以先8个或16 bit分组，再对组编码（比如霍夫曼），这样的话也许可以压缩的更多，不过相对的解压缩的成本也更大。
|
 |
17
clowwindy 2013-07-12 20:49:59 +08:00 1
如果是你在生产环境下遇到这样的场景，用一楼说的方法。如果你是在做作业，去研究霍夫曼吧 = =
|
 |
18
dennisyang 2013-07-12 21:55:27 +08:00 1
@clowwindy 试问这个怎么Huffman？分成N个k位的串？
|
 |
20
hewwcn 2013-07-13 16:53:46 +08:00 1
哈夫曼压缩会比直接存bit位省的吧。
|
|
21
deanguqiang 2013-07-13 17:50:18 +08:00 via iPhone 1
@hewwcn 理论上肯定有增益，但是编码前比特序列足够随机足够长的话，可以压缩的水分应该非常小，再考虑到还要存储码本，解码复杂度也高一些，在生产环境中就要考虑其必要性了
|
Select Language