Code the Huffman!

Python 2, 299 bytes

Here's my attempt at an answer.

The Huffman codes are different from the examples given, but should still be optimal.

i=raw_input();m=n=[(c,i.count(c))for c in set(i)]
while n[1:]:n.sort(key=lambda x:(x[1]));(a,b),(c,d)=n[:2];n=[((a,c),b+d)]+n[2:]
n=n[0][0]
r=[]
def a(b,s):
 if b[1:]:a(b[0],s+'0');a(b[1],s+'1')
 else:r.append(b+(s if s[1:]else s+'0'))
a(n,' ')
for y in sorted(r,key=lambda x:-dict(m)[x[0]]):print y

Pyth, 53 bytes

jo_/zhNee.WtHa>JohNZ2+shKC<J2]s.b+RYNeKU2m,/zd]+d\ {z

Demonstration

Here's a version that shows the internal state, so you can see the encoding being built:

jo_/zhNee.WtHvp+`a>JohNZ2+shKC<J2]s.b+RYNeKU2bm,/zd]+d\ {z

Demonstration

Copy the output to an environment with wider lines for a clearer picture.

Matlab, 116 bytes

tabulate makes a frequency table. huffmandict takes a list of symbols and probabilities for each symbol, and calculates the code.

t=tabulate(input('')');
d=huffmandict(t(:,1),cell2mat(t(:,3))/100);
for i=1:size(d,1);disp([d{i,1},' ',d{i,2}+48]);end