一种IP数据包快速分类算法

为了提高查找效率,在无冲突哈希查找算法和Grid of Tries算法的基础上提出了一种基于无冲突哈希和多比特Trie树(NHMT)的IP分类算法.该算法的核心有3部分:哈希函数的构造,主要是采用基于目的端口和协议两域构造哈希函数,使得在最坏情况下完全避免了空间爆炸问题;在Grid of Tries算法的基础上,对Grid of Tries算法改造成修剪的Trie树和多比特Trie树,以减少空间复杂度;在无冲突哈希查找算法的基础上扩展一层用于存放源端口号(或范围),扩展后一般要提高算法的时间复杂度,要通过引入多比特Trie树的方法进行解决.对于空间复杂度方面与无冲突哈希查找算法比较,一般情况下不增加空间复杂度.通过仿真,当对10 000条规则进行包分类时,该算法的分类速度可以达到1 Mbit/s,所消耗的最大内存为8.2 MB.     

基于统计决策树的包分类算法

基于网络包分类算法在时间和空间复杂度上的限制,启发式策略一般具有较快的速度,同时在应用上具有较好的前景,提出了一种基于统计决策树的启发式包分类算法.该算法把规则头部中的每一位看作一个特征属性,因为不同位有不同的区分效果,根据对规则的统计把最具有区分意义的几位提取出来作为决策树的决策属性,使规则在子集中分布比较均匀,在子集中也做同样的处理,递归形成树形的数据结构;匹配时在树的每一层根据区分位判断其所属的子集,直到找到相匹配的规则.算法测试表明能实现高效的分类.     

一个快速的多维数据包分类算法

通过引入位图映射以及元组空间的概念,提出了一个数据包分类算法,该算法可以满足高性能网络对骨干路由器的要求,能够以线速完成对输入数据包的分类处理。算法在时间及空间复杂度上性能较好,并具有很好的扩展性。     

基于小波域分类隐马尔可夫树模型的图像恢复

针对自然图像的非平稳特性和图像恢复中计算困难的问题,提出了一种基于小波域分类隐马尔可夫树(CHMT)模型的图像恢复算法.从图像恢复的贝叶斯框架出发,将CHMT模型作为自然图像小波域的先验知识,构造正则化约束进行图像恢复.该模型具有空间适应性,使建模更加精确.对恢复方程的求解,采用了分类简化的共轭梯度算法.实验结果表明,该算法具有较低的计算复杂度,能提高图像恢复峰值信噪比(PSNR).     

网络包分类算法仿真测试与比较研究

在深入分析基于树结构和计算几何学点定位算法而衍生的主要分类算法原理的基础上 ,建立了算法性能评估仿真测试平台 .平台包括网络流的软件仿真、算法的软件实现和算法性能参数测试统计三个主要部分 .通过对各算法的时间性能和空间性能及其随分类规则数和分类域数的变化趋势的测量 ,从数量上把握各算法的主要特点及其适用性 ,从而可以将各种算法有机地结合在一起胜任速度越来越高的网络应用需求 ,同时也是进一步研究其它算法的基础 .     

基于权重搜索树改进K近邻的高维分类算法

信息采集技术日益发展导致的高维、大规模数据,给数据挖掘带来了巨大挑战,针对K近邻分类算法在高维数据分类中存在效率低、时间成本高的问题,提出基于权重搜索树改进K近邻(K-nearest neighbor algorithm based on weight search tree,KNN-WST)的高维分类算法,该算法根据特征属性权重的大小,选取部分属性作为结点构建搜索树,通过搜索树将数据集划分为不同的矩阵区域,未知样本需查找搜索树获得最"相似"矩阵区域,仅与矩阵区域中的数据距离度量,从而降低数据规模,以减少时间复杂度.并研究和讨论最适合高维数据距离度量的闵式距离.6个标准高维数据仿真实验表明,KNN-WST算法对比K近邻分类算法、决策树和支持向量机(support vector machine,SVM)算法,分类时间显著减少,同时分类准确率也优于其他算法,具有更好的性能,有望为解决高维数据相关问题提供一定参考.     

应用时变小波包零树编码实现心电数据的高效压缩

为减少传统小波零树编码算法中孤立零的出现,以确保编码压缩后信号的熵减,提出了时变小波包零树编码算法,构建了最优小波包基下低冗余映射关系,同时考虑到心电信号自身的时域相关性,将时频域结合考虑,进一步降低了信息熵,最终明显改善了压缩效果.实验结果表明,该方法保留了小波零树编码可以实现累进传输编码的优点,并且取得了更好的压缩性能.     

基于小波包矢量量化图像压缩方法

提出了一种新的数字图像压缩方案——基于小波包的区域联合矢量量化(WPVQ)．WPVQ压缩方案充分利用了小波分析的三个重要特点，即零树特性、多层分解和适合跨区域联合编码．在具体实现过程中，WPVQ又采用了一系列措施来提高信噪比并降低算法复杂度．计算机模拟实验表明，同采用嵌入式零树编码(EZW)的JPEG2．000相比，WPVQ可以在高压缩比情况下保持良好的信噪比和主观效果，尤其适合于对图像进行高压缩比的压缩处理．     

基于分类树的高效关联规则挖掘算法

在分析类Apriori算法存在效率瓶颈的基础上，提出了一个高效改进算法——基于分类树的关联规则挖掘算法．该算法只需要两次访问数据库，把数据库中的数据利用分类树来存储，减少了访问数据库的次数；并且由分类树的全部或部分来求得频繁项目集，减少了求频繁项目集的比较次数．此算法通过结合Apriori和FP—tree两种算法来提高挖掘效率，降低了挖掘算法的时间复杂度和空间复杂度．通过多次试验证明该算法比Apriori及其改良算法的挖掘效率高2到8倍．     

一种基于朴素贝叶斯分类法的空间分类算法

 空间分类是空间数据挖掘的重要分支,寻找高效的空间分类算法是空间分类研究的重要方向.在空间对象的邻接图及朴素贝叶斯分类法的基础上提出一个新的空间分类算法,该算法对空间对象进行分类时,既考虑了待分类对象的属性对分类的影响,又考虑了其空间邻接对象对它分类的影响.该算法的计算复杂度不高,分类的正确性好.     

一种新的快速码本搜索算法设计

提出一种新的分类预选算法。旨在解决矢量量化数据压缩技术中,当码本值和矢量维数增大时,全码本搜索产生很大的实时复杂计算问题。该算法与传统的全搜索算法相比,能减小编码矢量选取过程中产生的计算复杂度。同时,编码器的性能几乎没有受到影响,仅仅在存储需求量方面略有增加。     

一个新的启发式搜索算法

本文提出一个新的启发式搜索算法,它可以在搜索过程中不断改善启发函数h,使最坏复杂度降为O(N)(N是被搜索图的大小)。本文还指了L.Mcro对“无普遍最优算法”的证明中的漏洞,并给出了新的证明。     

A quantum algorithm for searching a target solution of fixed weight

To search for a target n-product Boolean vector of fixed weight d, we propose an important method involving the notion of a fixed-weight "vector label" accompanied with a vector label restoration algorithm. Based on these, we present a new quantum algorithm designed to search for a fixed-weight target whose computation complexity, specifically O (（Cdn+1）^1/2) , is better than that for a classical algorithm. Finally, we use the procedure to search for the NTRU private key as an example to verify the efficiency of the new algorithm in searching for fixed-weight target solutions.     

Quantum mechanical meet-in-the-middle search algorithm for Triple-DES

We present a quantum mechanical meet-in-the-middle search algorithm inosculating the quantum computing theory with crypt-analysis method and basing on the Grover’s algorithm and the meet-in-the-middle attack, which can solve the three-key triple-DES in O(56 256) steps and with O(256) memory cost. The computational complexity is apparently reduced, compared with that of the existing algorithms.     

一种多传感器图像并行融合新方法

小波包变换能够为图像融合提供非常精细的分析。但是,在图像较大时融合的计算量大,耗时长,难以进行快速、实时融合。通过对小波包融合方法在单处理机上的执行效率的分析,针对算法固有的时间复杂性和并行性,提出了一种分布存储环境下的小波包并行融合算法。该算法针对小波变换计算的数据局部性特点,设计并实现了基于Pentium PC和1000Mbps交换式以太网的机群系统的MPI(Message Passing Interface)并行环境的并行小波包图像融合方法。针对不同大小图像、以及不同的集群规模,分析了并行计算的性能。在机群系统上对算法进行实现,结果表明该算法具有良好的并行性能。     

弧搜索内点算法

利用弧搜索内点算法对线性规划问题进行求解, 得到该算法的多项式复杂度为O(n^3/4L). 该算法在中心路径的一个宽邻域内, 沿椭圆近似寻找线性规划的最优解. 数值实验表明了该算法的有效性.     

线性规划基于修正牛顿方向的宽邻域内点算法

通过修正经典宽邻域算法的搜索方向, 提出一种新的求解线性规划问题的宽邻域内点算法, 并对算法进行收敛性分析, 证明了该算法具有经典宽邻域算法的迭代复杂性界O(nL). 数值实验表明算法是有效的.     

基于散列表的快速分组分类算法

通过分析Internet网络主干路由器分组分类的关键问题和解决方案, 提出了基于散列表的快速分组分类算法, 该算法时间复杂度为O(1); 通过分析规则表的相关性将规则表分成相关子集和不相关子集, 对不相关子集采用哈希法构造散列表. 实验测试表明, 所给算法比顺序匹配算法的吞吐率提高近10%. 进一步分析了规则冲突, 并给出了冲突的理论证明和查找算法.     

WFQ与WRR调度算法的性能分析与改进

不同类别的业务对时延及时延抖动的要求是不同的,为了满足不同业务的服务质量(QoS),选择一种合适的队列调度算法至关重要. 研究了分组长度对WRR及WFQ算法公平性以及时延性能的影响,并提出了一种基于分组长度及队列权重的改进型WRR算法——enhanced-WRR. 仿真结果表明,当分组长度相同时,WRR与WFQ的时延性能几乎一致;当分组长度不同时,WRR算法不能保证高优先级队列的时延要求,而E-WRR算法的时延性能逼近WFQ算法,能很好地保证高优先级队列的时延要求,并且极大降低了算法复杂度.      

几种查找算法的比较

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，文中介绍四种查找算法，分别是顺序查找、二分查找、二叉排序树查找和哈希查找。并用JAVA语言编写了相应程序代码，比较了查找同一个数据的时间复杂度和空间复杂度。