Here's the trick: if you want to find the Levenshtein edit-sequence that leads from one string to another (or, you think, you just want to know which operation occurs at which position in either string), create the complete cost-table, then start at the terminal position and walk backward to the beginning. It's impossible to walk forward from the beginning, because there's too much ambiguity as to which direction the next `step' should take through the maze, but it's actually easy to walk backward: one merely needs to find the direction that either preserves the cost or decrements it by one, with preference given first to cost-decrement and then to diagonal movement (because diagonal cost-preservation is a `keep' operation, and diagonal cost-decrement is a `substitute' operation; horizontal and vertical movement are either insertion or deletion, depending on which string is the source and which is the destination). [Reply] |
![[@]](/icons/VisualIDs/levenshtein-edit-sequences.png){kind=icon}