Advertisement
Guest User

Abs timing

a guest
Oct 9th, 2013
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.30 KB | None | 0 0
  1. def suggest_alternatives(w):
  2.     """Opens words.txt and returns  a list of possible corrections for word 'w'
  3.     words.txt is the generic word dictionary for linux with a little under 100k words"""
  4.     result = []
  5.     words = get_words('words.txt')
  6.     wordset = set(words)
  7.     start = time.time()
  8.     for word in wordset:
  9.         #if 1 >= len(w) - len(word) >= -1: continue
  10.         #if (len(word) > (len(w)+1)) and (len(word) < (len(w)-1)): continue
  11.         if abs(len(w) - len(word)) > 1: continue
  12.         distance = 0
  13.         distance = levenshtein(w,word)
  14.         if (distance == 1):
  15.             result.append(word)
  16.     print timer(start)
  17.     return result
  18.  
  19. def levenshtein(s1, s2):
  20.     "Calculates the Levenshtein distance between string 1 and string 2."
  21.     if len(s1) < len(s2):
  22.         return levenshtein(s2, s1)
  23.     if len(s2) == 0:
  24.         return len(s1)
  25.     previous_row = xrange(len(s2) + 1)
  26.     for i, c1 in enumerate(s1):
  27.         current_row = [i + 1]
  28.         for j, c2 in enumerate(s2):
  29.             insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
  30.             deletions = current_row[j] + 1       # than s2 
  31.             substitutions = previous_row[j] + (c1 != c2)
  32.             current_row.append(min(insertions, deletions, substitutions))
  33.         previous_row = current_row
  34.     return previous_row[-1]
  35.  
  36. def timer(s):
  37.     return "Executed in %0.5f" % float(time.time() - s)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement