[mkgmap-dev] Building Huffman tree

Fri Dec 31 10:58:55 GMT 2021

Hi Ticker,

I am indeed struggling with the code to generate the mdr16 data.
I don't think that Garmin manipulates the count for \0, we have
samples where \0 is encoded with the fewest bits.

My understanding is that the highest code for depth x is calculated
using the lowest code of the previous level :
code = ((prevCode - 1) * 2) + 1;
The code is then decreased for each encoded value.
My problem: I have n values to encode in one depth but the code is < n,
so it woud get negative and that will fail.
I guess that Garmin produces an empty level in that case...

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
Gesendet: Freitag, 31. Dezember 2021 10:57
An: mkgmap development
Betreff: [mkgmap-dev] Building Huffman tree

Hi Gerd

Some thoughts on this:

Dividing the \0 count by some factor between 3 and 6 should reduce the
overall length of the strings. This is because there will be 0..7 bits
free after each string

To make the canonical tree: after using the standard algo to make a
normal tree, just remember the count at each level and chuck the tree
away. Then simply allocate chars, in decreasing frequency order, in
previously levels, from root (and maybe high to low), much the same way
as the decoder handles levels 6 and above.

It might be that if you start with ordered list when building the
initial tree, and get the inequalities right for when sums of lower
levels are equal, you get the canonical tree, but this is just a guess.

Happy new year
Ticker

_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev