关于字符串压缩的问题,难难难!!!(100分)

  • 主题发起人 主题发起人 zdy928
  • 开始时间 开始时间
Z

zdy928

Unregistered / Unconfirmed
GUEST, unregistred user!
字符串组成为A-Z 共26个英文字母,0-9数字,其他符号:. ( ) ,最多为45个不同的字符
现在由以上字符组成的字符串最长为400个字符,但是我想把这500个字符压缩成150个字符以内,大概就是一半以上的压缩率.
不知道大家有没有好方法??
我试验了好几种压缩方式,但是效果不是很理想.
最后说一下,网上能找到的压缩编码对以上情况都不实用.
现在我有个想法,原来一个字符占一个字节,怎么样编码可以实现一个字节可以代表两个字符
一个字节是0-255,我现在的字符种类才45个,把字符从0-45 进行字典对应,
理论上可以实现45/255的压缩率,就是说可以实现压缩到原长度的1/4
各位,可否?
 
给一个参考字符串:
H 41046 11010800 P2 10.5 WS 7 PD 50.5 PX 100 PM 120 Z 1512.40 ZS 5 Q 624 QS 1 ZM 1513.52 QM 849 ST 41140 11010800 P2 11.3 WS 8 PD 17.3 PX 67.0 PM 84.5 Z 382.67 ZS 6 Q 265 QS 2 ZM 383.05 QM 506 ST 41150 11010800 WS 7 PX (58.5) PM (77.0) Z 327.40 ZS 6 HS 6 Q 620 QS 3 ZM 327.66 QM 722 ST 41330 11010800 P2 20.3 WS 9 PD 29.3 PX 113.0 PM 129.3 Z 91.95 ZS 4 Q ZM 92.15 QM 667 NN

实现压缩到150个字符以内
 
呵呵，楼主的算法有点问题，压缩率并不等于255/45。
如果有255个不同的字符，就必须要用2的8次方(256)即8个bit代表一个字符。
如果只有45个不同的字符，就必须要用2的6次方(64)即6个bit代表一个字符。
压缩率 = 8/6;
并没有你原来算的那么大。
 
我有这样的想法，像楼上讲的，使用6位来表示一个字节，这样4个byte可以表示6个字符。
然后把这些数转换成16进制数，每4位二进制一个16进制数，使用16进制数字组成新的字符串，这样可以减少25％的长度。此时我们的字符串是0..9，A..F。也就是16进制的数字，如果现在再进行一次压缩，看看长度可以减少多少。按照压缩的方式，如果字母越少，压缩率应该越高。
 
如果按此思路，倒可以这样
用1..45编码替换'A'..'Z','0'..'9'...等字符。
把原来字符串替换为一个数字数组，Str: array[1..500] of Byte;
压缩算法：
11个数字为一组，11个数字的乘积作为一个压缩数，45的11次方 < 10的19方；
可以用一个Int64来保存，而一个Int64是8个字节。这样就达到压缩的目的。
 
压缩率 = 8/6;
这个压缩比还是太低啦
我想应该有其他更好的方法
我感觉还是在编码上来解决,比喻怎么用是4个字节来实现8个字符的存储(当然需要根据编码字典来转换)
go
 
难啊，如何能找出这样的编码规则，还要保证数据的准确性。关注
 
编码上解决8/6是极限值了，你不可能拿4bit来表示45个不同的字符。
只有看压缩算法上有没有比较合适的。
 
抛一块砖,希望能引些玉出来
X*Y=Z,已知Z,且X,y为质数,求 x,y.
这个方程应该能解出来吧
可惜,质数太少啦,仅17*17=289,已经超出256的范围,所以这种方法不行.
所以看能不能有一种方法是 X+y=Z,Z<256,而且x,y为固定序列中两个数,知道Z的值可以求出X,y的值来.
如果能实现这个,不就是可以压缩到1/2了吗?
 
大家再切磋切磋,希望有奇迹出现哟.
 
楼主是拍砖能手，但是上面的算法还是问题，呵呵。
1 + 9 = 10；
2 + 8 = 10；
10 + 80 ：= 90；
20 + 70 ：= 90；
所以X,Y并不是唯一的。10/16的比率是达不到的。
 
我觉得还是先编码，然后压缩。编码已经减少20％，加上压缩，或许可以达到50％。
 
能压缩到什么程度,要看你的数据类型.只有数据内含有大量的冗余数据才能被压缩.无损压缩受到冗余率的限制,是不能无限压缩的.
如果数据比较固定,那么可以使用经典的字典压缩法.
比如你可以把四个字符的组合给一个编号,如果你的数据内四个字符可能的组合不超过4亿种,那么你完全可以做到用100个编号来代替400个字符.
 
我粗略算了一下,45的4次方(四个可能的字符组合)为400万多一点.用22个位可以保存这些数据.22位替换32位,也算压缩了3分之一,离楼主的需求还有距离
 
继续努力中......
继续努力中......
继续努力中......
 
您必须登录或注册才可回复。

Similar threads

Ray
[转]终于可以发布Delphi下收点OSGI精髓皮毛而设计的插件框架WisdomPluginFramework
回复
4
查看
4K
chlkuei
C
L
字符串處理 (10分)
回复
3
查看
256
leway
L
G
字符串的拼接问题(100分)
回复
7
查看
196
lldhz
L
A
请问一个关于字符串的概念问题(0分)
回复
10
查看
256
awfigsk
A
L
字符串是以什麼結尾的。(10分)
回复
14
查看
201
leway
L
后退
顶部