def max(*l)
	max = l.shift
	l.each { |i| if i > max then max = i end }
	return max
end

def min(*l)
	min = l.shift
	l.each { |i| if i < min then min = i end }
	return min
end

def levenshtein(a,b)	
	if a.length == 0 then return b.length end
	if b.length == 0 then return a.length end
	
	p = Array.new; d = Array.new
	for i in 0 .. a.length do p[i] = i end
	
	for j in 1 .. b.length
		token_j = b[j - 1]
		d[0] = j

		for i in 1 .. a.length
			if a[i - 1] == token_j then cost = 0 else cost = 1 end
            # minimum of cell to the left+1, to the top+1, diagonally left and up +cost
            d[i] = min(d[i - 1] + 1, p[i] + 1, p[i - 1] + cost)
        end

       # copy current distance counts to 'previous row' distance counts
       swap = p; p = d; d = swap
	end
	
	return p[a.length]
end


def similarity(a,b)
	if a.length > 100 or b.length > 100 then
		a = a.split(/\s/)
		b = b.split(/\s/)
	end
	return 1.0 - levenshtein(a,b).to_f / max(a.length,b.length).to_f
end