HashTrie:一种空间高效的多模式串匹配算法

经典的多模式串匹配算法AC的内存开销巨大,已经无法满足当前高速网络环境下大规模特征串实时匹配的应用需求。针对这一问题,提出一种空间高效的多模式串匹配算法—Hash Trie。该算法运用递归散列函数,将模式串集合的信息存储在位向量中,以取代状态转移表来减少空间消耗,并利用Rank操作进行快速匹配校验。理论分析表明,Hash Trie算法的空间复杂度为O(|P|),与模式串集合的规模|P|线性相关,与字符集大小σ无关,优于经典多模式串匹配算法AC的空间复杂度O(|P|σlog|P|)。在随机数据集和真实数据集(Snort、Clam AV和URL)上的测试结果表明,Hash Trie算法比AC算法节约高达99.6%的存储空间,匹配速度约为AC算法的一半左右。Hash Trie算法适合于模式串集合规模较大、模式串长度较短的多模式串匹配问题,是一种空间高效的多模式串匹配算法。

大规模PC集群语义系统纠删码Hash容错算法

设计基于纠删码技术的大规模PC集群语义系统,有效保证数据的容错性是关键。传统方法采用水平阵列纠删码可能导致随机码的校验数据位与信息数据位分离,从而导致误删。提出一种基于集合间的映射机制和集合内的分发机制的大规模PC集群语义系统的纠删码Hash容错算法,首先把纠删码容错技术的存储系统映射到Hash空间,设计纠删码编码数据块放置算法,定义了可靠性代价函数、删码容错性评价值和平均访问时间作为评价指标。实验表明,该方法能有效提高大规模PC集群语义系统中数据传输和存储的容错性,平均访问时间缩短,平均无故障时间延长,容错性评价值最高,保证数据传输和存储安全。

面向基于内容图像检索的图像感知Hash

提出一种建立在HSV空间颜色分类和形态特征基础上的图像Hash方法,用于图像检索.将图像尺寸规格化,并根据HSV空间中各分量的取值范围,将像素归为11类,在各类颜色成分中提取亮度、大小、形态等特征,加权得到Hash值以构成图像库的索引表,从而实现基于内容的图像检索(content-based image retrieval,CBIR).与其他方法相比,用该方法提取的图像特征除颜色外还包含形态特征,能较好地体现图像内容.实验结果表明,该方法具有良好的性能.

基于Min-Hash数据降维的伴随关系研究

文中提出一种新的计算伴随关系(同行、同停留)的方法,该方法基于手机信号数据、人脸行踪和车辆记录等多源数据。首先,利用ID-MAPPING技术将多源数据统一关联到同一ID,实现数据融合;接着,采用min-Hash算法进行数据降维,降低运算量和存储空间;最后,利用分块Hash映射将具有相同轨迹特征片段的用户映射进同一个桶,计算时空相似度,得到具有相似时空序列的人员列表,从而生成伴随关系。实测数据表明:该方法在提高伴随关系准确度的同时,运行效率比传统方法提升了12倍。

基于锚点的无监督跨模态哈希算法

基于图的无监督跨模态哈希学习具有存储空间小、检索效率高等优点,受到学术界和工业界的广泛关注,已成为跨模态检索不可或缺的工具之一.然而,图构造的高计算复杂度阻碍其应用于大规模多模态应用.主要尝试解决基于图的无监督跨模态哈希学习面临的两个重要挑战:1)在无监督跨模态哈希学习中如何高效地构建图?2)如何解决跨模态哈希学习中的离散值优化问题?针对这两个问题,分别提出基于锚点图的跨模态学习和可微分哈希层.具体地,首先从训练集中随机地选择若干图文对作为锚点集,利用该锚点集作为中介计算每批数据的图矩阵,以该图矩阵指导跨模态哈希学习,从而能极大地降低空间与时间开销;其次,提出的可微分哈希层可在网络前向传播时直接由二值编码计算,在反向传播时亦可产生梯度进行网络更新,而无需连续值松弛,从而具有更好的哈希编码效果;最后,引入跨模态排序损失,使得在训练过程中考虑排序结果,从而提升跨模态检索正确率.通过在3个通用数据集上与10种跨模态哈希算法进行对比,验证了提出算法的有效性.

基于伪ID的RFID认证协议及串空间证明

安全有效的认证协议是对RFID系统安全的有力保障,适宜的形式化分析方法能为RFID认证协议提供有效的证明。设计了基于伪ID的RFID认证协议,伪ID由标签ID、标签认证数值和随机数产生。标签ID不出现在协议执行过程中,减少了系统遭受攻击的可能性。协议通过标签ID、标签认证值和随机数的Hash运算实现认证。利用串空间模型对协议进行形式化分析,建立认证协议的串空间模型丛图,证明了协议的保密性和匿名性。通过分析常规的基于Hash函数的认证协议的性能可知,该协议在使用较低运算成本的情况下可以抵抗多种攻击,并能够完成标签和读写器之间的双向认证。

基于包围盒与空间分解的碰撞检测算法

本文提出了一种基于包围盒方法与空间分解方法相结合的碰撞检测算法,用于解决变形体的碰撞检测问题。该算法首先用包围盒来快速判断物体之间是否相交,如果相交则进一步用空间分解法来定位相交的区域,在此阶段用哈希表的数据结构来保存物体的几何信息。与其他碰撞检测算法相比较,本算法不仅能够较大地节省空间,而且时间复杂度也比较低。除此之外,本算法不仅能够找出发生碰撞的基本几何元素对,而且还能够精确地找出碰撞点。

一种改进的Philips音频指纹检索算法

在Philips音频指纹检索算法中,构造一个查询表作为索引,由于内存消耗过大限制其广泛应用。为此,基于Philips音频指纹检索原型,提出一种改进算法。结合斐波那契数列和右移运算,构造新的哈希函数,通过斐波那契优化哈希值分布,并执行右移运算调整哈希表的长度。实验结果表明,改进算法能减少内存消耗,提高系统的实用性。

基于MD5算法的重复数据删除技术的研究与改进

随着信息技术的快速发展,信息化已成为决定企业生存与发展的关键因素之一;然而随着企业数据信息量的不断地增加,海量数据信息的存储和不断备份已经给企业的存储空间带来了巨大的存储压力;为此,深入研究了重复数据删除技术,并针对目前重复数据删除技术中存在的数据丢失及性能低等问题以及MD5算法流程和重复数据删除策略的分析和研究,提出了一种重复数据删除技术优化模型;测试分析表明,该优化模型实现了高效和安全的重复数据删除功能,节省了企业内部存储空间的存储成本开销。

无人机序列图像快速三维重建系统设计与实现

设计并实现了一种适用于高分辨无人机序列图像的快速三维重建系统(FDroneMap)。通过两个方面的改进提高系统运行的效率:一方面对重建算法进行优化,使用了一种新的基于哈希表的图像匹配方法,并根据无人机图像的时空序列特性对匹配策略进行调整,加快图像匹配速度;另一方面对重建算法各个模块进行并行化设计,提高系统对硬件的性能使用率。对比实验表明,在处理高分辨率无人机序列图像时,FDroneMap能显著提升三维重建的效率,并且能保证重建精度。

基于局部坐标系和哈希技术的空间曲线匹配算法

针对三维物体识别领域中的问题，提出了一种基于局部坐标系和哈希技术的空间曲线匹配算法。该方法通过提取一条曲线的恒定特征点，构造局部坐标系；然后再计算局部坐标系中的相似不变量，构造哈希表；采用哈希技术对这些不变量进行比较,达到匹配曲线的目的。此算法应用于计算机辅助文物复原系统中，经实验表明，所给方法具有运行稳定、高效和适用性强等优点。

利用集合差异度实现基于内容聚类的P2P搜索模型

基于内容的非结构化P2P搜索系统中直接影响查询效果和搜索成本的两个主要问题是,高维语义空间所引起的文本相似度计算复杂以及广播算法带来的大量冗余消息.本文提出利用集合差异度实现基于内容聚类的P2P搜索模型提高查询效率和减少冗余消息.该模型利用集合差异度定义文本相似度,将文本相似性的计算复杂度控制在线性时间内而有效地减少了查询时间;利用节点之间的集合差异度实现基于内容的聚类,既降低了查询时间,又减少了冗余消息.模拟实验表明,利用集合差异度构建的基于内容的搜索模型不仅具有较高的召回率,而且将搜索成本和查询时间分别降低到了Gnutella系统的40%和30%左右.

基于融合鲁棒特征与多维尺度变换的紧凑图像哈希算法

目的为了增强哈希序列对任意旋转角度的鲁棒性与识别能力,提出一种基于融合鲁棒特征与多维尺度变换的紧凑图像哈希算法。方法首先,利用双线性插值来固定图像的哈希序列长度,获取规则尺寸的图像;借助高斯低通滤波对规则图像完成过滤操作,消除噪声污染和插值误差对哈希生成的影响;将滤波图像转换到YCbCr颜色空间,提取亮度Y分量,增强哈希对亮度调整的鲁棒性;利用极坐标变换LPT方法处理亮度Y分量,输出二次图像;引入SVD机制来分解二次图像,获取其抗旋转的鲁棒特征;同时,根据Fourier变换与残差机制,获取Y分量的局部显著特征;随后,将这2种特征组合,形成融合鲁棒特征,将其视为中间哈希序列;引入多维尺度变换,对中间哈希序列完成压缩,获取紧凑哈希;基于Logistic映射,完成紧凑哈希序列的加密,形成目标哈希;通过计算真实图像与待认证图像之间哈希序列对应的Hamming距离,根据预设阈值,完成图像识别。结果测试数据表明,较已有的哈希方案而言,所提方案拥有更高的鲁棒性和更紧凑的哈希长度,呈现出更为理想的ROC曲线,在多种攻击下,其稳定的正确识别率保持在96%以上。结论所提哈希方案拥有良好的鲁棒性与敏感性,在包装图标检索、信息水印等行业具备较好的应用价值。

基于网络处理器的并行包分类方法

在大型网络中大量的规则数量会导致位向量(BV)算法的位向量过长和稀疏,要在网络处理器中实现BV算法需要大量的存储资源,而且多次存储读取也降低了算法匹配效率。针对BV算法位向量的问题,将Tuple空间分割思想与BV算法相结合缩短了位向量长度,充分利用网络处理器的并行处理机制和硬件加速单元,提出了一种适用于网络处理器的改进算法——Tuple-BV算法。该算法的元组分割缩短了位向量的长度,减少了位向量的存储空间和读取次数。通过对数据包处理延时的实验比较,当较多规则时,Tuple-BV算法在最大延时和平均延时指标上优于BV算法。

基于哈希表与十字链表存储的Apriori算法优化

Apriori算法在数据挖掘过程中需要多次扫描数据库,会造成I/O上有较大时间开销和负载,影响算法的运行速度,同时在计算频繁项集的过程中,需要进行大量迭代搜索与计算,算法的时间复杂度和空间复杂度较高。基于此,提出一种基于哈希表与十字链表存储的优化算法HTACL-Apriori。通过理论分析和数据进行实验对比,验证了优化后的HTACL-Apriori算法相对于传统的Apriori算法在时间效率和空间效率方面有明显的提高,达到了预期效果。

基于节点共享计数型Bloom filter高效动态数据包过滤方案

入侵防御系统（intrusion prevention system，IPS）中常用的包过滤方案大量消耗时间和空间，丢包率高，不能实现多过滤器并行处理。针对此问题，设计了一种新的过滤器方案，该方案在网络设备驱动层采用节点共享计数型bloom filter技术，通过改进哈希函数的集合，减少了位数组元素的碰撞率，实现了过滤规则的动态添加和删除。由元组空间法把过滤规则划分多个集合，在每个集合中创建不同的节点共享计数型Bloom filter位数组，并且优化搜索算法，进一步降低了位数组元素的碰撞率。通过在多核处理器中建立多个并行处理线程，实现了过滤的并行处理。实验结果表明，新的方案能够减少28％～31％的碰撞率和12％～19％的hash表的访问次数。

两级哈希表存储模式的高效多模式匹配算法

为了弥补多字符串模式匹配效率低下的缺陷,给出了一种基于双哈希表的多模式匹配算法。这个算法通过两个相关联的哈希表对模式串进行存储,同时采用一个转移表将发生失配时的跳跃距离存储。处于匹配阶段时:如果模式串无公共前缀,那么仅仅于第一个哈希表中进行查找;如果模式串有公共前缀,那么就在两个哈希表中顺序查找。经分析发现,此算法在最短模式串长度很长的环境中尤为适用,相对于经典算法,其时间复杂度较低,且其尝试次数也比较少。最后经实验可以证明,该算法具备较好的时空性能。

基于分布式哈希表的协作式Web服务组合

集中式的基于案例推理(CBR)应用于感知服务质量(QoS)的Web服务组合时,面临信息维护量大、节点负载高、中心失效等问题。为解决上述问题,提出了基于分布式哈希表(DHT)的协作式Web服务组合方法 COCO,利用哈希函数和空间填充曲线(SFC)将组合服务的工作流和服务质量映射为一维数据键,并利用底层DHT Overlay以Peer-to-Peer的方式查询满足用户请求的已知组合服务,一次成功查询可获得同时满足功能性要求和非功能性要求的组合服务。实验结果表明,COCO在查询时延和查询命中率方面均有较好性能,适用于大规模网络计算环境。

认证测试方法的扩展及其应用

基于串空间模型的认证测试方法分析协议的安全性有一定的局限性,只能分析有限的协议.因此,对基于串空间模型的认证测试方法进行了扩展,通过修改测试分量和认证测试规则,对该方法进行了改进,运用扩展后的认证测试方法对使用签名和哈希函数的TLS协议进行了分析,扩大了认证测试方法的使用范围;并提出了对测试分量新鲜性的检验,进一步完善了认证测试方法.

基于柯西分布的深度哈希跨媒体检索

针对深度哈希跨媒体检索方法中,语义相似的媒体对象的哈希码在汉明空间内的分布不合理问题,提出了一种新的深度哈希跨媒体检索模型.该模型是在汉明空间内利用柯西分布对现有的深度哈希跨媒体关联损失进行改进,使得语义相似的媒体对象哈希码距离较小,语义不相似的媒体对象哈希码较大,进而提高模型的检索效果.同时,本文给出了一种高效的模型求解方法,采用交替迭代方式获得模型的近似最优解.在Flickr-25k数据集,IAPR TC-12数据集和MS COCO数据集上的实验结果表明,该方法可以有效的提高跨媒体检索性能.