File Exchange

image thumbnail

Find nearest-matching string from a set

version 1.2 (2.43 KB) by

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

10 Downloads

Updated

View License

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

>>

Comments and Ratings (5)

Yung-Yeh

Oh...I see

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

Yung-Yeh

This is weird, I tried

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

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

Brandon Kuczenski

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
+ 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;
     %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

lala

lala (view profile)

Still no working example? :)

Sven

Sven (view profile)

Was this tested?

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

index =

    [1]

distance =

     0

Perhaps a working example would be useful.

Updates

1.2

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

1.1

Add link to strdist.m

MATLAB Release
MATLAB 7.13 (R2011b)
Acknowledgements

Inspired by: Calculation of distance between strings

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video