From: Kirk Haines <wyhaines@...>
Date: 2011-03-08T02:11:52+09:00
Subject: Re: Hamming Distance

On Mon, Mar 7, 2011 at 8:47 AM, Martin Hansen <mail@maasha.dk> wrote:
> What is the fastest way to calculate the Hamming Distance between two
> equally long strings in Ruby? A have looked at the amatch gem, but I was
> wondering what can be done with Ruby only?
>
> Here is a very interesting discussion on the subject:
>
> http://www.perlmonks.org/?node_id=500235
>
>
> Note the elegant and extremely fast Perl solution:
>
> sub hd {
>    return ($_[0] ^ $_[1]) =~ tr/\001-\255//;
> }

There are a bunch of ways. There isn't a built in xor of strings in
Ruby, but it's easy to define one.  Once you have that, you can do it
pretty similarly to the Perl example:

  def hd(l, r)
    l.xor(r).tr("\x00",'').length
  end

You can implement xor of two strings using pure ruby, but to get it
fast, you'll probably want to utilize an extension.  Here's one
approach using a technique that, I believe, was in the mailing list
several years ago:


require "narray"

class String
  def xor(other)
    if other.empty?
      self
    else
      left = self
      right = other

      if left.length < right.length
        n,r = right.length.divmod(left.length)
        left = left * n + left[0, r]
      elsif right.length < left.length
        n,r = left.length.divmod(right.length)
        right = right * n + right[0, r]
      end

      left_na = NArray.to_na(left, "byte")
      right_na = NArray.to_na(right, "byte")

      (left_na ^ right_na).to_s
    end
  end

  def hamming_distance(other)
    self.xor(other).tr("\x00",'').length
  end
end


Kirk Haines
Software Engineer
Engine Yard