From: Bill Kelly <billk@...>
Date: 2001-10-09T18:49:26+09:00
Subject: [ruby-talk:22293] Re: Fuzzy string match upgrade needed

Hi Phlip,

From: "Phlip" <pplumlee@celterra.com>
>
> 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?

I like regexps.  Can't help it - I'm addicted.  . . . So, fresh aglow
with the String#scan tip from matz - here's an attempt at a solution
that relies a little more heavily on regexps to do the tokenizing.

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

[Perhaps I ought to have posted a diff - only a few lines changed
really. :) ]

Bill

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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


Tokenizer = /-?\d+(?:\.\d+)?|[a-zA-Z]+|(?:-(?!\d)|[^\d\s-])/

def stringTolerance string1, string2, verbose = 0

    list1 = string1.scan(Tokenizer)
    list2 = string2.scan(Tokenizer)

    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

        result = if /[a-zA-Z]/.match(token1) then
            matchWord (token1, token2)
        elsif /[0-9.-]/.match(token1) then
            matchNumber (token1, token2)
        else
            token1 == 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 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)