Real Two Dimensional Scaled Matching

Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is an important problem that was originally inspired by Computer Vision. Finding a combinatorial definition that captures the concept of real scaling in discrete images has been a challenge in the pattern matching field. No definition existed that captured the concept of real scaling in discrete images, without assuming an underlying continuous signal, as done in the image processing field. We present a combinatorial definition for real scaled matching that scales images in a pleasing natural manner. We also present efficient algorithms for real scaled matching. The running times of our algorithms are as follows. For T, a two-dimensional n×n text array, and P, an m×m pattern array, we find in T all occurrences of P scaled to any real value in time O(nm ³+n ² mlog m). Research of A. Amir partially supported by ISF grant 282/01 and NSF grant CCR-01-04494.     

支持带有通配符的字符串匹配算法

研究了查询字符串中含有通配符"*"以及"?"两种情况下的字符串匹配问题,其中,"*"代表任意长度的字符串,"?"代表字母表中任意一个字符。由于gram索引结构在空间大小以及查询效率上的优势,将gram索引结构用于带通配符的字符串匹配问题。通过将带有通配符的查询字符串分解为若干不含通配符的查询片段,成功地将带有通配符的复杂查询问题转化为不含通配符的简单精确子串匹配问题。同时在片段查询过程中运用长度过滤、位置过滤以及计数过滤等方法来提高查询速度。     

On-line scheduling with extendable working time on a small number of machines

Speranza and Tuza [Ann. Oper. Res. 86 (1999) 494-506] studied the on-line problem of scheduling jobs on m identical machines with extendable working time. In this problem, each machine is assumed to have an identical regular working time, which can be extended if necessary. The working time of a machine is the larger one between its regular working time and the total processing time of jobs assigned to it. The objective is to minimize the total working time of machines. They presented an on-line algorithm H_x, with a competitive ratio at most 1.228 for any number of machines by choosing an appropriate parameter x. In this paper we consider a small number of machines. The best choices of x are given for m=2,3,4 and the tight bounds, 7/6, 11/9 and 19/16, respectively, are proved. Among them, the algorithm for m=2 is best possible. We then derive a new algorithm for m=3 with a competitive ratio 7/6.     

基于Horspool算法的模糊匹配

匹配模式中存在模糊信息的匹配形式称为模糊匹配,它是目前字符串匹配的重要研究方向。Horspool算法是精确匹配的经典算法,但不能实现模糊匹配。该文将要求匹配的模式转化为相应的二进制数序列,在HorSpool算法基础上扩大其功能,使其能够实现模糊匹配,且不影响其精确匹配的功能。     

Two-Dimensional Prefix String Matching and Covering on Square Matrices

Two linear time algorithms are presented. One for determining, for every position in a given square matrix, the longest prefix of a given pattern (also a square matrix) that occurs at that position and one for computing all square covers of a given two-dimensional square matrix. Received December 21, 1995; revised September 12, 1996.     

A Randomized Algorithm for Approximate String Matching

We give a randomized algorithm in deterministic time O(Nlog  M) for estimating the score vector of matches between a text string of length N and a pattern string of length M , i.e., the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. A direct application is approximate string matching. The randomized algorithm uses convolution to find an estimator of the scores; the variance of the estimator is particularly small for scores that are close to M , i.e., for approximate occurrences of the pattern in the text. No assumption is made about the probabilistic characteristics of the input, or about the size of the alphabet. The solution extends to string matching with classes, class complements, ``never match' and ``always match' symbols, to the weighted case and to higher dimensions. Received July 20, 1997; revised April 20, 1998, and June 1, 1999.     

Squares,cubes, and time-space efficient string searching

We address several technical problems related to the time-space optimal string-matching algorithm of Galil and Seiferas (called the GS algorithm). This algorithm contains a parameterk on which the complexity depends and that originally satisfiesk 4. We show thatk=3 is the least integer for which the GS algorithm works. This value of the parameterk also minimizes the time of the search phase of the string-searching algorithm. With the parameterk=2 we consider a simpler version of the algorithm working in linear time and logarithmic space. This algorithm is based on the following fact: any word of lengthn starts by less than log n squares of primitive prefixes. Fibonacci words have a logarithmic number of square prefixes. Hence, the combinatorics of prefix squares and cubes is essential for string-matching with small memory.We give a time-space optimal sequential computation of the period of a word based on the GS algorithm. The latter corrects the algorithm given in [GS2] for the computation of periods. We present an optimal parallel algorithm for pattern preprocessing. This paper also provides a cleaner version and a simpler analysis of the GS algorithm.Work by this author was partially supported by PRC Mathématiques-Informatique, by GDR Informatique et Genome, and by NATO Grant CRG 900293.Work by this author was supported by Grant KBN 2-11-90-91-01.     

模式匹配算法的研究与改进

随着网络的迅速发展,网络安全问题日益突出,入侵检测技术也成为当今社会关注的焦点。对于基于规则的入侵检测来说,模式匹配算法非常重要,它直接影响到系统的准确性和实时性能。本文介绍了KMP和BM算法,对BM算法的改进进行了研究,并提出一种改进的BM算法。改进后的算法运用到入侵检测系统模型中极大地提高了检测性能。     

模式匹配算法的研究与改进

随着网络的迅速发展,网络安全问题日益突出,入侵检测技术也成为当今社会关注的焦点。在基于规则的入侵检测系统中,模式匹配算法非常重要,它直接影响到系统的准确性和实时性能。介绍了BM算法和BMH算法,对BM算法的改进进行了研究,并提出一种改进的BM算法。改进后的算法运用到入侵检测系统中极大地提高了系统的检测性能。     

An algorithm for Exact Satisfiability analysed with the number of clauses as parameter

We give an algorithm for Exact Satisfiability with polynomial space usage and a time bound of poly(L)⋅m!, where m is the number of clauses and L is the length of the formula. Skjernaa has given an algorithm for Exact Satisfiability with time bound poly(L)⋅m² but using exponential space. We leave the following problem open: Is there an algorithm for Exact Satisfiability using only polynomial space with a time bound of cm, where c is a constant and m is the number of clauses?     

Approximate regular expression pattern matching with concave gap penalties

Given a sequenceA of lengthM and a regular expressionR of lengthP, an approximate regular expression pattern-matching algorithm computes the score of the optimal alignment betweenA and one of the sequencesB exactly matched byR. An alignment between sequencesA=a₁a₂ ... a_M andB=b₁b₂... b_N is a list of ordered pairs, (i₁,j₁), (i₂j₂), ..., (i_t,j_tt) such that i_k < i_k+1 and j_k < j_k+1. In this case the alignmentaligns symbols a_ik and b_jk, and leaves blocks of unaligned symbols, orgaps, between them. A scoring schemeS associates costs for each aligned symbol pair and each gap. The alignment's score is the sum of the associated costs, and an optimal alignment is one of minimal score. There are a variety of schemes for scoring alignments. In a concave gap penalty scoring schemeS={, w}, a function (a, b) gives the score of each aligned pair of symbolsa andb, and aconcave function w(k) gives the score of a gap of lengthk. A function w is concave if and only if it has the property that, for allk > 1, w(k + 1) –w(k) w(k) –w(k –1). In this paper we present an O(MP(logM + log² P)) algorithm for approximate regular expression matching for an arbitrary and any concavew. This work was supported in part by the National Institute of Health under Grant RO1 LM04960.     

基于后缀树的带有通配符的模式匹配研究

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究 的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其 中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束。采用非线性数据结构—后缀树,设计了求 解模式所有解的完备算法PAS"I'。预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合 动态规划的思想,逐个匹配模式中字符,最终得到完备解。在基因序列上的实验表明,PAST比其他算法具有更好的 时间性能。     

From Nerode’s congruence to suffix automata with mismatches

In this paper we focus on the minimal deterministic finite automaton _Sk$S_k$ that recognizes the set of suffixes of a word w$w$ up to k$k$ errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with _Sk$S_k$. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of _Sk$S_k$ to accept in an efficient way the language of all suffixes of w$w$ up to k$k$ errors in every window of size r$r$ of a text, where r$r$ is the repetition index of w$w$. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches.     

几种字符串匹配算法的分析和比较

字符串匹配技术在许多领域里被广泛应用。分析了BF、KMP、BM算法以及一些重要的改进算法,并对其性能进行了测试,为不同的应用领域采用适当的算法提供了思路。     

一种带有通配符和长度约束模式匹配问题的动态剪枝算法

近年来,随着生物信息学、信息检索等领域的发展,串模式匹配问题被不断扩展.其中,具有代表性的是在模式中引入可变长度的通配符而形成带有通配符的模式匹配(PMWL).该问题定义的灵活性给用户提供了方便,却也造成了求解上的困难.因此,如何在多项式时间内得到更好的匹配解成为研究的焦点.提出了一种启发式的小兵算法.小兵算法通过将PMWL问题转化为路径搜索问题,并借鉴动态剪枝思想,在算法搜索的过程中动态地将不可能的匹配位置剪枝,从而提高解的质量.实验在真实DNA序列上进行,并人工生成了196个模式.结果表明,相比于目前最有效的SAIL算法,小兵算法在绝大多数的尾部有重复字符的模式中可以获得更好的匹配解.     

带有通配符和长度约束的模式匹配问题求解模型

讨论了带有通配符和长度约束的模式匹配(PMWL)问题,其中模式由子模式序列集组成,两个相邻子模式的间隔在一定长度范围内。针对PMWL问题,已有工作包括设计启发式求解算法和对特殊情况进行完备性分析,然而还需要构建问题的基础求解模型。借鉴约束可满足问题框架,构建了由变量、值域和约束组成的三元组求解模型,对PMWL问题的基本概念和基本性质给出了形式化描述。最后,给出了算法求解PMWL问题的特定条件下的完备解。     

带通配符的模式匹配问题及其解空间特征分析

随着生物信息学、信息检索等领域的发展,带有通配符和长度约束的模式匹配问题引起了广泛关注。该问题扩展了精确模式匹配问题,使匹配更加灵活,同时也增加了匹配的复杂性,极大地提高了非线性匹配算法的复杂度。求解该问题的匹配算法的效率与问题的解空间密切相关,而目前针对该问题的解空间及其特征尚缺乏系统的研究。鉴于此,描述了该问题的解空间,并分析了解空间的可分性。之后,提出解空间划分算法SPLIT,并分析了SPLIT的时间复杂性。实验部分以3个匹配算法为对照,在真实DNA数据集下,使用了5109组模式。实验结果表明,SPLIT不影响匹配解的结构,且可以有效降低非线性匹配算法的时间消耗。