title: What is an efficient way to measure similarity between two strings? (Levenshtein Distance makes stack too deep)
body: <p>So, I started with this: <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Ruby" rel="nofollow">http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Ruby</a></p>
  
  <p>Which works great for really small strings. But, my strings can be upwards of 10,000 characters long -- and since the Levenshtein Distance is recursive, this causes a stack too deep error in my Ruby on Rails app.</p>
  
  <p>So, is there another, maybe less stack intensive method of finding the similarity between two large strings?</p>
  
  <p>Alternatively, I'd need a way to make the stack have much larger size. (I don't think this is the right way to solve the problem, though)</p>