[mkgmap-dev] Building Huffman tree

Sat Jan 1 11:53:50 GMT 2022

Hi all!

don't bother with huffman-alpha.patch. It doesn't work yet.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com>
Gesendet: Freitag, 31. Dezember 2021 15:20
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] Building Huffman tree

Hi all,

Just got it working the first time :)
I just decreased code onces too often :O
(Used the frequencies from Adria Topo to find out where my
code went out of sync with that data).
Attached is my code so far, with lots of logging.

No need to create a canonical tree, we just have to fill mdr16 structures and
use the codes that are created thereby (method Mdr16.addCode)

I think I stop for now before I find new problems, I am sure there are still a few ;)
Will continue next year.

Happy new year to all!

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 14:14
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] Building Huffman tree

Hi Gerd

The \0 frequency reduction is something that Garmin might not have
thought of. It can be experimented with once the encoding is working.
It won't make any difference to the actual encoding/decoding algo.

Building the basic tree with the standard Huffman algo, it is to be
expected there will sometimes be empty levels. When re-constituting to
give the canonical version, calc the lowest/next-to-use as normal, but
if the level isn't used (because empty), use this value as the prevCode
for the next level. There could be a adjacent empty levels. I think
this works!

Ticker

On Fri, 2021-12-31 at 10:58 +0000, Gerd Petermann wrote:
> 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
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

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