1
$\begingroup$

I have a requirement to reduce the size of the request / response XML by compressing repetitive productID data in compatible tag.

My request / response xml looks something like below

<products>
   <id>
     2XZ
   </id>
   <compatible>
   2TR,07N,2TS,082,084,2TT,2TU,2TV,2TW,2TX,2TY,2TZ,2U0,2U1,2U2,2U3,2U4,081,083,2U5,2U6,2U7,2U8,2U9,2UA,2UB,2UC,2UD,2UE,2UF,2UG,2UH,2UI,012,014,015,016,2UJ,2UK,2UL,2UM,2UN,2UO,2UP,2UQ,2UR,2US,2UT,2UU,2UV,2UW,2UX,2UY,2UZ,2V0,2V1,2V2,2V3,2V4,2V5,2V6,2V7,2V8,2V9,2VA,2VB,2VC,2VD,2VE,2VF,2VG,2VH,2VI,2VJ,2VK,2VL,2VM,2VN,2VO,2VP,2VQ,2VR,2VS,2VT,2VU,2VV,2VW,2VX
   </compatible>
</products>

I was given a suggestion to use Huffman code to compress compatible list data.

What I am confused about is how would Huffman encoded data in the XML reduce the size of the request / response XML as the resulting stream of binary data in the compatible tag might just increase the length and size of XML.

Example: Huffman encoding first 2 product IDs generates a longer binary string Original String: 2TR,07N Encoded binary String: 11101100110100010101

So my XML will change from

<products>
   <id>
     2XZ
   </id>
   <compatible>
   2TR,07N
   </compatible>
</products>

TO:

<products>
   <id>
     2XZ
   </id>
   <compatible>
   11101100110100010101
   </compatible>
</products>

Am I missing something obvious here?

$\endgroup$
  • 4
    $\begingroup$ Every method of compression makes many inputs longer -- that's a fundamental fact. A good compression algorithm for your application makes most inputs shorter. That will in particular happen for short inputs, which is apparent from the way the methods work. $\endgroup$ – Raphael Jan 17 '16 at 10:34
  • 6
    $\begingroup$ Well if you're going to waste an entire character on every bit, it actually cannot get smaller using single-symbol Huffman coding since it cannot use fewer than one bit per symbol. $\endgroup$ – harold Jan 17 '16 at 13:52
  • $\begingroup$ You can always use a minimum-length one of​ ​ 0 || Huffman_encoded_data ​ and ​ 1 || raw_data , ​ so that lengths will never increase by more than one. ​ ​ ​ ​ $\endgroup$ – user12859 Jan 17 '16 at 14:12
  • $\begingroup$ If your characters are triplets maybe get rid of the comma? You are using XML - how reduntant... Anyway, for 3 letter strings any compression method will suffer overhead - there is no place to pack data or dictionary, but if your strings are like you gave, and separator is always there, you can try far better compression scheme arithmetic and dictionary at once. $\endgroup$ – Evil Jan 17 '16 at 17:02
  • $\begingroup$ Is there a reason why just compressing the XML to send it over the wire isn't an option? $\endgroup$ – Pseudonym Mar 30 '16 at 12:53
2
$\begingroup$

I cannot see the benefit of Huffman coding in XML. First, the coding dictionary of each symbol has to be known on the receiving end, i.e.

<dictionary><code symbol=",">01</code><code symbol="2">11</code>....</dictionary>

Second, the Huffman coded data should be represented as 8-bit data to be space efficient. For example, your Huffman code for 2TR,07N becomes &xECD1;&x50;. However, 8-bit data is incompatible to XML because a lot of symbols are reserved for tags "<>" or attributes ":=".

If you are free to use any compression technique, I would suggest gzipping your data and then encoding the 8-bit data as base64. In this case, the string (264 characters without comma)

2TR,07N,2TS,082,084,2TT,2TU,2TV,2TW,2TX,2TY,2TZ,2U0,2U1,2U2,2U3,2U4,081,083,2U5,2U6,2U7,2U8,2U9,2UA,2UB,2UC,2UD,2UE,2UF,2UG,2UH,2UI,012,014,015,016,2UJ,2UK,2UL,2UM,2UN,2UO,2UP,2UQ,2UR,2US,2UT,2UU,2UV,2UW,2UX,2UY,2UZ,2V0,2V1,2V2,2V3,2V4,2V5,2V6,2V7,2V8,2V9,2VA,2VB,2VC,2VD,2VE,2VF,2VG,2VH,2VI,2VJ,2VK,2VL,2VM,2VN,2VO,2VP,2VQ,2VR,2VS,2VT,2VU,2VV,2VW,2VX

will be encoded as (232 characters)

H4sIACSf+1YAAxXPS1ZCMRBF0b5jSeMlgmDTDyAKfuDVFZ3/QNg0zlrVqcrOmE9tWn22MZ/btB5a
mGeVol9d9Kf/NmpS19C9Fna6bvNSD1pprUc96VkvetVGW+30pn2bune7O32p2/67PnTQUXz1pW/9
6KSzOIuzOIuzOIuzOMMZznCGLf4VvrgfvvCFL3zhC1/4whe+8IUve/GEJzzhCU94whOe8IQnPOEJ
T3hyubsCdDvGCWABAAA=

It is worth noting that gzip has Huffman coding in design, and the base64 encoding is a common practice for embedding PNG images in HTML.

References:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.