串匹配算法中模式串与文本之间关系的研究

经典的串匹配算法设计和分析中假设“字符互相独立并且等概率出现”,这与实际应用环境差异很大,导致出现很多问题.考虑了字符的概率分布和上下文的关联,同时兼顾应用的方便,提出了命中密度的概念.在给出基本定义和扩展定义后,通过对4种类型的代表性算法的理论和实验分析,给出了命中密度与算法性能之间的关系.同时,在对命中密度的分析中得出一些极具价值的结论.对命中密度概念的多角度理解以及对它与算法性能关系的深入剖析都说明,命中密度作为一个特征量,可以从一个侧面刻画模式串和文本之间的相关性,它对算法的设计和分析以及串匹配领域研究工作的扩展都具有指导意义.     

BM串匹配算法与改进算法的研究

串匹配算法在数字通信等方面应用广泛,BM算法是主要的串匹配算法之一。文章在分析了BM算法过程和一些现有的改进算法,对这些算法进行了比较,并结合BMG算法,提出了一个新的改进算法。该算法考虑了模式匹配时出现重复字符时,比较的前一个字符的出现情况以及模式串首字符的特性,提高了模式串移动m＋1位的概率,提高了匹配速度。     

Boyer-Moore串匹配算法的改进

在分析Boyer-Moore(BM)算法的基础上,提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段,对扩展模式串Pa建立好后缀规则,其中:P是模式串,a是字母表中的任一字符,既加大了已匹配后缀的长度,同时隐含了Sunday算法的坏字符规则,从而获得更大的窗口跳跃距离。理论分析证明,该算法具有线性最差时间复杂度和亚线性平均时间复杂度,空间复杂度为O(m(σ+1))。实验结果表明,该算法的实际性能与BM算法相比有明显改善,尤其适合小字母表的情形。     

Boyer-Moore串匹配算法的改进

在分析Boyer-Moore (BM)算法的基础上,提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段,对扩展模式串Pa建立好后缀规则,其中：P是模式串,a是字母表中的任一字符,既加大了已匹配后缀的长度,同时隐含了Sunday算法的坏字符规则,从而获得更大的窗口跳跃距离。理论分析证明,该算法具有线性最差时间复杂度和亚线性平均时间复杂度,空间复杂度为O(m(σ+1))。实验结果表明,该算法的实际性能与BM算法相比有明显改善,尤其适合小字母表的情形。     

基于后缀WM匹配算法的改进算法

针对基于后缀WM匹配算法中的字符重复匹配问题,给出了相应的改进算法.该算法针对扫描阶段确定的与模式串前缀、后缀和前m个字符的后缀都相同的文本串字符块,在匹配阶段跳过文本串字符块中已经确定的字符块,避免了对已经确定的字符块的重复匹配,减少匹配开销.实验结果表明,相对于原始算法,改进算法降低了系统匹配的运行时间,提高了系统运行的效率.     

一种改进的朴素模式串匹配算法

本文基于朴素模式串匹配算法的基本思想及鉴于一些高级语言所提供的字符(串)函数的启发,阐述了在算法中主串匹配起点字符定位的灵活性及多次匹配的必要性,并基于VC 6.0环境下验证了该算法的可行性.     

一种按字长匹配的Wu-Manber多模式匹配算法

多模式匹配是串处理系统中最重要的操作之一,而Wu-Manber算法是多模式串匹配算法中平均性能表现最好的算法.针对Wu-Manber多模式匹配算法在规则集中存在短模式串时性能下降的问题,提出一种按字长匹配的多模式匹配算法.改进的算法是在32位机器上实现,哈希的字符块长度取2,每次匹配的单位由原来的一个字符变为一个机器字,缩小了访存时间,同时利用机器字长存储的特点合理设计哈希函数,加快了字符块哈希值的计算,极大的提高了有短模式串存在时模式集的匹配性能.与原Wu-Manber算法对比,当最短模式串长度小于6时,改进后的算法搜索时间平均缩短了40％.当最短模式串长度为2和3时,搜索时间缩短了60％以上.     

BM串匹配的一个改进算法

在分析BM算法和文献[12]的基础上，给出了BM串匹配的一个改进算法。该算法有以下重要的特点：1)最坏情况下，算法有效地减少了字符重复比较的次数，提高了匹配效率；2)匹配算法在二维匹配和不精确匹配中较易推广。     

一种串匹配的快速Boyer-Moore算法

在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上,提出了一种更加快速的串匹配算法Quick Boyer-Moore（QBM）。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置信息,以在每一次跳跃中获得更大的跳跃距离,从而使算法具有更高的效率。在真实语料上的实验结果表明,QBM算法的效率较显著地高于原始的BM算法及其改进算法Impmved Boyer-Moore（IBM）。     

面向中英文混合环境的多模式匹配算法

分析了中英文混合环境下多模式匹配的特点,以及已有多模式匹配算法应用于中英文混合环境时的不足,给出并证明了中英文混合环境下多模式匹配算法的性能定理,提出了一种适合于中英文混合环境的基于线索完全哈希Trie结构的多模式匹配算法.该算法扩展了标准Trie结构,以中英文字符内码为键值构造完全哈希Trie匹配机,并利用模式串之间的关系对Trie匹配机进行线索化.理论分析与实验结果表明,所提出的算法在匹配中无需复杂的哈希运算,不需要回溯匹配指针,在中英文混合环境下能够进行正确、高效的匹配,而且不存在空间膨胀问题,具有较低的空间与时间复杂度,有较大理论与应用价值.     

交互式网络数据库应用程序的多线程解决方案

本文介绍了在交互式网络数据库应用程序的开发中利用多线程方式提高客户端实时响应能力的解决方案，并着重讨论了如何合理地构造本地资源机制，以提高在客户端取数据时的命中率；最后还介绍了一个采用Java多线程的解决方案的具体实例，以及Java中线程间的调度问题.     

基于背包理论的流媒体缓存算法

为了使缓存总体效益最大化,基于字节命中率,利用0-1背包对代理缓存建立模型,给出流媒体缓存替换算法。实验结果表明,与传统流媒体缓存算法相比,该算法能减少占用带宽,提升缓存写入效率,具有较高的字节命中率。     

基于汉语二字应成词的歧义字段切分方法

文章提出了利用汉语中的二字应成词,计算汉语句内相邻字之间的互信息1及t-信息差这两个统计信息量的新方法,进而应用这两个统计量,解决汉语自动分词中的歧义字段的自动切分问题。实验结果表明,采用该文所述的方法,对歧义字段的切分正确率将达到90%,与其他分词方法相比较,进一步提高了系统的分词精度,尤其与文献1所述方法比较,对于有大量汉语信息的语料,将降低系统的时间复杂度。     

State-space neural network for modelling,prediction and control

The state-space neural network paradigm is a neural model suitable for various applications in the field of control engineering. In this paper, it is shown how this neural model can be applied to three common tasks in control engineering: modelling of a diffusion section in a sugar industry, prediction in a wastewater plant, and neural model-based predictive control in a sugar factory. Results from these applications show the applicability and good performance of this neural model that, together with the theoretical results available for this type of neural model, gives an excellent alternative to classical linear models in cases where the non-linearity of the system requires it.     

坦克射击效力仿真系统设计

坦克射击效力仿真系统通过分析现装备的坦克火控系统存在的误差,给出在不同条件下坦克火控系统的射击误差议程、计算出射击的命中概率和毁伤概率、仿真出实际射击时的射弹散布情况,并通过半实物仿真来实现检测射手的射击水平。     

循环Cache命中率分析方法的研究与实现

循环Cache命中率的分析是编译优化中的关键技术之一。CME(CacheMissEquation)作为描述一个精确描述程序循环中数组引用的Cache冲突情况的数学模型及其相关的理论为较精确地分析循环的Cache命中率奠定了理论基础。该文以CME理论为基础,从数理统计的角度对CME抽样分析作了理论上的说明,采用序贯抽样方法来进行CME的抽样分析,并对抽样检验过程中判断线性约束条件下丢番图方程是否存在整数解这一NP问题,结合一些整数计算的理论,给出了格测试的快速算法。     

基于无指导学习策略的无词表条件下的汉语自动分词

探讨了基于无指导学习策略和无词表条件下的汉语自动分词方法，以期对研制开放环境下健壮的分词系统有所裨益,全部分词知识源自从生语料库中自动获得的汉字Bigram．在字间互信息和t-测试差的基础上，提出了一种将两者线性叠加的新的统计量md，并引入了峰和谷的概念，进而设计了相应的分词算法，大规模开放测试结果显示，该算法关于字间位置的分词正确率为85．88％，较单独使用互信息或t-测试差分别提高了2．47％和5．66％。     

基于差分隐私的社交网络位置近邻查询方法

针对社交网络中近邻位置查询时个人位置隐私泄漏的问题,采用地理不可区分性机制对位置数据添加随机噪声,提出了一种隐私预算分配方法。首先,对空间区域进行网格化分割,根据用户在不同区域的位置访问量来个性化分配隐私预算;然后,为了解决在扰动位置数据集中近邻查询命中率偏低的问题,提出了一种组合增量近邻查询（CINQ）算法,以扩大需求空间的检索范围,并利用组合查询过滤冗余数据。在仿真实验中,与SpaceTwist算法相比,CINQ算法的查询命中率提高了13.7个百分点。实验结果表明,CINQ算法有效解决了因为查询目标的位置扰动所带来的查询命中率偏低问题,适用于社交网络应用中扰动位置的近邻查询。     

基于正态云模型的篮球机器人投篮命中率研究

为研究投篮角度、投篮速度、投篮高度对类人篮球机器人投篮命中率的影响规律,提出一种正态云模型,模拟篮球机器人在制造设计过程中的精度误差,并用Matlab进行仿真实验。实验结果表明,对命中率影响的因素强弱从大到小依次是投篮角度、投篮高度和投篮速度,如果这些参数的熵和超熵变小,命中率会提高,反之则会降低。     

基于概念树的文本自动分类系统的研究与实现

该文分类是信息处理的重要研究方向,现在应用较多的都是基于统计的分类系统,本文介绍了一种新型的文本分类理念,通过概念符号化,使用数字化的概念而非词汇来组成特征项,能最大限度地保留文本信息,且不需要训练语料,能灵活适应不同的分类体系。接下来详细描述了领域特征信息提取的4个步骤,以及分类体系的选取与设计。最后给出了实验的测试数据,并对影响性能的一些关键因素进行了分析,指出了进一步提高分类性能的途径。