Opened 3 years ago

Last modified 3 years ago

#25798 new defect

Same frequency table gives different Huffman encoding table.

Reported by: gh-AntGeorge Owned by:
Priority: major Milestone:
Component: coding theory Keywords: Huffman
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Way to reproduce:

sage: from sage.coding.source_coding.huffman import Huffman
sage: a = {'120': 1, '167': 1, '17': 1, '75': 1, '98': 2, '99': 1}
sage: b = a.copy()
sage: H1 = Huffman(a)
sage: H2 = Huffman(b)
sage: H1.encoding_table() == H2.encoding_table()
False

Sage version:

sage: version()
'SageMath version 7.5.1, Release Date: 2017-01-15'

I think the problem is with enumerate and items calls inside the _build_code function of Huffman class because there is no a standard order of the elements.

Change History (4)

comment:1 follow-up: Changed 3 years ago by dcoudert

For a given frequency distribution, Huffman code is not unique. May be you are expecting a canonical Huffman code ?

comment:2 Changed 3 years ago by gh-AntGeorge

Last edited 3 years ago by gh-AntGeorge (previous) (diff)

comment:3 in reply to: ↑ 1 Changed 3 years ago by gh-AntGeorge

Oh ok, it's my fault.

However, is there any way to re-create the same Huffman code from the existing Huffman object?

Maybe should i replace the _tree and the _index of the new object, it is right?

Thanks.

Replying to dcoudert:

For a given frequency distribution, Huffman code is not unique. May be you are expecting a canonical Huffman code ?

comment:4 Changed 3 years ago by dcoudert

I don't understand what you want to do. You should ask on https://ask.sagemath.org/, it's the right place for such questions.

Note: See TracTickets for help on using tickets.