how could I make a search match for similar words

Question

I'm working trying to automatically categorize short articles and I'm trying to figure out how to match similar words - eg, shelf shelves or painting and repaint

I'm using the Porter stemming algorithm but it only helps for certain situations and only with the end of the word (both examples above don't work with it).

Is there an algorithm or related word lists that would help with something like this (outside of making my own?)

(I'm working in php so any solutions in that language would be more helpful.)

Answer 1

The Levenshtein Distance is what you are looking for.

For any two strings, it calculates the minimum number of insertions, mutations and deletions that need to occur to changes one string to the other.

If the distance is low then the two words are similar.

You could also use the Soundex algorithm to determine if two words sound similar.

See also:
PHP levenshtein function
PHP soundex function