> How should I calculate the similarity between any two words?
The Levenshtein distance (http://www.merriampark.com/ld.htm) algorithm is a good place to start.