算法与实现

算法与实现（精选12篇）

算法与实现 篇1

在因特网应用初期, 带宽资源常常富余, 但现在, 由于机关、企事业单位许多频繁的营运活动如上网查找信息、远程通讯与管理等依赖于因特网, 常见应用如疯狂下载软件BT、迅雷等大量占用带宽, 因此带宽资源使用常常困境屡生, 需要网管时刻关注以便及时处理出现的问题。

假定代理从一台路由器通过网络流消息收集HTTP所使用的总带宽, 然后每隔5分钟向服务器报告一下。如何存储这些收集值以便可计算出任意时间段所使用的总带宽呢?

如果将收集的带宽值存储在RRD中, 虽然可以很容易地绘制出带宽使用情况时间序列图, 但却不能准确计算出任意时间段 (例如, 2014-06-20 10:00至2014-06-20 11:00) HTTP所使用的总带宽。为解决这一问题, 设计一种带宽存储算法 (Band Width Storage Algorithm, 即BWSA) 用来存储、处理详细带宽值和汇总值。

1 算法设计

(1) 归档文件设计

归档文件是一个按时间顺序存储带宽值的固定长度的数组阵列。例如, 可以用3个归档文件分别存储来自于3个网络流设备的所有带宽值。

归档文件中的一条记录存储一个包含N个步长 (步长是指将时间轴均匀分成若干段, 每段包含的分钟数, 比如网络流设备可使用5分钟的步长。N可自行设置) 的特定时间段的所有带宽值。例如, 为了存储来自网络流设备的带宽信息, 可创建一个包含366条记录的归档文件, 每条记录存储包含288个步长的所有带宽值, 而每个步长为5分钟。这样, 1条记录就可存储1天的数据 (288 x 5分钟=1440分钟=24小时) , 而1个归档文件就可存储长达1年的数据。

如果有新的第367天的数据需要存储, 而归档文件却仅有366条记录, 怎么办?其实, 归档文件被视为一个循环数组阵列。当需要存储第367天的数据时, 原来存储第1天数据的那条记录将被改写。

(2) 记录设计

每条记录均包含两种信息。

汇总带宽值。例如, 如果一条记录对应于1天, 而步长为5分钟, 并且代理已经发给服务器涵盖从00:00到03:00时间段的36次带宽收集值, 那么此时, 汇总数据等于在开始的3小时内所使用的总带宽。

每次收集的详细带宽值。在上述包含288个步长、每个步长5分钟的记录例子中, 假如代理已经发给服务器涵盖从00:00到00:15时间段的数据, 那么这条记录就包含3个分别对应于00:05、00:10和00:15的详细带宽值, 和1个汇总值 (总是1个, 并且等于该记录中到目前为止所有详细带宽值的总和。

(3) 增加操作设计

服务器在收到一个新的带宽值 (例如, 2012-06-25 03:50 UDP=1.2M, TCP=4M) 后, 将找到适当的记录。如果在此之前更新过的记录与该记录间有间隔, 那么服务器将清除掉间隔间的所有记录值。然后服务器追加带宽值到详细信息部分并更新汇总值。

(4) 查询操作设计

假如希望查询从2014-06-25 10:00至2014-06-28 09:00时间段的总带宽, 操作方法为:首先, 载入2014-06-25、2014-06-26、2014-06-27和2014-06-28这4天的记录。由于这一时间段涵盖了2014-06-26和2014-06-27全天, 所以可以直接使用它们的汇总值。但是, 这一时间段只涵盖了2014-06-25和2014-06-28的部分时段, 因此需要加载这两天的详细信息, 并计算2014-06-25 00:00至2014-06-25 10:00之间以及2014-06-28 00:00至2014-06-28 09:00之间的汇总值。然后, 对这4个汇总值进行算术运算就得到总带宽。

2 基于My SQL的实现

使用My SQL作为后端存储数据库的实现方法如下。

2.1 创建元信息表

命名为bwarchivecontrols的表用来保存归档文件的元信息, 表创建代码如下。

在表bwarchivecontrols中, 每个归档文件都有相应的记录以便存储元数据信息, 其中:

(1) name:标识归档文件的唯一的名称。

(2) step_length:一步的长度 (单位:分钟) 。

(3) step_count:每条记录所包含的步长数。

(4) archive_length:归档文件包含的记录数。

(5) last_collecting_sequence:最近报告的时间段所对应的序列号 (需先将时间按步长分成若干时间段, 并给每个时间段分配一个序列号) 。

2.2 创建归档记录表

命名为bwarchives的表用来存储归档记录, 表创建代码如下。

其中:

(1) record_index:每条记录分配的索引号, 范围0~archive_length-1。

(2) valid:表示是否参与计算总带宽。在现实世界中, 代理可能会漏报告, 设备也有可能停止工作, 因此不可能指望每条记录都填满数据。当要计算特定时间段的总带宽时, 可以忽略valid='n'的记录, 以提高查询性能。

(3) compressed:表示details值是否已被压缩。details列中存储的是JSON字符串, 从逻辑上讲, 它是当前记录所涵盖的时间段上所有详细带宽值的一个数组阵列。若JSON字符串长度超过规定的阈值, 那么就在数据库中保存压缩版本。

(4) aggregated:针对当前记录, 存储到目前为止的时间段内带宽汇总值。这些值存储在一个JSON字符串中, 格式为{metric1:value1, metric2:value2, ......}, 例如, {udp:1677721, tcp:10256}。

(5) details:以JSON字符串数组形式存储所有详细带宽值。在数组中, 每个详细带宽值都存储在JSON对象中, 格式如下:

一个详细带宽值所在的JSON对象必须包含一个sequence键, 其值为当前步长时段所分配的序列号, metrics的值也存储在一个JSON对象中。JSON对象中的每个键值都将参与汇总。

为加快查询bwarchives表的速度, 需创建索引 (bwarchivecontrol_id, record_index) 。

2.3 创建归档文件

当创建一个新归档文件时, 用户需提供一个唯一名称, 以便于管理。服务器首先会在表bwarchivecontrols中插入一条记录, 用来保存新归档文件的元信息。然后, 服务器将在表bwarchives中插入数量为archive_length的多条记录, 记录索引号0~archive_length-1。

3 结语

设计的BWSA由于使用My SQL作为后端存储数据库, 并以JSON (字符串) 数组形式存储所有带宽值, 可扩展性和灵活性好。通过BWSA, 能够准确计算出任意时间段HTTP所使用的总带宽, 给网管全面了解带宽使用情况提供了良好的方法。

摘要：带宽使用情况是网管时刻关注的内容, 针对存储、处理任一时间段的详细带宽值和总带宽的要求, 设计一种带宽存储算法, 并以My SQL作为后端存储数据库、以JSON字符串形式存储带宽值, 不仅灵活性好, 而且可以很方便地准确计算出任意时间段HTTP所使用的总带宽。

关键词：带宽存储算法,My SQL,JSON,带宽

参考文献

[1]施瓦茨.高性能My SQL (第3版) [M].北京:电子工业出版社.2013.

[2]Json.http://www.json.org/json-zh.html.

[3]王魁生, 王晓波.利用JSON进行网站客户端与服务器数据交互[J].软件导刊, 2010, 09 (3) :147-149.

[4]吴纲.RRDtool性能优化的研究与实现[J].襄樊职业技术学院学报, 2008 (4) :7-9.

算法与实现 篇2

这篇文章主要介绍了二分查找算法与相关的Python实现示例,Binary Search同时也是算法学习当中最基础的知识,需要的朋友可以参考下

二分查找Binary Search的思想：

以有序表表示静态查找表时，查找函数可以用二分查找来实现，

二分查找(Binary Search)的查找过程是：先确定待查记录所在的区间，然后逐步缩小区间直到找到或找不到该记录为止。

1二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)。

假设 low 指向区间下界，high 指向区间上界，mid 指向区间的中间位置，则 mid= (low + high) / 2;

具体过程：

1.先将关键字与 mid 指向的元素比较，如果相等则返回mid。

2.关键字小于 mid 指向的元素关键字，则在 [ low,mid-1 ]区间中继续进行二分查找。

3.关键字大于mid 指向的元素关键字，则在[ mid +1 , high] 区间中继续进行二分查找。

用Python实现二分查找示例：

算法与实现 篇3

关键词：图像处理； 边缘检测； 模板； 卷积； 非极大抑制

边缘检测方法的优劣直接影响着图像特征提取及其它后续处理，是图像预处理中的关键。边缘检测是对灰度变化的度量与定位，灰度变化的显著程度可以通过导数来度量，即函数导数能够反映图像灰度变化的显著程度，因此边缘检测的一个基本思想就是通过求一阶导数的局部极大值，二阶导数的过零点来体现出来的。利用梯度最大值提取边缘点的这种思想产生了许多经典的边缘检测方法如：Sobel算法、Log 算法、Canny 算法等。

一、边缘检测概述

图像中边缘检测是利用物体和背景在某种图像特征中的差异来实现的， 这些差异包括灰度、颜色或纹理特征， 检测出图像特征发生变化的位置从而达到检测目的。图像边缘是分析和理解图像的基础， 是图像中最基本的特征， 图像处理的研究中许多都涉及到边缘检测。图像边缘检测在实际工程中有着广泛的应用， 如图像匹配、模式识别、特征提取和图像编码等。

二、国内外现状

边缘检测技术作为一个低级的计算机视觉处理技术很早就引起了人们关注。最早提出边缘检测技术的是Julez，但他并未展开系统研究，而最早期对其进行系统研究的是Roberts在1965年开始的，从此，拉开了图像边缘检测技术研究的序幕。

很多年来，由于众多专家、学者的不懈努力，在边缘检测领域提出了很多相关理论和边缘检测算法，大致将已有的边缘检测算法分类如下：

1.传统边缘检测算法。传统边缘检测算法以原始图像为基础，对图像中的各个像素考察它的某个领域内灰度值的阶跃变化，利用边缘邻近一阶或者二阶方向导数变化规律来检测边缘，这种方法简单而且有效。其中最基本的算子有：Roberts算子， Sobel算子、Prewitt算子和Kirsch算子等等，这些算子都是一阶微分算子。其检测原理为：一阶导数在边缘处取得最大值。但是运用上述一阶边缘检测算子检测边缘时，在边缘像素邻域产生的响应较宽，还需要后期进行细化处理，所以这些算子的边缘定位精确度不高。

2.改进的传统边缘检测法。传统边缘检测法大多属于微分算法，在数字边缘检测中，常用不同的模板算子与图像的像素灰度值做卷积运算，来求解边缘的导数值。这些算法简单有效，可操作性强，相对来说比较成熟，并且在matlab中可以直接调用，已经应用于很多领域，并取得了显著成绩。所以，基于这些算子的改进是今后研究边缘检测算法的方向之一。很多学者已经付出了很多努力，取得了很多研究成果。

3.基于小波变换和形态学的图像边缘检测算法。小波变换是一种有效的数学工具，它通过时间和频域的局域变换能有效提取有用信息，并且，还能够通过伸缩和平移对信号进行多尺度细化分析，具有良好的时频局部化特性、方向选择性以及多尺度分析能力，是检钡（突变信号的有力工具。各种基于小波变换的图像边缘检测方法也取得了很大发展，并且，应用领域越来越广泛。例如，二进制小波；多进制小波、巴布小波、正交小波等等类型的小波也在图像边缘检测方面也取得了不错的研究成果。

三、医学图像边缘检测算法

1.canny算法。基于这三个准则，Canny得出了c-y边缘检测算子。完整的c-y边缘在高斯噪声中代表一个跳变的强弱情况。按照这个模型，canny研究了已有的边缘检测算子以及其在边缘检测领域内的相关应用，在1986年canny提出了一个相对比较好的边缘检测方法，这种算法要求满足下述几个准则：

（l）信噪比准则：该准则主要是在图像边缘处来检测有无结果。并且不能出现虚假边缘。

（2）精度定位准则：也就是我们所标记的边缘位置必须要和其他在图像上的边缘的中心位置相近。

（3）单边响应准则：单独边缘所产生的响应的频率不要太高，并且需要最大地抑制虚假边缘响应。

这里，脉冲响应导数的零交叉点平均距离D（f）必须满足下面的关系式：

D（f）=π

h”（x）是h（x）的二阶导数。根据上面的指标和准则，我们使用泛函求导的方法来推导出Canny边缘检测器，并得出这个检测器恰恰是信噪比和定位之乘积的最优的逼近算子。

主要过程如下：

（1）对图像进行平滑，我们主要使用高斯滤波器来进行；

（2）计算幅值和方向；

（3）必須要让梯度的幅值被极大值所抑制；

（4）用双闽值算法对边缘进行检测与连接。

canny边缘检测重点是用来寻找到梯度幅度的局部最大值。这里的梯度通过高斯滤波器的导数来进行计算出来的。Canny方法主要使用两个闽值分别对强边缘以及弱边缘进行检测，同时在对强边缘与弱边缘进行相连操作的时候。

2.MTM算法。均值滤波算法对于脉冲信号去噪的能力是很不理想的。然而，中值滤波算法却能够很好滴对脉冲噪声进行去噪，但是对于高斯噪声的去噪能力相对差了一点。

但是在最后评价时，这些方法往往都采用利用单一的噪声进行评价。假如能够找到某种方法可以将脉冲噪声以及被高斯噪声影响的像素进行区分开来，然后对于受到不同噪声干扰的像素进行不同的滤波，所以理论上将，这将会起到比较好的滤波效果。

3.Otsu算法研究。在对图像的处理过程中，长期以来，阈值的自动选取都是对图像进行研究的重点话题。往往阈值的选取都是在这样的一种假设上进行研究的。那么最佳的阈值应该具备最好的而且可以所示分开的两类门限。这种算法计算比较简单，并且一定情况下不会受到图像对比度和亮度变化的影响，同时在某些图像在进行实时处理系统中的应用也变得十分广泛，长期以来就被认为是阈值自动化选取领域里的最优化的方法。

四、结语

由于边缘检测技术的复杂性和研究时间的限制，本课题的研究对象主要针对医学图像算法，所提出方法的应用领域还有待于进一步扩展和完善，但是这些方法对后续边缘检测研究工作具有很高的参考价值。此外，由于技术上的限制，还有很多问题有待进一步的研究。展望今后的研究工作，还有待研究。

参考文献：

[1] 段瑞玲，李庆祥，李玉和.图像边缘检测方法研究综述[J].光学技术，2005，31（3）：415-419.

[2] 马艳，张治辉.几种边缘检测算子的比较[J].工业自动化，2004（1）：54-56.

Dijkstra算法设计与实现 篇4

最短路径问题是指在一个非负权值图中找出两个指定节点间的一条权值之和最小的路径。Dijkstra算法在很多计算机专业可均有介绍, 如数据结构, 离散数学等, 但大都比较粗略。迪克斯特拉算法是经典的求解最短路径问题的方法, 是按路径长度递增的次序来产生最短路径的算法[1]。

最短路径问题描述:设n, m带权图G=<V, E, W>, V={v0, v1, …, vn-1}, E={e1, e2, …, em}, 其中假设每条边ei的权值为wi, 单源的最短路径就是从图G中找到起源点V0到图中其余各点的最短路径。

2 最短路径概念

带权图G=<V, E, W>, 其中W:ER, (1) eE, w (e) 称作e的权。若vi和vj相邻e= (vi, vj) , 记w (vi, vj) =w (vi, vj) , 若vi, vj不相邻, 记w (vi, vj) =。通路L的权是指L的所有边的权值之和, 记作w (L) , u和v之间的最短路径指的是u和v之间边权最小的通路[2]。

3 Dijkstra算法描述

1) 算法基本过程:设带权图G=<V, E, W>, 把图G中顶点集合V分成两个子集, 第一个子集是已求出最短路径的顶点集合, 用V1表示, 初始化时V1中只有一个起源点, 以后每求得一条最短路径, 就将被选定点加入到集合V1中, 直到图中全部顶点都依次添加到到V1中, 算法就结束了;第二个集合为G中其余未确定最短路径的顶点集合, 用V2表示, 按最短路径长度的递增次序依次把第二个集合V2中的被选顶点加入集合V1中。特别, 在加入的过程中, 总保持从起源点v0到V1中各顶点的最短路径长度不大于从源点v0到V2中任何顶点的最短路径长度。此外, 每个顶点对应一个距离, V1中的顶点的距离就是从v0到此顶点的最短路径长度, V2中的顶点的距离, 是从v0到此顶点只包括V1中的顶点为中间顶点的当前最短路径长度。

2) 算法具体步骤:

a.初始时, V1只包含源点, 即V1={v0}, v0的距离为0。V2包含除v0外的其他顶点, 即:V2={v1, v2…, vn-1}。定义集合V2中的顶点的距离:若v0与V2中顶点v有边, 则dist (v) =w (v0, v) 正常有权值, 若v0与v点不相邻, 则dist (v) =∞。

b.从V2中选取一个点k加入V1中, 选择公式dist (k) =min (dist (v) |v∈U) , 把k加入V1中 (该选定的距离就是v0到k的最短路径长度) 。此时V1=V1∪{k}, 同时V2集合中删除k点, 即V2=V2-{k}。

c.以k为新考虑的中间点, 修改V2中各顶点的距离;若从源点v0到顶点v的距离 (经过顶点k) 比原来距离短, 则修改顶点v的距离值, 否则v的距离值不变, 修改公式dist (v) =min{dist (v) , dist (k) +dist (k, v) }[3]。

d.重复步骤b和c直到V1=V, 算法停止。

4 算法实例

1) 先给出一个无向图G=<V, E, W>, 如图1所示:

用Dijkstra算法找出以A为起点的单源最短路径步骤如表1:

5 算法代码实现

测试案例如图2所示:

测试结果如图3所示:

6 小结

作为一门计算机的专业基础课《离散数学》在计算机学科领域中发挥了重要的作用。最短路径算法在很多方面有着重要的应用, 针对教材中Dijkstra最短路径算法讲解粗略, 学生学习困难等问题, 本人结合多年的教学经验, 对Dijkstra算法求最短路径给出了详细的算法设计和实现, 对这部分内容的教学帮助明显。

摘要：最短路径算法在各领域应用广泛, 大多《离散数学》的图论部分最短路径算法讲解较为粗略, 不便于学生学习和实践。经过多年教学总结, 对最短路径算法给出设计和实现, 有利于学生对本知识的掌握和实践应用。

关键词：最短路径,离散数学,Dijkstra算法

参考文献

[1]李妍妍.Dijkstra最短路径分析算法的优化实现[J].测绘与空间地理信息, 2014, 37 (5) :172-190.

[2]耿素云, 屈婉玲, 张立昂.离散数学[M].5版.北京:清华大学出版社, 2013:128-130.

算法与实现 篇5

双环网络G(N;1,s)直径的改进求解算法与实现

目前实现的.双环网络G(N;1,s)直径求解算法的不足之处是利用数据库存取中间结果,严重影响了计算速度,当N值很大时需要计算的时间过长.针对这一不足,提出利用数组取代数据库来存取中间结果,实验结果表明,改进的算法极大地提高了计算速度;给出两例大值N直径分布图,并对直径分布特点作了进一步的分析.

作 者：邰伟鹏 TAI Wei-peng 作者单位：安徽工业大学,计算机科学系,安徽,马鞍山,243002刊 名：微电子学与计算机 ISTIC PKU英文刊名：MICROELECTRONICS & COMPUTER年，卷(期)：200724(8)分类号：O157.9 TP302关键词：双环网络 直径 紧优 算法 族

算法与实现 篇6

摘 要：随着数字化校园进程的快速推进，科研和教学都进入了数字信息化管理时代，研究如何利用数字信息化的优势来高效管理高校后勤具有重要意义。本文设计了基于改进的贪心算法的智能宿舍分配系统，把选定的分配条件如作息时间、爱好、专业、个性等作为特征项，为每个特征项根据其在匹配中的重要程度赋予一定的权重，通过计算匹配度为学生进行宿舍分配，实现一个人性化的宿舍分配系统。在减少后勤人员的工作量、提高宿舍分配效率的同时，也有助于营造和谐的宿舍氛围。实现了学生管理的信息化、自动化，对于数字化校园的建设有一定的理论和现实意义。

关键词：贪心算法；宿舍分配；数字化校园

中图分类号：TP311

随着高校招生规模的不断扩大，学生人数的急剧增加，住宿资源也愈发紧张，学生对宿舍分配与管理的要求也在不断地提高。同时，随着社会信息化发展步伐的加快，学校的管理和服务工作也需要越来越周到、全面、先进和高效。在校生的学历层次、文化水平、思想状态呈多样化、复杂化的趋势，学生对宿舍分配和管理的要求也在不断地提高.这使得管理工作变得越来越繁重复杂和琐碎。采用传统的手工模式进行管理，其效率低，易出错，利用现代信息技术来实现高校宿舍分配的智能化，不仅可以有效的降低分配的人力和时间成本，而且可以提高分配宿舍的质量和效率，更有益于加快数字化校园建设的步伐。也使得管理工作更加人性化，充分体现以人为本的管理理念和服务思想，不断提高服务质量，营造和谐的宿舍氛围为学生提供优质的学习生活环境。

1 宿舍分配系统的需求分析

宿舍分配系统的主要目的是使用先进的信息技术来实现学生宿舍分配相关基础数据的处理，宿舍的分配以及宿舍资源的查询等功能。学生宿舍分配系统主要包括如下的需求：

（1）能够对全校的宿舍资源及宿舍分配情况进行统一管理，并保证宿舍分配的高效性与准确性。

（2）能够收集学生的相关信息，进行数据处理，根据学生的特点为其分配宿舍。

（3）能实时查看住宿的情况，便于分析和统计等。

（4）能够为学生收费系统提供相应的住宿费收费依据。

2 系统设计

2.1 宿舍分配系统的分配原则

（1）学院、专业、班级实行相对集中的原则：尽量将同一学院、专业、班级的学生安排在一起（同一楼层或相近的楼层），为便于进行日常管理，尽量安排同一个专业或班级的学生住满若干间宿舍。[1]

（2）年级集中原则：以便于做好迎新接待，日常活动，毕业设计及就业工作，尽量减小不同的年级之间的互相影响。[1]

（3）对同一楼层的安排，安排宿舍到头后再后退折回，对于不同的楼层的安排，宿舍安排到头后上楼后退折回，不再从头开始，以便使同一个专业或班级的宿舍尽可能地靠在一起。[1]

（4）尽量将作息时间相近，兴趣爱好互补的同学安排在同一宿舍。

2.2 宿舍分配系统的分配流程

根据实际调研的结果，得出影响宿舍氛围的因素及其权重，以确定宿舍分配时所依据的条件及权重。分配前，准备可用的宿舍资源，即增加新宿舍和回收毕业生的宿舍；将学生的基本信息录入互联网服务器的数据库系统后开放该系统，再由学生通过登录该系统填入一些个性化的信息如性格、爱好、作息时间等，到设定的截止日期系统会自动关闭。分配时，系统依据学生的学院、年级、专业、班级、性别、兴趣爱好、作息时间等条件进行加权计算，完成学生与宿舍资源的比对和匹配，在辅以必要的人工干预的同时，实现学生宿舍的智能分配。分配完毕后在网站上公示各宿舍人员名单，若有需要调整的可在公示期内联系宿舍管理员进行适当调整，最后公布各宿舍人员的正式名单。

2.3 算法分析

贪心算法是一种简化解题复杂度的算法，不追求最优解，不用回溯，只希望得到较为满意的解。它的基本思想是：从问题的某一个初始解出发，采用逐步构造当前状态下最优解，以尽可能快的速度逐步逼近给定的目标的搜索方法。贪心算法不在整体上考虑最优，而是把整个问题分成多个阶段，保证在每个阶段求出当前看来的最优解，并且一旦求出解就不再更改，使用贪心算法省去了为找到整体最优解穷尽所有可能而耗费的大量时间，并且可以快速得到较为满意的解。虽然贪心算法不是对所有问题都能得到整体最优解，但对于范围相当广泛的求最优解的问题来说，它是一种最直接的算法设计技术，通过一系列局部最优的解的选择，贪心算法可以产生整体的最优解。[2][3][4][5]

（1）贪心算法的求解步骤。从问题的某一个初始状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数增长最快（或最慢）为准则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。[6]

（2）基于贪心法的宿舍分配算法设计。①首先进行宿舍分配的预处理：将所有学生的学号按性别、学院、年级、专业、班级由高到低的优先级顺序依次排列好。②取出排在最前面的学生，以该学生为对象，计算出其所在班级待分配的同性别学生与他在作息时间、兴趣爱好等特征项的匹配度以及该班级待分配的人数m，根据计算出的匹配度的值将该班级同性别学生重新排序。③根据贪心算法的思想：若m不小于n-1（n为一个宿舍的人员容量），将该学生及与其匹配度高的前n-1个学生分配到一个宿舍，并将m的值减小（n-1）。④当m小于n-1时，保存m个学生的信息，跳过这些学生，继续进行本专业下一个班级学生宿舍的分配。⑤重复步骤②③④，直至本专业所有班级可以分配宿舍的学生分配宿舍完毕。⑥将本专业还未分配到宿舍的学生（之前跳过的学生）按学号排好，取出排在最前面的学生，以该学生为对象，计算出其所在专业待分配的同性别学生与他在作息时间、兴趣爱好等特征项的匹配度以及该专业待分配的人数p，根据计算出的匹配度的值将该班级同性别学生重新排序。⑦根据贪心算法的思想：若p不小于n-1（n为一个宿舍的人员容量），将该学生及与其匹配度高的前n-1个学生分配到一个宿舍，并将p的值减小（n-1）。⑧当p小于n-1时，保存p个学生的信息，跳过这些学生，继续进行本年级下一个专业学生宿舍的分配。⑨依此类推直到该校所有学生分配完宿舍（不同性别不可分配在同一个宿舍）。

3 系统实现与开发工具

根据系统的需求，采用B/S模式进行系统设计，应用C#语言进行程序设计，其数据库设计按照Oracle数据库的标准进行。[7]运用B/S模式，不需要安装客户端的软件，可以支持跨平台访问，支持多校区的联网运行，宿舍管理人员可在多地区、任意时间段登录进行学生宿舍的分配和管理，学生也可在多地点进行信息录入、修改及查询，系统适应性强。

4 结束语

宿舍分配是大学宿舍管理系统中一个非常重要同时也是非常复杂的一个工作，良好的宿舍分配系统对宿舍资源的统一管理有十分重要的意义，可以在很大程度上提高管理效率和资源利用率，能够有效缓解高校宿舍资源的紧张局面，提高学校管理的科学化和人性化。本文采用贪心算法作为学生宿舍分配系统的核心算法，对宿舍分配问题做出了一些有益的尝试，也希望能够为宿舍智能分配系统的研究做出自己微薄的贡献。

参考文献：

[1]舒攀，陈金刚.数字化校园建设中宿舍管理系统的设计与实现[J].武汉工程大学学报，2008，30（4）：108-111.

[2]王伟，余利华.基于贪心法和禁忌搜索的实用高校排课系统[J].计算机应用，2007，27（11）：2873-2876.

[3]邓曦辉.浅谈贪心算法在排课系统中的应用[J].电脑与电信，2011，7.

[4]江朝勇，陈子庆，谢赞福.基于优先级贪婪算法的排课系统的研究与实现[J].信息技术，2008.

[5]聂小东.基于贪婪算法的排课系统的研究与实现[D].广州：广东工业大学，2006.

[6]王红梅.算法设计与分析[M].北京：清华大学出版社，2006，7.

高效冒泡排序算法设计与实现 篇7

排序是一种很重要的数据运算,目的是方便对数据元素的查找。常见的排序算法有插入排序、交换排序、选择排序、归并排序和基数排序。在文献[1]、文献[2]、文献[3]中,分别提出了分组排序、组合式排序、二路选择排序算法。排序算法的执行效率常用算法的时间复杂度和空间复杂度来衡量。

冒泡排序是一种应用广泛的基本排序算法,属于交换排序,其主要思想是:每趟将相邻的数据元素按照关键字值的大小进行两两比较,基于“前小后大”的规则,交换不满足条件的元素,每趟结束,冒出一个最大者到待排序元素的末尾。若经过一趟排序后,没有发生数据元素的位置互换,则可以提前结束排序。

本文在分析了基本的冒泡排序基础上,提出二路冒泡排序,经过一趟两路冒泡排序,在序列首和尾部能同时冒出关键字值最小与最大(最大与最小)的数据元素,减少了外层排序循环趟数,提高了排序效率。

1 算法设计

1.1 算法思想

利用二路冒泡排序,首先从第1个数据元素与最后1个数据元素开始,从前向后与从后向前,同时扫描冒出关键字值最大的数据元素到后位、关键字值最小的数据元素到首位。接着从待排序元素的第2个与倒数第2个元素开始,从前向后与从后向前同时扫描,冒出关键字值最大的数据元素到倒数第2位,关键字值最小的元素到第2位,依此类推,直到所有的数据元素都按照关键字值的大小排好序。

1.2 算法实现

1.2.1 定义存储结构类型

本算法采用线性表顺序存储形式。为了方便理解,将数据项定义成单类型的整型,具体如下(采用C语言编程实现):

typedef struct

{int data[MAXSIZE];/*MAXSIZE为数组的长度*/

int length;/*length是顺序表的长度*/

}SeqList

1.2.2 初始化线性表

通过从键盘上手动输入相关数据构建线性表[4],当然,也可采用生成随机数的形式。

1.2.3 两路冒泡排序算法设计

(1)设计思想。每趟排序都使前后两个有序区各增加一个数据,经过n/2趟排序之后,前后有序区中就都有n/2个数据,而无序区中数据总是大于等于前有序区中的数据而小于等于后有序区的数据,所以整个冒泡排序过程至多需要进行n/2趟排序。

(2)算法设计。

在主函数中调用上面的函数。

1.3 算法实例

位置(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)

1.4 冒泡排序比较分析

利用随机算法生成数据,见表1,将二路冒泡排序算法与简单冒泡排序算法的比较趟数与比较次数进行对比,排序效率如图1所示。

(1)算法的最好时间复杂度。若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:C min=n-1;M min=0。则二路冒泡排序最好的时间复杂度为O(n)。

(2)算法的最坏时间复杂度。若初始文件是反序的,需要进行n/2趟排序。每趟排序要进行n-2i次关键字比较(1≤i≤n-1),且每次比较都必须移动记录3次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

则两路冒泡排序的最坏时间复杂度为O(n2)。

2 结语

二路排序思想可以应用到基本的排序算法中。本文在基本的冒泡排序基础上进行了扩展,引入了二路冒泡排序。有关二路排序的算法效率在文献[3]中进行了详细叙述。本文利用随机生成的数据,对简单的冒泡排序与二路排序进行了对比实验,验证了算法的效率。若元素本身初始状态局部或整体有序时,采取二路冒泡排序或二路插入排序是比较好的策略;若数据量非常大,则可采取二路归并排序算法。基本的二路归并排序算法效率虽然高,但还可以进一步优化,这也是笔者今后努力的方向。

摘要：在分析冒泡排序算法的基础上,对算法进行了改进,使冒泡排序算法的执行效率大大提高。用随机生成的数据将冒泡排序与本排序方法进行了实验比较,验证了该算法的高效性。

关键词：排序,冒泡排序,二路选择排序,二路冒泡排序

参考文献

[1]汪维清,罗先文,汪维华.分组排序算法[J].计算机工程与应用,2008(33):53-56.

[2]周建钦.组合式排序算法[J].安徽工业大学学报:自然科学版,2006(4):449-452.

[3]于春霞,代文征.二路选择排序探究[J].黄河科技学院学报,2009(6):155-159.

[4]王晓东.数据结构与算法设计[M].北京:电子工业出版社,2002.

[5]刘琴.计算思维在“数据结构”课程教学中的运用[J].计算机教育,2013(5):32-34.

[6]叶茂功.数据结构项目化教学[M].北京:国防工业出版社,2013.

[7]姜浩.“数据结构”教学过程中应重视算法设计与分析能力的培养[J].计算机教育,2007(16):27-29.

[8]杨秋格,吴鹏,黄猛,等.计算思维驱动的数据结构实践教学改革[J].福建电脑,2015(2):58-59.

克隆选择算法的研究与实现 篇8

人工免疫系统是一个新兴的计算智能研究领域。近年来，人工免疫系统及其应用已逐渐成为了智能信息系统中的研究热点。生物免疫系统的免疫识别过程能在较短的时间内利用数量相对有限的抗体去识别近乎无限多的抗原，从信息处理的角度看，这是在资源受限条件下的一整套高效问题求解机制。克隆选择学说的基因重组、亲和度成熟、受体编辑等机制较好地从个体层次上阐述了这种高效问题求解能力的形成，因而成为多种人工免疫系统模型和算法的重要思想来源，免疫算法就是一种借鉴该系统特性而形成的启发式搜索算法．它具有保持种群分布多样性的特性，避免陷入局部最优解的优点。

二、克隆选择原理

克隆选择是生物免疫系统理论的重要学说，其原理 (如下图1所示) 的基本思想是只有那些能够识别抗原的细胞才进行扩增，只有这些细胞才能被选择并保留下来，而那些不能识别抗原的细胞则不选择，也不进行扩增。骨髓中微小的“休眠”的B细胞每一个都载有一个不同的抗体类型。这些细胞载有对于抗原特异的受体，扩增分化成浆细胞和记忆细胞。

免疫系统在成长的克隆中也是自适应的，同时也呈现了一种变异机制，在对抗体特异编码的基因中产生极高频率点变异。该机制（体细胞高频变异）与为改进抗原结合而进行的选择，共同导致细胞与抗原具有极高的亲和力匹配。

根据免疫系统中的克隆选择学说的思想，该算法在抗体种群和抗体优秀决定基中进行克隆选择操作，全面的模拟了生物免疫系统克隆选择的过程，很好的保持了抗体种群的多样性。

三、克隆选择算法

3.1抗体/抗原匹配算法

要确定一个B细胞对象与提呈的抗原结合得有多好，在抗原上任何点开始匹配；匹配算法计算每一位，在抗原与抗体之间以互补的方式进行匹配，得出匹配值，再从匹配分值得到结合值，根据抗体的结合值的大小可以看出抗体和抗原是否结合的完美，并且可以判定出结合完美的抗体中哪些决定基起到了关键的作用。

对于一个抗体结合一个抗原，结合必须是稳定的，也就是匹配分值在匹配发生之前必须超过一定的阈值。该设定阈值为抗体大小的一半。该方法是Hightower的匹配算法的修改，只是多种伪生物匹配的一种。

抗体/抗原匹配算法的描述：

(1）初始化抗体群，针对抗体与抗原的决定基逐位进行异或操作，若抗体和抗原相对应的决定基相同为0，不同为1，结果统记为c;

(2）将抗体与抗原的决定基逐位进行异或操作结果的累积和记为（公式一）；

(3）对由两个或者更多个1组成的每一区域记录长度为l;

(4) 记抗体的结合度为 (公式二) ;

(5) 定义阈值为

3.2克隆选择算法的实现

克隆选择算法的实质是在进化过程中，在每一代最优解的附近，根据亲和度的大小进行克隆，产生一个变异解的群体，从而扩大了搜索范围 (即增加了抗体的多样性) ，有助于防止进化的早熟和搜索限于局部极小值，同时通过克隆选择来加快收敛速度。其基本思想为：随机生成N个抗体组成的抗体群，对这些抗体进行一些操作后，选出抗体中优秀的决定基片段，针对这些优秀的决定基片段为人民提供良好的生活品质。

我们应该提倡设计的原创性！创造性的建筑设计可使事物再现其岁月流逝所失去的东西，它以一种异化和同化的作用过程，使我们再一次感受到它们的存在，而这正是“场所精神”的本质所在。

设计的本身就是积累与深化的过程，实现于主观世界的创造性思维向客观世界的物质实体转化。它并不是由人脑凭空产生，而通过物质基础的保证，生活经验的积累，艺术素养的沉淀，理论总结的升华。建筑，作为一门艺术，具有历史性，美观性。但她又不同于其他纯粹艺术的特征就在于她的功能性、实用性。脱离功能限定的“设计”概念，泛艺术化倾向的“设计”概念，都是人的欲望和道德相悖而需要协调的内容。这样对“美”的追求不符合建筑装饰行业可持续发展的原则。满足人的这种“欲望之美”的追求不应该作为建筑设计艺术原创性的定位。

建筑最现实的艺术，而不是高高在上，让人顶礼膜拜的艺术，作为生活中与人交流的方式，植根到普通人的日常生活中，帮助并给人们带来快乐。同时那些少数人的高尚品质无法代表正真意义上的“生活的高品质”。只有当设计普及大多数人，并让大多数人都能从中收益时，才是达成了正真的高度。在丹麦，融入大众拥有的设计，被看成是最崇高的，设计需要以人为本，更为完美生活和贴近心灵———这不是什么口号, 而是实实在在的事情, 当设计与人息息相通时, 它能让大众感到艺术和文化的气息, 获得善良、真诚以及美好情感的回馈。

对中国建筑设计行业而言，现在正是一个新的起点：一切充满了不确定、交锋和各种可能。正如矶崎新大师所说“那些未建成的建筑，非常有意义”。设计师独立意识和创新精神的培养以及行业的规范化，是开展一切的基础。我们应该更加注重独立思考和判断的能力，有意保持独立性，放下历史意识的包袱，崇尚自我发展道路，做自己喜欢的作品，有自己的见解和洞察力。

摘要：基于人工免疫系统的原理, 提出了一种克隆选择算法。该算法引入了克隆选择、受体编辑、抗体循环补充机制等思想, 并通过整合克隆选择过程中亲和度的成熟, 可在搜索过程中自动获取与积累相关联搜索空间的知识, 在有限资源的条件下高效的求得问题的解。

关键词：免疫原理,克隆选择,抗体循环补充

参考文献

[1]韦巍, 张国宏.人工免疫系统及其在控制系统中的应用.控制理论与应用, 2002, 19 (2) :157-160

[2]莫宏伟.人工免疫系统原理与应用.哈尔滨工业大学出版社.2003.1390

[3]罗小平.人工免疫遗传学习算法及其工程应用研究「学位论文」.浙江大学.2002.7.129

[4]Luh Guan-Chun, Chueh Chung-Huei.Multi-objective optimal design of truss structure with immune algorithm[J].Computers and Struc-tures, 2004.82:829-844

去噪算法的分析与实现 篇9

图像的滤波重建是图像处理学的一个重要分支, 早在20世纪40年代, N.Wiener就阐明了再平稳条件下的线性滤波理论, 即Wiener滤波器理论, 这些理论在控制领域得到了广泛的应用。但是Wiener要求储量大, 计算的复杂度高, 在后来的图像处理领域逐渐诞生了双边滤波, 高斯滤波, 中值滤波等算法。

优化边缘检测算法, 加入了各种滤波算法, 通过编写一些小的程序实现各种滤波的过程, 这是优化图像的一种方式也是图像处理的一般步骤, 滤波的目的是减少图像上噪声和失真, 但是使用滤波算法或多或少都会减少边缘的强度, 因而图像的增强和滤波之间是一个折衷的选择。滤波的图像效果会有些模糊, 也称为模糊处理。

实现滤波的算法有很多种, CV_BLUR (简单滤波) 、CV_BLUR_NO_SCALE (简单无缩放变换的滤波) 、CV_MEDIAN (中值滤波) 、CV_GAUSSIAN (高斯滤波) 、CV_BILATERAL (双边滤波) 。

2 主要滤波算法原理分析

2.1 高斯滤波

滤波算法中, 周围局部领域的像素值决定了目标点的像素值。具体实现在2D高斯滤波中分别将不同的高斯权重值也就是加权平均之后得到的当前点的最后结果。然而此处的高斯权重因子是利用了两个像素之间的空间距离得出的。通过高速分布曲线我们可以看出, 离目标像素越远的点对最终结果的贡献越小, 反之则越大。

2.2 双边滤波

双边滤波是在高斯滤波中加入一部分权重来得到更好的处理效果, 应用了卷积原理。先对其进行离散化, 这个步骤是在处理前完成的。而且没有必要对每一个局部像素从整张图像上都用加权操作这个过程, 从距离上, 如果像素超了一定程度, 其实实际上对目标像素的影响是非常非常小的, 几乎可以忽略不计。

2.3 中值滤波

中值滤波是一种非线性信号处理技术并且能够有效地抑制噪声, 其基本原理就是把数字影像或者数字序列中的用该点的一个领域的各点值的中值代替让周围像素成为接近值, 进而消除孤立噪声点。二维中值滤波输出模型为g (x, y) =med{f (x-k, y-l) , (k, l∈W) }, 其中, f (x, y) , g (x, y) 分别为原始图像和处理后图像。W为二维模板, 通常为2*2, 3*3区域, 也可以是不同的的形状, 如圆形, 线性, 圆环形, 十字形等。

2.4 简单滤波

窗口中输入图像对应像素的简单平均值是输出图像的每一个像素。其支持1-4个通道处理32位或者8位的浮点图像。

2.5 不缩放比例滤波

对每个像素的各个领域求和, 可以利用函数CVintergral来计算图像尺度的变化。支持8位的输入图像, 也可以在32位浮点图像上进行, 结果也是32位浮点类型, 在很多情况下选择不缩放比例的模糊操作是由于比缩放比例的模糊操作要快。

3 通过评判标准比较滤波算法

3.1 评判标准

在估计噪声方差中可以用到小波变换、图像二维小波分解、噪声方差估计法, 能不能去除椒盐噪声, 双边滤波的弱项在于对椒盐噪声的处理而中值滤波对此却有很好的处理效果。

3.2 算法比较

高斯滤波虽然在低通滤波的算法中效果非常好, 但是还存在另一个问题, 它只考虑了像素见的空间上的关系, 所以结果会丢失边缘的信息, 但是高斯滤波对高斯噪声有很好的去噪效果。

双边滤波, 在高斯滤波的基础上加入了另外的一个权重, 在数学上用了无限积分在空间中应用了离散化。双边滤波对低频噪声处理效果不好, 但对高频却有很好的处理效果。

中值滤波是一种非线性平滑技术, 对某一点的灰度值设置为所有像素点灰度值的中值。对消除椒盐噪声很有效, 而且可以有效的保护边缘。

简单滤波对输入图像的像素求平均值, 支持一到四个通道处理8位或者32位图像。

简单无缩放比例滤波, 对每个像素的一定区域求平均值, 其尺度变化用CVintergral来计算。支持8位输入图像, 也可以用32位浮点图像进行。

4 滤波算法优化效果对比

对边缘检测算子加入各种滤波算子, 加入滤波算法是为了优化边缘检测算法, 加入这些算法的时候首先要找到处理图片的路径, 进行灰度转化, 同时分配一幅图像的结构空间, 用于储存单通道的灰度图像。由于这些算法位于按键触发的小程序中, 将写好的滤波算法直接调用就可以了。

将各种滤波算法对canny边缘检测算法优化后用QT用户界面展示出来。

参考文献

[1]章毓晋编著.图象处理与分析[D].北京清华大学出版社, 1999.

[2]唐良瑞, 马全明, 等编著.图像处理实用技术[M].北京化学工业出版社, 2002:40-41.

指纹识别算法研究与实现 篇10

关键词：预处理,扇形分区,二值化,Gabor滤波,特征提取和匹配

随着计算机技术的发展,指纹识别技术已在各个领域得到广泛的应用。但是随着应用的日益普及,人们对系统的识别性能提出了更高的要求。如何提高低质量指纹图像,特别是存在严重非线性形变的指纹图像的识别性能,是研究人员面临的重大挑战之一。为了使指纹的识别率更高,识别速度更快,识别算法的设计,在系统中占了尤为重要的地位,其过程包括图像预处理、指纹的特征提取、指纹的匹配和输出结果。

指纹包含若干交错分布的脊线和谷线,相邻脊线之间的交叉点和脊线的端点统称为细节点。基于细节点特征的指纹图像匹配方法,是目前自动指纹识别系统中最基础、应用最广泛的匹配方法。但是如果指纹图像质量比较低,获取的细节点集合中往往会包含一定数量的伪细节点,同时还会丢失许多真实的细节点,即使是正确提取的真实细节点,其类型、位置和方向值也会存在一定的误差。这些因素使得仅仅基于细节点特征匹配指纹图像效果并不理想。为了提高识别的准确性,人们在细节点之外[1],不断尝试引入其它更加鲁棒的特征[1]。同时,根据指纹的总体特征,指纹图像又简单地分为弓形纹、箕形纹、螺形纹等。本文针对从公开数据库BVC2004随机选取的100幅图像做了大量处理工作[2],主要包括指纹图像灰度归一化和均衡化、指纹图像扇形分区[3]、指纹图像二值化、不同方向gabor滤波、特征提取、编码、匹配算法。

1 指纹图像预处理算法

1.1 指纹图像归一化和均衡化

指纹归一化[4](Fingerprint Normalization)的目的是为了消除传感器本身的噪声以及因为手指压力不同而造成的灰度差异,将不同原图像的对比度和灰度调整到一个固定的级别上,为后续处理创造一个统一的规格。一般按下式进行归一化[5]:

设整个灰度图像I的大小为N×N,其灰度均值和方差的大小分别为M和V,由式(1)、(2)确定:

undefined

undefined

归一化的公式见式(3):

undefined

其中,I(i,j)代表原始图像(见图1)在(i,j)处的灰度值, G(i,j)代表归一化后图像在(i,j)处的灰度值,M0和VARO分别期望得到的均值和方差。

对于一个离散的图像,第i个灰度级的出现频率数目用ni表示,该灰度像素对应的概率值pr(ri)为:

undefined

式中:n为像素总数,ri满足归一化条件。

图像进行均衡化的函数表达式为式(5):

undefined

式中:k为灰度级。

1.2 指纹图像扇形分割

把图像分成N×N的非重叠小块[6],分别计算每一块的均值M和方差V,由式(6)、(7)确定。

undefined

undefined

其中,M和V分别为灰度均值和方差。

由于大部分的指纹图像可以使用采集器的dPi(每英寸点)规范来衡量,所以比例不变性是一个很重要的问题。旋转和平移不变性可以基于旋转平移不变的指纹内在特征建立一个参考框架来实现。也可以根据指纹中几个有影响的结构建立许多参考框架来获得多重表示。以额外的处理和存储消耗为代价,当提取特征算法不能提取一个或多个参考框架时,多重表示匹配具有鲁棒性[7]。本文提出的特征提取策略中,平移是在特征提取阶段由单个参考点定位解决的。现有的特征提取的执行假定指纹是垂直方向的。通过基于图像数据的指纹方向自动定位,图像旋转将得到纠正。当前的特征提取策略根据参考点将给定的指纹的模式区扇形化。

令I(x,y)表示在一个M×M的图像中象素(x,y)的灰度,(xc,yc)表示参考点。模式区定义为所有块Si的集合,其中第ith个块根据参数(r,θ)计算如下:Si={(x,y)|b(Ti+1)≤r≤b(Ti+2),θi≤θ≤θi+1,1≤x≤N,1≤y≤N}其中undefined。

b是每个段的宽度,k是每段上的块的数目,而且i=0…B×k-1,其中B是围绕参考点的用于特征提取的中心区域的段个数。这些参数依赖图像分辨率和尺寸。在特征提取中采用五个中心段(B=5)。每一个段是20象素宽(b=20),而且分割成十二块(k=12),结果如图1图示。

1.3 指纹图像二值化

二值化是将灰度指纹图像变成0,1两个灰度级的图像,目前最常用的是阈值法。阈值法的主要思想是在指纹增强时设定某一灰度阈值,将图像像素灰度与阈值相比较,大于此值的灰度置灰度最大值255(白色),小于此值的灰度置0(黑色),从而使图像前景和背景彻底分开。在本算法中我们采用matalb自带的图像处理函数并且取得了比较好的效果。用于实现灰度图像二值化的Matalb函数代码为:

function I=binarization(a)

level=graythresh(a);

l=im2bw(a,level)。

2 指纹特征提取

2.1 不同方向Garbor滤波

Gabor滤波器是一种具有方向选择性和频率选择性的带通滤波器[9],通过滤波可以去除噪音,并不失真地保留指纹脊和谷的结构信息,是指纹特征提取的常用物理模型。将Gabor滤波器作用于指纹特征提取区域可以很好地提取指纹特征。指纹有局部平行的纹线和谷线,容易定义局部频率和方向。适当调整的Gabor滤波[10],不仅可以去噪,还能保护真的脊线和谷线结构,同时提供包含在图像的特定方向中的信息。一个细节点在局部平行的纹线中是不规则的,所以尝试使用不同方向的加博滤波器来捕获这个信息。

偶对称的二维Garbor滤波器的形式如式(8):

G(x,y;undefined

undefined

其中,θ是滤波器的方向因子;f表示指纹纹线在θ角度上频率度参数,定义为平均脊线宽度λ的倒数1/λ;f是在x轴上沿θ方向的正弦平面波;δx′和δy′相应的是沿x′和y′轴的高斯函数的标准差。根据经验值,取f=1/10,δx′=δy′=4.0,θ∈{0°,22.5°,45°,67.5°,90°,112.5°,135°,157.5°}。一般利用4方向(0°,45°,90°,135°)的Gabor滤波可以提取指纹的全局特征;8方向的Gabor滤波用来提取指纹的局部脊线特征[13]。

设置滤波频率f等于平均纹线频率(1/K),其中K是纹线间的平均距离。平均纹线间距在500 dpi的图像中大约是10象素。当f太大时,滤波图像将产生假的纹线,而f太小时,相邻的两条纹线会合成一条[11]。在本算法中,我们对共使用了8个不同的θ值(0°,22.5°,45°,67.5°,90°,112.5°,135°,157.5°)。用0度garbor滤波后的图像分别卷积其他8个不同值的滤波图像的方法来平滑其他方向的纹线。

其中图2、图3、图4分别为θ值取0°、22.5°、45°、67.5°、90°、112.5°、135°、157.5°的garbor滤波器、滤波后的指纹图像以及特征向量图。

2.2 指纹特征向量提取

在本文中将指纹图像分成大小为8×8的图像块,在每个图像块B中,任意一点S∈B的梯度可表示为gs=(gundefined,gundefined)。图像块B的协方差矩阵表示为式(9):

undefined

其中J的特征向量值为式(10):

undefined

则定义标准化一致性度量因子为式(11):

undefined

其中反映了图像块B的脊线和谷线方向的清晰程度。若l1≫l2,≫1则脊线谷线方向很清晰,相反则图像质量很低。因此经滤波后得到的指纹图像是纹理与滤波方向一致的区域,滤波后的纹理比较清晰,相反,与滤波方向差别越大,则得到的指纹图像越模糊[12]。我们将作为图像块B的质量特征向量,经方向滤波后得到的指纹特征向量指纹码(见图5)。

3 指纹编码及纹理匹配

3.1 指纹编码

通过对上面得到的不同方向的指纹特征向量按顺序排列存储,就得到了指纹编码。由于每幅滤波图有80个特征,一个指纹的8个滤波图一共有 640(80×8)个特征。每个特征可以被量化为256以内的值,需要1字节的存储空间[13],所以整个特征向量仅需要640字节存储空间。提取的指纹特征存储在数据库中,警用指纹识别系统的数据库还包含输入指纹的压缩图像以及与前两类数据相应的罪犯的文本记录信息。

3.2 指纹图像匹配

指纹匹配[14]是指从已有的指纹集合中找出与待识别指纹图像匹配的过程。指纹匹配是自动指纹识别系统中最关键的一步。目前指纹匹配方法可以分成两类,即验证(Verification)模式和识别(Identification)模式[15]。验证模式即一对一比对,在这种模式通过将现场采集的指纹特征与已经保存在模板数据库中的一个生物特征进行比对,并与一个唯一的个人识别码建立联系,从而达到身份确认的目的,防止多人用同一个身份。而识别模式是1:N的比对,通过将现场采集[16]到的指纹特征与模板数据库中的指纹特征逐一对比,找到与之相匹配的指纹特征信息,从而达到身份验证的目的。

在本文中我们采用识别模式,原理为通过计算指纹码之间的欧式距离[16],与最小距离相对应者即为输出结果。

4 系统运行结果

通过用公开数据库BVC2004中100张不同的指纹图像进行了指纹图像编码,并作为标准指纹数据库,同时利用已完成的指纹数据库,随机的抽取60个样本分别进行10次模拟识别测试,统计平均GAR(genuine acceptance rate)为94.17%、FRR(false rejection rate)为5.83%、FAR(false acceptance rate)为0%,达到使用要求。

表1为10次随机抽取20个样本得到的GAR、FAR、FRR。

FRR曲线如图5所示:

5 结论

算法与实现 篇11

【关键词】多CCD；大幅面扫描仪；图像拼接；拼接线

0.引言

多CCD大幅面扫描仪主要采用外视场拼接方式，通过对各个CCD采集的图像进行图像拼接处理最终得到完整的大幅面扫描图像。由于扫描仪多CCD之间的非一致性以及扫描材质表面的平整程度等因素，会导致扫描图像拼接存在较大误差。如果使用直接拼接方法进行处理时，则在拼接缝附近会出现较为明显的拼接缝，这严重降低了扫描图像的质量。

最佳拼接线可以消除拼接缝两侧图像灰度值过度不连续的问题。James Davis[1]很早提出了一种拼接缝寻优方法，他利用Dijkstra算法检测最佳拼接线，但该算法复杂度高且拼接速度慢。在文献[2][3][4]中通过采用动态规划的思想来寻找最佳拼接线，但由于使用的是人为的栅格结构，会使得寻找到的拼接线有可能不是最佳的。其他拼接缝寻优方法还有最小灰度差值法、梯度差异法、重叠区域平方线法[5]等，这些方法算法实现简单，运算速度快，但是处理效果不是很理想。

本文针对上述各种方法的不足，设计并实现了一种寻找最佳拼接线的方法，其在多CCD大幅面扫描仪的图像拼接处理中有一定的应用价值。

1.扫描图像配准策略

多CCD大幅面扫描仪图像的配准策略是扫描图像拼接的关键。通常使用的配准算法是基于相邻两个CCD采集的图像重叠部分对应的像素在RGB色彩空间系统中灰度级的相似性。相邻图像的对应重叠部分上的两个像素点A、B在RGB色彩空间中的距离为：

根据上式搜索D为最小值时的（x，y）点，可以认为该点为最佳的拼接位置。配准过程分为粗略配准和精确配准两个步骤。粗略配准过程中，网格每次水平移动一个网格间距。精确配准过程中，以粗略配准的最佳匹配点为中心，移动步长减半，计算网格点对应像素RGB差值的平方和，并与当前最优值进行比较，如果优于当前值，则替换当前的最佳匹配点。循环进行该过程，每次步长减半，直至水平步长为零为止。

经过上述配准步骤后，确定了拼接缝的位置，并且确定了每个CCD使用的有效采集像元范围及重叠区域宽度。

2.寻找最佳拼接缝

扫描图像经过相关预处理及确定重叠区域宽度之后，便可以进行最佳拼接缝的寻找。本文提出的拼接缝寻优方法具体设计的流程如图2.1所示。

根据扫描图像拼接缝寻优流程图，下面给出拼接缝寻优方法的具体实现步骤：

第一步，裁剪获取相邻CCD采集的两幅图像的重叠部分。通过图像配准可以得到重叠区域，将重叠部分截取存入单独的两幅图像中。

第二步，将重叠图像做差得到差图像。如果是彩色方式扫描，则彩色图像各个通道做差，将得到的彩色差图像灰度化，得到灰度差图像。

第三步，在灰度差图像上寻找拼接缝上的第一个像素点。这里选取灰度差图像第一行图像数据中像素灰度值最小的那个点作为拼接缝的起始像素点，使用二维的位图数据结构存储拼接缝上的点。

第四步，从拼接缝上的起始像素点开始依次找出所有满足条件的像素点，规则为：以刚刚寻找出的拼接缝上的像素点为参考点，在其周围的八个像素点中寻找出当前不在拼接缝上，并且权值最低的像素点作为拼接缝上的下一个像素点。其中像素点权值的具体定义为：（PixelValue+1）×K+Height-y。

像素点权值主要由两部分组成：一个是像素点灰度值大小，另一个是像素点靠近图像底部的程度。这里的PixelValue代表像素点的灰度值，K为一个比例参数，Height为灰度差图像的高度，y为参考点的纵坐标。其中 K值一般取值为10到20之间。K值过小，拼接效果不是很好；K值过大，拼接缝上的像素点会增多，影响处理速度。

第五步，根据二维位图数据结构中记录的拼接缝上的点，实现扫描图像的拼接。

3.扫描仪图像拼接缝寻优结果分析

为了验证本文提出的扫描图像拼接缝寻优方法可以降低拼接缝处扫描图像的过渡不连续性，采用油画扫描介质进行了测试，具体测试及结果分析对比如下。

图3.1是直接拼接的图像，可以看出拼接图像在拼接缝的上半部分丢失了部分图像数据，在拼接缝的下半部分则存在冗余图像数据，仍然存在较为明显的拼接缝。按照拼接缝寻优进行拼接得到的图像如图3.2所示。

对比分析两种拼接方法可知，对于表面凹凸不平的油画扫描材质，进行扫描后图像变形较大，如果进行直接拼接，则会出现较为明显的拼接缝。而如果重新寻找一条更优的拼接缝，然后按照该拼接缝进行扫描图像的拼接，则可以获得较好的效果，消除了拼接缝处的过渡不连续现象。 [科]

【参考文献】

[1]James Davis. Mosaics of scenes with moving objects.IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Santa Barmara，1998：354-260.

[2]方贤勇，潘志庚，徐丹.图像拼接的改进算法. 计算机辅助设计与图形学学报，2003，15（11）：1362-1365.

[3]Efros A，Freeman W.Image quilting for texture synthesis and transfer. Computer Graphics Proceedings，Annual Conference Series.ACM SIGGRAPH 2004，Angeles，California，2001：341-346.

[4]Marie-Lise Duplaquet. Building large image mosaics with invisible seam lines.Proceedings of SPIE Aerosense.Orlando，Florida.1998，3387：369-377.

高阶哈夫曼算法分析与实现 篇12

一般哈夫曼算法是根据符号的频度分配编码进行压缩的。即出现次数较多的符号分配较短的编码, 出现次数较少的符号分配较长的编码。高阶哈夫曼算法是依据前面出现的符号来统计当前符号的频度, 然后再根据这样的频度分配编码。前面出现的符号称为上下文 (Context) , 依据上下文的长度称为阶 (Order) 。假如依据前面出现的3个符号的上下文, 称为3阶哈夫曼算法。相应的, 一般哈夫曼算法可以称为0阶哈夫曼算法。因为一般哈夫曼算法只考虑当前符号的频度, 不考虑当前符号前面的符号。

高阶哈夫曼算法需要建立一个复杂的统计模型。保存压缩数据时也需要导出一个异常复杂的码表, 以便解码程序重建统计模型。这些问题使得高阶哈夫曼算法速度较慢, 而且压缩性能不稳定。但是, 对于部分数据高阶哈夫曼算法可以获得比0阶哈夫曼算法高得多的压缩率。

2 统计模型分析

哈夫曼算法需要扫描一遍数据统计符号的频度, 建立符号的统计模型。这个过程被称为建模。0阶哈夫曼算法的建模过程非常简单, 只需要建立一个同符号容量一样大小的数组计算频度即可。高阶哈夫曼算法的建模过程 (以下简称“高阶建模”) 比较复杂, 由于涉及到上下文的查找, 所以使用Trie结构比较合适。Trie的概念最早由Donald E.Knuth在1972年提出[1], 它是Retrieval的缩写。Trie是一种搜索树, 从根节点开始根据关键词中的符号进行查找, 从而由一层节点进入到下一层节点。每次下移一层都消耗掉关键词中的一个符号。当移动到一个终止节点或终止符号时完成一次成功的查找。

高阶建模中使用的Trie与一般的Trie略有不同。一般Trie需要有一个终止节点或终止符号来判断关键词的结束, 高阶建模中的Trie则不需要。因为阶数是固定的, 所有关键词的长度都一样而且是不变的。这意味着Trie中的终止节点都在同一层, 而且是最下一层。在查找中到达这一层就表示查找结束。

现在来看一个例子:“ABABACABABADBABC”。这份数据的长度是16, 共出现了4种符号。假设对这份数据进行3阶哈夫曼算法压缩, 来分析一下高阶建模的过程。

首先, 设定所有数据都是由同一个引导上下文开始的。在3阶的情况下设定引导上下文为“###”。注意, “###”是什么符号并不重要。甚至于“###”3个符号是否相同也不重要。重要的是编码程序和解码程序必需要使用相同的引导上下文, 这样才可以正常地编解码。在数据的开头添加了引导上下文之后就可以开始建模了。建模时, 从原数据的第一个符号开始扫描数据。根据符号前的3个符号确定上下文。在例子里, 上下文依次是“###”、“##A”、“#AB”、“ABA”、“BAB”……。如果对应上下文中的符号没有在Trie中, 就插入符号并设置频度为1。如果有在Trie中, 就增加对应的频度。最后, 建立完成的模型如图1所示。

在建立完统计模型后, 就可以为符号分配编码。分配时以上下文为单位, 不同上下文中的符号分配不同的编码。分配共分为3种情况:第一种情况, 上下文中只出现了一种符号。这种情况称为单叶子节点。在例子里出现了很多单叶子节点。例如, 上下文“###”后只出现“A”, 上下文“ACA”后只出现“B”。对于单叶子节点不分配编码, 因为单叶子节点的符号可以根据上下文直接判断出来。当进行编码的时候遇到单叶子节点可以直接跳过。例如在编码的时候, 当前的上下文为“A-CA”现在要编码“B”, 那么什么都不输出直接开始编码下一个符号。例如在解码的时候, 当前的上下文为“ACA”现在要解码一个符号, 那么什么都不输入直接判断出符号“B”。因此, 单叶子节点不需要分配编码。

第二种情况, 上下文中出现了两种符号。这种情况称为双叶子节点。在上面的例子里上下文“BAB”就是双叶子节点。在上下文“BAB”后出现了两种符号“A”和“C”。双叶子节点分配编码比较简单。这时可以忽略符号频度, 直接按照符号值的大小分配编码。“A”可以分配编码“0”, “C”可以分配编码“1”。

第三种情况, 上下文中出现了三种或者三种以上的符号。这种情况称为多叶子节点。在上面的例子里上下文“ABA”就是多叶子节点。在上下文“ABA”后出现了三种符号“B”、“C”、“D”。多叶子节点可以像一般的哈夫曼算法一样分配编码。“ABA”一共出现了4次, 其中有2次后面出现“B”, 各有1次后面出现“C”和“D”。可以根据这些频度信息为符号“B”、“C”、“D”分配编码。在实现的时候使用了范式哈夫曼算法分配编码。

为符号分配编码的时候需要对Trie遍历一遍, 找出所有存在的上下文, 为上下文中的符号分配编码。编码全部分配完成后还要对数据再扫描一遍输出编码。3阶范示哈夫曼的编码表如表1所示。作为对比, 在例子中, 如果用0阶范式哈夫曼算法进行编码。那么生成的编码表如表2所示。

现在可以比较一下, 在不计算码表输出大小的情况下, 3阶算法最后输出的数据只有9位。而0阶算法最后输出的数据有28位。很明显, 3阶算法极大地提高了压缩率。但是, 同时也注意到:3阶算法要输出一个比0阶算法大得多的码表。而庞大的码表会严重地拖累压缩率。

3 统计模型实现

统计模型的具体实现主要集中在Trie结构的实现上。Trie是一种树结构, 一种实现方式是每个节点都保存一个同符号容量一样大小的数组。例如, 对于字节数据, 符号容量为256。那么每个节点都保存一个256大小的数组, 每个数组元素都保存一个指向其子树的指针。但这种方式会占用大量的存储空间, 不适合在内存中使用。另一种实现方式是兄弟-儿子方式。即:每个节点都保存两个指针, 一个指向兄弟节点, 一个指向子节点。另外还要增加一个域保存符号值。这种方式可以节约存储空间, 但是查找速度很慢。第三种方式在上述两种方式上取得了一个折中。这就是双数组Trie (Double Array Trie) 。Jun-Ichi Aoe在1989年提出了这种数据结构[2]。双数组Trie是一种很高效的方法, 尤其是查询速度非常快。

双数组Trie将Trie看成是一种DFA (Deterministic Finite Automation, 确定有限自动机) 。在树结构中, 每个节点看成是一个DFA状态。从树的一层节点移动到下一层节点看成是DFA状态转换的有向边。双数组Trie将一个DFA保存到两个数组Base和Check中。Base中的每个单元对应于Trie中的一个节点。Base中每个单元保存对应节点的子节点的起始索引。Check与Base平行的工作, Check中每个单元保存对应节点的父节点的索引。双数组Trie可以将不同父的节点交叉存放在一起, 利用Check中的信息来区别彼此。在查找时, 利用Base中的起始索引加上符号值来完成一次状态转换。利用Check中的索引来验证这次转换是否成功。

双数组Trie的插入操作较为复杂。插入时先要查找关键词, 当出现状态转换失败时才可以插入。出现状态转换失败后, 根据当前Base中的起始索引计算出插入单元的索引。如果该单元空闲那么可以直接插入, 如果没有空闲那么将出现冲突。解决冲突的方法是:首先, 根据当前Base中的起始索引找到所有的子节点。然后, 在Base中查找空闲单元, 空闲单元的位置必需足够容纳所有的子节点。如果没有足够的空闲单元就扩展数组。接着, 将子节点移动到新的位置, 并更新Base中的起始索引。最后, 如果子节点不是叶子节点, 那么遍历所有子节点的下级节点, 更新Check中对应父节点的索引。可以发现, 当插入出现冲突的时候操作会变得非常复杂, 这也是双数组Trie所有操作中最耗时的部分。

在双数组Trie实现的时候, 可以利用Base和Check中的空闲单元建立一个双向循环链表。利用该链表将空闲单元连接起来, 这样可以加快冲突解决时空闲单元的查找速度。将Check中的空闲单元设置为负数, 这样就可以将空闲单元和非空闲单元区分开来。一般情况下, 空闲单元在链表中按照单元的位置排序。位于数组前面的空闲单元放置在链表的前面。这样这些空闲单元将优先分配。这种做法可以减少数据的稀疏, 降低内存的占用。但是, 这种做法速度较慢。一方面, 当一个单元被释放, 放入链表的时候。需要在链表中查找, 以确定插入位置。另一方面, 数据稀疏减少意味着冲突次数的增多。而冲突的解决是最耗时的操作。高阶建模时需要临时建立双数组Trie, 所以速度也很关键。这里有一个简单的改进方案:对链表不做排序, 使用无序链表。当一个单元被释放的时候, 直接将该单元放入链表开头。扩展数组时新增的单元也放入链表开头, 优先分配。这样做会增加内存的使用, 但可以提高速度。利用卡尔加里语料库 (The Calgary Corpus[4]) 中的18个文件对两种方案进行比较测试。其结果如表3所示。

以上测试所使用计算机的配置见本论文第5节。在本次测试中使用3阶哈夫曼算法进行压缩。其中的耗时是压缩完成后所使用的时间。在压缩过程中是以字节 (8位符号) 为单位进行压缩。数组空间不足时, 每次扩展一个符号容量大小, 即:256个单元。单元个数是指建模完成后双数组Trie总共占用的单元个数。使用个数是指所有单元中实际使用单元的个数。原方案使用排序链表, 而改进方案进行无序链表。

现在可以比较一下测试结果。原方案的空置率明显很低, 大约在20%到30%左右。这证明数据稀疏较小。但是, 冲突次数和耗时明显比较高。改进方案的空置率在40%到50%左右, 也就说有一半左右的单元是空闲的。对于部分文件, 空间占用“恶化”的比较利害。例如“obj1”、“obj2”等文件, 空置率高达70%左右。在改进方案中, 双数组Trie的内存占用在数MB左右。但是, 它的耗时比原方案快很多。所以说, 从总体而言, 改进方案还是可以接受的。

除了上述的改进方案外, 还有一些可以改进的地方。前面已经讲过, 高阶建模中使用的Trie与一般的Trie略有不同。对于双数组Trie也是如此。一般情况下, Base中的终止节点用负数来表示, 其他的节点用正数表示。但是在高阶建模中不需要终止状态, 查找何时终止可以用阶数判断出来。那么Base中的非终止节点也可以用负数来表示, 这就意味着Base中保存的起始索引可以为负数。那么在分配子节点的时候可以将子节点尽可能地往数组前方放置, 这样可以减少数据稀疏。另外, 最后终止节点对应的Base单元 (以下简称“最终单元”) 将不再使用, 当然可以利用最终单元来保存其他信息。

在编码的时候, 最终单元对应于上下文中的一个符号。在建模期间可以利用最终单元来保存符号的频度。在分配编码的时候, 可以建立一张编码表保存所有上下文中符号的编码及其位长。然后利用最终单元保存指向编码表的索引。其结构如图2所示。对于不分配编码的单叶子节点可以将最终单元设置为-1以示区别。在解码的时候, 可以确定当前上下文, 但是无法确定上下文后的符号。所以Trie结构比编码的时候要少一层, 其最终单元对应于一个上下文。解码的时候, 每个上下文都对应一张解码表和一张符号列表。可以将这些数据分别保存在同一个数组中。利用最终单元保存指向数组的索引。其结构如图3所示。由于单双叶子节点的解码方式不太一样, 所以可以将对应解码表中的位长一栏设为0以示区别。

4 码表保存

4.1 码表分析

一般的哈夫曼算法都需要保存一份码表数据, 以便解码程序可以建立相关的解码结构。高阶哈夫曼算法也不例外。保存高阶建模产生的Trie结构, 第一映像就是保存所有的节点。然后在解码的时候重建整个Trie结构。这需要输出大量的数据。但是, 仔细观察图1中的Trie树可以发现, 所有的上下文都是有规律的。由于在建模的时候是顺序的扫描数据。一个上下文后的符号形成下一个上下文。例如:在上面的例子中, 位于数据开始的上下文“ABA”后面出现“B”。那么下一个上下文将是“BAB”。这意味着可以根据一个上下文推导出其他上下文。例如:在上下文“ABA”后出现了“B”、“C”、“D”, 那么可以推导出在Trie中还出现了“BAB”、“BAC”、“BAD”3个上下文。根据这三个上下文又可以推导出其他上下文。由于建模时的上下文都是由一个引导上下文“###”开始的, 从导引上下文“###”开始可以推导出所有的上下文。利用这种方法可以遍历Trie中的所有上下文, 同时逐一输出上下文对应的符号。这就意味着在保存码表的时候, 只需要保存图1中最末端的叶子节点。上方的分支节点可以不用保存。另外, 由于分配编码的时候也需要遍历Trie, 那么可以将分配编码和保存码表的操作合并起来。这样只需要遍历一次Trie。

在实现的时候可以设定一个上下文栈。首先, 将引导上下文“###”入栈。然后, 从栈中弹出一个上下文, 查找该上下文中的所有符号, 为这些符号分配编码。并按一定的格式将符号个数、符号值以及编码位长输出。同时将推导出来的上下文压入栈中。接着, 再从栈中弹出一个上下文, 按照上述方法操作, 直到栈空。在解码的时候, 由于可以确定引导上下文。所以, 先将引导上下文“###”添加进Trie中, 并且入栈。然后, 从栈中弹出一个上下文, 按照一定的格式输入符号个数、符号值以及编码位长。同时将推导出来的上下文添加进Trie中, 并且入栈。接着, 再从栈中弹出一个上下文, 按照上述方法操作, 直到栈空。

这里还有两个问题需要注意。第一, 推导出来的上下文可能会发生重复。例如:上下文“ABA”中出现“B”, 可以推导出上下文“BAB”。而上下文“DBA”中也出现“B”, 也可以推导出上下文“BAB”。对于重复出现的上下文需要排除。在将一个上下文入栈的时候, 要判断该上下文是否已经入栈或者已经处理过了。第二, 末尾上下文可能没有出现在Trie中。在上面的例子里最后出现的上下文是“BAB”, 后面是“C”。根据这个上下文可以推导出上下文“ABC”。“ABC”就是末尾上下文。由于符号“C”之后就没有数据了, 所以“ABC”没有被添加到Trie中。另外, 如果最后一个符号不是“C”而是“A”, 那么末尾上下文就是“ABA”。而这个上下文存在于Trie中。所以说遍历的时候需要注意, 有一个推导出来的上下文可能不存在于Trie中。而且, 如果末尾上下文不存在, 那么需要将末尾上下文同码表一起输出。以便让解码程序知道, 有一个推导出来的上下文不存在。

在实际操作中, 在将上下文入栈之前, 可以先对上下文进行查找。如果上下文不存在则跳过, 如果存在则入栈。入栈前先将查找上下文时最后状态转换对应的Check单元设为-1, 这样对应的上下文将无法再次被找到。这就可以保证栈中的上下文都是需要处理的上下文。由于Check被破坏, 在编码期间将不能利用Check查找上下文。不过编码期间也不需要利用Check查找上下文。编码期间是第二次扫描数据, 可以断定相关上下文已经在Trie中。所以编码期间直接利用Base查找, 不进行Check检查。在解码的时候, 在将上下文入栈之前, 也可以先对上下文进行查找。如果上下文存在则跳过, 如果不存在则添加进Trie中, 并且入栈。另外, 如果有一个不存在的末尾上下文, 可以事先将该上下文添加进Trie中。这不会影响到解码。

4.2 元组压缩

每个上下文都需要按照一定的格式输出符号个数、符号值以及编码位长。输出数据格式是如下所示的一个元组。

其中, Num表示符号个数, Sym表示符号值, Bit表示编码位长。由于使用了范式哈夫曼算法, 所以只要保存编码位长就可以重建解码表。不过, 上面这个元组还是可以简化一下的。在分配编码的时候, 单叶子节点不分配编码, 双叶子节点按符号值分配编码。只有多叶子节点按一般的范式哈夫曼算法分配编码。所以, 对于单双叶子节点可以不需要保存Bit元素。元组格式可以简化, 并分为三种情况, 如下所示。

一份码表会输出很多元组, 所以在输出的时候需要对元组进行压缩。可以看出, 元组是由Num、Sym、Bit三个元素构成。在这里可以采用分组压缩的方式, 使用三个0阶范式哈夫曼编码器分别对三个元素进行压缩。所产生的二次码表, 再使用指数哥伦布编码进行压缩。

另外, 对于Sym元素的保存有两种方案。第一种方案 (以下简称“方案一”) 就是直接对符号值进行压缩保存。第二种方案 (以下简称“方案二”) 是保存符号的差值。先将符号按值的大小, 从小到大排序。第一个符号值直接压缩保存, 其他符号则计算与前一个符号的差值。然后对差值进行压缩保存。对于一份数据, 如果上下文中的符号无规律分散, 那么使用方案一会取得比较好的效果。如果上下文中的符号集中在一定的区间内变化, 那么使用方案二会取得比较好的效果。现在使用卡尔加里语料库[4]中的18个文件对这两种方案进行比较测试。其结果如表4所示。

以上测试中使用3阶哈夫曼算法压缩数据, 表4中的数据为输出码表的大小, 单位是位。差值为方案二测试结果减去方案一测试结果。两套方案都使用3个0阶范式哈夫曼编码器分别对3个元素进行压缩。唯一不同的是, 方案一保存Sym的符号值, 方案二保存Sym的符号差值。

现在, 可以对测试数据进行一下比较。测试文件中有11个文件其方案一要优于方案二。见表4中带星号的文件。而对于其它文件方案二要优于方案一。这说明了一个问题, 两套方案对于不同的数据其压缩效果也不同。对于一份数据方案一要优于方案二, 而对于另一份数据可能恰恰相反。在压缩前很难判断当前数据适合用哪套方案, 不过可以在压缩的时候比较两套方案的压缩效率。实现时, 对元组进行扫描的时候, 两套方案都进行统计频度和分配编码的操作。然后, 根据频度和编码位长分别计算出两套方案压缩后的大小。比较这两个值就可以判断出应该用哪套方案。

5 测试与分析

在Delphi 7.0下开发, 编译通过并且调试正常。测试程序的计算机使用Intel 2.66GHz单核CPU, DDR400 512MB内存, Windows 2000 SP4操作系统。测试程序压缩文件的时候, 将文件全部读入内存进行压缩。压缩后的数据再写入到文件中。解压缩的过程也是如此。算法计时的时候, 读写文件的时间并没有计算在内。只计算单纯算法的耗时。另外, 程序中使用API函数GetTickCount进行计时。按照微软官方的说法, 该函数有15ms的误差。

最低限制在1阶。通过使用不同的阶数进行压缩, 可以发现高阶哈夫曼算法的一些特点。现在对卡尔加里语料库[4]中的“book1”文件进行不同阶数的压缩测试。从1阶到10阶, 测试结果如表5所示。

表5中的码表大小、数据大小和总计大小的单位都是位。码表大小是指压缩输出时码表占用的大小。数据大小是指压缩输出时压缩数据的大小。而总计大小是码表大小和数据大小之和。另外, bpc是根据最后输出文件的大小计算的。根据表5中的数据制作对应的分析图表, 如图4所示。

通过观察表5和图4可以发现, 输出压缩数据的大小随着阶数的提高而减少, 如图5所示。由于在实现的时候, 对于单叶子节点不输出编码。所以随着阶数的不断提高, 压缩数据会越来越少。当阶数超过待压缩数据的最长重复子串 (可重叠) 的长度时, 输出的压缩数据大小为0。即只输出码表数据, 没有压缩数据。此时, 所有的上下文中都只有一个符号。所有的符号都可以通过上下文直接判断出来。当然, 此时的码表将会十分庞大。

从图4可以看出, 输出码表的大小随着阶数的提高而增加。虽然对码表进行了压缩, 但是输出的码表数据大小仍然十分庞大。在第5阶的时候, 码表的大小超过了压缩数据的大小。这就意味着, 在总体输出数据中有一半以上的数据是为了在解码时重建模型。另外, 值得注意的一点:比较图4和图5可以发现, 码表的增加速度比压缩数据的减少速度要快。这一点也可以从图6中看出来。这就意味着, 高阶哈夫曼算法的压缩率有一个上限。并不是说阶数越高压缩率也越高。当阶数到达上限后, 继续提高阶数只会使压缩率下降。这就是说有一个最优阶数。使用最优阶数进行压缩时, 压缩率达到最高。现在对卡尔加里语料库[4]中的18个文件进行0阶到5阶的压缩测试。计算压缩后的bpc, 其结果如表6所示。

综上所述, 从算法耗时的角度分析, 高阶哈夫曼算法的瓶颈在于建模结构。高阶哈夫曼算法压缩数据时, 需要对数据扫描一遍, 建立模型, 统计频度。接着要对模型遍历一遍, 分配编码, 保存码表。最后还要对数据再扫描一遍, 输出编码。反复的对模型进行查找, 意味着对于建模结构的要求很高。优秀的建模结构可以有效地缩短算法耗时。文中使用双数组Trie进行高阶建模。虽然如此, 随着阶数的提高算法耗时仍然大幅提高。这点可以从表5中看出来。当然不排除还有其他的更优秀的结构。不管怎样, 对于高阶哈夫曼算法来说, 算法耗时主要集中在模型的建立和查找上。

从压缩率的角度分析, 高阶哈夫曼算法的瓶颈在于码表输出大小。从前面的测试数据可看出码表大小严重拖累了压缩率。随着阶数的增加码表的大小也大幅增加, 以至于超过压缩数据的大小。正是由于码表的影响, 使得高阶哈夫曼算法的压缩率很不稳定。对于部分文件, 高阶压缩甚至出现了负压缩率。这可以算是高阶哈夫曼算法的最大缺点, 极大地影响了高阶哈夫曼算法的应用。

6 结语

介绍了高阶哈夫曼算法的实现原理。详细讨论了高阶建模、码表保存等技术的理论基础和实现方式, 并给出了一个切实可行的应用程序。

摘要：介绍了高阶哈夫曼算法的实现原理, 详细讨论了高阶建模、码表保存等技术的理论基础和实现方式, 并给出了一个切实可行的应用程序。

关键词：哈夫曼,高阶哈夫曼,Trie,双数组Trie,Delphi

参考文献

[1]Donald E.Knuth.The Art of Computer Programming.Addi-son-Wesley, 1972, Vol 3.

[2]Jun-Ichi Aoe.An Efficient Digital Search Algorithm by Usinga Double-Array Structure.IEEE Transactions on SoftwareEngineering, 1989, 15 (9) :1066-1077.

[3]叶叶.范式哈夫曼算法的分析与实现, 电脑编程技巧与维护.