Efficient systolic string matching

Megson, Graham M. (1990) Efficient systolic string matching. Electronics Letters, 26 (24). pp. 2040-2042. ISSN 0013-5194

Full text not available from this repository.
Official URL: http://dx.doi.org/10.1049/el:19901316


Two new string matching heuristics are presented which reduce the hardware requirement and improve the computation speed of the systolic string matcher due to Lipton and Lopresti (see 1st International Workshop on Systolic Arrays, Oxford, p.181-91, Adam-Hilger, 1987). The new array requires A=m/2+n/2-1 basic cells, T=m/2+n/2-1+max (m,n) steps to match strings of size n and m, respectively, and has efficiency e=1 (100%). A measure of the heuristic effectiveness compared with the minimum edit distance is also given.

Item Type: Article
Uncontrolled Keywords: Computerised pattern recognition, systolic arrays, minimum edit distance, string matching heuristics, systolic string matching
Subjects: University of Westminster > Science and Technology > Electronics and Computer Science, School of (No longer in use)
Depositing User: Miss Nina Watts
Date Deposited: 27 Jan 2009 10:57
Last Modified: 19 Oct 2009 15:27
URI: http://westminsterresearch.wmin.ac.uk/id/eprint/5702

Actions (login required)

Edit Item (Repository staff only) Edit Item (Repository staff only)