#10864: Bug in Huffman algorithm
-----------------------------+----------------------------------------------
Reporter: jsrn | Owner: wdj
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: coding theory | Keywords: huffman
Author: Nathann Cohen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Description changed by ncohen:
Old description:
> 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.
New description:
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
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10864#comment:15>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
