热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

如何重新设计霍夫曼树节点的权重,使得权值尽可能小(整数),而且根据新权值生成的霍夫曼树和原树完全一致?

如何重新设计霍夫曼树节点的权重,使得权值尽可能小(整数),而且根据新权值生成的霍夫曼树和原树完全一致?如果可能的话,n个原始数据生成的2n-1个节点的树会不会有个权值上限A?即重新生成的权
如何重新设计霍夫曼树节点的权重,使得权值尽可能小(整数),而且根据新权值生成的霍夫曼树和原树完全一致?


如果可能的话,n个原始数据生成的2n-1个节点的树会不会有个权值上限A?即重新生成的权值不可能会大于这个数A?

16 个解决方案

#1


pu

#2


我看了半天也不太明白你的意思,可否将你的问题说得再详细一点,
================================================================

CSDN 论坛助手 Ver 1.0 B0402提供下载。 改进了很多,功能完备!

★  浏览帖子速度极快![建议系统使用ie5.5以上]。 ★  多种帖子实现界面。 
★  保存帖子到本地[html格式]★  监视您关注帖子的回复更新。
★  可以直接发贴、回复帖子★  采用XML接口,可以一次性显示4页帖子,同时支持自定义每次显示帖子数量。可以浏览历史记录! 
★  支持在线检测程序升级情况,可及时获得程序更新的信息。

★★ 签名  ●  
     可以在您的每个帖子的后面自动加上一个自己设计的签名哟。

Http://www.ChinaOK.net/csdn/csdn.zip
Http://www.ChinaOK.net/csdn/csdn.rar
Http://www.ChinaOK.net/csdn/csdn.exe    [自解压]

#3


霍夫曼树生成原理是权值越大的越在上面,每一层的节点的权值都比下一层的大

现在假设有如下原始数据:
6 8 14 25 23 9进行霍夫曼编码

           85
         /     \
           37      48
         /  \   / \
                 23  14 23 25
      /   \
  14   9
 / \
6   8
但我们知道根据以上权值构建的霍夫曼树不是唯一的
我的问题是:

能否根据已知的霍夫曼树生成每个节点的权值再根据此权值重新构建树
和原来的树完全一样?

还有就是能否让新生成的权值尽可能小

#4


没想到progame会问这样的问题:)

我先说两句吧。
首先,霍夫曼树就是一个权重最小的生成树,尽可能小又从何谈起呢?
其次,霍夫曼树不可能唯一,因为:
1、对换已生成的一个树的任一左、右子树,都会生成不同的霍夫曼树。
2、在已生成的一个霍夫曼树中,对换任两个权重相同的子树也会生成不同的霍夫曼树。

#5


我想你误会我的意思了
霍夫曼树当然生成的总权重是最小的

我的问题是,拿上面的例子说吧:
我可以把生成树后的节点权值替换成:
6 8 14 25 23 9
1 2  3  10 9 4

这样根据此数据重新构建树,树结构和原来是一样的

我要的就是重新生成一个可以重构树的权值集

#6


什么叫“能否让新生成的权值尽可能小”?是说所有整数之和最小么?

#7


不是所有整数之和

我要的是节点的最大权值最小

#8


           85
         /     \
           37      48
         /  \   / \
                 23  14 23 25
      /   \
  14   9
 / \
6   8

           85
         /     \
           37      48
         /  \   / \
                 14  23 23 25
                     /   \  
        9    14
            / \
           6   8

                     18
         /     \
           8      10
         /  \   / \
                 4  4  5 5
                     /  \  
        2    2
            / \
           1   1

偶不知道怎么说,就画了上面的图,第一张图令左子树的权小等于右子树的权,成为第二张数,然后从叶子节点往上推,如第三张图,可以作出最小值18,程序你自己编一下,哎,不知道怎么表达,大概偶的思路就是这样。


#9


/ \
 1   1

这样是不行的,因为这两个节点可以互换,生成的树不唯一

#10


/\ /\
4 4 5 5

这样加一编码也不行,万一这层有N个节点
这样的话如果编码为:
x x+1 x+2 ... x+n-1

x+(x+1)还应该大于x+n-1才行

#11


你的意思是这个权值不能相同,那就是说新的权值的整数各不相同,这样行么:
                     25
         /     \
           12      13
         /  \   / \
                 5  7  6 7
                     /  \  
        4    3
            / \
           1   2

#12


                     27
         /     \
           14      13
         /  \   / \
                 5  9  6 7
                     /  \  
        4    5
            / \
           2   3

#13


又错了:
                     29
         /     \
           14      15
         /  \   / \
                 5  9  7 8
                     /  \  
        4    5
            / \
           2   3

#14


你不要把树的左右节点对换

要和原来完成一致的

这样重新编码才能也一致

我的想法是如果有个最顶端的M值
而下一层有N个节点,则:
N*X + N*(N-1)/2 = M
求出X,向下取整,即为此层第一个节点的权值

依此类推,直到最底下一层

可是M值无法获知:(

如果从自底而上的方法处理:
我即使能够保证这一层的节点的父节点都比这一层权值大
如:
 X   X
/ \ / \
X X X X
我可以X+(X+1)>X+3得到X值为3,即下面一层权值为:3 4 5 6
上一层为 7 11
可是我无法保证上一层节点数会不会大于6个,如下面这样
 X   X  X  X  X  X   X   X
/ \                     / \
X X                     X X

7~11之间的数是不够分配的

#15


有道理,我得好好想想...

#16


pu

推荐阅读
  • 简化报表生成:EasyReport工具的全面解析
    本文详细介绍了EasyReport,一个易于使用的开源Web报表工具。该工具支持Hadoop、HBase及多种关系型数据库,能够将SQL查询结果转换为HTML表格,并提供Excel导出、图表显示和表头冻结等功能。 ... [详细]
  • 本文介绍了如何利用JavaScript或jQuery来判断网页中的文本框是否处于焦点状态,以及如何检测鼠标是否悬停在指定的HTML元素上。 ... [详细]
  • Python自动化处理:从Word文档提取内容并生成带水印的PDF
    本文介绍如何利用Python实现从特定网站下载Word文档,去除水印并添加自定义水印,最终将文档转换为PDF格式。该方法适用于批量处理和自动化需求。 ... [详细]
  • 基于KVM的SRIOV直通配置及性能测试
    SRIOV介绍、VF直通配置,以及包转发率性能测试小慢哥的原创文章,欢迎转载目录?1.SRIOV介绍?2.环境说明?3.开启SRIOV?4.生成VF?5.VF ... [详细]
  • 本文详细介绍了如何准备和安装 Eclipse 开发环境及其相关插件,包括 JDK、Tomcat、Struts 等组件的安装步骤及配置方法。 ... [详细]
  • 本文详细介绍如何利用已搭建的LAMP(Linux、Apache、MySQL、PHP)环境,快速创建一个基于WordPress的内容管理系统(CMS)。WordPress是一款流行的开源博客平台,适用于个人或小型团队使用。 ... [详细]
  • 在现代Web应用中,当用户滚动到页面底部时,自动加载更多内容的功能变得越来越普遍。这种无刷新加载技术不仅提升了用户体验,还优化了页面性能。本文将探讨如何实现这一功能,并介绍一些实际应用案例。 ... [详细]
  • Hybrid 应用的后台接口与管理界面优化
    本文探讨了如何通过优化 Hybrid 应用的后台接口和管理界面,提升用户体验。特别是在首次加载 H5 页面时,为了减少用户等待时间和流量消耗,介绍了离线资源包的管理和分发机制。 ... [详细]
  • Python处理Word文档的高效技巧
    本文详细介绍了如何使用Python处理Word文档,涵盖从基础操作到高级功能的各种技巧。我们将探讨如何生成文档、定义样式、提取表格数据以及处理超链接和图片等内容。 ... [详细]
  • Windows 7 64位系统下Redis的安装与PHP Redis扩展配置
    本文详细介绍了在Windows 7 64位操作系统中安装Redis以及配置PHP Redis扩展的方法,包括下载、安装和基本使用步骤。适合对Redis和PHP集成感兴趣的开发人员参考。 ... [详细]
  • 本文探讨了 RESTful API 和传统接口之间的关键差异,解释了为什么 RESTful API 在设计和实现上具有独特的优势。 ... [详细]
  • HTTP 请求与响应详解
    本文深入探讨了HTTP请求和响应的结构,详细解释了每个部分的作用,并提供了相关示例。通过本文,读者可以全面理解HTTP协议中请求和响应的工作原理。 ... [详细]
  • 在当前众多持久层框架中,MyBatis(前身为iBatis)凭借其轻量级、易用性和对SQL的直接支持,成为许多开发者的首选。本文将详细探讨MyBatis的核心概念、设计理念及其优势。 ... [详细]
  • 将Web服务部署到Tomcat
    本文介绍了如何在JDeveloper 12c中创建一个Java项目,并将其打包为Web服务,然后部署到Tomcat服务器。内容涵盖从项目创建、编写Web服务代码、配置相关XML文件到最终的本地部署和验证。 ... [详细]
  • RecyclerView初步学习(一)
    RecyclerView初步学习(一)ReCyclerView提供了一种插件式的编程模式,除了提供ViewHolder缓存模式,还可以自定义动画,分割符,布局样式,相比于传统的ListVi ... [详细]
author-avatar
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有