Re: Minimum levenshtein distance for a set of words


weinzier wrote:
|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'm guessing that by "minimum distance" you mean the
minimum of the maximum distance from s to one of the
given strings.

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

The most famous reference, perhaps, is _Time Warps, String Edits,
and Macromolecules: The Theory and Practice of Sequence Comparison_,
David Sankoff and Joseph Kruskal eds.

The algorithm in there that perhaps comes closest to doing
the job is one that would give you the string having the
smallest *total* distance to the given strings. It doesn't
take much of a modification to get the string having the
smallest weighted sum of distances to the given strings.
There's a tweak for getting all the possible strings achieving
the minimum, just as it's possible to generate all the
sequences of insertions and deletions that achieve the minimum--
although the number can of course increase quickly.

The algorithm solves the problem for each set of strings
that you can get by taking an initial segment of each of
the original strings respectively. Consequently the time
required grows quickly with the number of strings. I don't
suppose that anybody knows of any terribly efficient
algorithm known for the problems, although this is better
than a more naive brute-force approach.

Then I suppose by adjusting the weights you could find the
one having the smallest maximum distance. I'm afraid that
although this auxiliary problem sounds familiar (a little
bit like linear programming), I don't happen to know
a good algorithm for it. Surely some procedure where you
increase the weights on the distances that are greatest
for the optimum solution you can get to the minimax.

Keith Ramsay

.

Quantcast