检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

一种高速精确单模式串匹配算法

计算机研究与发展 2009年第8期46卷 1341-1348页

作者：范洪博姚念民哈尔滨工程大学计算机科学与技术学院哈尔滨150001 绥化学院计算机科学与技术系黑龙江绥化152000

串匹配问题是计算机科学的基础问题之一,是网络安全、信息检索与过滤、计算生物学等众多领域的核心问题,其中,高速精确单模式匹配算法设计又是各种串匹配问题的基础.基于SBNDM2,通过修改位掩码有效位到无符号整数的高位,将BNDM算法核心... 详细信息

串匹配问题是计算机科学的基础问题之一,是网络安全、信息检索与过滤、计算生物学等众多领域的核心问题,其中,高速精确单模式匹配算法设计又是各种串匹配问题的基础.基于SBNDM2,通过修改位掩码有效位到无符号整数的高位,将BNDM算法核心循环化简至最简形式(5指令/字符),并引入越界保护机制,提出S2BNDM系列精确单模式匹配算法.实验结果显示,S2BNDM系列算法在任何情况下都快于SBNDM2,对于英文语料(m<32)和DNA序列(m<8),S2BNDM系列算法为现有已知最快算法.

关键词：串匹配精确单模式算法设计位并行文本搜索

在线全文

学校读者我要写书评

暂无评论

一种时间复杂度最优的精确串匹配算法

软件学报 2005年第5期16卷 676-683页

作者：贺龙涛方滨兴余翔湛哈尔滨工业大学计算机网络与信息安全技术研究中心黑龙江哈尔滨150001

现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m?1的扫描窗口.在每个扫描窗口内,算法批量地... 详细信息

现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m?1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(logσm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用.

关键词：后缀自动机有限状态自动机 LDM算法串匹配复杂度分析

在线全文

学校读者我要写书评

暂无评论

分布式存储的并行串匹配算法的设计与分析

软件学报 2000年第6期11卷 771-778页

作者：陈国良林洁顾乃杰中国科学技术大学计算机科学技术系合肥230027

并行串匹配算法的研究大都集中在 PRAM(parallel random access machine)模型上 ,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多 .该文采用将最优串行算法并行化的技术 ,利用模式串的周期性质 ,巧妙地将改进的 KMP(Knuth- ... 详细信息

并行串匹配算法的研究大都集中在 PRAM(parallel random access machine)模型上 ,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多 .该文采用将最优串行算法并行化的技术 ,利用模式串的周期性质 ,巧妙地将改进的 KMP(Knuth- Morris- Pratt)算法并行化 ,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法 ,其计算复杂度为 O(n/ p+m) ,通信复杂度为 O(ulogp) ,其中 n为文本串长 ,m为模式串长 ,u为模式串最小周期长 ,p为处理器数 .

关键词：串匹配 KMP(Knuth-Morris-Pratt) 分布式算法可扩放性

在线全文

学校读者我要写书评

暂无评论

面向硬件的多模式串匹配算法及其链式实现

计算机工程 2006年第15期32卷 242-244页

作者：张小山赵国鸿王勇军国防科学技术大学计算机学院长沙410073

描述了一个面向硬件的简单有效的多模式字符串匹配算法,该算法易于用硬件实现。算法的主要思想是利用硬件的并行工作特性,让所有模式的每个字符都同时与输入的待匹配字符进行匹配,再迭代利用上轮匹配中的匹配信息来产生本轮匹配的结果... 详细信息

描述了一个面向硬件的简单有效的多模式字符串匹配算法,该算法易于用硬件实现。算法的主要思想是利用硬件的并行工作特性,让所有模式的每个字符都同时与输入的待匹配字符进行匹配,再迭代利用上轮匹配中的匹配信息来产生本轮匹配的结果。根据该算法设计了一种链式匹配结构并通过FPGA芯片对结构进行了逻辑实现,同时根据实验结果对设计进行了评价。

关键词：算法多模式串匹配匹配链

融合像素串匹配的AVS2全色度屏幕与混合内容视频编码算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2018年第11期41卷 2482-2495页

作者：赵利平周开伦郭靖蔡文婷林涛朱蓉嘉兴学院数理与信息工程学院同济大学超大规模集成电路研究所

新一代主流云计算与信息处理模式及平台中的一个主要问题是客户端与云服务器端(或客户端)之间的数据传输瓶颈问题,屏幕与混合内容编码技术以带宽最省、安全性高等优势,成为解决该问题的核心技术之一.该文在我国第二代数字音视频编解码... 详细信息

新一代主流云计算与信息处理模式及平台中的一个主要问题是客户端与云服务器端(或客户端)之间的数据传输瓶颈问题,屏幕与混合内容编码技术以带宽最省、安全性高等优势,成为解决该问题的核心技术之一.该文在我国第二代数字音视频编解码技术标准(AVS2)的屏幕与混合内容编码(SMCC)扩展版中,提出了一种融合像素串匹配的全色度屏幕与混合内容编码技术,该技术已经被AVS2-SMCC扩展版工作草案稿采纳.针对目前AVS2不支持全色度4∶4∶4格式的特点,作者设计与实现了一种融合4∶4∶4格式的像素串匹配编码算法和4∶2∶0格式的帧内、帧间预测编码算法的全色度屏幕混合内容编解码框架与算法.在此框架下,首先提出了一种4∶2∶0格式的帧内、帧间编码算法与4∶4∶4格式的串匹配编码算法的率失真代价值计算方式;然后给出了一种改进的像素串匹配算法及其关键技术,包括最佳参考串确定算法、基于N元组的快速哈希表搜索算法、基于分段截断二进制码的长度参数编码方案和基于N元组的位移参数编码方案.实验结果表明,对于AVS2-SMCC通用测试序列中的移动的文字和图形类别,提出的算法与AVS2-P2基准算法集成了色度上、下采样后支持YUV4∶4∶4格式的编解码器相比,在编码复杂度增加较少的情况下,对于有损全帧内(AI)配置Y分量、U分量、V分量平均BD-rate降低率分别可达56.1%,97.2%,99.2%;对于有损低延迟P(LDP)配置Y分量、U分量、V分量平均BD-rate降低率分别可达41.8%,70.9%,72.9%,能大幅提高屏幕与混合内容的编码效率.

关键词：视频编码数字音视频编解码技术标准屏幕混合内容串匹配哈希搜索熵编码

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

串匹配算法中的自动机紧缩存储技术

计算机工程 2009年第21期35卷 39-41页

作者：杨毅夫刘燕兵刘萍郭莉中国科学院计算技术研究所北京100190 中国科学院研究生院北京100039

自动机是串匹配算法中常用的数据结构,对自动机实现紧缩存储可以节省算法空间。总结常用自动机紧缩存储方法,分析其原理、时间效率、空间效率和优缺点,给出各种方法与数据稀疏性之间的关系。运用紧缩存储方法实现基本AC算法,对随机数据... 详细信息

自动机是串匹配算法中常用的数据结构,对自动机实现紧缩存储可以节省算法空间。总结常用自动机紧缩存储方法,分析其原理、时间效率、空间效率和优缺点,给出各种方法与数据稀疏性之间的关系。运用紧缩存储方法实现基本AC算法,对随机数据和真实数据的实验结果证明该算法有效。

关键词：紧缩存储自动机串匹配

在线全文

学校读者我要写书评

暂无评论

串匹配的一种算法

计算机研究与发展 1990年第2期27卷 35-37,34页

作者：周培德北京理工大学

本文提出一种合理的分割模式的方式,模式被分割后再将模式的各部分分别与正文进行匹配的算法。该算法的平均特性为O(m·10g_2 n),其中m为模式中字符的个数,n为正文中字符的个数。本算法对在正文中多次寻找不同模式的匹配较为适用。

关键词：串匹配算法数据结构

在线全文

学校读者我要写书评

暂无评论

DSP处理器上的高效串匹配实现

小型微型计算机系统 2021年第4期42卷 847-852页

作者：叶鸿顾乃杰林传文中国科学技术大学计算机科学与技术学院合肥230027 合肥学院计算机科学与技术系合肥230601

字符串匹配是生物识别、入侵检测的基础,也是大数据互联网时代的研究热点.随着现代信息技术的发展,日常工作生活中移动及手持小型化设备的使用越发普遍.这些设备的应用场景中包含大量有关串匹配的需求,如人脸识别、实时数据查询等.串匹... 详细信息

字符串匹配是生物识别、入侵检测的基础,也是大数据互联网时代的研究热点.随着现代信息技术的发展,日常工作生活中移动及手持小型化设备的使用越发普遍.这些设备的应用场景中包含大量有关串匹配的需求,如人脸识别、实时数据查询等.串匹配算法的实时和准确性决定了使用场景的范围,因此在DSP处理器等移动小型化设备的嵌入式处理器上实现高效串匹配算法的问题变得十分迫切.该文针对DSP处理器因缺乏逻辑判断与跳转指令,难以支持高效串匹配运算的问题,提出了一种基于DSP平台特点的改进串匹配算法.该算法采用位并行的思路,在DSP处理器上实现了串匹配算法的并行化.同时通过前序启动、基于VLIW的数学运算替代逻辑判断、Q-grams等优化手段,提高该算法对于DSP平台的适应性与执行效率,最终实现了一种基于HXDSP的高效串匹配算法VBNDM2.实验结果表明,本算法针对DSP平台,有效地提高了串匹配的效率,实现了算法的高效并行化.

关键词： DSP 串匹配 VLIW SIMD 位并行

在线全文

学校读者我要写书评

暂无评论

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

中文信息学报 2005年第2期19卷 20-27页

作者：刘萍谭建龙中国科学院计算技术研究所软件室北京100080

本文提出了一种对XML文本进行快速串匹配的算法 -XMatch。在对于XML文本的含路径信息的模式串匹配中 ,由于XML文本的结构化特点 ,使得传统的串匹配算法不能直接有效的使用 ;而现有的大部分XML内容筛选方法都是基于SAX分析的事件驱动过... 详细信息

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

关键词：计算机应用中文信息处理 XML数据处理串匹配多关键词匹配