Math Is Fun Forum

gnitsuk

Member

Registered: 2006-02-09

Posts: 121

Levenshtein Distance

Hello,

I've recently written code to calculate the Levenshtein distance
between two strings of characters. I further wish to find the a
minimal cost path through the matrix generated.

This page explains fully the cost function - http://www.levenshtein.net/

My approach is to start at the top left cell and move to the bottom right cell by a series of locally minimal-cost moves.

Where there is a choice of equally costly such moves I follow all routes which begin at this branching point. I can discard a branch when its cumulative cost rises above the Levenshtein distance.

Trouble is this can be a very very very slow process.

Is there an efficient algorithm for finding at least ONE minially
costly route through the matrix?

Is there one for finding ALL such routes?

I have implemented a fast approximate algorithm but this can often be quite off from the minimal distance.

I may have read somewhere that this problem is NP hard but I can't re-find that reference. If it is then I'm out of luck.

Thanks for any help.