Same frequency table gives different Huffman encoding table.

9bcdc8ae-e33c-4bbe-ae30-d4371d8a45d0 commented 6 years ago

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 commented 6 years ago

comment:1

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

9bcdc8ae-e33c-4bbe-ae30-d4371d8a45d0 commented 6 years ago

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 commented 6 years ago

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.

sagemath / sage

Same frequency table gives different Huffman encoding table. #25798