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 is necessary to transform the first string into the second string. You can find a brief description of this metric in https://en.wikipedia.org/wiki/Levenshtein_distance.
In our example, you will implement two operations:
- The first operation returns...
