Fast string matching algorithms for run-length coded strings

Given a run-length coded text of length 2n and a run-length coded pattern of length 2m,m?n commonly, this paper first presents anO(n+m) time sequential algorithm for string matching, then presents anO(1) time parallel algorithm on a two-dimensionalm×n mesh with a reconfigurable bus system.     

Vectorizations of randomized matching for run-length coded strings

Matching run-length coded strings (RLCSs) is very important in the field of pattern recognition. This paper considers the design of vectorized matching algorithms that operate directly on RLCSs. We first modify the algorithm of Karp and Rabin (1987) to design a linear-time randomized matching algorithm for RLCSs. Following this algorithm, two new and fast vectorized algorithms are presented. The first one is off-line and the second one is on-line. Some experiments are carried out on a CRAY X-MP EA/ 116se vector supercomputer to demonstrate the good performance of our vectorized algorithms.     

新的自适应多串匹配算法

在不同关键词规模、最短关键词长度和字符集大小等情况下,有效的多串匹配算法是不同的。新提出的自适应多串匹配算法（Adapted Multiple Strings Matching Algorithm,AMSM）改善了SBOM算法中Oracle树存在不精确跳跃计算的缺点,同时采用了WuManber算法的块跳跃策略和压缩形式的Oracle树比较策略,提高了算法的性能,可适用于各种情况,是一种通用多串（多模式）匹配算法。     

Edit distance of run-length encoded strings

Let X and Y be two run-length encoded strings, of encoded lengths k and l, respectively. We present a simple O(|X|l+|Y|k) time algorithm that computes their edit distance.     

Distinct squares in run-length encoded strings

Squares are strings of the form ww where w is any nonempty string. Two squares ww and w^′w^′ are of different types if and only if w≠w^′. Fraenkel and Simpson [Avieri S. Fraenkel, Jamie Simpson, How many squares can a string contain? Journal of Combinatorial Theory, Series A 82 (1998) 112-120] proved that the number of square types contained in a string of length n is bounded by O(n). The set of all different square types contained in a string is called the vocabulary of the string. If a square can be obtained by a series of successive right-rotations from another square, then we say the latter covers the former. A square is called a c-square if no square with a smaller index can cover it and it is not a trivial square. The set containing all c-squares is called the covering set. Note that every string has a unique covering set. Furthermore, the vocabulary of the covering set are called c-vocabulary. In this paper, we prove that the cardinality of c-vocabulary in a string is less than , where N is the number of runs in this string.     

A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively, be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl+min{p₁,p₂}) time, where p₁ and p₂ denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl,km}) and outperforms the time bounds O(kllogkl) or O((k+l+q)log(k+l+q)) for some cases, where q denotes the number of matched blocks.     

An efficient algorithm for matching multiple patterns

An efficient algorithm for performing multiple pattern match in a string is described. The match algorithm combines the concept of deterministic finite state automata (DFSA) and the Boyer-Moore algorithm to achieve better performance. Experimental results indicate that in the average case, the algorithm is able to perform pattern match operations sublinearly, i.e. it does not need to inspect every character of the string to perform pattern match operations. The analysis shows that the number of characters to be inspected decreases as the length of patterns increases, and increases slightly as the total number of patterns increases. To match an eight-character pattern in an English string using the algorithm, only about 17% of all characters of the strong and 33% of all characters of the string, when the number of patterns is seven, are inspected. In an actual testing, the algorithm running on SUN 3/160 takes only 3.7 s to search seven eight-character patterns in a 1.4-Mbyte English text file     

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.     

An improved parallel algorithm for maximal matching

A parallel O(log³ vbEvb) algorithm for finding a maximal matching in a graph G(V, E) is presented. The model of computation is the CRCW-PRAM, and vbVvb + vbEvb processors are used.This algorithm is a substantial improvement upon the two previous algorithms known to us. These algorithms by Karp and Wigderson (1984) and Lev (1980) achieve O(log⁴ vbEvb) depth with vbEvb³/log vbEvb and vbEvb + vbVvb processors respectively. The last one though having a better performance than the first, only applies to bipartite graphs.     

An algorithm for optimal free-form object matching

A novel method of matching for 3-D free-form objects (points vs. surface and surface vs. surface) is proposed. The method formulates the problem in terms of solution of a non-linear polynomial equation system, which can be solved robustly by the Interval Projected Polyhedron (IPP) algorithm. Two intrinsic surface properties, the Gaussian and the mean curvatures, are used as object features for matching. The related iso-curvature lines are used to establish the correspondence between two objects. The intersection points of these iso-curvature lines are calculated and sorted out to satisfy the Euclidean constraints from which the translation and rotation transformations are estimated. The performance of the proposed algorithm is also analyzed. This approach can cover global and partial matching, and be applied to automated inspection, copyright protection of NURBS models, and object recognition. Examples illustrate our technique.     

An adaptive resolution hybrid binary-real coded genetic algorithm

In genetic algorithms (GAs), is it better to use binary encoding schemes or floating point encoding schemes? In this article, we try to tackle this controversial question by proposing a novel algorithm that divides the computational power between two cooperative versions of GAs. These are a binary-coded GA (bGA) and a real-coded GA (rGA). The evolutionary search is primarily led by the bGA, which identifies promising regions in the search space, while the rGA increases the quality of the solutions obtained by conducting an exhaustive search throughout these regions. The resolution factor (R), which has a value that is increasingly adapted during the search, controls the interactions between the two versions. We conducted comparison experiments employing a typical benchmark function to prove the feasibility of the algorithm under the critical scenarios of increasing problem dimensions and decreasing precision power.     

基于对角线行程的直线生成算法研究

提出了一种基于对角线行程的直线生成算法。针对现有基于行程模式的直线生成算法在直线斜率大于1/2时效率极剧下降的问题,提出将在同一45°对角线上的连续点亮的像素点个数作为行程计算。算法详细分析了决定对角线行程长度的所有因素,对于满足一定条件的特殊直线,算法不需要进行偏差判断,可直接生成整条直线;对普通直线,仅使用一次加法运算和判零运算即可得到对角线行程长度,改善了行程算法的效率,弥补了直线行程算法长期以来存在的缺点。     

An improved hexahedral mesh matching algorithm

Mesh matching is an effective way to convert the non-conforming interfaces between two hexahedral meshes into conforming ones, which is very important for achieving high-quality finite element analysis. However, the existing mesh matching algorithm is neither efficient nor effective enough to handle complex interfaces and self-intersecting sheets. In this paper, the algorithm is improved in three aspects: (1) by introducing a more precise criteria for chord matching and the concept of partition chord set, complex interfaces with internal loops can be handled more effectively; (2) by proposing a new solution, self-intersecting sheet can be inflated and extracted locally; and (3) by putting forward a mesh quality evaluation method, the sheet extraction operation during mesh matching can be done more efficiently. Our improved mesh matching algorithm is fully automatic, and its effectiveness is demonstrated by several examples in different matching situations.     

Fast template matching algorithm for contour images based on its chain coded description applied for human face identification

A new matching algorithm for contour images described by chain coded expression is presented. In our face authentication system, the isodensity contours has been introduced to differentiate between the facial features. These isodensity contours can be transformed into chain codes. By using these coded isodensity contours, remarkable improvement in the processing performance can be expected in terms of the processing time and memory requirements.From the computer simulation performed using images of 50 people, it turned out clear that the processing time was decreased to approximately one-seventh compared to the conventional method. With respect to memory requirement, it was reduced to a quarter.     

A new chain-coding algorithm for binary images using run-length codes

This paper presents a new algorithm for converting a binary image into chain codes using its run-length codes. The basic idea of conventional chain-coding algorithm is to follow boundary pixels by convolving a 3 × 3 window with the image and to sequentially generate chain codes. The proposed algorithm has two phases, namely run-length coding and chain-code generation. We use connectivity information between runs as well as their coordinates in the phase of run-length coding. In the second phase (chain-code generation) the connectivity information extracted in the first phase is utilized for sequentially tracking runs containing the boundary pixels to be followed. This algorithm has an advantage that we can detect easily the inclusion relationship between boundaries at the same time as chain-code generation.     

An asymmetric fingerprint matching algorithm for Java Card TM

We propose a light-weight fingerprint matching algorithm that can be executed inside the devices with a limited computational power. The algorithm is based on the minutiae local structures (the “neighborhoods”), that are invariant with respect to global transformations like translation and rotation. The match algorithm has been implemented inside a smartcard over the Java Card^TM platform, meeting the individual’s need for information privacy and overall authentication procedure security. The main characteristic of the algorithm is to have an asymmetric behavior, in respect to the execution time, between correct positive and negative matches. The performances in terms of authentication reliability and speed were tested on some databases from the Fingerprint Verification Competition 2002 and 2004 editions (FVC2002 and FVC2004). Moreover, our procedure showed better reliability when compared with a related algorithm on the same database. We can achieve a false acceptance rate (FAR) of 0.1%, a false rejection rate of about 6%, and from 0.3 to 8 s to match most of the finger pairs during the FAR tests.     

一种面向入侵检测系统的模式匹配算法的改进

分析引擎是入侵检测系统的核心部分,一个好的模式匹配算法直接决定了入侵检测系统分析引擎的效率。本文对几种经典的模式匹配算法如:BM算法,BMH算法以及BMHS算法等经典算法进行了研究和分析,比较了几种算法的优劣。最后在BMHS算法的基础上提出一种改进的算法,该算法可以有效提高入侵检测系统的检测速度。     

An adaptive block-based matching algorithm for crowd motion sequences

For crowd analytics and surveillance systems, motion estimation is an essential first step. Lots of crowd motion estimation algorithms have been presented in the last years comprising pedestrian motion. However, algorithms based on optical flow and background subtraction have numerous limitations such as the complexity of the computation in the presence of high dense crowd and sudden motion changes. Therefore, a novel estimation algorithm is proposed to measure the motion of crowd with less computational complexity and satisfy the real time requirements. The proposed algorithm is based on block-based matching, particle advection, and social force model. By the block-based matching, the motion is estimated in each frame, and the corresponding motion field is created. The particle advection process provides more information about the behavior of pedestrians groups, their tracked trajectories and the boundary of each group segment. Relying on the social force model, a predicted direction of the motion vectors (MV) could be measured significantly. Subsequently, the block-based technique is combined with the social force model to obtain the accurate motion vector with the less possible number of search points. The experimental results indicate that the proposed method achieves high performance by reducing the search points, particularly when many collision situations or obstacles exist in the scenes. Considering the reduction in the computational complexity, the quality of degradation is very low. In all cases, average PSNR degradation of the proposed algorithm is only 0.09.     

Disjoint pattern matching and implication in strings

We deal with the problem of deciding whether a given set of string patterns implies the presence of a fixed pattern. While checking whether a set of patterns occurs in a string is solvable in polynomial time, this implication problem is well known to be intractable. Here we consider a version of the problem when patterns in the set are required to be disjoint. We show that for such a version of the problem the situation is reversed: checking whether a set of patterns occurs in a string is NP-complete, but the implication problem is solvable in polynomial time.     

Indexing and matching multiple-attribute strings for efficient multimedia query processing

Multimedia data can be represented as a multiple-attribute string of feature values corresponding to multiple features of the data. Therefore, the retrieval problem can be transformed into the q-attribute string matching problem if q features are considered in a query. A general solution is proposed in this paper. It includes an index structure and the matching methodologies, which can be applied on different values of q. The experiment results show the efficiency of the proposed approach.