Code covered by the BSD License

### Highlights from Find nearest-matching string from a set

4.0
4.0 | 2 ratings Rate this file 19 Downloads (last 30 days) File Size: 2.43 KB File ID: #36981 Version: 1.2

# Find nearest-matching string from a set

### Brandon Kuczenski (view profile)

04 Jun 2012 (Updated )

Computes shortest distance between a key string and a set of strings to find the nearest match.

File Information
Description

Uses a modified Vagner-Fischer algorithm to find the Levenshtein distance between each pair of strings. Progressively narrows the threshold to equal the distance of the best match found so far, reducing run time.

Updated to correct the algorithm. (sorry!)

Optional behaviors include an upper-bound threshold distance, detect first or multiple matches of equal distance, case insensitivity.

Examples:

>> [i,d]=strnearest({'first string'},{'string 2','abcdefgh','FURSrtd','firststring'})

i =

[4]

d =

2

>> [i,d]=strnearest({'1','first string'},{'string 2','abcdefgh','1st string','FURSrtd','seconaaad string','2'})

i =

[6] [3]

d =

1 5

>>

Acknowledgements

Calculation Of Distance Between Strings inspired this file.

Required Products MATLAB
MATLAB release MATLAB 7.13 (R2011b)
03 May 2014 Yung-Yeh

### Yung-Yeh (view profile)

Oh...I see

It's actually the Levenshtein distance. The title "nearest-matching string" really confuses me.

03 May 2014 Yung-Yeh

### Yung-Yeh (view profile)

This is weird, I tried

[x,d] = strnearest('ABC',{'""','"ABC"'})

but it return
x = [1 2]
d = 3

16 Aug 2013 Brandon Kuczenski

### Brandon Kuczenski (view profile)

apologies- I have uploaded a corrected submission.

@@ -98,13 +98,16 @@
else
bb=list{T};
end
- luma=numel(key); lima=numel(bb);
- dl=dist*ones([luma+1,lima+1]);
- dl(1,:)=0:lima; dl(:,1)=0:luma;
+ eql=char({key;bb}); % equal length
+ luma=numel(keyy);
+ dl=dist*ones([luma+1,luma+1]);
+ dl(1,:)=0:luma; dl(:,1)=0:luma;
%Distance
for i=1:luma
- for j=max([1,i-dist]):min([lima,i+dist])
- kr=krk*(~(key(j)==bb(i)));
+ for j=max([1,i-dist]):min([luma,i+dist])
+ kr=krk*(~(keyy(min([j luma]))==bb(i)));
dl(i+1,j+1)=min([dl(i,j)+kr,dl(i,j+1)+1,dl(i+1,j)+1]);
end
end

Comment only
16 Aug 2013 lala

### lala (view profile)

Still no working example? :)

Comment only
10 Sep 2012 Sven

### Sven (view profile)

>> [index,distance] = strnearest({'first string'},{'string 2'})

index =

[1]

distance =

0

Perhaps a working example would be useful.

Comment only