Code covered by the BSD License  

Highlights from
Find nearest-matching string from a set

Be the first to rate this file! 24 Downloads (last 30 days) File Size: 2.43 KB File ID: #36981

Find nearest-matching string from a set



04 Jun 2012 (Updated )

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

| Watch this File

File Information

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.


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

i =


d =


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

i =

    [6] [3]

d =

     1 5



Calculation Of Distance Between Strings inspired this file.

Required Products MATLAB
MATLAB release MATLAB 7.13 (R2011b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (3)
16 Aug 2013 Brandon Kuczenski

apologies- I have uploaded a corrected submission.

@@ -98,13 +98,16 @@
- 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
+ keyy=eql(1,:); % space-padded key
+ bb=eql(2,:); % space-padded candidate
+ luma=numel(keyy);
+ dl=dist*ones([luma+1,luma+1]);
+ dl(1,:)=0:luma; dl(:,1)=0:luma;
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)));

16 Aug 2013 lala

Still no working example? :)

10 Sep 2012 Sven

Was this tested?

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

index =


distance =


Perhaps a working example would be useful.

26 Jun 2012

Add link to strdist.m

19 Aug 2013

Updated to correct an error in the code and to add working examples to the description.

Contact us