title: Huffman codes over non binary alphabets
body: <p>I was looking at constructing optimal Huffman codes over non-binary alphabets. </p>
  
  <p>This question was asked in <a href="https://stackoverflow.com/questions/5452522/huffman-trees-for-non-binary-alphabets">Huffman trees for non-binary alphabets?</a>. The solution suggested to use the Huffman coding procedure combining n lowest frequency symbols at a time (as is also suggested by wikipedia). However, This does not seem to be optimal. Say I have 4 alphabets with frequencies,</p>
  
  <pre><code> A --&gt; 0.4
  
   B --&gt; 0.25
  
   C --&gt; 0.2
  
   D --&gt; 0.15
  </code></pre>
  
  <p>The ternary Huffman code derived here using this would be</p>
  
  <blockquote>
    <p>A --> 0</p>
    
    <p>B --> 10</p>
    
    <p>C --> 11</p>
    
    <p>D --> 12</p>
  </blockquote>
  
  <p>However the following code would have shorter expected length:</p>
  
  <blockquote>
    <p>A --> 0</p>
    
    <p>B --> 1</p>
    
    <p>C --> 20</p>
    
    <p>D --> 21</p>
  </blockquote>
  
  <p>Am I missing something here?</p>
  
  <p>PS I am posting this as a question because I can not comment on the previous post.</p>