Hi Ticker, OK, I see. It seems to work out for most of the delta values. Deltas are 6,9,6,4,3,2,5,2,3,3,1,4,9,4 I'll try to find out if I can modify the tree so that it matches all numbers. Probably sometimes I found too short codes. Good finding! Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 10:38 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Are you OK with the idea of the letters at any level being to the right. Then the letters at this level take decreasing values. When exhausted, the next lower slot will be the start of the next level, so subtract 1 to find it and append '1' to the bit-string to get the starting position for the next level. in the test map there is, say: 000002cf | 000019 | 11 | struct level: 17 000002d0 | 00001a | 15 50 00 00 | struct for 17 000002d4 | 00001e | 10 | struct level: 16 000002d5 | 00001f | 19 80 00 00 | struct for 16 000002d9 | 000023 | 0f | struct level: 15 000002da | 000024 | 1c c0 00 00 | struct for 15 The differences between the first byte after the level indicator ie 15, 19 & 1c) give 4 and 3, which are the number of letters at level 17 and level 16 Ticker On Mon, 2021-12-20 at 09:18 +0000, Gerd Petermann wrote:
Hi Ticker, please explain. What counters do you see? What do they mean?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 09:49 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Gerd
The tree is arranged so that letters at any level always have the highest values, ie come in from the right, and there are no gaps so no need for bit-flags. All it needs is the count of letters at each level to determine the tree.
For levels 7 to 18 this is consistent and the count can be determined from the first byte in the "struct for {level}".
Levels 19 and 20 are slightly out, but I think you found some strangeness here, including something indicate using Mdr3x data.
Level 6 count might be mixed into the following
I haven't been able to work out levels 1-5 yet, but somewhere would hope to find counts 0,0,1,7,9 maybe cumulative, maybe backwards, maybe without the first 2 values, maybe starting from the cumulative level 6 value.
Ticker
On Sun, 2021-12-19 at 21:12 +0000, Gerd Petermann wrote:
Hi Ticker,
my thought for the struct bytes was that the 1-bits might represent the position of leafs, but the bit counts don't match.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Sonntag, 19. Dezember 2021 10:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Gerd
It looks like the order of the letter patterns approaches canonical Huffman (but not quite as far as I can see). With this, only the number of codes of each length is required to form the tree.
The "struct for {level}" looks like 2 numbers. Both increasing as levels go from 20 to 6. The first, a single byte from #00 to #3d - this could be give the accumulated lengths at each level (but I didn't get it to match). The second, variable length, from #000006 to #180c00 and I've no idea what it could mean.
Levels 1 - 5 seem to be handled differently. with the repeat * 4, repeat * 2, no repeat and the padding.
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
_______________________________________________ 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
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev