Same frequency table gives different Huffman encoding table.

[AntGeorge]

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.

Component: coding theory

Keywords: Huffman

Issue created by migration from https://trac.sagemath.org/ticket/25798

[dcoudert]

comment:1

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

[AntGeorge]

comment:3

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 ?

[dcoudert]

comment:4

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.