用什么方法的储存一串010101最节约空间?

2013 年 7 月 12 日
 andybest
字串例如："0001100101101110011010110010000001111010"

由0与1组成，首位可能为0，长度不定，大于64位

需要一种针对这种字串的压缩方式，可以以最节约空间的方式储存这堆字串

想听听各位的想法和意见，必定感谢！ ：）


----------------------------------------
我的想法是例如30位一切，前面补个1（防止转为整数时首位0被忽略），作为二进制字串转为十六进制整数，然后用逗号分隔累加出一个新字串
但感觉这个方式挺笨，而且压缩/解压缩的时候并不会很高效
3990 次点击
所在节点    问与答
21 条回复
sNullp
2013 年 7 月 12 日
就是32位切存unsigned int就是咯。。
首位0有任何问题么，每个unsigned还原的时候都还原成32个字符就是了。
andybest
2013 年 7 月 12 日
@sNullp 十分感谢！

如果最后一切只有比如6位而且是：000101
这样怎么处理比较妥善？
sNullp
2013 年 7 月 12 日
一个简单的办法是再加一个unsigned int记录字符串总长，然后把原字符串尾部补0到32的整数。
ETiV
2013 年 7 月 12 日
char * zero_one = "0001100101101110011010110010000001111010";
timonwong
2013 年 7 月 12 日
简单的话使用Run length encoding吧，无论是速度还是压缩率都可以。更高效算法也有，要运算量或实现难度来换。
andybest
2013 年 7 月 12 日
@sNullp 谢谢！ 转出来得到的多个unsigned int怎么存合适呢？像我想的那样用逗号分隔组合成一个字串？有没有更好的办法呢？
andybest
2013 年 7 月 12 日
@ETiV 谢谢，请问这个*号是什么意思？在java语法里是什么？
ETiV
2013 年 7 月 12 日
..........
@andybest QQ里敲代码习惯了, 直接ctrl+回车发了出去...................没敲完啊- -
andybest
2013 年 7 月 12 日
@timonwong 非常感谢！这种编码非常合适！ +10086
ETiV
2013 年 7 月 12 日
@andybest C指针~
andybest
2013 年 7 月 12 日
@ETiV 这样转换后，zero_one变量结果是啥？
gracece
2013 年 7 月 12 日
我本来还想说哈夫曼压缩，不过好像用不上。
ETiV
2013 年 7 月 12 日
@andybest 这不是转换啊亲= =

还没写完呢就发出去了
daoluan
2013 年 7 月 12 日
如果 0 居多的话可以用 《数据库系统实现》中讲到的压缩算法。
Radeon
2013 年 7 月 12 日
要想取得好的压缩比必先知道目标数据的特征

如果没有特征（比如随机），那只能用2进制老老实实来编码
deanguqiang
2013 年 7 月 12 日
如果码流足够长并且足够随机，最简单的方法当然就是存成unsigned char 或者unsigned int之类的，没有进一步压缩的必要，并且解码也容易。如果一定要进一步压缩的话可以先8个或16 bit分组，再对组编码（比如霍夫曼），这样的话也许可以压缩的更多，不过相对的解压缩的成本也更大。
clowwindy
2013 年 7 月 12 日
如果是你在生产环境下遇到这样的场景，用一楼说的方法。如果你是在做作业，去研究霍夫曼吧 = =
dennisyang
2013 年 7 月 12 日
@clowwindy 试问这个怎么Huffman？分成N个k位的串？
sNullp
2013 年 7 月 12 日
@andybest 爱怎么存怎么存啊。。你一定要存到char[]里？那就按8bit分呗。
hewwcn
2013 年 7 月 13 日
哈夫曼压缩会比直接存bit位省的吧。

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://v2ex.ih06.com/t/75589

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX