CODEWITHSUNDEEP
stringlevenshtein-distanceedit-distance
Anirvana
Anirvana

Reputation: 29

Edit distance with varying dictionaries

My question is similar to Algorithm to transform one word to another through valid words

But with is a major difference. I have one fixed word say "JAMES" and varying dictionaries as i/p. Ofcourse, I can't preprocess dictionary now.

So I have to find the minimum cost for processing "JAMES" to "JOHNY" with different dictionaries as input.

Is there anyway I could preprocess the word "JAMES" so that I need to perform minimum number of edit distance calculations at run time? What do you guys suggest?

Upvotes: 1

Views: 1400

Answers (2)

roshaz
roshaz

Reputation: 26

I am assuming the rules are similar to the question you cited i.e. only single edit is allowed at a time, and each intermediate word should be present in the given dictionary.

  1. Create single edit versions of source string to destination string. for eg: JOMES JAHES JAMNS JAMEY

Recurse for each of these words and keep creating nodes for every unique word. Just create edges if the node is already is created. This completes the preprocessing.

Now given a dictionary, find all the first level words in dictionary. For all matches, further find all the second level words and so on, till you reach destination word.

Upvotes: 1

Tony Delroy
Tony Delroy

Reputation: 106096

First, you need to properly define your rules - is an "edit" allowed to add or delete multiple characters, substitute one character etc.?

Anyway - I'd just start with the obvious - create a graph where each word links to all those it can be directly edited into. Then, use recursion with a depth limit, marking visited elements as "dirty" to avoid cycles, then see if there's a one-edit solution, two-edit solution etc. until you find a solution or all paths are dirty at that depth. (If you record the depth being attempted in the "dirty" member, you don't have to worry about cleaning them out each time you increment the depth limit. You could also mark all-dirty sub-trees to avoid recursing into them again.)

Upvotes: 0

Related Questions