Re: Minimum levenshtein distance for a set of words

> >Is there a unique word which minimizes the levenshtein distance to any
> >of the elements of a given set of words?
>
> Clearly not. Consider the set {'ab', 'ac'}; there is more than
> one word that gives this minimum.

That is correct. Two solutions...mhh
In my considerations I forgot about replacements, clearly my fault.

So lets make replacements more expensive than inserts and deletions and
consider the set {'aa', 'abcd', 'acfg'}.
What is the word which minimizes levenshtein distance then?
It isn't in the set {'aa', 'abcd', 'acfg'} since 'a' has a lower
distance to all members of the set than any member of the set itself.

> >Where can i find an algorithm?
> >
> >Any hints on links and literature are welcome...
>
> About five minutes ago I had no idea what the "levenshtein distance"
> was. I tried
>
> www.google.com

Yes, I also have heard about that google thingy;-)

But seriously, I was not looking for an implementation of the
levenshtein algorithm.
What I am looking for is an algorithm which takes
- set of words
- costs for insert, delete, replace
and gives
- minimum levenshtein distance
- tells me how many words have this distance (one, many, infinite)
- set of all words which have the minimum distance if finite


I am sure there is literature about this out there.
Again any hints welcome...

Ludwig Weinzierl

.