VLSI architectures for string matching and pattern matching

摘要

In this paper, we discuss string-matching and dynamic time-warp pattern-matching. The string-matching problem arises in a number of applications such as in artificial intelligence, pattern recognition and information retrieval. The method of dynamic time-warping is a well-established technique for time alignment and comparison of speech and image patterns. It has found extensive application in speech recognition and related areas of pattern-matching.We propose a VLSI architecture based on the space-time domain expansion approach which can compute the string distance and also give the matching index-pairs which correspond to the edit sequence. The time complexity is O(max(m, n)) by using m× n processing elements array, where m is the length of the input string and n is the length of the reference string. With a uniprocessor the matching process will have the time complexity O(m × n). If there are p reference strings, using the proposed architecture the string-matching problem can be solved in time O(max(m, n, p)). With a uniprocessor the time complexity will be O(m × n × p). We also propose a VLSI architecture for dynamic time-warping based on the space-time expansion method which can obtain high throughput by using extensive pipelining and parallelism. It can measure the dissimilarity between two patterns in time O(max(m, n, N)). If using a uniprocessor the time complexity will be O(m × n × N), where m and n are the numbers of feature vectors of the unknown input pattern and the reference template respectively, and N is the number of elements of the feature vector. If there are p reference templates, the time complexity will be O(max(m, n, N × p)), and if using a uniprocessor the time complexity will be O(m × n × p × N). The algorithm partition problems are discussed. Verifications of the proposed VLSI architectures are also given. The backtracking procedures are discussed in much detail and their hardware implementations are also given. The proposed architectures can be applied to many areas such as pattern recognition, information retrieval, image processing, speech processing, remote sensing, robotics, computer vision, artificial intelligence and office automata. They are useful to real-time information processing.