From: pplumlee@... (Phlip)
Date: 2001-10-09T10:42:59+09:00
Subject: [ruby-talk:22271] Fuzzy string match upgrade needed

Rubizens:

The source below my signature compares two strings for a "good enough"
match. The strings expect to be program source (specifically, POVray),
so they needn't match perfectly. They can match to within mathematical
tolerance. Blanks may differ; keywords & delimiters must be the same;
numbers may differ by insignificant digits, and zeros may differ by
sign.

The problems:

	the functions treat a minus sign, -, as a delimiter, not part of a
number. The last assertion blows because of this.

	a slower algorithm would stretch the limits of computer science

	89.43 gets treated as two integers, not one float

How can we rewrite the central function to improve the logic? possibly
by packing more thought into the regular expressions and less into the
if statements?

The code exploits RubyUnit to make its point, but the reply needn't.

Thanks!

-- 
  Phlip                          phlip_cpp@my-deja.com
   http://www.greencheese.org/PhilosophyBrethrenThree
  --  Proud victim of the dreaded boomerang effect  --

require 'runit/testcase'
require 'runit/cui/testrunner'


def tolerance a, b
	small = a / 1000.0
	small = small.abs
	small = 0.000001 if small == 0.0
	absdiff = a - b
	absdiff = absdiff.abs
	got = absdiff < small
	return got
end


def matchWord token1, token2
	return token1 == token2
end


def matchNumber token1, token2
	n1 = token1.to_f
	n2 = token2.to_f
	return tolerance (n1, n2)
end


def removeBlanks (token)
	for blankness in ["\n", "\r", "\t", " "] do
		token = token.split(blankness).join("")
	end

	return token
end


def stringTolerance string1, string2, verbose = 0
	list1 = string1.split(/\b/)
	list2 = string2.split(/\b/)

	result = true

	for idx in 0..list1.size do
		token1 = list1[idx]
		token2 = list2[idx]

		if token1 == nil then
			return token2 == nil
		end
		
		if token2 == nil then
			return token1 == nil
		end

		if /[a-zA-Z]/.match(token1) then
			result = matchWord (token1, token2)

		elsif /[0-9]/.match(token1) then
			result = matchNumber (token1, token2)

		elsif token1 != token2 then
			result = removeBlanks (token1) == removeBlanks (token2)
		end

		if not result then 
			break
		end
	end
	
	if verbose and not result then
		trace_{token1}
		trace_{token2}
	end
				
	return result
end


class TestStringTolerance_ < RUNIT::TestCase
	def test_stringTolerance
	
	#  show two strings are a "good enough" match

		assert removeBlanks (""          ) == ""
		assert removeBlanks ("\n>\n} \n" ) == ">}"
		assert removeBlanks ("yo"        ) == "yo"
		assert removeBlanks ("\t\r.. ."  ) == "..."
		assert removeBlanks ("\t\r..\n. ") == "..."
		assert removeBlanks ("<>   "     ) == "<>"
		assert removeBlanks (" 5 6 "     ) == "56"

		assert matchWord ("frob", "frob")
		assert ! matchWord ("frob", "frog")
		assert ! matchWord (" frob", "frob")
		assert ! matchWord ("frob ", "frob")
	
		assert matchNumber ("12345", "12345")
		assert matchNumber ("12345", "12356")
		assert ! matchNumber ("12345", "1234")
		assert ! matchNumber ("12345", "2345")
		assert ! matchNumber ("12345", "12445")

		baseString = """ translate <0, 0, 0> rotate < 0, 0, 99.4838> rotate
< 0, -89.5354, 0>
           translate < 0, 180.791, 215.459>}
			"""

		stringDiffersByDelimiters = """ translate <0, 0, 0> rotate < 0, 0,
99.4838> rotate < 0, -89.5354, 0>
           translate < 0, 180.791, 215.459}
			"""

		stringDiffersBySpaces = """ translate <0, 0, 0> 
			rotate < 0, 0, 99.4837> rotate < 0, -89.5354, 0>
           translate  <  0, 180.791, 215.459> } 
			"""

		stringDiffersWithinNumericTolerance = """ translate <0, 0, 0> rotate
< 0, 0, -99.4837> rotate < 0, -89.5354, 0>
           translate < 0, 180.791, 215.459>}
			"""

		stringDiffersOutsideNumericTolerance = """ translate <0, 0, 0>
rotate < 0, 0, 99.4840> rotate < 0, -89.5354, 0>
           translate < 0, 180.791, 215.459>}
			"""

		stringsDifferByIrrelevantNegatives = """ translate <-0, 0, 0> rotate
< 0, 0, 99.4840> rotate < -0, -89.5354, -0.0>
           translate < 0, 180.791, 215.459>}
			"""

		verbose = false

		assert stringTolerance (baseString, baseString, verbose)
		assert ! stringTolerance (baseString, stringDiffersByDelimiters,
verbose)
		assert stringTolerance (baseString, stringDiffersBySpaces, verbose)

		assert ! stringTolerance (baseString,
stringDiffersWithinNumericTolerance, verbose)
		assert stringTolerance (baseString,
stringDiffersOutsideNumericTolerance, verbose)
	
		assert stringTolerance (baseString,
stringsDifferByIrrelevantNegatives, verbose)
	
	end
end

RUNIT::CUI::TestRunner.run(TestStringTolerance_.suite)