Fuzzy string matching?

[John Machin]

On 26 Aug 99, at 21:31, Magnus L. Hetland wrote:

> mlh at idt.ntnu.no (Magnus L. Hetland) writes:
> 
> > "Hans Nowak" <hnowak at cuci.nl> writes:
> > 
> > > ...Anyone know of such a beast in Python?
> [...]
> > Other than that - fuzzy matching is a non-trivial problem. It is
> > possible to use dynamic programming to make a quadratic time distance
> > function that you can use to compare words or strings - to see how
> > similar they are. (If you like, I can post a Python variant of it.)
> 
> I decided not to wait for your answer... :)
> 
> def distance(a,b):
> [[ SNIP ]]

> 
> (And if anyone wants an explanation as to how this distance function
> really works, I'll be glad to supply it... I've done lectures about it
> in an algorithm class - and will be doing so later this fall as well...)

Magnus,
One presumes that your first assignment for your students is to go to 
the library and/or think a little and come back with the well-known 
O(min(m,n)) instead of O(mn) space requirement optimisation to the 
algorithm you presented and therefore you would prefer not to have it 
posted to this list, just in case they read it. Oh and for what it's 
worth, although the time is still O(mn), it decreases --- I have yet to 
see a language where foo[i,j] takes no more time than bar[j]. Python, 
with foo being a dictionary and bar being a list, is definitely not 
such a language.
Cheers,
John