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.     

Approximate string matching for music analysis

Approximate pattern matching algorithms have become an important tool in computer assisted music analysis and information retrieval. The number of different problem formulations has greatly expanded in recent years, not least because of the subjective nature of measuring musical similarity. From an algorithmic perspective, the complexity of each problem depends crucially on the exact definition of the difference between two strings. We present an overview of advances in approximate string matching in this field focusing on new measures of approximation.     

Faster two-dimensional pattern matching with rotations

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n²m³)$\mathrm{O}(n^2{m}^3)$, where the size of the text is n×n$n\times n$ and the size of the pattern is m×m$m\times m$. In this paper we present a new algorithm for the problem whose running time is O(n²m²)$\mathrm{O}(n^2{m}^2)$.     

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.     

Permuted function matching

We consider the combination of function and permuted matching, each of which has fast solutions in their own right. Given a pattern p of length m and a text t of length n, a function match at position i of the text is a mapping f from Σp to Σt with the property that f(pj)=ti+j−1 for all j. We show that the problem of determining for each substring of the text, if any permutation of the pattern has a function match is in general NP-Complete. However where the mapping is also injective, so-called parameterised matching, the problem can be solved efficiently in O(nlog|Σp|) time. We then give a 1/2-approximation for a Hamming distance based optimisation variant by reduction to multiple knapsack with colour constraints.     

Matching with don't-cares and a small number of mismatches

In matching with don't-cares and k mismatches we are given a pattern of length m and a text of length n, both of which may contain don't-cares (a symbol that matches all symbols), and the goal is to find all locations in the text that match the pattern with at most k mismatches, where k is a parameter. We present new algorithms that solve this problem using a combination of convolutions and a dynamic programming procedure. We give randomized and deterministic solutions that run in time O(nk²logm) and O(nk³logm), respectively, and are faster than the most efficient extant methods for small values of k. Our deterministic algorithm is the first to obtain an O(polylog(k)⋅nlogm) running time.     

Approximate string matching with address bit errors

A string S∈Σ^m$S\in {\Sigma }^m$ can be viewed as a set of pairs S={(_σi,i):i∈{0,…,m−1}}$S=\{({\sigma }_i,i):i\in \{0,\dots ,m-1\}\}$. We consider approximate pattern matching problems arising from the setting where errors are introduced to the location component (i$i$), rather than the more traditional setting, where errors are introduced into the content itself (_σi${\sigma }_i$). In this paper, we consider the case where bits of i$i$ may be erroneously flipped, either in a consistent or transient manner. We formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution, while introducing some novel techniques.     

Fast exact string matching algorithms

String matching is the problem of finding all the occurrences of a pattern in a text. We propose a very fast new family of string matching algorithms based on hashing q-grams. The new algorithms are the fastest on many cases, in particular, on small size alphabets.     

Faster index for property matching

In this paper, we revisit the Property Matching problem studied by Amir et al. [Property Matching and Weighted Matching, CPM 2006] and present a better indexing scheme for the problem. In particular, the data structure by Amir et al., namely PST, requires O(nlog|Σ|+nloglogn) construction time and O(mlog|Σ|+K) query time, where n and m are the length of, respectively, the text and the pattern, Σ is the alphabet and K is the output size. On the other hand, the construction time of our data structure, namely IDS_PIP, is dominated by the suffix tree construction time and hence is O(n) time for alphabets that are natural numbers from 1 to a polynomial in n and O(nlogσ) time otherwise, where σ=min(n,|Σ|). The query time is same as that of PST. Also, IDS_PIP has the advantage that it can be built on either a suffix tree or a suffix array and additionally, it retains the capability of answering normal pattern matching queries.     

基于Horspool算法的模糊匹配

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

Approximate string matching with suffix automata

Theapproximate string matching problem is, given a text string, a pattern string, and an integerk, to find in the text all approximate occurrences of the pattern. An approximate occurrence means a substring of the text with edit distance at mostk from the pattern. We give a newO(kn) algorithm for this problem, wheren is the length of the text. The algorithm is based on the suffix automaton with failure transitions and on the diagonalwise monotonicity of the edit distance table. Some experiments showing that the algorithm has a small overhead are reported.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^{1.5k –1.5k} ((n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, is the inverse Ackermann function, and 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ) times the weight of a minimum weight complete matching.This research was supported by a fellowship from the Shell Foundation.     

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.     

The labeled perfect matching in bipartite graphs

In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph G=(V,E) with |V|=2n vertices such that E contains a perfect matching (of size n), together with a color (or label) function , the labeled perfect matching problem consists in finding a perfect matching on G that uses a minimum or a maximum number of colors.     

An aggressive algorithm for multiple string matching

A new algorithm based on the Wu-Manber algorithm for multiple string matching is presented in this paper. The algorithm eliminates the functional overlap of the table HASH and SHIFT, and computes the shift distances in an aggressive manner. After each test, the algorithm examines the character next to the scan window to maximize the shift distance. This idea is consistent with that of the quick-search (QS) algorithm. Experimental results on four alphabets show that the new algorithm is more efficient than Wu-Manber and other recent algorithms, particularly on short pattern sets and large alphabet.