基于改进BM算法的确定型有穷自动机的设计

通过对有穷自动机理论与BM算法进行分析,设计了一个基于改进BM算法的确定型有穷自动机的模型,该模型描述了向基于改进BM算法的确定型有穷自动机输入文本字符串,自动机输出TRUE,说明文本串中存在与模式串相匹配的字符;自动机输出FALSE,说明文本串中不存在与模式串相匹配的字符串,并给出了对比实验及分析.     

一种基于有限自动机的快速串匹配算法

串匹配是字符串的基本操作之一,因此为它设计一个高效算法具有一定意义.文中基于有限自动机理论,在对经典的K.M.P.算法进行分析的基础上,提出了一种快速的串匹配算法.该算法利用自动机的状态转换表实现串匹配,避免了扫描字符串时的失败链回溯,从而加快了算法的运行速度.理论分析与实验结果均表明,在正文串比较长,模式串中局部匹配失败时失败链反馈较多的情况下,该算法在速度上明显优于K.M.P.算法.但在空间复杂度上,该算法需要较多的存储空间.     

双向AC算法及其在入侵检测系统中应用

在经典的多模式字符串匹配算法-AC算法的基础上,提出了双向AC算法.该算法在预处理阶段构造正向和反向两个有限状态自动机,匹配时使用正向有限自动机从文本串中间位置向右扫描,同时依据反向有限状态自动机从中间位置向左扫描.将该算法应用于开放源码的入侵检测系统Snort中,实验结果表明较BM算法、WM算法和AC算法本算法有更好...     

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

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

基于像素字符串比较的图像快速匹配算法

在分析传统的模板匹配算法的基础上提出了一种新的基于字符串匹配的快速匹配算法.算法的思路是在模板图像上任意确定一列像素,并将这一列像素的灰度值看成是一个字符串,以此对原图像的每一列进行字符串匹配.如果在原图像上的某一列上找到了完全匹配的串,或者找到最大匹配的串,就找到了所要匹配的模板在图像中的可能位置.然后在所有找到的位置上再做进一步的字符串匹配.如此继续就可以确定模板图像在待匹配图像上的位置.算法在统计意义上保证了匹配效果,且提高了匹配速度.实验结果表明该算法是一种有效的图像匹配算法.     

基于像素字符串比较的图像快速匹配算法

在分析传统的模板匹配算法的基础上提出了一种新的基于字符串匹配的快速匹配算法。算法的思路是在模板图像上任意确定一列像素，并将这一列像素的灰度值看成是一个字符串，以此对原图像的每一列进行字符串匹配。如果在原图像上的某一列上找到了完全匹配的串，或者找到最大匹配的串，就找到了所要匹配的模板在图像中的可能位置。然后在所有找到的位置上再做进一步的字符串匹配。如此继续就可以确定模板图像在待匹配图像上的位置。算法在统计意义上保证了匹配效果，且提高了匹配速度。实验结果表明该算法是一种有效的图像匹配算法。     

基于Bloom filter的高效正则表达式匹配算法*

针对确定有限自动机(DFA)的正则表达式匹配技术存在状态膨胀和一次状态转移只能处理单个字符的问题,提出了一种基于布鲁姆过滤器的正则表达式匹配算法。该算法将正则表达式中的每个确定字符串组成DFA的一个状态,添加比特向量完成匹配过程,并且在一次状态转移中根据确定字符串的匹配结果达到处理多个字符的目的。实验分析表明该算法有效降低了DFA状态的膨胀,提高了匹配速率。     

一种基于反向有限自动机的多模式匹配算法

在基于有限自动机的多模式匹配算法DFSA的基础上,结合改进的BM单模式匹配算法的优点,提出一种快速的多模式字符串匹配算法。在一般情况下,该算法不需要匹配目标文本串的每个字符,能充分利用匹配过程中本次匹配不成功的信息和已成功的信息,跳过尽可能多的字符。实验表明,模式串较短时,该算法需要的时间约为DFSA的1/2,模式串较长时,所需时间约为DFSA算法的1/3。     

一种改进的BM模式匹配算法

针对BM模式匹配算法的效率问题,提出其改进算法.分析BM模式匹配算法的原理,若文本串中连续的几个字符不在模式字符串中出现,则不需要被比对,以此改变模式字符串的匹配顺序,提高算法的匹配效率.实验结果表明,改进的BM模式匹配算法可以有效地减少字符串的匹配次数和比对次数,能获得良好的字符串匹配效率.     

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

提出一种改进的字符串模式匹配算法。该算法对文本串进行预处理,即对文本串中不存在于模式串中的字符以及文本串中剩下的出现次数最少的字符分别进行标记,再通过匹配模式串的首尾字符来减少出现次数最少的字符的标记个数。发生匹配失败时,将模式串直接滑动到标记了的出现次数最少的字符处。通过实验证明,该算法的移动次数和比较次数有较大减少,耗费的额外空间的大小也不超过模式串的长度,进一步提高模式匹配的效率。     

Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm

Multiple string matching is often completed under the presence of U- or V-uncertain-strings,or combinations thereof.Recognizing large numbers of strings with U-, V-,and U-V-uncertain-strings,including the interleaving of two or more uncertain strings,is important to thoroughly gathering useful information and detecting harmful information.This paper proposes a complete automaton and its high-speed construction algorithm for large-scale U-, V-,and U-V-uncertain multiple strings,including two or more uncertai...     

U-系统与 V-系统的理论及应用综述

传统的 Fourier 级数在逼近间断信号时因 Gibbs 现象的干扰,会产生比较大的误差。针对此问 题,国内学者齐东旭教授带领的课题组提出了非连续正交函数系的研究课题,其中 U-系统和 V-系统是两类典 型的非连续完备正交函数系。从数学理论上来说,U-系统和 V-系统分别是对著名的 Walsh 函数和 Haar 函数由 分段常数向分段 k 次多项式进行推广的结果,其最重要的特点是函数系中既有光滑函数又有各个层次的间断函 数。因此,U,V-系统可以处理连续和间断并存的信息,在一定程度上弥补了 Fourier 分析和连续小波的缺憾。 本文从理论与应用 2 个方面对 U,V-系统进行了综述。在理论方面,首先介绍了单变量 U-系统与 V-系统各自 的构造方法,其次介绍三角域上 U,V-系统的构造方法,最后介绍 U,V-系统的主要性质。在应用方面,介绍 了若干具有代表性的应用案例。     

基于嵌入式Linux的汽车信息服务系统

本文介绍了一种集成汽车定位导航,防盗报警,故障诊断的汽车信息服务系统。采用IntelPxa255微处理器,在嵌入式Linux操作系统下综合GPS,GPRS,GIS,图象采集压缩等技术建立一种U-V-S(User-Vehicle-Server)三位一体的智能化汽车服务体系。     

中文语音合成中的文本正则化研究

中文文本正则化是把非汉字字符串转化为汉字串以确定其读音的过程。该工作的难点:一是正则化对象——非汉字串形式复杂多样,难于归纳;二是非汉字串有歧义,需要消歧处理。文章引入非标准词的概念对非汉字串进行有效归类,提出非标准词的识别、消歧及标准词生成的三层正则化模型。在非标准词的消歧中引入机器学习的方法,避免了复杂规则的书写。实验表明,此方法取得了很好的效果,并具有良好的推广性,开放测试的正确率达到98.64%。     

A formal model of computing with words

Classical automata are formal models of computing with values. Fuzzy automata are generalizations of classical automata where the knowledge about the system's next state is vague or uncertain. It is worth noting that like classical automata, fuzzy automata can only process strings of input symbols. Therefore, such fuzzy automata are still (abstract) devices for computing with values, although a certain vagueness or uncertainty are involved in the process of computation. We introduce a new kind of fuzzy automata whose inputs are instead strings of fuzzy subsets of the input alphabet. These new fuzzy automata may serve as formal models of computing with words. We establish an extension principle from computing with values to computing with words. This principle indicates that computing with words can be implemented with computing with values with the price of a big amount of extra computations.     

An improved algorithm for the longest common subsequence problem

The Longest Common Subsequence problem seeks a longest subsequence of every member of a given set of strings. It has applications, among others, in data compression, FPGA circuit minimization, and bioinformatics. The problem is NP-hard for more than two input strings, and the existing exact solutions are impractical for large input sizes. Therefore, several approximation and (meta) heuristic algorithms have been proposed which aim at finding good, but not necessarily optimal, solutions to the problem. In this paper, we propose a new algorithm based on the constructive beam search method. We have devised a novel heuristic, inspired by the probability theory, intended for domains where the input strings are assumed to be independent. Special data structures and dynamic programming methods are developed to reduce the time complexity of the algorithm. The proposed algorithm is compared with the state-of-the-art over several standard benchmarks including random and real biological sequences. Extensive experimental results show that the proposed algorithm outperforms the state-of-the-art by giving higher quality solutions with less computation time for most of the experimental cases.     

Robust identification for multi_section freeway traffic models

Since it is difficult to fit measured parameters using the conventional traffic model, a new traffic density and average speed model is introduced in this paper.To determine traffic model structures accurately, a model identification method for uncertain nonlinear system is developed.To simplify uncertain nonlinear problem, this paper presents a new robust criterion to identify the multi-section traffic model structure of freeway efficiently.In the new model identification criterion,numerically efficient U-D factorization is used to avoid computing the determinant values of two complex matrices.By estimating the values of U-D factor of data matrix, both the upper and lower bounds of system uncertainties are described. Thus a model structure identification algorithm is proposed.Comparisons between identification outputs and simulation outputs of traffic states show that the traffic states can be accurately predicted by means of the new traffic models and the structure identification criterion.     

A relation between edit distance for ordered trees and edit distance for Euler strings

We consider a relationship between the unit cost edit distance for two rooted ordered trees and the unit cost edit distance for the corresponding Euler strings. We show that the edit distance between trees is at least half of the edit distance between the Euler strings and is at most 2h+1 times the edit distance between the Euler strings, where h is the minimum height of two trees. The result can be extended for more general cost functions.     

Maximal Common Subsequences and Minimal Common Supersequences

The problems of finding a longest common subsequence and a shortest common supersequence of a set of strings are well known. They can be solved in polynomial time for two strings (in fact the problems are dual in this case), or for any fixed number of strings, by dynamic programming. But both problems are NP-hard in general for an arbitrary numberkof strings. Here we study the related problems of finding a shortest maximal common subsequence and a longest minimal common supersequence. We describe dynamic programming algorithms for the case of two strings (for which case the problems are no longer dual), which can be extended to any fixed number of strings. We also show that both problems are NP-hard in general forkstrings, although the latter problem, unlike shortest common supersequence, is solvable in polynomial time for strings of length 2. Finally, we prove a strong negative approximability result for the shortest maximal common subsequence problem.     

筛选查找法

本算法是将给定的一个或多个模式串分解成若干个等长的状态,将这些状态转换成１比特信息并构造信息表。然后用这一信息表筛选数据。最后将筛选出的字符串去假留真,达到在随机数据中一次查找多个模式串的目的。