Levenshtein Distance looping in Python

Question

I have a set of reference words (spelled correctly) and I need to take a user input word. The input word is compared with the reference list using levenshtein distance and I need to return the word from reference list that has the lowest cost. Furthermore, that reference list is sorted by frequencies so higher frequencies appear at the top. In case the distance is same for 2 words,the word with higher frequency is returned. "NWORDS" is my reference list sorted according to the frequency. "Candidate" is the user input word.

Code:

for word in NWORDS: #iterate over all words in ref
    i = jf.levenshtein_distance(candidate,word) #compute distance for each word with user input

        #dont know what to do here
    return word #function returns word from ref list with lowest dist and highest frequency of occurrence.

Levenstein distance is not the way to approach this problem. http://norvig.com/spell-correct.html — Slater Victoroff, Feb 16 '14 at 09:16
See also this question: http://stackoverflow.com/questions/2294915/what-algorithm-gives-suggestions-in-a-spell-checker — Krumelur, Feb 16 '14 at 09:17
this is just a part of the whole problem. i have already implemented peter norvig before this, but i need to improve the efficiency using levenshtein. And my data contain very few english words. — Hypothetical Ninja, Feb 16 '14 at 09:18

score 2 · Accepted Answer · answered Feb 16 '14 at 10:07

You could approach this as follows:

match = None # best match word so far
dist = None # best match distance so far
for word in NWORDS: #iterate over all words in ref
    i = jf.levenshtein_distance(candidate, word) #compute distance for each word with user input
    if dist is None or i < dist: # or <= if lowest freq. first in NWORDS
        match, dist = word, i
return match #function returns word from ref list with lowest dist and highest frequency of occurrence

Levenshtein Distance looping in Python

1 Answers1