# Re: Mini quiz (Was: Detecting similar strings)

**URL:** <https://www.ruby-forum.com/t/re-mini-quiz-was-detecting-similar-strings/100818>\
**Category:** Ruby\
**Created:** [August 1, 2006, 10:49am UTC](https://www.ruby-forum.com/t/re-mini-quiz-was-detecting-similar-strings/100818 "2006-08-01T10:49:08Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [August 1, 2006, 10:49am UTC](https://www.ruby-forum.com/t/re-mini-quiz-was-detecting-similar-strings/100818/1 "2006-08-01T10:49:08Z")

</div>

> It’s missing from wikipedia though.

Does wikipedia provide the code for the implementations it lists?  
Maybe Hal would be so kind to add it then, if we ask him politely  
to do so 🙂

Best regards,

Axel

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [August 1, 2006, 3:20pm UTC](https://www.ruby-forum.com/t/re-mini-quiz-was-detecting-similar-strings/100818/2 "2006-08-01T15:20:10Z")

</div>

> > It’s missing from wikipedia though.
> 
> Does wikipedia provide the code for the implementations it lists?  
> Maybe Hal would be so kind to add it then, if we ask him politely  
> to do so 🙂
> 
> Best regards,

Here’s my implementation anyway (not at all fast):

def lev(s1, s2)

# A hash to build up the solution matrix in.

l = Hash.new do |h,k|  
h = if k.member? 0  
# Edge case for the top and left of the solution matrix.  
k.max  
else  
# Otherwise, recursively find this cell based on the rest of  
# the solution matrix.  
i,j = \*k  
[l[[i-1,j]]+1,  
l[[i,j-1]]+1,  
l[[i-1,j-1]] + (s1[i]==s2[j]?0:1)].min  
end  
end

# The answer’s stored in the bottom right of the solution matrix.

l[[s1.size-1, s2.size-1]]  
end

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [August 2, 2006, 1:44am UTC](https://www.ruby-forum.com/t/re-mini-quiz-was-detecting-similar-strings/100818/3 "2006-08-02T01:44:55Z")

</div>

removed\_email\_address@domain.invalid wrote:

> > It’s missing from wikipedia though.
> 
> Does wikipedia provide the code for the implementations it lists?  
> Maybe Hal would be so kind to add it then, if we ask him politely  
> to do so 🙂

Ping me in a week and I will…

Hal

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [August 2, 2006, 2:39am UTC](https://www.ruby-forum.com/t/re-mini-quiz-was-detecting-similar-strings/100818/4 "2006-08-02T02:39:16Z")

</div>

A quick search on Google reveals a levenshtein ruby function has already  
been created.  
[http://po-ru.com/projects/levenshtein/](http://po-ru.com/projects/levenshtein/)

To my untrained eye (I am new to Ruby) using the levenshtein distance to  
calculate what someone might have meant to type mught be expensive. You  
will need to calculate the distance for all values in the field to  
compare it with the user input, then pick the small distances and  
display them as options. As the list of values grows larger, your app  
will bog down.

Perhaps a better way is to use an auto-complete ajax call on the input  
field?

Andrew