Changeset 30490 in osm for applications/editors/josm/plugins/pbf/src

Timestamp:

2014-06-09T18:08:08+02:00 (11 years ago)

Author:

donvip

Message:

[josm_pbf] upgrade to protoc 2.5.0 and crosby.binary 1.3.3

Location:

applications/editors/josm/plugins/pbf/src/crosby/binary

Files:

• BinaryParser.java (modified) (2 diffs)
• StringTable.java (modified) (5 diffs)
• fileformat.proto (added)
• osmformat.proto (added)

applications/editors/josm/plugins/pbf/src/crosby/binary/BinaryParser.java

@@ -55 +55 @@
     }
     
-    //@Override
+    @Override
     public void handleBlock(FileBlock message) {
         // TODO Auto-generated method stub
@@ -77 +77 @@
 
 
-    //@Override
+    @Override
     public boolean skipBlock(FileBlockPosition block) {
         // System.out.println("Seeing block of type: "+block.getType());

applications/editors/josm/plugins/pbf/src/crosby/binary/StringTable.java

@@ -2 +2 @@
 
    This program is free software: you can redistribute it and/or modify
-   it under the terms of the GNU Lesser General Public License as 
-   published by the Free Software Foundation, either version 3 of the 
+   it under the terms of the GNU Lesser General Public License as
+   published by the Free Software Foundation, either version 3 of the
    License, or (at your option) any later version.
 
@@ -46 +46 @@
 
     /** After the stringtable has been built, return the offset of a string in it.
-     * 
+     *
      * Note, value '0' is reserved for use as a delimiter and will not be returned.
      * @param s
@@ -57 +57 @@
     public void finish() {
         Comparator<String> comparator = new Comparator<String>() {
-            //@Override
+            @Override
             public int compare(final String s1, String s2) {
                 int diff = counts.get(s2) - counts.get(s1);
@@ -63 +63 @@
             }
         };
+
+        /* Sort the stringtable */
+
+        /*
+        When a string is referenced, strings in the stringtable with indices:
+               0                : Is reserved (used as a delimiter in tags
+         A:  1 to 127          : Uses can be represented with 1 byte
+         B: 128 to 128**2-1 : Uses can be represented with 2 bytes,
+         C: 128*128  to X    : Uses can be represented with 3 bytes in the unlikely case we have >16k strings in a block. No block will contain enough strings that we'll need 4 bytes.
+
+        There are goals that will improve compression:
+          1. I want to use 1 bytes for the most frequently occurring strings, then 2 bytes, then 3 bytes.
+          2. I want to use low integers as frequently as possible (for better
+             entropy encoding out of deflate)
+          3. I want the stringtable to compress as small as possible.
+
+        Condition 1 is obvious. Condition 2 makes deflate compress stringtable references more effectively.
+        When compressing entities, delta coding causes small positive integers to occur more frequently
+        than larger integers. Even though a stringtable references to indices of 1 and 127 both use one
+        byte in a decompressed file, the small integer bias causes deflate to use fewer bits to represent
+        the smaller index when compressed. Condition 3 is most effective when adjacent strings in the
+        stringtable have a lot of common substrings.
+
+        So, when I decide on the master stringtable to use, I put the 127 most frequently occurring
+        strings into A (accomplishing goal 1), and sort them by frequency (to accomplish goal 2), but
+        for B and C, which contain the less progressively less frequently encountered strings, I sort
+        them lexiconographically, to maximize goal 3 and ignoring goal 2.
+
+        Goal 1 is the most important. Goal 2 helped enough to be worth it, and goal 3 was pretty minor,
+        but all should be re-benchmarked.
+
+
+        */
+
+
 
         set = counts.keySet().toArray(new String[0]);
@@ -71 +106 @@
           // sorted lexiconographically.
           // to maximize deflate compression.
-          
+
           // Don't sort the first array. There's not likely to be much benefit, and we want frequent values to be small.
           //Arrays.sort(set, Math.min(0, set.length-1), Math.min(1 << 7, set.length-1));
-          
+
           Arrays.sort(set, Math.min(1 << 7, set.length-1), Math.min(1 << 14,
               set.length-1));