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@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@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@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev