title: Looking for similar words
body: <p>I'm trying to write a spellchecker module.</p>
  
  <p>It loads a text, creates a dictionary from 16 mb file and then checks if encountered word is similar to the word in dictionary (similar = varies up to two chars) if so then it changes it to the form from dictionary.</p>
  
  <p>Right now I'm using a Levenshtein Distance algorithm and processing of a 50 words set takes 3 min...</p>
  
  <p>I'm pretty sure that there must be a faster solution.
  Profiler told me that my app spends more than 80% of it's time in Levenshtein Distance function.</p>
  
  <p>Are there any better solutions/algorithms?</p>
  
  <p>Here is the implemented of version of the algorithm I use:</p>
  
  <pre><code>def levenshteinDistance(s1, s2):
      l_s1 = len(s1)
      l_s2 = len(s2)
      d = [[a for a in genM(x, l_s2 + 1)] for x in xrange(l_s1 + 1)]
      for i in xrange(1, l_s1 + 1):
          for j in xrange(1, l_s2 + 1):
              d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + decide_of_equality(s1[i - 1],s2[j - 1]))
      return d[l_s1][l_s2]
  </code></pre>