id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
10864,Bug in Huffman algorithm,jsrn,wdj,"There seems to be a bug in the Huffman build algorithm when given a frequency dictionary.
The following example results in a wrong encoding table: Let there be 10 symbols numbered 1,..,10 where number i occurs with probability i/55.
The Huffman table I end up with, manually running the algorithm is something like the following:
{{{
{ 1: '00000', 2: '00001', 3: '0001', 4: '1000', 5: '1001',
6: '001', 7: '110', 8: '111', 9: '101', 10: '01' }
}}}
which has expected length 173/55.
The current Huffman-algorithm returns
{{{
{1: '1100', 2: '1101', 3: '1110', 4: '1111', 5: '000',
6: '001', 7: '010', 8: '011', 9: '100', 10: '101'}
}}}
which has expected length 175/55.
Apply :
* trac_10864.patch
* trac_10864-2.patch
",defect,closed,major,sage-4.7,coding theory,fixed,huffman,ncohen mvngu,sage-4.7.alpha3,Nathann Cohen,Johan Sebastian Rosenkilde Nielsen,N/A,,,,,