From: Nuralanur@...
Date: 2006-08-02T18:18:55+09:00
Subject: Re: Mini quiz (Was: Detecting similar strings)

-------------------------------1154510328
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit

>You will need to calculate the distance for all values in the field to  
compare it with the user >input, then pick the small distances and display  them 
as options.  As the list of values >grows larger, your app will bog  down.

That's an interesting point: I once used Levenstein distance in a  
self-written typo correcting
program, where I used a list of about  200000 English words as a  reference, 
and tried
to correct words that couldn't be found by suggesting words of small  
Levenstein distance ...
Then it took several minutes to correct a text of 100 pages with quite a  lot 
of typos
in it (I corrected each typo only once for all the document), which was  
nevertheless acceptable for me in that case.
One could speed this up a little bit by excluding some comparison pairs  
right from
the start, because they consist of long and short words which would have  too 
great Levenstein distance anyway....
 
But if you are working on person's names in a database, I doubt that there  
are going to
be that many different names in them... 
 
Best regards,
 
Axel 

-------------------------------1154510328--