Revision 484a919d-a7f7-46ec-bc8a-8091bc01e835 - Code Golf Stack Exchange

###Ruby, 104 characters###

 def f(s)m=("a".."z").to_a;l=m.map{|x|[-s.downcase.count(x),x]};s.tr(m.join, l.sort.transpose[1].join)end

[Online Version][1] here. Sorting of characters with the same count is not defined, as mentioned in another answer. With the input "asdf", each answer has another output so far.

In other words: all answers have the same behaviour (thus represent a decodable encoding) when the input contains all lower case letters with each having a unique count.

 [1]: http://repl.it/PAl