#10864: Bug in Huffman algorithm
-----------------------------+----------------------------------------------
Reporter: jsrn | Owner: wdj
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.6.2
Component: coding theory | Keywords: huffman
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Changes (by ncohen):
* status: new => needs_review
* milestone: => sage-4.6.2
Comment:
This happens when Sage is fed with a dictionnary where it expects a
string.
{{{
sage: freq = dict([(i,i) for i in range(1,11)])
sage: freq
{1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10}
sage: Huffman(freq).encoding_table()
{1: '1100', 2: '1101', 3: '1110', 4: '1111', 5: '000', 6: '001', 7: '010',
8: '011', 9: '100', 10: '101'}
sage: Huffman(table = freq).encoding_table()
{1: '01110', 2: '01111', 3: '0110', 4: '1110', 5: '1111', 6: '010', 7:
'100', 8: '101', 9: '110', 10: '00'}
sage: enc = Huffman(table = freq).encoding_table()
sage: sum(map(lambda (x,y): x*len(y),enc.items()))
173
}}}
This would take half a second to notice if only Sage was returning an
error rather than work on a dictionary instead of a string. This patch
should avoid this problem in the future `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10864#comment:1>
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.
