# Levenshtein distance between 2 words - "madonna", "modanna" = 2 ?

## Recommended Posts

Hello everyone

I'd like to implement a function in Filemaker Advanced 10 would calculate the Levenshtein distance between 2 words ( the Levenshtein distance is a metric for measuring the amount of difference between two sequences).

For example, the distance between "Madonna" and "Modanna" is 2.

There is a good article on wikipedia:

http://en.wikipedia.org/wiki/Levenshtein_distance

Unfortunately, I didn't find this feature in BrianDunning and others :-(

If anyone has a solution, I'm interested :-)

##### Share on other sites

Hi Benka,

I'm surprised you didn't follow up on your other post. It seems similar (if not the same concept). Having said that, you would need a dictionary attached. And how would you know the result should be Madonna? How would you specify which words should be compared because if it compared every word then there could be hundreds of results changing each word to another.

We need to know what exactly you want to accomplish and, more importantly in this instance, why.

LaRetta

##### Share on other sites

Hi

I'd like to create a function working like this :

LevenshteinDistance ( "madonna";"modanna") = 2

LevenshteinDistance ( "GUMBO";"GAMBOL") = 2

LevenshteinDistance ( "ZXRZYXX";"ZXRZZZXZZ") = 4

like this :

http://www.merriampark.com/ld.htm

Edited by Guest

##### Share on other sites

Okay, but I'm stuck on a few rules:

If it were reversed, ie, "GAMBOL" ; "GUMBO" ... would it still equal 2 because there was no L on Gumbo?

"ZXRZYXX";"ZXRZZZXZZ") = 4

Please explain (in exact sequence) how this can equal 4. I come up with 5.

UPDATE: Oh, the X by position matches the second X. Forget the second question then.

Edited by Guest

##### Share on other sites

:waytogo: http://en.wikipedia.org/wiki/Levenshtein_distance

Yes, if it were reversed, ie, "GAMBOL" ; "GUMBO", it would be still equal 2

Edited by Guest

##### Share on other sites

Custom Function: CompareStringErr

Parameters:

NewString

OldString

Let ( [

\$posErr = \$posErr + 1 ;

newChar = Middle (newString ;\$posErr ; 1 ) ;

oldChar = Middle (oldString ; \$posErr ; 1 ) ;

match = If ( newChar ≠ oldChar ; TextColor (newChar ; RGB (255 ; 0 ; 0 ) ) )

] ;

If ( \$posErr ≤ Length ( newString ) ; match & CompareStringErr( newString ; oldString ) )

)

Then calculation (number):

Let ( \$posErr = 0 ; Length ( CompareStringErr ( newString ; oldString ) ) )

Given time, I could fine-tune it further ...

UPDATE: I totally expect (and hope) that a few Masters here show us how it REALLY should look!

Edited by Guest
Added update & removed incorrect sentence

##### Share on other sites

You don't use any matrix?

##### Share on other sites

It appears (to me) that you are simply comparing letter to letter right down the line. If so, a recursive custom function can handle it. But I'm unsure which string takes priority. For instance, you'd need to adjust the calculation portion of my CF (to account if reversing GAMBOL and GUMBO to:

Let ( [

add = Case ( Length ( oldString ) > Length ( newString ) ; Length ( oldString ) - Length ( newString ) ) ;

\$posErr = 0 ] ;

Length ( CompareStringErr ( newString ;oldString) ) + add

)

##### Share on other sites

I see there is a lot more to Levenshtein than simple match letter to letter. You might just search here for Levenshtein and you'll get a few other hits.

##### Share on other sites

Here's my attempt. FileMaker isn't particularly well suited to this sort of thing, but anything is possible with enough trickery.

This is implemented via a set of custom functions to port the code on wikipedia to FM. I use global variable repetitions and dynamic variable names to make up the 2D matrix.

It seems speedy enough on small words, but I wouldn't suggest trying it on pages on text.... :

Levenshtein.fp7.zip

##### Share on other sites

Thanks The Shadow! :thanks:

I'm gonna try to understand what you did

It seem to be very clever!

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×

• ### Who Viewed the Topic

1 member has viewed this topic:
spand
×
×
• Create New...

## Important Information

By using this site, you agree to our Terms of Use.