共查询到16条相似文献,搜索用时 140 毫秒
1.
字符串匹配是计算机科学中最经典、研究最广泛的问题之一,并且已经被应用到了众多领域当中。近似字符串匹配问题的研究虽然经历了不短的时间历程,但是其中的研究对象绝大多数主要是针对DNA等小型字符集或针对英文等中等大小字符集,而对于汉字乃至亚洲语音等大型字符集的研究却仍然不多。因此,研究高效的近似字符串匹配算法具有重要的理论价值和实际意义。 相似文献
2.
黄荣喜 《计算机光盘软件与应用》2013,(13):261+263
串匹配问题是计算机科学研究中比较广泛的问题之一,目前字符串匹配算法主要是针对英文等字符的匹配居多,而针对中文等字符的匹配比较少,本文将针对中文字符匹配的算法进行浅析,提出一种适合中文字符模式近似匹配算法的设计,通过实验证明了该算法的有效性。 相似文献
3.
4.
王静婷 《网络安全技术与应用》2010,(12):41-44,40
字符串近似匹配在网络安全中有广泛的应用。本文从中文字符串相似度角度出发,提出了通过单个汉字的细分来提高字符相似度的想法,并从汉字"成簇性"方面进行分析,引出了汉字的Key表示方法,将汉字与Key的映射关系归结为规则,讨论了规则的获取方法。设计了基于规则的中文字符串近似匹配的框架,提出了新的相似度计算模型,并通过实验对整个流程加以验证,证明基于规则的中文字符串近似匹配的优越性。 相似文献
5.
近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。 相似文献
6.
7.
一种有效的字符串有序跳跃模式近似匹配算法 总被引:1,自引:0,他引:1
字符串的模式匹配问题是计算机科学的基本问题之一,而近似模式匹配更是近期的研究热点。本文分析了文本分析领域中出现的一种特殊的近似模式匹配问题,即字符串有序跳跃模式近似匹配问题,提出了一种基于有限自动机的组件组合分析算法。算法的特点在于将组件匹配过程与组配过程进行分离,这样既降低了问题的复杂度,又可以实现按策略组配的灵活性。组件匹配过程中利用有限自动机对跳跃模式的组件进行匹配查找;组件的组配过程中先对查找到的组件进行组合分析,然后再对各种组合进行初步筛选和基于策略的优选。初步筛选工作是依据顺序性、唯一性和最大数三条原则进行;而优选工作是根据四个设计的评价参数选择其中最佳组合。实验结果表明,该算法的确能解决字符串有序跳跃模式匹配问题,完全可以适用于句型匹配与主题词跳词匹配。 相似文献
8.
9.
10.
快速中文字符串模糊匹配算法 总被引:9,自引:3,他引:9
本文解决了中文字符串模糊匹配的两个主要问题:空间问题和时间问题。目前字符串模糊匹配的两个主要方法是位向量方法和过滤方法。由于汉字众多,应用位向量方法时,需要大量空间。对于某些内存很少的小型计算机,比如嵌入式系统,这将会是一个问题。本文改进了位向量方法,使其在应用于中文字符串时,空间需求降低到约5%。本文还利用汉字非常多的特点,提出一种新的基于过滤方法的中文字符串模糊匹配算法,BPM-BM,其速度比世界上最快的算法至少提高14%;在大部分情况下,是其速度的1.5~2倍。 相似文献
11.
一种高速精确单模式串匹配算法 总被引:1,自引:0,他引:1
串匹配问题是计算机科学的基础问题之一,是网络安全、信息检索与过滤、计算生物学等众多领域的核心问题,其中,高速精确单模式匹配算法设计又是各种串匹配问题的基础.基于SBNDM2,通过修改位掩码有效位到无符号整数的高位,将BNDM算法核心循环化简至最简形式(5指令/字符),并引入越界保护机制,提出S2BNDM系列精确单模式匹配算法.实验结果显示,S2BNDM系列算法在任何情况下都快于SBNDM2,对于英文语料(m<32)和DNA序列(m<8),S2BNDM系列算法为现有已知最快算法. 相似文献
12.
字符串模式匹配算法的改进 总被引:2,自引:0,他引:2
字符串模式匹配算法是入侵检测系统中的一种重要算法.通过对两种著名的匹配算法KMP和BM算法以及现有的各种改进算法的分析,提出一种简单实用、易于理解的字符串匹配改进算法.该算法通过每次匹配失败时特殊位置上字符的启发来获得字符串向后移动的可能距离,这个距离由定义的一个统一函数求出,取其中的最大值作为字符串向后移动的实际距离.实验结果表明,该算法能减少模式匹配中字符的比较次数和尝试次数,提高模式匹配的效率. 相似文献
13.
蒋莉莉 《数字社区&智能家居》2008,(3)
字符串模式匹配算法是入侵检测系统中的一种重要算法。通过对KMP算法和BM算法以及其他改进算法的分析,提出一种简单实用、易于理解的字符串匹配改进算法。实验表明该算法能减少模式匹配中字符的比较次数和尝试次数,提高模式匹配的效率。 相似文献
14.
基于匹配区域特征的相似字符串匹配过滤算法孙德才 总被引:1,自引:0,他引:1
相似字符串匹配过滤算法因其适合大库查找而被广泛应用,为通过提高过滤算法的过滤效率加快匹配速度,提出一种基于匹配区域特征的过滤算法.该算法将模式串和文本串分割成固定长度为kq+1的逻辑块,并从各块中提取了2个新的匹配区域特征:q-gram命中的均匀性和q-gram有效命中的区域性.新算法利用这些新特征优化了传统过滤标准,提高了算法的过滤效率;并改进了QUASAR中基于分块策略的过滤区确定方案.实验结果表明,新算法与改进前相比有效地加快了匹配速度,尤其在误差率较小时改进效果更佳. 相似文献
15.
基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。通过分析几种常见的字符串匹配算法(AC、AC_BMH、Sunday等)的基础,提出了一种对AC算法的改进,新算法每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配,使得匹配次数大大减少,从而提高了匹配效率。分析了该算法的性能,并用具体的实验数据给出了几种匹配算法的测试结果。 相似文献