How to elegantly compute the anagram signature of a word in ruby?

Question

Arising out of this question, I'm looking for an elegant (ruby) way to compute the word signature suggested in this answer.

The idea suggested is to sort the letters in the word, and also run length encode repeated letters. So, for example "mississippi" first becomes "iiiimppssss", and then could be further shortened by encoding as "4impp4s".

I'm relatively new to ruby and though I could hack something together, I'm sure this is a one liner for somebody with more experience of ruby. I'd be interested to see people's approaches and improve my ruby knowledge.

edit: to clarify, performance of computing the signature doesn't much matter for my application. I'm looking to compute the signature so I can store it with each word in a large database of words (450K words), then query for words which have the same signature (i.e. all anagrams of a given word, that are actual english words). Hence the focus on space. The 'elegant' part is just to satisfy my curiosity.

Answer 1

I'm not much of a Ruby person either, but as I noted on the other comment this seems to work for the algorithm described.

s = "mississippi"
s.split('').sort.join.gsub(/(.)\1{2,}/) { |s| s.length.to_s + s[0,1] }

Of course, you'll want to make sure the word is lowercase, doesn't contain numbers, etc.

As requested, I'll try to explain the code. Please forgive me if I don't get all of the Ruby or reg ex terminology correct, but here goes.

I think the split/sort/join part is pretty straightforward. The interesting part for me starts at the call to gsub. This will replace a substring that matches the regular expression with the return value from the block that follows it. The reg ex finds any character and creates a backreference. That's the "(.)" part. Then, we continue the matching process using the backreference "\1" that evaluates to whatever character was found by the first part of the match. We want that character to be found a minimum of two more times for a total minimum number of occurrences of three. This is done using the quantifier "{2,}".

If a match is found, the matching substring is then passed to the next block of code as an argument thanks to the "|s|" part. Finally, we use the string equivalent of the matching substring's length and append to it whatever character makes up that substring (they should all be the same) and return the concatenated value. The returned value replaces the original matching substring. The whole process continues until nothing is left to match since it's a global substitution on the original string.

I apologize if that's confusing. As is often the case, it's easier for me to visualize the solution than to explain it clearly.

Answer 2

Here's it in one line:

str1.split('').sort == str2.split('').sort

However, I would recommend something more like this:

class String
  def anagram_of?(other)
    self.to_char_array.sort == other.to_char_array.sort
  end

  def to_char_array
    self.split('')
  end
end

str1.anagram_of?(str2)

Edit:

I apparently ignored the part about encoding repeated letters, but why would you want to do this? It offers no performance benefit whatsoever.

Answer 3

I don't see an elegant solution. You could use the split message to get the characters into an array, but then once you've sorted the list I don't see a nice linear-time concatenate primitive to get back to a string. I'm surprised.

Incidentally, run-length encoding is almost certainly a waste of time. I'd have to see some very impressive measurements before I'd think it worth considering. If you avoid run-length encoding, you can anagrammatize any string, not just a string of letters. And if you know you have only letters and are trying to save space, you can pack them 5 bits to a letter.

---Irma Vep

---

EDIT: the other poster found join which I missed. Nice.

Answer 4

The fastest way to create a sorted list of the letters is this:

"mississippi".unpack("c*").sort.pack("c*")

It is quite a bit faster than split('') and join(). For comparison it is also best to pack the array back together into a String, so you dont have to compare arrays.