From: Rick DeNatale <rick.denatale@...>
Date: 2006-09-13T03:50:03+09:00
Subject: Re: How about Enumerable#find_pattern?

On 9/12/06, A. S. Bradbury <asbradbury@tekcentral.org> wrote:
> Well, here's a (not very good) implementation, kind of ported from some python
> code.
>
> module  Enumerable
>
>   def find_pattern(*pat)
>     match_length=0
>     match_pos=0
>     shifts=compute_table(pat)
>     self.each do |obj|
>       while (match_length >=0) and !(pat[match_length]===obj)
>         match_pos+=shifts[match_length]
>         match_length-=shifts[match_length]
>       end
>       match_length+=1
>       if match_length == pat.length
>         return match_pos
>       end
>     end
>     return nil  # failed match
>   end
>
>   private
>   def compute_table(pat)
>     shifts=Array.new(pat.size)
>     shift = 1
>     0.upto pat.size do |i|
>       a=pat[i-1]
>       b=pat[i-shift-1]
>       while (shift < i) and (pat[i-1] != pat[i-shift-1])
>         shift += shifts[i-shift-1]
>       end
>       shifts[i]=shift
>     end
>     return shifts
>   end
> end
>
> a="aaaabbaabbab".split(//)
> a.find_pattern 'a', 'b', 'b'       #=> 3
> a.find_pattern 'c'    #=> nil
> a.find_pattern /a|b/, 'a', 'b'      #=> 2
>
> The idea is to allow efficient searching for patterns in the elements of any
> Enumerable object, the example above is contrived.

Nice, but it can fall down if the pattern contains a regexp which
matches more than one element:

a = "aaaabbabbab".split(//)
a.find_pattern /aab/,  'b'  #=> nil

There's probably a way to fix that, but I'm not sure I can see how.

I did a pretty slavish translation to ruby of the KMP algorithm as
given in the Wikipedia article.  It involved turning the enumerable
into either an array or a string so that it could be indexed instead
of using each.  That didn't allow regexps at all though.

I've been working on hacking that to work with regexps, but that would
really only work if the enumerable was a string anyway, so it would
probably be better to do a specialized implementation in String.


-- 
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

IPMS/USA Region 12 Coordinator
http://ipmsr12.denhaven2.com/

Visit the Project Mercury Wiki Site
http://www.mercuryspacecraft.com/