基于D维映射的布谷鸟哈希表

哈希的数据结构和算法是海量信息存储的有效方式,特别是对于与网络流量测量、监控和安全相关的应用。目前存在许多哈希表算法,如布谷鸟哈希、Peacock Hash、Link Hash和Double Hash等,但是这些哈希算法仍存在着一些问题,如占用内存空间过大、插入查找等操作时间过长以及插入过程中遇到死循环而导致插入失败需要进行重新哈希等。针对这些问题,文中提出了基于D维映射的布谷鸟哈希算法,对哈希表进行属性划分,并增加链表结构,然后与辅助数据结构布隆过滤器和位图进行结合,并通过预先识别踢出操作是否有必要来减少不必要的内存访问次数,提高了哈希表的负载因子和插入查找效率。     

BM模式匹配算法的研究与改进

本文在分析传统模式匹配BF算法、KMP算法和BM算法的基础上,提出对BM算法的改进.主要针对BM算法中模式串向右滑动距离进行改进,BM算法和改进后的BM算法在同等条件下,分别调用各自算法的滑动距离函数,实验结果可以看出改进后的BM算法查找效率、查找次数等均优于BM算法.     

改进的KR模式匹配算法的研究与实现

文章在详细分析KR匹配算法的基础上,提出了改进的I_KR算法.I_KR算法的改进之处:一是采用2次Hash函数的方法在计算T的子串的散列值之后,马上与P的散列值进行比较;二是采用双向并行方式进行匹配.为了分析I_KR算法的性能,从不同文本串和模式串角度,在匹配次数和比较的字符个数方面对I_KR算法进行实验.实验结果表明,I_KR算法能够极大地减少匹配次数,缩短匹配时间,有效地提高模式匹配速度.     

一种基于汉字编码特征的中文多模式匹配算法

对于大规模中文模式串匹配,由于汉字的散度较高,导致AC算法有限状态自动机中的零状态过长,算法的效率急剧下降。文章提出了一种基于汉字编码特征的改进算法,考虑到汉字的首字节范围比尾字节的小,先查找首字节,再查找尾字节,若失败则直接跳转,降低了查找时间。该算法通过给零状态中字符设置标记,有效避免重复匹配和部分匹配,提高了匹配效率。     

适合中文的双向比较模式匹配算法

分析了几种常用的模式匹配算法,提出一种适合于中文的基于KMP的改进算法,即双向比较模式匹配算法.该算法以KMP算法为基础,引入特征数组以记录模式串尾字符在模式串中出现的位置信息,从而获得模式串在匹配过程中的最大移动距离和最少比较次数.实验结果表明,双向比较模式匹配算法可有效降低匹配次数.     

一种信息审计系统中的多关键字匹配算法

针对审计系统中搜索大量审计数据的需要,设计了一种基于哈希表机制的多关键字匹配算法.该算法把关键字集合储存到哈希表中,并为关键字集合建立了两个过滤表和一个关键字长度类型表.在查找过程中,对未经过滤表验证的字符串不再进行匹配查找,同时,关键字长度类型表的使用减少了循环的次数.测试结果表明,该算法在速度和精度上都优于BM和mgrep算法.     

一种面向中文的快速字串多模式匹配算法

针对中文字串匹配问题,提出一种快速模式匹配算法,算法采用新型组合状态自动机,将2个状态组合起来匹配一个双字符,从而解决了双字节符构建完全Hash表时带来的存储空间膨胀问题;同时考虑到待匹配模式串中的字符在大字符集中稀疏分布的特点,尝试将单模式QS匹配算法的思想与DFSA算法进行结合,应用于多模式匹配中,实验结果显示,本算法明显优于DFSA算法,平均所花费时间仅为DFSA算法的45．2％。     

基于哈希和合并技术的FP-Growth新算法

对频繁模式增长(FP-Growth)算法进行了改进,用哈希头表代替头表.通过合并频繁模式树(FP-Tree)中支持数相同的结点,压缩了树的规模,有效地节省了空间.实验结果表明,改进后的算法在查找效率上有了大幅度的提高,可以更好地适用于大规模数据集的关联规则挖掘.     

一种带红黑树的哈希表在物流信息系统中的应用研究

针对在节假期间物流业务量急剧增长及大量用户在线查询订单信息而导致物流信息系统响应速度慢的问题,提出了带红黑树的哈希表,有效地提高了订单查询的速度,并将链表和红黑树进行比较,实验结果表明:带红黑树的哈希表在查找时间上有明显优势.     

字符串匹配算法Sunday的改进

字符串的模式匹配应用十分广泛,在信息的搜索查询等方面具有重要作用,研究串匹配算法的效率具有重要的理论价值和实际意义。在分析几种经典模式匹配算法的基础上,对当前应用最广泛的Sunday算法提出了改进的算法Zhusunday.算法主要改进之处是:在字符串从右向左匹配过程中,当文本字符中出现不匹配模式字符串的字符且该文本字符不是坏字符时,算法从右向左搜索当前文本字符在模式串中出现的位置;找到当前字符在模式串中的位置后继续再向左匹配模式串字符一次,如果仍不匹配时,模式窗口比Sunday算法多向右移动一个字符。改进的算法提高了模式匹配的执行效率,通过大量对比实验证明了该算法的有效性。最后得出结论:在实际应用中,坏字符大量存在的情况下,改进算法的最优时间复杂度可达O(n/m),在同一时间复杂度下,比Sunday算法效率提高25~50%.     

量子可逆逻辑电路最小代价综合算法

采用位运算构造了一个完备的Hash函数,提出了基于Hash表的新型量子可逆逻辑电路综合算法.利用该算法可对多种量子门采用任意量子代价标准,以较高的效率生成最优的量子可逆逻辑电路.按照国际同行认可的三变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其他算法.实验结果表明,该算法在同等计算环境下,以目前最好结果为基准,按最小量子代价标准,综合电路的平均速度是最好结果的472.5倍.     

一种基于DHP的动态链地址关联规则挖掘算法

采用动态链地址法建立Hk 表,提出DLDHP算法,克服DHP算法不能给Ck 中的每个项集单独计数的缺点,在增加Hk 表的空间时也会删除链表中的结点空间,从而Hk 表不会占用较大的内存,最终直接由Hk 表得到频繁k-项集的集合Lk ,不用再次扫描数据库。实验结果表明:DLDHP算法是有效可行的。     

基于WM算法改进的多模式匹配算法

为提高入侵检测系统整体的性能和效率,在研究经典的WM(Wu-Manber)多模式匹配算法的基础上,提出一种改进的WM多模式匹配算法.该算法使用后缀表方法,减少了匹配过程中模式字符串与文本的比较次数.实验结果表明,该算法有效提高了入侵检测系统匹配的速度和效率.     

Wu-Manber算法在大规模模式串下的改进

对笔者在另一篇文章《一种改进的Wu-Manber多关键字匹配算法》中提出的算法进行了改进,把原算法中next链表中结点的Same-Subsuffix域中分裂成两个子域,使得搜索过程中字符比较的次数进一步减少,从而提高算法的效率.特别是在大规模模式串的情况下新算法的效率比原算法有进一步的提高.实验结果表明,当模式串较少时,新算法效率与原算法相比有一定的损失.而随着模式串的增加,新算法具有更高的效率.因此,新的算法比原算法具有更大的适用范围.     

基于Hash和二叉树的路由表查找算法

提出了一种基于Hash和二叉树的路由表查找算法,这一算法可以满足OC-768的转发要求,支持超过10万条前缀的大规模路由表,并且在路由表更新时,只有少量的存储器需要被改写.仿真结果显示,对于一个149 458条前缀的路由表,算法仅需要2 MB存储器,如果采用200MHz的存储器芯片,平均的查找速度可以达到100M次/秒.     

轻量化神经网络和哈希跟踪算法在嵌入式人脸抓拍系统中的应用

针对嵌入式设备上难以兼顾人脸抓拍的速度和准确率的问题,基于轻量化神经网络和哈希(Hash)跟踪算法设计了一种快速精准的嵌入式人脸抓拍系统.首先,对轻量化网络MobileNet固态硬盘(solid state disk,SSD)剪枝和优化网络结构构建人脸检测网络;其次,人脸对齐后基于均值哈希(average Hash,a...     

基于Hash B+树RFID复杂事件检测算法

在分析现有RFID复杂事件检测算法的基础上,提出一种基于Hash B+树复杂事件检测算法。根据原子事件在Hash表中映射的位置状态,决定原子事件插入的位置,降低数据操作的时间复杂度。同时引入插入优化算法及滑动窗口,删除中间结果中过期数据,以提高内存的利用率。实验结果表明该方法在保证复杂事件检测有效性的同时可提高其处理效率。     

基于最小完美哈希函数的数据挖掘算法

提出了一种基于最小完美哈希函数的关联规则的挖掘算法.这一基于Apriori的算法在综合了传统哈希剪枝技术的同时,充分利用了最小完美哈希函数的优点,从而在保证静态数据库关联规则挖掘的同时,使对关联规则的哈希结构数据进行动态调整成为可能.这一算法不仅提高了挖掘效率,而且通过抑制哈希地址冲突提高了算法的稳定性和可用性.     

一种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.