AutoHotkey Community

[TheGood]

I made a nice little function that basically takes a string, and matches it to another string from a list of strings. The trick here is that it must pick the "most matching" string. To show you an example of what I mean, consider movie titles. Let's say you have a list of four movie titles:

- The Shawshank Redemption
- The Dark Knight
- Schindler's List
- The Godfather: Part II

And then you find yourself in a situation where, you need to match a movie title to one of those movies. But because it is not formatted the same way, you can't simply check for equality to get a match. For example, the string might be "Shawshank Redemption, The (1994)" or even "[2008] - The Dark Knight". So the question is, how would you go about matching them? What would be your algorithm?

The way I went about it is to compare the string to each item of the list, and counting how many words match. So, for example, "[2008] - The Dark Knight" would match 3 words with "The Dark Knight", and 1 word with both "The Shawshank Redemption" and "The Godfather: Part II". My function simply returns the index of the item of the list that matches the most words with the string. In our particular case, that would be 2 (since The Dark Knight is in the second position in the list).

I'm not only presenting it, but asking also, how would you have done this? Is there a more efficient (or accurate) way of doing this? I was thinking of some kind of re-synchronizing comparison, but it felt too complicated to implement.

Jan 28, 2008 - Edit: The algorithm now calculates the similarity based on trigrams. The script now also gives a "matching fitness" between 0% and 100%.

[PurloinedHeart]

How about your method along with counting letters themselves?

Example:
Movie 1: racecar roar
Movie 2: racecar raar

You're looking for racecar raar

The new method would return 12 for both, however if you checked words as well, one of them would return 13 (12 Matched letters + 1 matched word)

[TheGood]

Yeah, but the problem is that the length of the string you're looking for and the string it matches with don't necessarily have the same length. Like for example "[2008] - The Dark Knight" and "The Dark Knight". So there's no use in taking it into consideration.

[PurloinedHeart]

Yeah, I wasn't really thinking when I made that last post

Just noticed that your search wouldn't work in certain examples

[TheGood]

Well, the thing is, I don't want to make the algorithm specifically for movie titles. I want the function to be good in any situation where the user wants to match any kind of strings. Movie titles was just an example.

However, I do agree that, even out of the movie title context, the string "The Dark Knight" is most similar to "The Dark Knight [2008]" (from the list you gave). I'll work on incorporating some kind of leftover bias.

[TheGood]

OK, I made the following changes:
- Made the sList parameter ByRef to boost performance for big lists
- Numbers and hyphens are also considered word characters now
- In case there's two list items with the same word count matches, the shortest one wins

I am still hesitant to make changes based on how digits are handled in the leftover count because although assuming they don't matter in the matching process of a movie title is true, we can't be sure that it is always the case for other kinds of strings. Or maybe it is . I need to think about this a little more.

[totalmig]

Hi..

I would seperate all of the titles into seperate words, then compare the words, letter by letter.

[hugov]

You might find this of interest:

Fuzzy string searching with Damerau–Levenshtein distance
http://www.autohotkey.com/forum/topic28243.html
_________________
AHK Wiki FAQ
TF : Text files & strings lib, TF Forum

[TheGood]

[Rabiator]

A very satisfactory method is comparing all n-grams (a sequence of n consecutive letters) of both strings.
I used it to find similar sentences for translating parts of the AutoHotkey help into german. Trigrams (3 characters) worked good for me.

Example:
The following string with 15 letters has 13 n-grams:

[TheGood]

That is very cool! Thanks for the detailed explaination.

[TheGood]

I updated the algorithm using Rabiator's idea. Since it now gives back a fitness level, you can apply a threshold to decide whether the match is close enough or not.

[Morpheus]

I think I found a bug. If I use these as my items:

[TheGood]

Both s2 and s3 have a fitness level of 100%. It just returns the first of the two. In fact, even s4 has a fitness level of 100%.

I did this a long time ago, so I'm not too sure what is the best way of giving weight to the difference in length of the string.

What I would do is probably first check if multiple items have the same (and highest) fitness level, and then only return the one with the length closest to the length of sItem.

[Morpheus]

First I would like to say that this is the best matching algorithm that I have found for my needs. Second, I don't understand how it works, it is too advanced for my skills.

I guess I wasn't going to try to find a better match, I just wanted to make sure that the user knew that it wasn't really a 100% match. That's why I was going to set a new fitness level created by dividing the two string lengths.

I have also changed the way 100% matches are handled. The script I use looks like this: