[ruby-talk:8544] Re: speedup of anagram finder

In article <[e-mail]>,
Dave Thomas  <[e-mail]> wrote:
>[e-mail] (Jean Michel) writes:
>
...
>That's a good approach.
>
>I was wondering if there's a totally different way of doing
>this. Right now, all solutions (including the original based on Perl)
>generated a hash from each word, such that hash(A) == hash(B) => A == B.
>
>How about going statistical? Anyone fancy writing a Bloom filter based 
>finder (perhaps using #sum as the hash)? Let's think more radically!

I  guess I  got  bitten  by the  ruby  benchmarking  bug. The  following
version  which sidesteps  unpack  and sort  seems  slighly faster  under
'benchmark' that  the unpack-sort  version, although  it is  much slower
under 'profile'.  It seems 'profile' does  a very bad job  of accurately
reflecting time  spent in various  places, since  its main effect  is to
enormously  increase the  interpretive  overhead. I  think  ruby needs a
better 'profile' (kernel help seems necessary).

def histogram(words) # assumes lower-case words using only a..z
  anagrams, keys, word, key = {}, {}
  for word in words do 
    word.chomp!
    hist=Array.new(26,0)
    word.each_byte{|b| hist[b-?a]+=1}
    key = hist.pack('c*')
    if anagrams[key] then anagrams[key] << (keys[key] = word)
    else anagrams[key] = [ word ]
    end
  end
end

As to  possible algorithms  for the  problem: I think  one needs  to use
*some* function with  the property that words which are  anagrams map to
the  same value.  This  function however  does not  need  to be  exactly
injective for anagrams, it may map a few words which are not anagrams of
each other  to the same  value; these would then  be separated out  in a
second (inexpensive) pass.

 Also, hashing is a good way to bring together anagrams, but another way
would  be just  sorting:  in a  first  step, build  an  array of  pairs
[anagram,word], and then  sort it. The efficiency of  this would depend
if ruby is very efficient or not at growing an array.

 Best regards,
    Jean MICHEL