不是。。。这说明霍夫曼编码对于大量连续重复的内容，压缩效率不行？ <- 中国开发网

CNDEV.ORG

当前在线

论坛

CBD
- 程序员情感CBD
- 程序员见面交流会
CBD开发区
- Java/J2ME
- .NET/C#
- 数据库
- Delphi/BCB
- Visual C
个人
- 袁国术的个人网站
- 翟旭东网!!!
其它
情感
游戏
- CNDEV-CS/WOW
- 浩宇长空
生活
论坛系统

中国开发网: 论坛: 程序员情感CBD: 贴子 155172

haitao：

不是。。。这说明霍夫曼编码对于大量连续重复的内容，压缩效率不行？

[阅读: 709] 2005-06-28 03:52:25

霍夫曼最高的压缩率也就是8倍了！！！因为它是直接拿编码去替换，
没有不知道靠记录重复次数而达到压缩的效果。。。

相关信息:

我的加密算法做到完全扩散（影响）、混乱度接近随机数了 (31782字) (haitao [55115] 2005-06-27 15:27)
- 从这个测试压缩率用的随机数文件的实际压缩率引出一个问题 (8424字) (haitao [1091] 2005-06-27 15:50)
  - 哈哈哈哈 (8字) (GoodHope [751] 2005-06-27 16:21)
    - 你们两人在一个公司，还是就是一个人？！ (9字) (haitao [696] 2005-06-27 16:27)
  - 哈哈哈。。。 (25字) (JoJo [739] 2005-06-27 16:23)
    - 上次问你有没有工具，你又说没有。。。 (14字) (haitao [758] 2005-06-27 16:26)
  - 1/3是真正的信息量 (37字) (haitao [758] 2005-06-27 16:32)
    - 那我问你 (18字) (JoJo [830] 2005-06-27 16:34)
      - 空格这么有规律的重复出现。。。 (70字) (haitao [690] 2005-06-27 16:40)
        haitao版本的哈夫曼编码吧 (13字) (JoJo [880] 2005-06-27 16:46)
        这个编码的原则不正是这样的吗？ (56字) (haitao [672] 2005-06-27 17:53)
    - 你知道其中1/3的信息是有用的，可怜的压缩软件怎么知道啊。 (空) (GoodHope [569] 2005-06-27 16:35)
      - 大学时应该学过香农的信息学方面的章节吧。。。 (24字) (haitao [727] 2005-06-27 16:47)
        压缩算法怎么知道原始的信息是怎样的？对于压缩算法，输入的所有信息都是有效的。 (55字) (GoodHope [811] 2005-06-27 16:54)
        不是不必要，而是重复。。。压缩算法只知道是不是重复，而不知道是不是必要 (81字) (haitao [792] 2005-06-27 17:56)
    - 那你改成这样是不是压缩率要到1/5啊 (119字) (GoodHope [769] 2005-06-27 16:38)
      - 不用，多加两个空格就行了，加99个空格，压缩率就是100:1 (空) (JoJo [790] 2005-06-27 16:40)
        依海涛大师的说法,俺也是这第认为. (空) (oyjt [712] 2005-06-27 16:42)
      - 既然是定格式填充，那么填充的数据不用空格也完全是可以的。这样更好 (63字) (GoodHope [970] 2005-06-27 16:42)
        填充的数据不用空格，但也必须是相同的字符嘛 (28字) (haitao [741] 2005-06-27 16:45)
        1字节的数据后面放1M - 1个空格，这样压缩率就应该是1ppm吧？ (空) (GoodHope [794] 2005-06-27 16:50)
        难道不是这样的？ (62字) (haitao [656] 2005-06-27 17:50)
        你试一下不就知道了 (空) (JoJo [645] 2005-06-27 17:57)
        唉，这么简单的事情还要试？？看在你Jojo以往帖子，试了一个跟500个字符的 (16764字) (haitao [663] 2005-06-27 18:06)
        再提醒你一下吧 (65字) (JoJo [738] 2005-06-27 18:03)
        看你的样子不像开玩笑。。。那是不是我们理解的不一样？？ (34字) (haitao [704] 2005-06-27 18:08)
        你要讨论压缩，至少要有一点这方面的理论基础，凭空想象有什么意义呢？ (空) (JoJo [795] 2005-06-27 18:15)
        凭空想象，而且想错了，还以为别人错了的是你们俩吧。。。 (69字) (haitao [870] 2005-06-27 18:21)
        坑灰未冷山东乱，haitao原来不读书啊 (191字) (JoJo [879] 2005-06-28 09:42)
        书的确只是10多年前读的。。。所以熵的引用不一定恰当，只是记得是一个有效信息的意思 (327字) (haitao [1014] 2005-06-28 10:45)
        汗吖。你这个是特例。而且需要特定的专门针对你这种数据的算法。给两段代码你看看。 (空) (ycm0263 [768] 2005-06-27 18:21)
        Lzrw 算法 (7400字) (ycm0263 [1041] 2005-06-27 18:22)
        Lzw 算法 (8823字) (ycm0263 [930] 2005-06-27 18:25)
        你也这么说？我只是说goodhope的做法。。。（争论总结） (503字) (haitao [802] 2005-06-27 19:18)
        你的理论就是错的，而且错得很离谱。压缩算法是知道有重复，所以才能压缩。 (146字) (GoodHope [1112] 2005-06-27 21:03)
        看来你没理解错。。。我的3:1当然是理论值 (322字) (haitao [795] 2005-06-27 21:12)
        你这个理论就是错的，还我理解了 (68字) (GoodHope [776] 2005-06-27 21:52)
        已经假设伪随机数是无法压缩的了。。。如果你知道压缩是通过一个编码表来实现的话，你就真的理解了 (1195字) (haitao [1117] 2005-06-27 22:14)
        随机数序列也是算出来的，你的序列也是算出来的。为什么随机数序列不能压缩，你认为正常，而你的序列却认为正常。 (40字) (GoodHope [921] 2005-06-27 22:35)
        刚才计算了一下，理想的压缩率应该是2.181818.... (1394字) (haitao [0] 今天 22:49) (14字) (haitao [687] 2005-06-27 22:50)
        你走极端了。。。从伪随机数反推函数和种子的难度和从字符出现的概率直接编码压缩的难度可以相比吗？ (64字) (haitao [1649] 2005-06-27 23:39)
        是啊，我们都走极端了，还是海涛老师始终保持清醒。 (7字) (GoodHope [717] 2005-06-28 09:11)
        说实话，我很讨厌这样的做法 (219字) (haitao [678] 2005-06-28 09:26)
        对于RAR的结果，没什么好说的。 (71字) (GoodHope [744] 2005-06-28 09:33)
        如果只是这一点，倒是范围小了很多 (204字) (haitao [759] 2005-06-28 09:40)
        压缩率为3的论断已经不仅仅是好笑了。 (28字) (GoodHope [703] 2005-06-28 09:48)
        压缩率为3 本来也只是理论值。。。另外，它的熵是不是3呢？ (104字) (haitao [803] 2005-06-28 10:00)
        winrar的实际压缩率已经接近理论值了，说明"XX "其实已经被rar“识别”出来了 (78字) (haitao [973] 2005-06-27 23:00)
        你的理论值是后来的2.1818……还是3啊 (空) (GoodHope [710] 2005-06-28 09:38)
        如果只是这个错误，需要这么夸张吗。。。忘了霍夫曼编码的压缩率是不是就是熵呢？ (58字) (haitao [910] 2005-06-28 09:42)
        我靠，压缩率是压缩率，熵是熵！风马牛不相及的事情！ (12字) (GoodHope [828] 2005-06-28 11:41)
        用词可能不当。。。 (15字) (haitao [669] 2005-06-28 11:57)
        说了，你那个是特例。 (42字) (ycm0263 [713] 2005-06-27 22:00)
        3:1是极限，不用专门的针对性压缩算法，只要霍夫曼编码。。。 (122字) (haitao [876] 2005-06-27 22:17)
        我并不是要搞一个压缩算法。。。而是借助rar来验证我的加密算法。。。（沟通真的成问题） (325字) (haitao [885] 2005-06-27 19:26)
        好的通用压缩算法（如rar），可以“硬性、盲目”压缩而达到接近“专用”算法的效果 (142字) (haitao [1450] 2005-06-27 23:30)
        你要想看大压缩率的话，试试 7ZIP. (空) (ycm0263 [873] 2005-06-28 09:21)
        我的实际应用，lzw也就够了。。。我是指出：好的通用压缩算法（如rar），可以“硬性、盲目”压缩而达到接近“专用”算法的效果 (199字) (haitao [1227] 2005-06-28 09:33)
        反例不用偶去举，你自己已经举了。 (100字) (ycm0263 [824] 2005-06-28 10:01)
        我的例子是证明压缩率在数量级上接近理论值了 (8字) (haitao [693] 2005-06-28 10:15)
        可是你那个例子的结果符合你的结论么? (空) (ycm0263 [655] 2005-06-28 10:51)
        －－结果大约是100多倍！理论上应该能到500倍。。。 (402字) (haitao [691] 2005-06-28 11:14)
        看来要么RAR算法有问题，要么你的理论有问题。 (空) (GoodHope [769] 2005-06-28 11:20)
        不是。。。这说明霍夫曼编码对于大量连续重复的内容，压缩效率不行？ (56字) (haitao [708] 2005-06-28 11:52)
        这说明 (13字) (ycm0263 [717] 2005-06-28 12:28)
        霍夫曼编码的压缩率可能离理想的压缩率还是比较远的。。。 (3024字) (haitao [7] 昨天 23:23) (15字) (haitao [774] 2005-06-28 12:33)
      - 信息量是1/5 (78字) (haitao [648] 2005-06-27 16:43)
        如果原始数据可以压缩，加密后的数据是否也应该有类似的压缩率呢？信息量是一样的嘛…… (20字) (GoodHope [790] 2005-06-27 16:46)
        呵呵，这是最典型的问题。。。告诉你原因吧 (89字) (haitao [746] 2005-06-27 18:00)
  - 免费普及了。。。信息熵 (1510字) (haitao [945] 2005-06-27 18:19)
  - 倒。。。。。 (9字) (变废为宝 [667] 2005-06-27 20:47)
    - 三人成虎。。。 (135字) (haitao [664] 2005-06-27 20:50)
      - 我是菜鸟，饶了我吧 (空) (变废为宝 [625] 2005-06-27 22:39)
        唉，其实错了不要紧，最怕自己错了却反指对方错了。。。 (21字) (haitao [720] 2005-06-27 22:54)
  - 刚才计算了一下，理想的压缩率应该是2.181818.... (1394字) (haitao [1610] 2005-06-27 22:49)
    - winrar的实际压缩率只有：8320:3976，即大约2.1:1 (44字) (haitao [715] 2005-06-27 22:51)
      - 霍夫曼编码的压缩率可能离理想的压缩率还是比较远的。。。 (3024字) (haitao [1590] 2005-06-27 23:23)
- 。。 (空) (zengr [577] 2005-06-27 15:51)
- 牛啊，全球那么多数学家没有做到的事情，海涛做到了！ (空) (GoodHope [722] 2005-06-28 09:36)
  - 又来了。。。你嘲讽的到底是哪一件事情？ (92字) (haitao [740] 2005-06-28 09:46)
    - 我以为…… (17字) (没脾气2x [580] 2005-06-28 10:27)
      - 纯属巧合。。。 (21字) (haitao [691] 2005-06-28 10:34)
- 恭喜呀！快写成论文发表吧，说不定能混个图灵奖啥的！ (空) (zhenghj [729] 2005-06-28 09:45)
  - 又来一个瞎起哄的。。。完全扩散（影响）、混乱度接近随机数，是加密算法的基本要求啊。。。 (128字) (haitao [691] 2005-06-28 09:51)
    - 嗬嗬，还用看你的数据吗？ (8字) (老玉米 [710] 2005-06-28 09:56)
      - 这个最牛。 (空) (ycm0263 [633] 2005-06-28 10:03)
      - 又变成这样了 (10字) (haitao [668] 2005-06-28 10:03)
        我错了，其实我不懂加密算法理论。 (空) (老玉米 [729] 2005-06-28 10:14)
    - 满足这些条件有P用 (62字) (GoodHope [718] 2005-06-28 10:06)
      - 你怎么知道我的算法的强度一定要超过或接近DES？。。。为什么只有3组是高强度的？莫非你真的知道？？ (233字) (haitao [834] 2005-06-28 10:22)
        自己用，只要别人不知道算法就很难破了。何苦要做到雪崩效应。 (62字) (GoodHope [783] 2005-06-28 10:50)
        就是要让潜在的尝试者吓一跳 (38字) (haitao [752] 2005-06-28 10:55)
        那还不如自己做个码表转换一下，再DES一下。 (空) (GoodHope [730] 2005-06-28 11:03)
        那没有用的。。。DES只能混乱同组的，那就要求你的码表能实现完全混乱 (37字) (haitao [755] 2005-06-28 11:22)
        这个是很简单的东西了，随便搞一个动态的码表就可以做到。 (空) (GoodHope [807] 2005-06-28 11:31)
        以前做过一个这种动态码表的，现在不想用它 (50字) (haitao [680] 2005-06-28 11:46)
        你的动态码表，是指动态产生吧。偶的动态码表指的码表在使用过程中不断的变化。 (空) (GoodHope [676] 2005-06-28 11:48)
        只有分组加密才有雪崩效应的要求，不分组谈什么雪崩。 (空) (GoodHope [863] 2005-06-28 11:51)
        又武断了。。。一般的分组是指8byte或其它固定长度的分组吧 (39字) (haitao [763] 2005-06-28 12:32)
        什么叫武断，密码学上就是这样的。 (32字) (GoodHope [870] 2005-06-28 12:51)
        密码学要分组混乱是有它的原因的。。。我的算法的确做到了（当然也是有特定的限制条件的） (103字) (haitao [901] 2005-06-28 13:02)
        我驽钝，以我掌握的有关加密的知识，实在是无法理解你的话了。 (42字) (GoodHope [710] 2005-06-28 14:02)
        是啊。。。限制条件就是整个包不大于10K！ (16字) (haitao [655] 2005-06-28 14:22)
- 呵呵，把两个只差一个字符的长字符串，用一个密钥加密 (13字) (老玉米 [710] 2005-06-28 09:49)
  - 好，这才是讨论问题嘛。。。不过，我贴的不是有吗？ (161字) (haitao [750] 2005-06-28 09:55)
    - 你要是真的对密码学有一些了解，就不会去用这个来验证自己的算法。 (16字) (GoodHope [824] 2005-06-28 09:59)
      - 你们这样大起大落的预想别人，平时怎么能沟通好呢？！。。。我的本来就是一个很简单、弱智的自用算法。。。所以先用这2个要求来否定一下 (341字) (haitao [700] 2005-06-28 10:13)
        我错了，其实我不懂加密算法理论。 (空) (老玉米 [0] 今天 10:14) (空) (GoodHope [677] 2005-06-28 10:19)
        又来了。。。为什么只有3组是高强度的？莫非你真的知道？？ (42字) (haitao [703] 2005-06-28 10:25)
        嘿嘿，不知道归不知道。可不是经验结果。 (空) (GoodHope [691] 2005-06-28 10:49)
        我只是看到长贴忍不住要顶 (23字) (老玉米 [648] 2005-06-28 10:24)
        真的搞一个经得起外部检验的加密算法是很困难的。。。我要的只是一个自己的系统里可能用的 (168字) (haitao [782] 2005-06-28 10:30)
        JoJo说的加密强度是另一码事了。 (15字) (GoodHope [743] 2005-06-28 10:54)
        是纯数学的，【不知道归不知道。可不是经验结果。】 (空) (haitao [710] 2005-06-28 11:25)
        哦，我以为你要推翻WinRAR (7字) (JoJo [620] 2005-06-28 10:41)
        我是不管什么压缩算法、工具，只是拿它分别压缩我的密文和伪随机数，作对比 (134字) (haitao [781] 2005-06-28 10:51)
        我只能说：“强！真的狠强！” (6字) (GoodHope [635] 2005-06-28 10:58)
        又变成这样了 (10字) (haitao [8] 今天 10:03) (空) (haitao [665] 2005-06-28 11:26)
  - 这个只是必要条件，不是充分条件。满足这个条件不能说明什么问题，不满足到能说明一些问题。 (空) (GoodHope [786] 2005-06-28 09:57)
    - 本来就不说明什么问题，只是说明我的算法满足了这2个要求。。。 (58字) (haitao [670] 2005-06-28 10:33)
- haitou兄，我脚得你有点误入歧途了，在开发中不应该在自己比较陌生的领域浪费时间，当然如果你本来就做这个研究的例外。专业的事让专业的淫来做，你应该采用个现成的成熟算法就好。 (空) (Yxd [699] 2005-06-28 10:55)
  - 非也非也，你说的是公司的目标 (38字) (老玉米 [639] 2005-06-28 11:00)
    - 对程序员来说，这种实验太难了吧。 (33字) (JoJo [780] 2005-06-28 11:10)
      - 研究这个，我还不如睡觉 (空) (kevincsg [649] 2005-06-28 11:11)
      - 所以说你的目标一上来就是很高，自然就没什么好作的了 (149字) (haitao [809] 2005-06-28 11:19)
        这个我也同意 (39字) (JoJo [766] 2005-06-28 11:25)
        只是借助理论作为淘汰的2个关卡而已 (38字) (haitao [650] 2005-06-28 11:29)
        我只能告诉你 (34字) (JoJo [667] 2005-06-28 11:36)
        这2个要求怎么会错呢。。。 (84字) (haitao [939] 2005-06-28 11:49)
    - 嗯，眉笔，我也常工作的时候整自个儿感兴趣的事。。 (空) (Yxd [688] 2005-06-28 11:12)
    - 非也，现在在这里等会议，所以。。。 (9字) (haitao [600] 2005-06-28 11:23)
  - 中国的程序员就是要什么都干的。。。 (74字) (haitao [755] 2005-06-28 11:31)
- 高楼，又见高楼。 (空) (疯子张 [624] 2005-06-28 11:33)
  - 不顶不蒜好汗、、、、 (空) (C007 [660] 2005-06-28 12:54)
  - 无奈啊，看这棵树能多高 (6字) (jacky1936 [735] 2005-06-28 13:45)
    - 你是用pda上网的？ (空) (haitao [714] 2005-06-28 13:47)
    - 那你记得多踩几脚了。 (空) (ycm0263 [688] 2005-06-28 13:52)

欢迎光临本社区，您还没有登录，不能发贴子。请在这里登录

页面内容处理时间: 0.021 - 814688