CODEWITHSUNDEEP
algorithmlanguage-agnosticstring-comparisonlevenshtein-distance
hyankov
hyankov

Reputation: 4120

Matching string using levenshtein distance and euristics

I have string patterns ('rules'), in 'categories'. e.g.:

Category1

Category2

Now, I want to be able to 'categorize' a string based on those rules. Let's say we want to find out which category the string fusce laoreet amet ante nisi belongs to. My current implementation will use levenshtein distance implementation and find out that the string mostly 'looks like' fusce sit amet ante nisi and hence, the category is Category1.

Let's say we want to categorize vivamus vel lorem imperdiet sit. Because I put threshold 1/5th of the string length (i.e. the string must be at least 80% similar to its match) on the levenshtein distance algo, the string will remain 'uncategorized'.

In such case I would continue with the following algorithm ...

From each category, I will extract the 'common words' - i.e. words which repeat between the rules within the category. In way, those are the dominating words in the category. So, we'll have:

Category1

Category2

Now I will split the vivamus vel lorem imperdiet sit string word by word and I will give each category a value, depending on how many of the string words are present in the category's 'dominating words'. i.e.:

Category1 will have value of 3 (lorem) + 2 (sit), and Category2 will have a value of 0 (no matches between the split words of the string I am categorizing and the dominating words in the category). The highest-value category 'wins'.

In short, my algorithm is:

  1. Use levenshtein distance with a threshold of allowing 1/5th of the string to change, to find the closest matching rule.
  2. If it fails, split the string we are categorizing into words and with each word, check how 'dominating' that word is in each category, creating a value for the category. The highest value category is our best guess.

Is there a better way to do this? Do you see a problem with this algorithm? Any suggestions?

Upvotes: 0

Views: 499

Answers (1)

Leandro Caniglia
Leandro Caniglia

Reputation: 14858

I don't see a problem with the algorithm. However, I do think there may be a problem behind the question.

No algorithm, provided they are correctly implemented, will present a problem per se. It is the use we make of them under the circumstances of a particular domain that would give appropriate or inappropriate results.

Therefore, instead of trying to find the best algorithm you can think of, I would advise you to put your algorithm at practice in the particular situation you are considering. It is that kind of exercise, and not the algorithm as an isolated entity, what will provide you with insights about the limitations and strengths of a given solution. In other words, do not pursue an abstract perfection beforehand. Implement the simplest solution that might work and then keep improving as you learn more.

Upvotes: 2

Related Questions