From: Axel Etzold <AEtzold@...>
Date: 2008-04-30T17:34:23+09:00
Subject: Re: Levenshtein_distance and recreate the string

Dear all,

maybe what the OP wants is not so much Levenstein distance but
the McIlroy-Hunt longest common subsequence (LCS) algorithm, an algorithm
which not only tells you how far apart two strings are (how
many changes you have to make to get from string A to string B),
but also where they have to be made.
There's a Ruby implementation by Austin Ziegler here:

http://raa.ruby-lang.org/project/diff-lcs/

If you want to know how many strings have Levenstein distance n from 
a given string A, you'll probably have to create all possible
combinations of letters from the alphabet of lengths length(A)-n through length(A)+n, and
throw away those that don't have the correct Levenstein distance.
That's going to be an enormous amount of words in any case ...
Even if only words from a dictionary are allowed, in most
cases, you'll still have many words that are "close" to each other ;-(

Best regards,

Axel 




-- 
Psst! Geheimtipp: Online Games kostenlos spielen bei den GMX Free Games! 
http://games.entertainment.gmx.net/de/entertainment/games/free