开发研究与设计技术
本栏目责任编辑：谢媛媛
对哈夫曼树唯一性的探讨
沈音乐
（杭州职业技术学院，浙江杭州３１００１８）
摘要：在我们的日常教学中，我们经常会对哈夫曼树的建立给出不同答案，那么是否有唯一标准答案？通过相关程序流程及代码实验，分析了导致认为创建哈夫曼树不唯一的原因，说明了在一种既定的算法下，我们是可以达到哈夫曼树建立的唯一性的。
关键词：哈夫曼树；哈夫曼算法；权值；唯一性中图分类号：ＴＰ３１１．１２文献标识码：Ａ文章编号：１００９－３０４４（２００７）２０－４０４４２－０２
ＤｉｓｃｕｓｓｉｏｎｏｎｔｈｅＵｎｉｑｕｅｎｅｓｓｆｏｒＣｒｅａｔｅｔｈｅＢｉｎａｒｙＴｒｅｅｂｙＨｕｆｆｍａｎＡｌｇｏｒｉｔｈｍ
ＳＨＥＮＹｉｎ－ｙｕｅ
（ＨａｎｇｚｈｏｕＶｏｃａｔｉｏｎＴｅｃｈｎｏｌｏｇｙＣｏｌｌｅｇｅ，Ｈａｎｇｚｈｏｕ３１００１８，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｅｒｅａｒｅｍａｎｙｃａｓｅｉｎｏｕｒｄａｉｌｙｅｄｕｃａｔｉｏｎｗｏｒｋ：ｐｅｏｐｌｅｏｆｔｅｎｆｉｎｄｔｈａｔｔｈｅｙｃａｎｗｏｒｋｏｕｔｄｉｆｆｅｒｅｎｔａｎｓｗｅｒｓｆｏｒａｃｒｅａｔｉｏｎｏｆｂｉ－ｎａｒｙｔｒｅｅｂｙＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ．ＴｈｅｐｒｏｇｒａｍｆｌｏｗａｎｄｃｏｄｅｓｅｘｐｌａｉｎｔｈｅｒｅａｓｏｎｗｈｙｓｏｍｅｐｅｏｐｌｅｃａｎｎｏｔｗｏｒｋｏｕｔｔｈｅｓａｍｅａｎｓｗｅｒｂａｓｅｄｏｎＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ，ａｎｄｆｉｎａｌｌｙ，ｐｒｏｖｅｔｈａｔｗｅｃａｎｇｅｔａｕｎｉｑｕｅｂｉｎａｒｙｔｒｅｅｂｙｔｈｅＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ．
Ｋｅｙｗｏｒｄｓ：ＢｉｎａｒｙｔｒｅｅｂａｓｅｄｏｎＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ；Ｈｕｆｆｍａｎａｌｇｏｒｉｔｈｍ；ｗｅｉｇｈｔ；Ｕｎｉｑｕｅｎｅｓｓ
１概述
我们的二叉树的应用教学中，最优二叉树是重要的内容，而哈夫曼编码又是实用性最强的技术，要完成哈夫曼编码，首先要创建哈夫曼树，哈夫曼树又称为最优二叉树，它是这样定义的：设有ｎ个权值｛ｗ１，ｗ２，…，ｗｎ｝，在这些权值为各个叶子结点的权所构成的二叉树中，带权路径长度ＷＰＬ最小的二叉树叫做哈夫曼树。哈夫曼（Ｈｕｆｆｍａｎ）于１９５２年提出了得到这种树的算法，因此相应的算法称为哈夫曼算法。一般的教科书上多是讲述了哈夫曼算法的三个步骤：
（１）将ｎ个权值｛ｗ１，ｗ２，…，ｗｎ｝按递增次序排列，设其顺序为ｗ１，ｗ２，…，ｗｎ，取出最小的两个ｗ１和ｗ２，分别作为根结点的左、右儿子结点的权组成一个二叉树，并认为其根结点的权ｗ１２＝ｗ１＋
图２
情况３如图３所示：
ｗ２；
（２）将ｗ１２按其数值大小插入到ｗ３至ｗｎ之间，使数值仍保持为递增的次序；
右儿子的权组成二叉树，（３）再取出最小的两个作为根的左、
也令根的权等于此两数值之和，并同样将此根结点按权值大小插入到剩下的数据中，保持数值的递增次序。如此重复进行下去，直到构成一个二叉树为止，即得到哈夫曼树。
左边结果是正确的。情况４如图４所示：
图３
２问题分析
按照以上这样的程度讲授，经常会遇到如下情况：一般教师给出一个数列，希望学生给出相应得Ｈｕｆｆｍａｎ树，并都有一个标准答案。但我们在讲课时哈夫曼树只讲其解题思路，并不提及具体的编码，这势必造成学生在不了解计算机计算步骤的情况下，对类似以下四种情况产生困惑：（我们暂时以哈夫曼编码时以字母频度计算权值为例）情况１如图１所示：
图４
图１
比如对于原始输入数列：ｃｈａｒｔｅｘｔ［１２８］＝＂ＡＢ＂；左边结果就是正确的。
情况２如图２所示：
Ａ权值最小，放在左边结果是正确的。
其中右边结果是正确的。
以上四种情况，我们来逐一进行分析：
当两个字母的权值（出现的频度）相等时，如何安排左右子树？我们的程序开始时都有数据输入，数据输入是有先后的（有序性），答案在于此，因为只有大小不等才会发生最小值的变动，在没有大小差异的情况下，输入的原始数列是不会发生易位的，故原始序列中，相等的两个值谁在前，谁将放置在最小值中，谁在后，谁将放置在次小值中。程序中，首先定义了两个最小值ｍｉｎ１，ｍｉｎ２，而ｍｉｎ１与ｍｉｎ２之间的关系是确定的，即ｍｉｎ１＜ｍｉｎ２，ｍｉｎ１与ｍｉｎ２次小，对应得代码：
ｉｆ（ｔ－＞ａｒｒ［ｉ］．ｗｅｉｇｈｔ＜ｍｉｎ２）｛／＊结点的权比最次小权小＊／ｉｆ（ｔ－＞ａｒｒ［ｉ］．ｗｅｉｇｈｔ＜ｍｉｎ１）｛／＊如果它比最小的结点还小＊／
ｍｉｎ２＿ｉ＝ｍｉｎ１＿ｉ；ｍｉｎ２＝ｍｉｎ１；
ｍｉｎ１＿ｉ＝ｉ；ｍｉｎ１＝ｔ－＞ａｒｒ［ｉ］．ｗｅｉｇｈｔ；／／则它成为最小结点｝
收稿日期：２００７－０９－１８
作者简介：沈音乐（１９７３－），女，上海人，讲师，硕士，研究方向为软件工程、数据挖掘和信息编码。
４４２
电脑知识与技术
本栏目责任编辑：谢媛媛
开发研究与设计技术
ｅｌｓｅ｛
ｍｉｎ２＿ｉ＝ｉ；ｍｉｎ２＝ｔ－＞ａｒｒ［ｉ］．ｗｅｉｇｈｔ；／／则它成为次小结点｝｝
当有不同大小时，是放在左子树上，还是放在有子树上？结论是ｍｉｎ１放在左子树上，ｍｉｎ２放在有子树上。对应代码段：
ｔ－＞ａｒｒ［ｔ－＞ｔｏｔａｌ］．ｌｃｈｉｌｄ＝ｍｉｎ１＿ｉ；ｔ－＞ａｒｒ［ｔ－＞ｔｏｔａｌ］．ｒｃｈｉｌｄ＝ｍｉｎ２＿ｉ；
新生成的二叉树，根结点的权值与原有结点权值相等，是放
因为从情在左子树上，还是放在有子树上？结论是放在有子树上。
况１看，首先我们的输入序列为ａｒｒ［０］…ａｒｒ［ｎ－１］，新的根结点生成后是以［ｎ］…［２ｎ－１］的序列出现的，所以从次序上可知，新生成的结点只能落在原有数列之后，当权值相等时未发生大小易位，故按照情况１一样，后者放在新根结点的右边。
当新生成的根结点权值与次小的相同时，是否替代次小的位置？结论是否定的。因为新增的根结点排位在后ａｒｒ［＋＋ｔｏｔａｌ］，所以再次组合时，该根结点排在右子树。对应代码：
ｔ－＞ｔｏｔａｌ＋＋；
ｔ－＞ａｒｒ［ｔ－＞ｔｏｔａｌ］．ｗｅｉｇｈｔ＝ｍｉｎ１＋ｍｉｎ２；
ｔ－＞ａｒｒ［ｔ－＞ｔｏｔａｌ］．ｐａｒｅｎｔ＝－１；／／新生成结点标志创建哈夫曼树的程序流程现分析如图５所示。
由以上分析，我们可以发现，如果按这样的流程建立哈夫曼树，答案肯定是唯一的。
许多教科书上所说的“将ｎ个权值｛ｗ１，ｗ２，…，ｗｎ｝按递增次序排列，设其顺序为ｗ１，ｗ２，…，ｗｎ，取出最小的两个ｗ１和ｗ２，分别作为根结点的左、右儿子结点的权组成一个二叉树，…．．将ｗ１２按其数值大小插入到ｗ３至ｗｎ之间，使数值仍保持为递增的次
右儿子的权组成二叉树，也序；…；再取出最小的两个作为根的左、
令根的权等于此两数值之和，并同样将此根结点按权值大小插入到剩下的数据中，保持数值的递增次序。如此重复进行下去，直到构成一个二叉树为止，即得到哈夫曼树。”这里算法描述强调了首先排序，然后取最小的两个，没有说明左右摆放的细节。而排序的方法是不一定的，如果选择的排序的算法是不稳定的，那么对于同样大小的权值，排序后就可能颠倒次序。这样的描述，因为缺少重要的细节，而又没有具体程序相辅，无法给大多数读者一个明确的解题过程。这就是造成认为不唯一的原因。
图５
（２）最小值成为左孩子结点，次小值成为右孩子结点，最终决定了在哈夫曼树种的一个重要特征：同层从左到右，结点的权值是由小到大排列的。
明确这两点，再繁琐的数列转化成哈夫曼树，都会得到唯一的一个解。
参考文献：
［１］严蔚敏，吴伟民编著．数据结构（Ｃ语言版）［Ｍ］．北京：清华大学出版社，１９９７．
［２］佟维，谢爽等编著．实用数据结构［Ｍ］．北京：科学出版社，２００３．
［３］徐长梅，严洁．Ｈｕｆｆｍａｎ编码的一种实现方法［Ｊ］．长沙大学学报，１９９７（２）：６２－６７．
［４］邱林海，余胜生，周敬利．快速Ｈｕｆｆｍａｎ解码算法及其实现［Ｊ］．计算机工程与应用，１９９９（４）：１－３．
［５］王群芳．哈夫曼编码的另一种实现算法．［Ｊ］．安徽教育学院学报，２００６，２４（６）：３６－３８．
［２］李红臣，史美林．工作流模型及其形式化描述．计算机学报，２００３．１１．
［３］唐邦志，魏生民，景韶宇，周欣．工作流网ＸＰＤＬ映射．计算机工程与应用，２００３．３６．
［４］马达，严隽薇，戴毅茹．可视化工作流管理系统的设计与开发．制造业自动化２００４．１１
技术、应用．电子工［５］史美林．计算机支持的协同工作－概念、
业出版社，２００１．
［６］胡锦敏，张申生．支持动态企业联盟的敏捷工作流系统．计算机研究与进展，１９９９．３：１７－２３．
［７］［美］ＥｒｉｃｈＧａｍｍａＲｉｃｈａｒｄＨｅｌｍＲａｌｐｈＪｏｈｎｓｏｎＪｏｈｎＶｌｉｓ－ｓｉｄｅｓ．著．李英军，马晓星．等．译．设计模式－可复用面向对象软件的基础．机械工业出版社．２０００．９：６０－７５．
［８］赵仲孟．等．基于ＥＪＢ和ＪＭＳ实现的Ｗｏｒｋｆｌｏｗ系统．计算机应用研究，２００３．６：３２－３４．
３结论
综合以上的分析，有两个关键性的认识：
（１）ｍｉｎ１，ｍｉｎ２的存储内容。ｍｉｎ１小于ｍｉｎ２，ｍｉｎ１是最小值，ｍｉｎ２则是次小值；在Ｐ１４７中提到的算法６．１２，关键在于ｓｅｌｅｃｔ（）函数的实现，中未说明ｓｅｌｅｃｔ的结果ｓ１，ｓ２的大小，这是一个不够明确之处，以致读者不能从程序中得到有力的证明，进而也就不能明确得到唯一的哈夫曼树，同样的疏漏在许多参考书上都有，究其缘由，主要事在翻译国外原著时，没能将唯一性的证明写入。
（上接第４３４页）
异），提高了活动定义的复用能力。
解析和执行，但采ＥＣＡ规则很适合工作流过程定义的存储、
用ＥＣＡ规则进行建模，也存在一些缺点，主要是缺少有力的模型分析手段，无法确保复杂结构建模的正确性，需要借助其他具有严
分析、验证，再转换格数学基础的建模工具（如ｐｅｔｒｉ网）进行建模、
成ＥＣＡ规则模型。
因此，本系统在工作流引擎中采用ＥＣＡ规则的工作流模型作为其存储和执行对象，将过程定义工具与过程执行系统分离，任何过程定义工具定义的过程描述都必须通过转换工具转换为本引擎所支持的ＥＣＡ规则式的工作流定义语言，这样，当过程定义工具变化时，只修改转换工具，而工作流引擎无须变动。
参考文献：
［１］徐正权，王治国．基于ＥＣＡ规则的工作流过程建模．计算机工程与科学，２００５．５：１０５－１０８．
４４３
开发研究与设计技术
本栏目责任编辑：谢媛媛
对哈夫曼树唯一性的探讨
沈音乐
（杭州职业技术学院，浙江杭州３１００１８）
摘要：在我们的日常教学中，我们经常会对哈夫曼树的建立给出不同答案，那么是否有唯一标准答案？通过相关程序流程及代码实验，分析了导致认为创建哈夫曼树不唯一的原因，说明了在一种既定的算法下，我们是可以达到哈夫曼树建立的唯一性的。
关键词：哈夫曼树；哈夫曼算法；权值；唯一性中图分类号：ＴＰ３１１．１２文献标识码：Ａ文章编号：１００９－３０４４（２００７）２０－４０４４２－０２
ＤｉｓｃｕｓｓｉｏｎｏｎｔｈｅＵｎｉｑｕｅｎｅｓｓｆｏｒＣｒｅａｔｅｔｈｅＢｉｎａｒｙＴｒｅｅｂｙＨｕｆｆｍａｎＡｌｇｏｒｉｔｈｍ
ＳＨＥＮＹｉｎ－ｙｕｅ
（ＨａｎｇｚｈｏｕＶｏｃａｔｉｏｎＴｅｃｈｎｏｌｏｇｙＣｏｌｌｅｇｅ，Ｈａｎｇｚｈｏｕ３１００１８，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｅｒｅａｒｅｍａｎｙｃａｓｅｉｎｏｕｒｄａｉｌｙｅｄｕｃａｔｉｏｎｗｏｒｋ：ｐｅｏｐｌｅｏｆｔｅｎｆｉｎｄｔｈａｔｔｈｅｙｃａｎｗｏｒｋｏｕｔｄｉｆｆｅｒｅｎｔａｎｓｗｅｒｓｆｏｒａｃｒｅａｔｉｏｎｏｆｂｉ－ｎａｒｙｔｒｅｅｂｙＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ．ＴｈｅｐｒｏｇｒａｍｆｌｏｗａｎｄｃｏｄｅｓｅｘｐｌａｉｎｔｈｅｒｅａｓｏｎｗｈｙｓｏｍｅｐｅｏｐｌｅｃａｎｎｏｔｗｏｒｋｏｕｔｔｈｅｓａｍｅａｎｓｗｅｒｂａｓｅｄｏｎＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ，ａｎｄｆｉｎａｌｌｙ，ｐｒｏｖｅｔｈａｔｗｅｃａｎｇｅｔａｕｎｉｑｕｅｂｉｎａｒｙｔｒｅｅｂｙｔｈｅＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ．
Ｋｅｙｗｏｒｄｓ：ＢｉｎａｒｙｔｒｅｅｂａｓｅｄｏｎＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ；Ｈｕｆｆｍａｎａｌｇｏｒｉｔｈｍ；ｗｅｉｇｈｔ；Ｕｎｉｑｕｅｎｅｓｓ
１概述
我们的二叉树的应用教学中，最优二叉树是重要的内容，而哈夫曼编码又是实用性最强的技术，要完成哈夫曼编码，首先要创建哈夫曼树，哈夫曼树又称为最优二叉树，它是这样定义的：设有ｎ个权值｛ｗ１，ｗ２，…，ｗｎ｝，在这些权值为各个叶子结点的权所构成的二叉树中，带权路径长度ＷＰＬ最小的二叉树叫做哈夫曼树。哈夫曼（Ｈｕｆｆｍａｎ）于１９５２年提出了得到这种树的算法，因此相应的算法称为哈夫曼算法。一般的教科书上多是讲述了哈夫曼算法的三个步骤：
（１）将ｎ个权值｛ｗ１，ｗ２，…，ｗｎ｝按递增次序排列，设其顺序为ｗ１，ｗ２，…，ｗｎ，取出最小的两个ｗ１和ｗ２，分别作为根结点的左、右儿子结点的权组成一个二叉树，并认为其根结点的权ｗ１２＝ｗ１＋
图２
情况３如图３所示：
ｗ２；
（２）将ｗ１２按其数值大小插入到ｗ３至ｗｎ之间，使数值仍保持为递增的次序；
右儿子的权组成二叉树，（３）再取出最小的两个作为根的左、
也令根的权等于此两数值之和，并同样将此根结点按权值大小插入到剩下的数据中，保持数值的递增次序。如此重复进行下去，直到构成一个二叉树为止，即得到哈夫曼树。
左边结果是正确的。情况４如图４所示：
图３
２问题分析
按照以上这样的程度讲授，经常会遇到如下情况：一般教师给出一个数列，希望学生给出相应得Ｈｕｆｆｍａｎ树，并都有一个标准答案。但我们在讲课时哈夫曼树只讲其解题思路，并不提及具体的编码，这势必造成学生在不了解计算机计算步骤的情况下，对类似以下四种情况产生困惑：（我们暂时以哈夫曼编码时以字母频度计算权值为例）情况１如图１所示：
图４
图１
比如对于原始输入数列：ｃｈａｒｔｅｘｔ［１２８］＝＂ＡＢ＂；左边结果就是正确的。
情况２如图２所示：
Ａ权值最小，放在左边结果是正确的。
其中右边结果是正确的。
以上四种情况，我们来逐一进行分析：
当两个字母的权值（出现的频度）相等时，如何安排左右子树？我们的程序开始时都有数据输入，数据输入是有先后的（有序性），答案在于此，因为只有大小不等才会发生最小值的变动，在没有大小差异的情况下，输入的原始数列是不会发生易位的，故原始序列中，相等的两个值谁在前，谁将放置在最小值中，谁在后，谁将放置在次小值中。程序中，首先定义了两个最小值ｍｉｎ１，ｍｉｎ２，而ｍｉｎ１与ｍｉｎ２之间的关系是确定的，即ｍｉｎ１＜ｍｉｎ２，ｍｉｎ１与ｍｉｎ２次小，对应得代码：
ｉｆ（ｔ－＞ａｒｒ［ｉ］．ｗｅｉｇｈｔ＜ｍｉｎ２）｛／＊结点的权比最次小权小＊／ｉｆ（ｔ－＞ａｒｒ［ｉ］．ｗｅｉｇｈｔ＜ｍｉｎ１）｛／＊如果它比最小的结点还小＊／
ｍｉｎ２＿ｉ＝ｍｉｎ１＿ｉ；ｍｉｎ２＝ｍｉｎ１；
ｍｉｎ１＿ｉ＝ｉ；ｍｉｎ１＝ｔ－＞ａｒｒ［ｉ］．ｗｅｉｇｈｔ；／／则它成为最小结点｝
收稿日期：２００７－０９－１８
作者简介：沈音乐（１９７３－），女，上海人，讲师，硕士，研究方向为软件工程、数据挖掘和信息编码。
４４２
电脑知识与技术
本栏目责任编辑：谢媛媛
开发研究与设计技术
ｅｌｓｅ｛
ｍｉｎ２＿ｉ＝ｉ；ｍｉｎ２＝ｔ－＞ａｒｒ［ｉ］．ｗｅｉｇｈｔ；／／则它成为次小结点｝｝
当有不同大小时，是放在左子树上，还是放在有子树上？结论是ｍｉｎ１放在左子树上，ｍｉｎ２放在有子树上。对应代码段：
ｔ－＞ａｒｒ［ｔ－＞ｔｏｔａｌ］．ｌｃｈｉｌｄ＝ｍｉｎ１＿ｉ；ｔ－＞ａｒｒ［ｔ－＞ｔｏｔａｌ］．ｒｃｈｉｌｄ＝ｍｉｎ２＿ｉ；
新生成的二叉树，根结点的权值与原有结点权值相等，是放
因为从情在左子树上，还是放在有子树上？结论是放在有子树上。
况１看，首先我们的输入序列为ａｒｒ［０］…ａｒｒ［ｎ－１］，新的根结点生成后是以［ｎ］…［２ｎ－１］的序列出现的，所以从次序上可知，新生成的结点只能落在原有数列之后，当权值相等时未发生大小易位，故按照情况１一样，后者放在新根结点的右边。
当新生成的根结点权值与次小的相同时，是否替代次小的位置？结论是否定的。因为新增的根结点排位在后ａｒｒ［＋＋ｔｏｔａｌ］，所以再次组合时，该根结点排在右子树。对应代码：
ｔ－＞ｔｏｔａｌ＋＋；
ｔ－＞ａｒｒ［ｔ－＞ｔｏｔａｌ］．ｗｅｉｇｈｔ＝ｍｉｎ１＋ｍｉｎ２；
ｔ－＞ａｒｒ［ｔ－＞ｔｏｔａｌ］．ｐａｒｅｎｔ＝－１；／／新生成结点标志创建哈夫曼树的程序流程现分析如图５所示。
由以上分析，我们可以发现，如果按这样的流程建立哈夫曼树，答案肯定是唯一的。
许多教科书上所说的“将ｎ个权值｛ｗ１，ｗ２，…，ｗｎ｝按递增次序排列，设其顺序为ｗ１，ｗ２，…，ｗｎ，取出最小的两个ｗ１和ｗ２，分别作为根结点的左、右儿子结点的权组成一个二叉树，…．．将ｗ１２按其数值大小插入到ｗ３至ｗｎ之间，使数值仍保持为递增的次
右儿子的权组成二叉树，也序；…；再取出最小的两个作为根的左、
令根的权等于此两数值之和，并同样将此根结点按权值大小插入到剩下的数据中，保持数值的递增次序。如此重复进行下去，直到构成一个二叉树为止，即得到哈夫曼树。”这里算法描述强调了首先排序，然后取最小的两个，没有说明左右摆放的细节。而排序的方法是不一定的，如果选择的排序的算法是不稳定的，那么对于同样大小的权值，排序后就可能颠倒次序。这样的描述，因为缺少重要的细节，而又没有具体程序相辅，无法给大多数读者一个明确的解题过程。这就是造成认为不唯一的原因。
图５
（２）最小值成为左孩子结点，次小值成为右孩子结点，最终决定了在哈夫曼树种的一个重要特征：同层从左到右，结点的权值是由小到大排列的。
明确这两点，再繁琐的数列转化成哈夫曼树，都会得到唯一的一个解。
参考文献：
［１］严蔚敏，吴伟民编著．数据结构（Ｃ语言版）［Ｍ］．北京：清华大学出版社，１９９７．
［２］佟维，谢爽等编著．实用数据结构［Ｍ］．北京：科学出版社，２００３．
［３］徐长梅，严洁．Ｈｕｆｆｍａｎ编码的一种实现方法［Ｊ］．长沙大学学报，１９９７（２）：６２－６７．
［４］邱林海，余胜生，周敬利．快速Ｈｕｆｆｍａｎ解码算法及其实现［Ｊ］．计算机工程与应用，１９９９（４）：１－３．
［５］王群芳．哈夫曼编码的另一种实现算法．［Ｊ］．安徽教育学院学报，２００６，２４（６）：３６－３８．
［２］李红臣，史美林．工作流模型及其形式化描述．计算机学报，２００３．１１．
［３］唐邦志，魏生民，景韶宇，周欣．工作流网ＸＰＤＬ映射．计算机工程与应用，２００３．３６．
［４］马达，严隽薇，戴毅茹．可视化工作流管理系统的设计与开发．制造业自动化２００４．１１
技术、应用．电子工［５］史美林．计算机支持的协同工作－概念、
业出版社，２００１．
［６］胡锦敏，张申生．支持动态企业联盟的敏捷工作流系统．计算机研究与进展，１９９９．３：１７－２３．
［７］［美］ＥｒｉｃｈＧａｍｍａＲｉｃｈａｒｄＨｅｌｍＲａｌｐｈＪｏｈｎｓｏｎＪｏｈｎＶｌｉｓ－ｓｉｄｅｓ．著．李英军，马晓星．等．译．设计模式－可复用面向对象软件的基础．机械工业出版社．２０００．９：６０－７５．
［８］赵仲孟．等．基于ＥＪＢ和ＪＭＳ实现的Ｗｏｒｋｆｌｏｗ系统．计算机应用研究，２００３．６：３２－３４．
３结论
综合以上的分析，有两个关键性的认识：
（１）ｍｉｎ１，ｍｉｎ２的存储内容。ｍｉｎ１小于ｍｉｎ２，ｍｉｎ１是最小值，ｍｉｎ２则是次小值；在Ｐ１４７中提到的算法６．１２，关键在于ｓｅｌｅｃｔ（）函数的实现，中未说明ｓｅｌｅｃｔ的结果ｓ１，ｓ２的大小，这是一个不够明确之处，以致读者不能从程序中得到有力的证明，进而也就不能明确得到唯一的哈夫曼树，同样的疏漏在许多参考书上都有，究其缘由，主要事在翻译国外原著时，没能将唯一性的证明写入。
（上接第４３４页）
异），提高了活动定义的复用能力。
解析和执行，但采ＥＣＡ规则很适合工作流过程定义的存储、
用ＥＣＡ规则进行建模，也存在一些缺点，主要是缺少有力的模型分析手段，无法确保复杂结构建模的正确性，需要借助其他具有严
分析、验证，再转换格数学基础的建模工具（如ｐｅｔｒｉ网）进行建模、
成ＥＣＡ规则模型。
因此，本系统在工作流引擎中采用ＥＣＡ规则的工作流模型作为其存储和执行对象，将过程定义工具与过程执行系统分离，任何过程定义工具定义的过程描述都必须通过转换工具转换为本引擎所支持的ＥＣＡ规则式的工作流定义语言，这样，当过程定义工具变化时，只修改转换工具，而工作流引擎无须变动。
参考文献：
［１］徐正权，王治国．基于ＥＣＡ规则的工作流过程建模．计算机工程与科学，２００５．５：１０５－１０８．
４４３