谁有招把这个小数组用最小的容量保存一下
高人们，谁帮我把这个数据用最小的容量保存一下由于要应用区间编码，需要保存一个头部统计数据（与题无关，仅供参考）
数据为一个ascii码和其对应的概率浮点数。
比如用php表示
[php]
$arrProbabilities=array(
....
'a'=>0.1,
'b'=>0.5,
'c'=>0.1
....
'y'=>0.001
'z'=>0.003
...
);
[/php]
共有256个(0-255)这样的符号，他们对应的浮点数概率的总和为1.
现在的疑难是，[b]如何设计一个格式，以最小的空间保存这个数据[/b]？
比如我想到的:
以32bits浮点数表示一个数据，所用空间就是32*256=8192b=1KB的空间。
但这1K已经过大了，遇到对应的数据如果只有几十个字节，头部却加个1KB。几万条数据就加几万KB。
浪费会很严重。
再说明一些事项：
-- 字符集不一定是全满256个，也可能是3个，5个，200个，在[0,255]之间。
-- 浮点精度要求不是很高，所以对浮点数能用16位左右的精度也能接受。
-- 最后容量最好能比1K少。
-- 尽量不用其他压缩算法，只从设计或技巧上入手。因为这已经是一套算法的头部，再套一个压缩算法就很废神了
ps:
拜托拜托，我已经绞尽脑汁了。如果大家目前也没有好招，能否指一个方向
或相应的书籍的章节，我能去自学也行。个人感觉是和数据存储结构设计有关，可回扫过自己有限的“数据结构”知识，也是没有找到灵感。
请高人指个方向，能具体到章节或者技术点最好！~
[[i] 本帖最后由 imkow 于 2008-10-19 10:28 编辑 [/i]] 如果浮点数都在0.001以上（或者说最小单位是0.001）的话
这样做可能可以小一些
理论上共1000 bit
对楼主的例子来说：
a (99个0)
00...01
b(499个0)
00...01
c(99个0)
00...01
y
1
z
001
把上面全部连起来。大小共1000 bit( 因为最小单位是0.001，总和为1，所以共1000个)， 1000bit / 8 = 125byte
so ~~ 读取的时候，转成字符串, explode ('1' , $string)，然后对获取到的数组每个元素操作 ：字符串长度+1 / 1000 ，即为概率……
最近表达能力急剧下降，不知道LZ看懂了没…… 又或者……可以做一个简化的浮点的实现~~
首先，去掉小数点变成Int，16bit = 65536，够用了吧？
然后，把第一个有效数字离小数点的位数记录下来，8位的浮点数，也就是8么~ 3bit搞定……
这样一个概率记录也就 16 + 3 = 19bit * 256 = 4864 bit = 608 byte
略少一些~ 先多谢！
2楼中的方法：数据精度可能高出3位小数，至少也要5-8位吧。没有完全看懂，我感觉也是一种熵方法。目前我没有把握能够用好。
3楼中的方法：似乎合用。以前ms-dos版的c编译器的浮点也是16位，精度够了。如果用php写，就差手工实现一个16位浮点。还要回头想想固定位浮点数的转换。因为数据都是0.xxxx，小数点是固定的话，还可以省去符号位和小数位。多谢！我看来要去都督16位的一些具体实现了
[[i] 本帖最后由 imkow 于 2008-10-19 10:41 编辑 [/i]] 你根本不应该考虑容量问题，你这个可能用文件存储是最好的方法。 [quote]你根本不应该考虑容量问题，你这个可能用文件存储是最好的方法。[/quote]
也许你根本看不懂我在问什么。
[del]需要指出来吗？问题是针对数据，精确到位bit的数据。文件都是和操作系统相关的更高级概念，而数据放在哪里——文件？内存？纸片？也是都应用的问题，（也许从概念层面和从人的知识层面都）“不是一个级别的”。先从环境无关的数据层面考虑吧[/del]
[[i] 本帖最后由 imkow 于 2008-10-19 08:25 编辑 [/i]] [quote]原帖由 [i]imkow[/i] 于 2008-10-19 08:03 发表 [url=http://www.phpchina.com/bbs/redirect.php?goto=findpost&pid=659120&ptid=84964][img]http://www.phpchina.com/bbs/images/common/back.gif[/img][/url]
也许你根本看不懂我在问什么。
[del]需要指出来吗？问题是针对数据，精确到位bit的数据。文件都是和操作系统相关的更高级概念，而数据放在哪里——文件？内存？纸片？也是都应用的问题，（也许从概念层面和从人的 ... [/quote]
先考虑需求，再考虑解决方案，不一定存储空间越小是好的方案，解决问题我感觉你没必要在存储空间上吊死的。换个方法可能对你来说更好。 先考虑实现，后考虑优化。 [quote]先考虑实现，后考虑优化。[/quote]
没看题目中间我已经说过一个占1KB的“实现”了，所以来问优化的可能
需求是“减小一个压缩算法的头部”。怎么去拿应用层的东西去优化好呢？
ps:
子曰：知之为知之，不知为不知，是知也
[[i] 本帖最后由 imkow 于 2008-10-19 10:38 编辑 [/i]] [quote]原帖由 [i]imkow[/i] 于 2008-10-19 10:25 发表 [url=http://www.phpchina.com/bbs/redirect.php?goto=findpost&pid=659178&ptid=84964][img]http://www.phpchina.com/bbs/images/common/back.gif[/img][/url]
没看题目中间我已经说过一个占1KB的“实现”了，所以来问优化的可能
需求是“减小一个压缩算法的头部”。怎么去拿应用层的东西去优化好呢？
ps:
子曰：知之为知之，不知为不知，是知也 [/quote]
这种问题根本不用多想。10M变成5M意义也不大。 [quote]这种问题根本不用多想。10M变成5M意义也不大。[/quote]
我建议删除那些“不该这么做，不用想，不该这么做”的废话回复，
没有什么现实意义，如果你真有法变10M成5M，那我还佩服
帖子发在“高级区”，原本不打算给那些不求甚解、敷衍了事的XX来灌水的，建议到初级区去宣传那些观点呀。
请原谅我的passive-agressive的口气呢，个人有点这方面的精神病。
大家看我首贴的长度和描述细节就该知道我对这个问题的认真态度呀。
请不要“无用论”来折磨我的耐心。 很明显需要以时间换空间。
对这个特殊问题来说：
将系统的类型占有的空间是固定的，在表示做一些手脚。
1. 提升进制 可以减少存储
0.1234 => 1234 => 16进制 ‘4D2’
2. 科学计数 减少化成整型的0的存储
0.5 => 500000 =>‘5,6’ 形如这个可以进一步减少 56，去掉分割符,或者再采用一个数组记录小数点分数
0.00001 => 10 =>‘1,2’ 同上 12
0.000045 => 45 =>45
3. 进一步，特殊的概率数值，以及分布 采用10进制数
0.1 1 1 1
0.5 5 *10^index 50 1
0.003 3 300 3
0.02 2 2000 2
如此上四条 2351 1132
/** 这里存为整型，不考虑溢出的话，可以存储10条记录*/
256 * 64 / 10 = 最乐观的就这么多位就够了 (256 * 8 / 10) 优于 256*4
4. 进一步通用化的方法，自己思考一下吧。
tips: 1. 如何记录非一位数值?
2. 如何避免溢出?
具体算法要看，概率数值的规律，概率空间的分布等等。理论上能减少多少存储，需要用数学方法去计算出来。
其实这些也算是一种简单的特殊的压缩算法了。
可以与通用压缩算法比较，看看最终的存储哪个花费少。
End 如果LZ精度要求不高的话, 研究一下浮点的数据表示, 试试去掉一些没用的位, 如指数位(都是小于1的数, 指数位没有用), 减小精度, 用更少的位静态浮点数.
页:
[1]