# Maximum Edit Distance code

8 views (last 30 days)

Show older comments

##### 0 Comments

### Answers (1)

Stephen23
on 8 Aug 2018

Edited: Stephen23
on 8 Aug 2018

The maximum edit distance between any two strings (even two identical ones) is infinity, unless you add some kind of restrictions on repetitions of edits. Even then you can create an arbitrarily large edit distance, with any arbitrarily large set character set. So unless you have some other restrictions the maximum edit distance is not likely to be very useful.

>> C = {'live','eve','believe','belive'};

>> cellfun(@(c)wfEdits(c,'beleive'),C)

ans =

3 4 2 1

Thus showing that 'belive' is the closest to 'beleive'. The function is:

function d = wfEdits(S1,S2)

% Wagner–Fischer algorithm to calculate the edit distance / Levenshtein distance.

%

N1 = 1+numel(S1);

N2 = 1+numel(S2);

%

D = zeros(N1,N2);

D(:,1) = 0:N1-1;

D(1,:) = 0:N2-1;

%

for r = 2:N1

for c = 2:N2

D(r,c) = min([D(r-1,c)+1, D(r,c-1)+1, D(r-1,c-1)+~strcmpi(S1(r-1),S2(c-1))]);

end

end

d = D(end);

%

end

If you are interested in the different possible direct edit paths (i.e. without repetition or unnecessary diversion to other characters) then you should investigate the Needleman–Wunsch algorithm.

##### 3 Comments

Stephen23
on 13 Aug 2018

Edited: Stephen23
on 13 Aug 2018

"In my situation I need the opposite, I need to choose from these suggests the answer with the highest edit number."

You need to be more specific than this, because currently this could be solved by several different interpretations. Are intermediate characters allowed (e.g. 'a' -> 'b' -> 'c')? Can edits be repeatedly applied (i.e. 'a' -> 'b' -> 'a' etc.)? Even without any intermediate characters and no edit repetitions, this still has a trivial solution:

- delete all of the first string
- add all of the second string

giving an edit distance of numel(str1)+numel(str2). If that is not what you want then you need to define your problem better.

Perhaps the Needleman–Wunsch algorithm might do what you want, once to you adjust the scoring values to suit your problem requirements.

Clearly you will have to do some experimentation yourself, e.g. trying different scoring schemes, and learn up about this algorithm and how it works. Before using nwalign (or perhaps something from FEX) you could try this on one of the several online Needleman–Wunsch tools, which graphically show the path (these are easy to find with an internet search). Keep experimenting!

### See Also

### Categories

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!