一种普适计算环境下基于语义的服务匹配算法

在普适计算环境中通过语义本体来表示环境中的概念进行服务发现可以提高服务发现的鲁棒性。给出了一种基于语义的服务匹配算法,根据不同的服务请求可以通过服务类型匹配、服务输入输出参数匹配和QoS参数匹配,实现了分层次、逐步过滤不匹配的服务。同时通过服务相似度的计算为服务请求者提供最满足需求的服务。实验结果证明该算法具有较高的匹配率和较好的匹配速度,完全适用于普适计算环境。     

SURF特征及预处理RANSAC算法在人脸识别中的应用

针对人脸识别问题,提出了一种基于SURF特征的人脸图像快速识别方法。首先,对经预处理后的人脸图像提取SURF特征点,采用最近邻匹配法对特征点进行粗匹配;其次,利用KMeans聚类算法对粗匹配的特征点进行预处理来过滤明显不合适的匹配点,再利用RANSAC算法对过滤后的特征点实现精匹配,以达到对人脸的特征点比较准确地识别匹配。实验结果表明,该方法适用于手机终端的人脸图像的快速匹配,具有较强的鲁棒性及一定的实用价值。     

基于匹配区域特征的相似字符串匹配过滤算法孙德才

相似字符串匹配过滤算法因其适合大库查找而被广泛应用,为通过提高过滤算法的过滤效率加快匹配速度,提出一种基于匹配区域特征的过滤算法.该算法将模式串和文本串分割成固定长度为kq+1的逻辑块,并从各块中提取了2个新的匹配区域特征:q-gram命中的均匀性和q-gram有效命中的区域性.新算法利用这些新特征优化了传统过滤标准,提高了算法的过滤效率;并改进了QUASAR中基于分块策略的过滤区确定方案.实验结果表明,新算法与改进前相比有效地加快了匹配速度,尤其在误差率较小时改进效果更佳.     

递进式网络数据包解析与过滤方法研究

在分析企业对内部网络监控系统需求的基础上,提出了一种适用于内网监控系统的递进式网络数据包解析与过滤的方法。该方法包括网络数据包的截获、解析和过滤3个主要功能,其中主要分析了数据包解析与过滤的实现,采用递进式分级解析数据包的方式和高效的BM模式匹配算法进行规则匹配,提高了数据包解析过滤的效率。实验结果表明,该方法的应用对网络数据传输产生的延时较小,基本不影响内网用户对网络的正常使用。     

粒子群优化点匹配算法

点匹配问题一直是计算机视觉,模式识别,医学临床诊断等领域的一项重要基础性工作。本文提出了一种基于粒子群优化算法的准确、快速和鲁棒性的点匹配方法。该方法首先确定两个特征点集的点匹配问题的能量函数,通过最小化该能量函数可以同时得到点集之间的匹配矩阵和映射参数,利用粒子群优化算法求解变换参数。实验表明,该算法适用于点匹配,具有操作方便,可靠性好,不易陷入局部极值等优点。     

工作流集成中基于代数表达式的语义匹配机制

针对现阶段工作流集成研究中功能匹配查准率和查全率低的问题,给出了基于软件功能形式化语义的匹配机制的实现。在前、后条件pre/post的完全匹配模式下,以高级程序设计语言中的代数表达式为基础,提出了匹配原则,并给出了具体的算法,并且用实例进行分析说明。该算法适用于工作流集成中的功能匹配,同时基于严格的形式化方法,便于分析和验证。该算法局限于初等代数性的前提。     

基于网格对应的双约束特征点匹配算法

常用的特征点匹配算法通常设置严苛的阈值以剔除错误匹配,但这样也会导致过多的正确匹配被删除。针对这一问题,提出了一种采用双约束的特征点匹配方法。首先,在局部上统计特征点匹配数量,运用网格对应的方法过滤部分错误匹配;然后,在全局上运用RANSAC方法计算基础矩阵,通过极线约束对匹配进行再一次筛选。实验表明,相比于传统的匹配算法,该算法能在不增加算法运行时间的前提下,获得更高数量和更高质量的匹配集合。     

一种基于尾匹配q-gram的近似串匹配算法

近似串匹配是生物信息学、文本检索、信号处理等领域的一个基础问题,如何提高近似串匹配的速度一直都是研究的关键问题。提出一种新的在大文本库中快速查找近似匹配的无损过滤算法。为保证在大文本库中的匹配速度,本算法使用了查询速度较快的q-gram索引。为通过提高过滤算法的过滤效率达到提升算法整体性能的目的,详细分析了含有匹配串的文本区域,提取了一些基于尾匹配q-gram特征的新过滤条件,然后用这些特征优化了过滤算法的过滤标准。实验数据表明,新过滤条件有效地提高了算法的过滤效率,提升了算法的整体性能。结果显示新算法适合各种匹配错误率下的近似匹配,算法的通用性较强。     

基于过滤的中文多模式近似字符串匹配算法

当前近似字符串匹配算法主要针对英文等中小字符集,该文针对汉字等大字符集的有效算法很少,尤其缺少适合汉字等大字符集的多模式近似匹配算法的情况,提出了一种适合汉字等大字符集的多模式近似匹配算法——MBPM-BM,通过实验证明了该算法的有效性。 近似字符串匹配;中文字符串匹配;多模式匹配;位并行运算;过滤     

区间树在DDM区域匹配中的应用

数据分发管理（DDM）是降低网络冗余数据的有效手段,区域匹配算法又是数据分发管理实现的关键。当前的多种匹配算法如直接匹配法、网格法、排序法等效率都不够理想,或者过滤效果不佳,或者耗时较长。通过对数据过滤机制的深入研究,提出了基于区间树的区域匹配算法——ITBM算法,该算法将范围的上下界映射到一个区间内,使用区间树来存储区域范围,通过对区间树的直接操作来完成匹配工作。结果表明,ITBM算法大大减少了匹配计算的时间,有效地减少了动态DDM的维护开销。     

基于压缩后缀数组的近似字符串匹配算法

近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。     

一种改进的字符串多模式匹配算法

基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。通过分析几种常见的字符串匹配算法（AC、AC_BMH、Sunday等）的基础,提出了一种对AC算法的改进,新算法每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配,使得匹配次数大大减少,从而提高了匹配效率。分析了该算法的性能,并用具体的实验数据给出了几种匹配算法的测试结果。     

一种改进的BM字符串匹配算法

经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的,在主串中存在大量子串与模式串前缀或者后缀相同时效率较低,并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法,有效地避免了由主串中大量子串与模式串前缀相同或者后缀相同引起的无意义比较次数。模式串的移动距离根据改进的坏字符规则进行计算,增大了模式串的移动距离。实验结果表明,改进的字符串匹配算法可以有效地减少字符串的匹配次数和移动次数,达到了提高算法效率的目的。     

XML内容筛选中的快速串匹配算法

本文提出了一种对XML 文本进行快速串匹配的算法- XMatch。在对于XML 文本的含路径信息的模式串匹配中,由于XML 文本的结构化特点,使得传统的串匹配算法不能直接有效的使用;而现有的大部分XML 内容筛选方法都是基于SAX 分析的事件驱动过程,效率普遍较低。XMatch 在对XML 文本的结构-schema 进行分析的同时,结合模式串的路径信息,建立一个扫描自动机的有限状态自动机;此外,算法还支持带循环引用路径信息的模式串匹配。XMatch 容易扩展,可以支持普通的结构化文本的串匹配。实验结果显示,本算法的效率比使用SAX事件驱动的方法有明显的提高。     

改进的多模式字符串匹配算法

在经典的AC多模式字符串匹配算法的基础上,结合BMH算法的优点,提出了一种快速的多模式字符串匹配算法。一般情况下,该算法不需要匹配目标文本串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配。在模式串较长和较短的情况下,算法都有很好的性能。实验表明,在模式串较短时,本算法所需的时间仅为AC算法的50%～30%;在模式串较长时,所需时间为AC算法的26.7%～15.2%。     

一种用于内容过滤和检测的快速多关键词识别算法

基于字符串匹配的检测方法是内容过滤和检测系统中一类很重要的分析方法，首先分析了现有的几种快速字符串匹配算法，然后提出了一种新的多模式字符串匹配算法，并简单分析了算法的复杂性，算法在设计的过程中吸取了BM算法中跳跃的特性，采用了后缀树算法得到了最大跳跃值，采用AC算法的匹配自动机原理从而避免对搜索树内每一个字符的匹配，最后，通过具体的实验数据验证了这些算法的性能，通过实验可以看出，新算法使得检测速度有很大提高，并有效屏蔽了关键词数量的增加对检测速度的影响。     

Finding rotational symmetries by cyclic string matching

Symmetry is an important shape feature. In this paper, a simple and fast method to detect perfect and distorted rotational symmetries of 2D objects is described. The boundary of a shape is polygonally approximated and represented as a string. Rotational symmetries are found by cyclic string matching between two identical copies of the shape string. The set of minimum cost edit sequences that transform the shape string to a cyclically shifted version of itself define the rotational symmetry and its order. Finally, a modification of the algorithm is proposed to detect reflectional symmetries. Some experimental results are presented to show the reliability of the proposed algorithm.     

字符串模式匹配算法的改进

字符串模式匹配算法是入侵检测系统中的一种重要算法.通过对两种著名的匹配算法KMP和BM算法以及现有的各种改进算法的分析,提出一种简单实用、易于理解的字符串匹配改进算法.该算法通过每次匹配失败时特殊位置上字符的启发来获得字符串向后移动的可能距离,这个距离由定义的一个统一函数求出,取其中的最大值作为字符串向后移动的实际距离.实验结果表明,该算法能减少模式匹配中字符的比较次数和尝试次数,提高模式匹配的效率.     

Improved string searching

We show that it is possible to improve the average time of the Boyer-Moore string matching algorithm using more space. This is accomplished by applying a transformation that virtually increases the size of the alphabet in use. The improvement is such that for long patterns it is possible to obtain an algorithm more than 50 per cent faster than the original one. We include experimental results on random and English text. Some improvements for searching on English text are also discussed.     

Approximate string matching using withinword parallelism

Given a text string, a pattern string, and an integer k, the problem of approximate string matching with k differences is to find all substrings of the text string whose edit distance from the pattern string is less than k. The edit distance between two strings is defined as the minimum number of differences, where a difference can be a substitution, insertion, or deletion of a single character. An implementation of the dynamic programming algorithm for this problem is given that packs several characters and mod-4 integers into a computer word. Thus, it is a parallelization of the conventional implementation that runs on ordinary processors. Since a small alphabet means that characters have short binary codes, the degree of parallelism is greatest for small alphabets and for processors with long words. For an alphabet of size 8 or smaller and a 64 bit processor, a 21-fold parallelism over the conventional algorithm can be obtained. Empirical comparisons to the basic dynamic programming algorithm, to a version of Ukkonen's algorithm, to the algorithm of Galil and Park, and to a limited implementation of the Wu-Manber algorithm are given.