From: Robert Dober <robert.dober@...>
Date: 2006-04-06T21:55:49+09:00
Subject: Re: String generalization

------=_Part_3729_19473189.1144328146001
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On 4/6/06, Peter Szinek <peter@rt.sk> wrote:
>
> Hello all,
>
> I am having the following problem: I have to implement a method
> which accepts a string and returns a  generalized form of the string.
> Some examples:
>
> '12345' -> \d+
> 'ABCDE' -> [A-Z]+
> 'john.smith@my.super.server.rb' -> [a-z]+\.[a-z]+@([a-z]+\.)+[a-z]
> '123-45-678-90' -> (\d+-)+\d+
> 'item:' -> [a-z]+:
> 'Peter, SZINEK': -> [A-Z][a-z]+, [A-Z]+
> 'http://www.google.com' -> [a-z]+://([a-z]+\.)+[a-z]
> 'jd=A3;d:L348kddd3' -> .*
>
> So, given an example, the function should generate a generic regexp
> which is then used to match the instances of the same class (i.e. based
> on an e-mail, you create a regexp which can be used to match other
> emails).
> Of course this problem is not solvable in general. You would need more
> examples (both positive and negative ones, as it is proven that just
> using positive examples you can not generalize a pattern (generate a
> regular grammar desribibg it) and then machine learn/induce a
> grammar/etc based on that. Unfortunately i have only one positive
> example. So i do not need a perfect solution (which is not possible
> anyway) just a mostly working one.
>
> I have implemented it in java, and it works pretty well but it is ugly
> as hell (as any java code dealing with stuff where you need regexps,
> slicing, maps etc). Any ideas for a nice Ruby code solving this? Then i
> would call it via JRuby (and killed by the other colleagues using java
> but not Ruby ;-).
>
> thx,
> Peter
>
>
As you said for yourself this is quite a *general* problem. So my code is
not to show off a clever automaton, it is completely stupid, but rather to
give you the idea how to hide it ;)
Please note that it is not even complete (end handling has to be done) I
just wanted to give you ideas.

Just an idea: Maybe you should make some more effort in the definition of
the problem and post it to Ruby Quiz!
----------------------------------------- 8<
---------------------------------------------
 cat gen1.rb; ruby gen1.rb
#!/usr/bin/env ruby
#

class Generalize < Regexp

# Do not use a Hash, order is crucial!
Generalisations =3D [ '\w', '\d', '@', '\.', '.' ]

        def initialize( str )
                @rep =3D generalize(str)

                super @rep
        end

        def to_s
                s =3D super
                "<" + s + ">:" + self.class.to_s + "\"" + @rep +"\""
        end

        private
        #
        # This is the real tough part which might become ugly, but at least
it is private :)
        def generalize( str )
                r =3D ""
                old =3D nil
                star=3D ""
                str.each_byte do
                        |b|
                        c =3D b.chr
                        # Much more intelligence to be put here, maybe also
more context than the
                        # single string we have at our disposal.
                        Generalisations.each do
                                | lit |
                                reg =3D Regexp.new( lit )
                                if reg =3D=3D=3D c then
                                        if lit =3D=3D old then
                                                star =3D "+"
                                        else
                                                if old then
                                                        r << old
                                                        r << star
                                                        star =3D ""
                                                end
                                                old =3D lit
                                        end
                                        break
                                end
                        end
                end
                r
        end


end

r =3D Generalize.new("robert.dober@gmail.com")
puts r.to_s
<(?-mix:\w+\.\w+@\w+\.)>:Generalize"\w+\.\w+@\w+\."
------------------------------- >8 ----------------------------------------=
-
Cheers
Robert
--
Deux choses sont infinies : l'univers et la b=EAtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

------=_Part_3729_19473189.1144328146001--