First example – a best-matching algorithm for words
The main objective of a best-matching algorithm for words is to find the words most similar to a string passed as a parameter. To implement one of these algorithms you need the following:
- A list of words: In our case, we have used the UK Advanced Cryptics Dictionary (UKACD) that is a word list compiled for the crossword community. It has 250,353 words and idioms. It can be downloaded for free from http://www.crosswordman.com/wordlist.html.
- A metric to measure the similarity between two words: We have used the Levenshtein distance that is used to measure the difference between two sequences of chars. The Levenshtein distance is the minimal number of insertions, deletions, or substitutions, which ...