🚀 go-pugleaf

Approximate String Matching".


DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

DATA STRUCTURING SEMINAR

                    -Monday, April 24, 1989

Mr.  Esko  Ukonnen of University of Helsinki will speak
on "Efficient Approximate String Matching".

TIME:                 3:30 PM

ROOM:              DC 1302

ABSTRACT

We discuss recent advances in sequential algorithms for
computing the edit distance between two strings and for
finding   approximate  occurrences  of  a  string  (the
pattern) in another string (the text).  Such algorithms
can  be  based  on  a  very  simple dynamic programming
method  with  running  time O(mn) where m and n are the
lengths  of  the  two strings compared. The emphasis of
the talk is on different ideas of speeding up the basic
dynamic programming. The resulting algorithms include a
method for the edit distance problem with the desirable
property  of being the faster the smaller is the actual
distance.  For  the approximate string pattern matching
problem  we obtain various O(kn) methods where n is the
length  of  the  text  and  k  is  the maximum distance
allowed in a match.