[mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
From Gerd Petermann gpetermann_muenchen at hotmail.com on Wed Dec 22 08:43:10 GMT 2021
Hi Ticker,
I also thought that some bytes may tells us the uncompressed size or frequencies. I don't see any clear pattern so far...
Some number for the Adria Topo Map: (Mdr 16 length 212)
Uncompressed size: 1.582.655 (0x18263e) , compressed: 1029077 (0x0fb3d5)
Frequencies of the tree nodes:
'' 0x3 freq: 1 (0x1)
'%' 0x25 freq: 1 (0x1)
':' 0x3a freq: 1 (0x1)
';' 0x3b freq: 1 (0x1)
'�' 0xfd freq: 1 (0x1)
'¸' 0xb8 freq: 1 (0x1)
'?' 0x3f freq: 2 (0x2)
'`' 0x60 freq: 2 (0x2)
'„' 0x1e freq: 2 (0x2)
'Ž' 0x7d freq: 3 (0x3)
'’' 0x19 freq: 2 (0x2)
'Ä' 0xc4 freq: 2 (0x2)
'Ø' 0xd8 freq: 2 (0x2)
'Ú' 0xda freq: 1 (0x1)
'Û' 0xdb freq: 2 (0x2)
'_' 0x5f freq: 4 (0x4)
'{' 0x7b freq: 6 (0x6)
'“' 0x1c freq: 4 (0x4)
'É' 0xc9 freq: 4 (0x4)
'Ð' 0xd0 freq: 5 (0x5)
'Ö' 0xd6 freq: 5 (0x5)
'+' 0x2b freq: 7 (0x7)
'–' 0x13 freq: 12 (0xc)
'Á' 0xc1 freq: 6 (0x6)
'Ü' 0xdc freq: 9 (0x9)
'' 0x4 freq: 19 (0x13)
'!' 0x21 freq: 18 (0x12)
'ž' 0x7e freq: 15 (0xf)
'Æ' 0xc6 freq: 43 (0x2b)
'È' 0xc8 freq: 34 (0x22)
'Q' 0x51 freq: 80 (0x50)
'Š' 0x60 freq: 49 (0x31)
''' 0x27 freq: 95 (0x5f)
'Ë' 0xcb freq: 51 (0x33)
'/' 0x2f freq: 64 (0x40)
'&' 0x26 freq: 153 (0x99)
' ' 0x1f freq: 195 (0xc3)
'W' 0x57 freq: 294 (0x126)
'X' 0x58 freq: 422 (0x1a6)
'' 0x5 freq: 242 (0xf2)
'Y' 0x59 freq: 719 (0x2cf)
'"' 0x22 freq: 614 (0x266)
'' 0x6 freq: 842 (0x34a)
'*' 0x2a freq: 1905 (0x771)
'F' 0x46 freq: 4481 (0x1181)
',' 0x2c freq: 2126 (0x84e)
'(' 0x28 freq: 2537 (0x9e9)
')' 0x29 freq: 2558 (0x9fe)
'5' 0x35 freq: 6778 (0x1a7a)
'6' 0x36 freq: 6634 (0x19ea)
'-' 0x2d freq: 6588 (0x19bc)
'7' 0x37 freq: 5972 (0x1754)
'3' 0x33 freq: 7478 (0x1d36)
'8' 0x38 freq: 5832 (0x16c8)
'9' 0x39 freq: 5314 (0x14c2)
'0' 0x30 freq: 6539 (0x198b)
'4' 0x34 freq: 7203 (0x1c23)
'H' 0x48 freq: 12992 (0x32c0)
'1' 0x31 freq: 13281 (0x33e1)
'2' 0x32 freq: 8713 (0x2209)
'.' 0x2e freq: 10184 (0x27c8)
'G' 0x47 freq: 24930 (0x6162)
'Z' 0x5a freq: 23284 (0x5af4)
'U' 0x55 freq: 31985 (0x7cf1)
'P' 0x50 freq: 34866 (0x8832)
'B' 0x42 freq: 33286 (0x8206)
'C' 0x43 freq: 66619 (0x1043b)
'S' 0x53 freq: 71047 (0x11587)
'D' 0x44 freq: 37462 (0x9256)
'T' 0x54 freq: 53719 (0xd1d7)
'M' 0x4d freq: 40220 (0x9d1c)
'V' 0x56 freq: 63113 (0xf689)
'J' 0x4a freq: 44778 (0xaeea)
'K' 0x4b freq: 63856 (0xf970)
'L' 0x4c freq: 63057 (0xf651)
'' 0x0 freq: 108543 (0x1a7ff)
' ' 0x20 freq: 139214 (0x21fce)
'E' 0x45 freq: 99070 (0x182fe)
'N' 0x4e freq: 79383 (0x13617)
'O' 0x4f freq: 101405 (0x18c1d)
'I' 0x49 freq: 113012 (0x1b974)
'R' 0x52 freq: 95298 (0x17442)
'A' 0x41 freq: 181900 (0x2c68c)
Maybe you find something new?
Gerd
________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com>
Gesendet: Dienstag, 21. Dezember 2021 17:49
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Ticker,
looks good.
With your hints I was able to write a patch for MdrDisplay
that seems able to decode compressed mdr15 for my
maps which have mdr 16 section.
Maybe you have another map...
It also changes some details for mdr 30/31 and 32/33.
Open problem is the length of the gap between the end of data for the 6th level and the first bytes for level 5 (prefix 0b).
I see either 7 or 12 or 5 bytes. Check the code that calculdates value for variable skip.
The values might not at all depend on the depth of the tree.
Code is not at all optimized, it just started to work for me.
Lots of bytes in MDR 16 are ignored.
Gerd
________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com>
Gesendet: Montag, 20. Dezember 2021 11:29
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Ticker,
yes, with your theory I found errors in my code. Here's the corrected version
// depth 3, prefix 0x07
addHuffmanNode("111", 'A');
// depth 4, prefix 0x09
addHuffmanNode("0111", '\0'); // 0x00
addHuffmanNode("1000", ' '); //0x20
addHuffmanNode("1001", 'E');
addHuffmanNode("1010", 'N');
addHuffmanNode("1011", 'O');
addHuffmanNode("1100", 'I');
addHuffmanNode("1101", 'R');
// depth 5, prefix 0x0b
addHuffmanNode("00101", 'C');
addHuffmanNode("00110", 'S');
addHuffmanNode("00111", 'D');
addHuffmanNode("01000", 'T');
addHuffmanNode("01001", 'M');
addHuffmanNode("01010", 'V');
addHuffmanNode("01011", 'J');
addHuffmanNode("01100", 'K');
addHuffmanNode("01101", 'L');
// depth 6
addHuffmanNode("000101", 'G');
addHuffmanNode("000110", 'Z');
addHuffmanNode("000111", 'U');
addHuffmanNode("001000", 'P');
addHuffmanNode("001001", 'B');
// depth 7
addHuffmanNode("0000110", 'H');
addHuffmanNode("0000111", '1');
addHuffmanNode("0001000", '2');
addHuffmanNode("0001001", '.');
// depth 8
addHuffmanNode("00000011", '5');
addHuffmanNode("00000100", '6');
addHuffmanNode("00000101", '-');
addHuffmanNode("00000110", '7');
addHuffmanNode("00000111", '3');
addHuffmanNode("00001000", '8');
addHuffmanNode("00001001", '9');
addHuffmanNode("00001010", '0');
addHuffmanNode("00001011", '4');
// depth 9
addHuffmanNode("000000010", 'F');
addHuffmanNode("000000011",',');
addHuffmanNode("000000100", '(');
addHuffmanNode("000000101", ')');
// depth 10
addHuffmanNode("0000000011", '*');
// depth 11
addHuffmanNode("00000000011", 'Y');
addHuffmanNode("00000000100", '"');
addHuffmanNode("00000000101", (char) 0x06); // non-print4
// depth 12
addHuffmanNode("000000000011", 'W');
addHuffmanNode("000000000100", 'X');
addHuffmanNode("000000000101", (char) 0x05); //non-print some shield code
// depth 13
addHuffmanNode("0000000000100", '&');
addHuffmanNode("0000000000101", (char) 0x1f); //non-print2
// depth 14
addHuffmanNode("00000000000011", 'Q');
addHuffmanNode("00000000000100", 'Š');
addHuffmanNode("00000000000101", '\''); // mdr16 says 0x8a
addHuffmanNode("00000000000110", 'Ë');
addHuffmanNode("00000000000111", '/');
// depth 15
addHuffmanNode("000000000000100", 'Æ');
addHuffmanNode("000000000000101", 'È');
// depth 16
addHuffmanNode("0000000000000101", (char) 0x04); // non-print3
addHuffmanNode("0000000000000110", '!');
addHuffmanNode("0000000000000111", (char) 0x9e); //Ž
// depth 17
addHuffmanNode("00000000000000110",'+');
addHuffmanNode("00000000000000111", '–'); // different to minus mdr16: 0x96
addHuffmanNode("00000000000001000", 'Á'); //Á
addHuffmanNode("00000000000001001", 'Ü');
// depth 18
addHuffmanNode("000000000000000110", '_');
addHuffmanNode("000000000000000111", '{');
addHuffmanNode("000000000000001000", '“'); // mdr16: 0x93
addHuffmanNode("000000000000001001", 'É');
addHuffmanNode("000000000000001010", 'Ð');
addHuffmanNode("000000000000001011", 'Ö');
// depth 19
addHuffmanNode("0000000000000000011", '?');
addHuffmanNode("0000000000000000100", '`'); // mdr16: 0x60
addHuffmanNode("0000000000000000101", '„'); // mdr16: 0x84
addHuffmanNode("0000000000000000110", 'ž'); // mdr16: 0x8e
addHuffmanNode("0000000000000000111", '’'); // mdr16: 0x92
addHuffmanNode("0000000000000001000", 'Ä');
addHuffmanNode("0000000000000001001", 'Ø');
addHuffmanNode("0000000000000001010", 'Ú');
addHuffmanNode("0000000000000001011", 'Û');
// depth 20
addHuffmanNode("00000000000000000000", '#'); // offset into MDR 30/31? MapSource displays "HWY "
addHuffmanNode("00000000000000000001", '%'); //
addHuffmanNode("00000000000000000010", ':');
addHuffmanNode("00000000000000000011", ';');
addHuffmanNode("00000000000000000100", (char) 0x8f);
addHuffmanNode("00000000000000000101", (char) 0xb8);
Gerd
________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com>
Gesendet: Montag, 20. Dezember 2021 10:59
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at 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 at lists.mkgmap.org.uk> im Auftrag von
> Ticker Berkin <rwb-mkgmap at 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 at lists.mkgmap.org.uk> im Auftrag
> > von Ticker Berkin <rwb-mkgmap at 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 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
> _______________________________________________
> 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
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
- Previous message: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
- Next message: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list