From: Dominik Bathon <dbatml@...>
Date: 2006-04-07T00:28:23+09:00
Subject: Re: String generalization

On Thu, 06 Apr 2006 14:11:10 +0200, 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�;d:L348kddd3' -> .*

Here is my shot at the problem:

class String

   # from strict to less strict
   PATTERNS_TO_GENERALIZE = [
     /\d/, /\d+/,
     /[a-z]/, /[a-z]+/,
     /[A-Z]/, /[A-Z]+/,
     /\w/, /\w+/
   ]
   def generalize_to_regexp
     parts = split(/(\W+)/).map { |x|
       case x
       when ""
         nil
       when /\W+/
         Regexp.escape(x)
       else
         PATTERNS_TO_GENERALIZE.find { |p|
           (p =~ x) && x == $&
         }.source
       end
     }.compact
     parts2 = [] # will contain the final parts
     size = 0 # size of the window we are currently checking
     parts.size.times { |idx|
       size += 1
       next if size < 4 # window to small
       if size % 2 == 0
         if parts[idx] != parts[idx-2] || parts[idx-1] != parts[idx-3]
           if size > 4
             parts2 << "(#{parts[idx-3]}#{parts[idx-2]})+"
             size = 2
           else # size == 4
             parts2 << parts[idx-3]
             size -= 1
           end
         end
       end
     }
     # handle the remaining window
     if size >= 4
       size %= 2
       parts2 << "(#{parts[-2-size]}#{parts[-1-size]})+"
     end
     parts2.concat(parts[-size, size]) if size > 0
     Regexp.new(parts2.join(""))
   end

end

if $0 == __FILE__
   ['12345', 'ABCDE', 'john.smith@my.super.server.rb',
    '123-45-678-90', 'item:', 'Peter, SZINEK',
    'http://www.google.com', 'jd�;d:L348kddd3'].each { |s|
     puts "#{s} => #{s.generalize_to_regexp.inspect}"
   }
end


The part that finds the repeating patterns is a bit ugly, but it should  
work. Here are the results:

$ ruby generalize_rx.rb
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 => /\w+,\ [A-Z]+/
http://www.google.com => /[a-z]+:\/\/([a-z]+\.)+[a-z]+/
jd�;d:L348kddd3 => /[a-z]+\243;[a-z]:\w+/


Dominik