Narrow Results

Vector algorithms allow the computation of an output vector r = r₁ r₂ ⋯ r_m given an input vector e = e₁ e₂ ⋯ e_m in a bounded number of operations, independent of m the length of the vectors. The allowable operations are usually restricted to bit-wise operations available in processors, including shifts and binary addition with carry. These restrictions imple that the existence of a vector algorithm for a particular problem opens the way to extremely fast implementations, using the inherent parallelism of bit-wise operations.

This paper presents general results on the existence and construction of vertor algorithms, with a particular focus on problems arising from computational biology. We show that efficient vector algorithms exist for the problem of approximate string matching with arbitrary weighted distances, generalizing a previous result by G. Myers. We also characterize a class of automata for which vector algorithms can be automatically derived from the transition table of the automata.

The factor oracle is a relatively new data structure for the set of factors of a string. It has been introduced by Allauzen, Crochemore, and Raffinot in 1999. It may recognize non-factors (hence the name "oracle") but its implementational simplicity and experimental behaviour are stunning; factor oracle based string matching has been conjectured optimal on average. However, its structure is not well understood. We take important steps in clarifying its structure by explaining how it can be obtained as a quotient of the trie of the set of factors. When seen this way, all known properties of the factor oracle become simple observations. Also, we introduce a framework where various oracles can be compared. The factor oracle is better than several natural ones obtained from the trie of the set of factors, the suffix and the factor automata, respectively.

In this article we present two efficient variants of the BOM string matching algorithm which are more efficient and flexible than the original algorithm. We also present bit-parallel versions of them obtaining an efficient variant of the BNDM algorithm. Then we compare the newly presented algorithms with some of the most recent and effective string matching algorithms. It turns out that the new proposed variants are very flexible and achieve very good results, especially in the case of large alphabets.

We study the problem of finding all maximal approximate gapped palindromes in a string. More specifically, given a string S of length n, a parameter q ≥ 0 and a threshold k > 0, the problem is to identify all substrings in S of the form uvw such that (1) the Levenshtein distance between u^r and w is at most k, where u^r is the reverse of u and (2) v is a string of length q. The best previous work requires O(k²n) time. In this paper, we propose an O(kn)-time algorithm for this problem by utilizing an incremental string comparison technique. It turns out that the core technique actually solves a more general incremental string comparison problem that allows the insertion, deletion, and substitution of multiple symbols.

Full-text index structures are widely used in string matching and bioinformatics. These structures such as DAWGs and suffix trees allow fast searches on texts. In this paper, we present a new partition of the factors of a word, called a consistent minimal linear partition. Based on this partition, we introduce the weighted directed word graph (WDWG), a space-economical full-text index. WDWGs are basically cyclic, which means that they may accept infinite strings. But by assigning weights to edges, the acceptable strings are limited only to the factors of the input string. For a given word w, any factor of w can be indexed by a state of the WDWG and its length. A WDWG of w has at most |w| states and 2|w| - 1 transition edges. We present an on-line algorithm to construct a WDWG for a given word in time linear in the length of the word. Our experiment shows the size of WDWGs is smaller than that of DAWGs for many data sets including DNA sequences, Chinese texts and English texts.

In this paper we propose an efficient approach to the compressed string matching problem on Huffman encoded texts, based on the BOYER-MOORE strategy. Once a candidate valid shift has been located, a subsequent verification phase checks whether the shift is codeword aligned by taking advantage of the skeleton tree data structure. Our approach leads to algorithms that exhibit a sublinear behavior on the average, as shown by extensive experimentation.

We give faster methods to compute discrete convolutions. We assume that all the inputs are packed, that is, strings are packed into words such that each word is packed with $\begin{array}{l}\alpha =\lfloor \omega /{\log }_2\left|\Sigma \right|\rfloor \\ \end{array}$ characters, where w is the length of a machine word and ∑ is the alphabet. The output of our methods is also packed, that is, each word of the output contains more than one element of the result. The approach is based on the word-level parallelism and the FFT. Given two strings with m and n ( n ≥ m ) characters that are packed into $\lceil m/\alpha \rceil$ and $\lceil n/\alpha \rceil$ words respectively, the convolution of them can be computed in $O\left(\frac{nu}{w}\log \frac{mu}{w}\right)$ time, where $u=\left(\lceil {\log }_{\left|\Sigma \right|}m\rceil +2\right){\log }_2\left|\Sigma \right|$ by the FFT. Experiments show that our method is three times faster than the convolution using the standard trick.

We consider the problem of pattern matching with wildcards on packed strings. It finds all the occurrences of a pattern in a text, both of which may contain wildcards. By the convolution of packed strings, we present algorithms that are faster than the previous $O(n\log m)$-time algorithm, where m is the length of the pattern and n the length of the text. The algorithm runs in $O\left(\frac{nu}{w}\log \frac{mu}{w}+\frac{n\log \left|\Sigma \right|}{w}{\log }^{1+o(1)}\log \left|\Sigma \right|+\frac{m\log \left|\Sigma \right|}{w}\log \frac{w}{\log \left|\Sigma \right|}+occ\right)$ time, where occ is the number of occurrences of the pattern in the input. Experiments show that the method is faster than the bit-parallel wildcard matching algorithm for long patterns.

Glushkov automaton is an efficient structure for matching regular expressions. We present an $O(k{2}^k)$ bits space representation of Glushkov automata of regular expressions, where $k$ is the number of strings in the regular expression. The state transition runs in time $O(\lceil m/w\rceil logk)$, where $w$ is the size of machine words, and $m$ is the number of states in the Glushkov automaton. For $k\le 4m/(\sqrt{8w+9}-1)$, the time is $O(\lceil m/w\rceil )$. Our approach is based on two operations on words that retrieve and set bits on a specific set of positions of a word. We present implementations of these operations using bit-parallelism and a permutation network, which are simple and efficient.

Given large number of words to be recognized, a two-stage strategy for eliminating unlikely candidates before recognition can be a reasonable and powerful approach for increasing the recognition speed. A holistic lexicon reduction technique for offline handwritten Arabic word recognition is proposed in this paper. The principle of this technique involves the extraction of dots and subwords from the cursive Arabic word image to describe its shape. In the first stage of reduction, the number of subwords in the input word is estimated. Then in the second stage, the word descriptor, based on the dots information, is used while taking into account only the candidates selected in the first stage. Experimental results on IFN/ENIT database, consisting of 26,459 cursive Arabic word images, show a lexicon reduction of 92.5% with accuracy of 74%.

This paper presents an efficient IrisCode classifier, built from phase features which uses AdaBoost for the selection of Gabor wavelets bandwidths. The final iris classifier consists of a weighted contribution of weak classifiers. As weak classifiers we use three-split decision trees that identify a candidate based on the Levenshtein distance between phase vectors of the respective iris images. Our experiments show that the Levenshtein distance has better discrimination in comparing IrisCodes than the Hamming distance. Our process also differs from existing methods because the wavelengths of the Gabor filters used, and their final weights in the decision function, are chosen from the robust final classifier, instead of being fixed and/or limited by the programmer, thus yielding higher iris recognition rates. A pyramidal strategy for cascading filters with increasing complexity makes the system suitable for real-time operation. We have designed a processor array to accelerate the computation of the Levenshtein distance. The processing elements are simple basic cells, interconnected by relatively short paths, which makes it suitable for a VLSI implementation.

Multi-string matching (MSM) is a core technique searching a text string for all occurrences of some string patterns. It is widely used in many applications. However, as the number of string patterns increases, most of the existing algorithms suffer from two issues: the long matching time, and the high memory consumption. To address these issues, in this paper, a fast matching engine is proposed for large-scale string matching problems. Our engine includes a filter module and a verification module. The filter module is based on several bitmaps which are responsible for quickly filtering out the invalid positions in the text, while for each potential matched position, the verification module confirms true pattern occurrence. In particular, we design a compact data structure called Adaptive Matching Tree (AMT) for the verification module, in which each tree node only saves some pattern fragments of the whole pattern set and the inner structure of each tree node is chosen adaptively according to the features of the corresponding pattern fragments. This makes the engine time and space efficient. The experiments indicate that, our matching engine performs better than the compared algorithms, especially for large pattern sets.

In this paper, we discuss how rule based expert system shells can be used in pattern recognition for the implementation of algorithms which are procedurally oriented in their nature rather than rule based, and have traditionally been implemented in procedural programming languages. Particular examples include finite state automata, context free parsing, string matching, graph matching and discrete relaxation.

Advances in VLSI technology make it possible to realize systems of very high complexity in a small volume of hardware using integration. In many application fields, it is necessary to implement certain algorithms, or even complete information processing systems, directly in silicon. Application domains which are likely to benefit are in the fields of signal processing and scientific computing.

In this paper, we consider several steps which we believe to be essential in the design path of a special purpose architecture, and we present methodologies for achieving design requirements. These solutions are based on experience gathered in the Parallel VLSI Architecture group of IRISA.

The recognition of patterns is an important task in robot and computer vision. The patterns themselves could be one- or two-dimensional, depending upon the application. Pattern matching is a computationally intensive and time consuming operation. The design of special purpose hardware could speed up the matching task considerably, making real-time responses possible. Advances in parallel processing and VLSI technologies have made it possible to implement inexpensive, efficient and very fast custom designs. Many approaches and solutions have been proposed in the literature for hardware implementations of pattern matching techniques. In this paper, we present a detailed overview of some of the important contributions in the area of hardware algorithms and architectures for pattern matching.

When optical character recognition (OCR) devices process the same page image, they generate similar text strings. Differences are due to recognition errors. A page of text rarely contains long repeated substrings; therefore, N strings generated by OCR devices can be quickly matched by detecting long common substrings. An algorithm for matching an arbitrary number of strings based on this principle is presented. Although its worst-case performance is O(Nn²), its performance in practice has been observed to be O(Nn log n), where n is the length of a string. This algorithm has been successfully used to study OCR errors, to determine the accuracy of OCR devices, and to implement a voting algorithm.

The recognition of polygons in 3-D space is an important task in robot vision. Advances in VLSI technology have now made it possible to implement inexpensive, efficient and very fast custom designs. The authors have earlier proposed a class of VLSI architectures for this computationally intensive task, which makes use of a set of local shape descriptors for polygons which are invariant under affine transformations, i.e. translation, scaling, rotation and orthographic projection from 3-D to any 2-D plane. This paper discusses the design and implementation of PMAC, a prototype for polygon matching, as a custom CMOS VLSI chip. The recognition procedure is based on the matching of edge-length ratios using a simplified version of the dynamic programming procedure commonly employed for string matching. The matching procedure also copes with partial occlusions of polygons. The implemented architecture is systolic and fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput.

This paper explores an efficient technique for the extraction of common subtrees in decision trees. The method is based on a Suffix Tree string matching process and the algorithm is applied to the problem of finding common decision rules in path planning.

Light-weight network gateways often employ a cost-effective embedded network processor and have received a strong demand for empowering content filtering services. In this regard, we were motivated to propose a specialized cache, fuzzy-updated cache automata matching (FCAM) circuit for accelerating the embedded network processors. Although automata matching algorithms are robust with deterministic matching time, there is still plenty of room for improving its average-case performance. The proposed FCAM employs cache to accelerate the root state and nonroot state with the multiple characters matching, and applies the fuzzy decision to improve the cache performance. In our experiment, the FPGA implementation of FCAM can perform at the rate of 10.5 Giga bits per second with the patterns of 25,642 bytes. This performance is superior to previous matching hardware in terms of throughput and pattern set.

The recognition of polygons in 3-D space is an important task in robot vision. Advances in VLSI technology have now made it possible to implement inexpensive, efficient and very fast custom designs. The authors have earlier proposed a class of VLSI architectures for this computationally intensive task, which makes use of a set of local shape descriptors for polygons which are invariant under affine transformations, i.e. translation, scaling, rotation and orthographic projection from 3-D to any 2-D plane. This paper discusses the design and implementation of PMAC, a prototype for polygon matching, as a custom CMOS VLSI chip. The recognition procedure is based on the matching of edge-length ratios using a simplified version of the dynamic programming procedure commonly employed for string matching. The matching procedure also copes with partial occlusions of polygons. The implemented architecture is systolic and fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput.

When optical character recognition (OCR) devices process the same page image, they generate similar text strings. Differences are due to recognition errors. A page of text rarely contains long repeated substrings; therefore, N strings generated by OCR devices can be quickly matched by detecting long common substrings. An algorithm for matching an arbitrary number of strings based on this principle is presented. Although its worst-case performance is O(Nn²), its performance in practice has been observed to be O(Nn log n), where n is the length of a string. This algorithm has been successfully used to study OCR errors, to determine the accuracy of OCR devices, and to implement a voting algorithm.