22
$\begingroup$

Compress and Uncompress are used internally by Mathematica to compress things like 3D data in notebook files - data that I'd like to read independently. Does anyone have any idea if the compression algorithm is documented somewhere - Google reveals nothing of interest - or where I should start if I want to understand it?

$\endgroup$
  • $\begingroup$ The best I could find is: "The Compress function in Mathematica [...] is based on a mix of an LZ-like compression scheme and Huffman coding, called the Lempel-Ziv-Welch (LZW) algorithm; this same algorithm is at the base of the widespread gzip data compression software." (from here). See also these questions as commentary: Compress uses too much memory and Is Compress compatible across version? $\endgroup$ – MarcoB Jan 23 '16 at 0:07
  • 3
    $\begingroup$ The comment is incorrect (twice in a single sentence), in that LZW does not use Huffman coding, and that gzip does not use LZW to compress. $\endgroup$ – Mark Adler Jan 23 '16 at 0:43
  • 3
    $\begingroup$ Also I found that Compress[] is currently using zlib compression, not LZW. $\endgroup$ – Mark Adler Jan 23 '16 at 1:07
  • $\begingroup$ @MarkAdler +1 for your answer, but I think it is not the comment of MarcoB which is wrong but the content of what he is quoting. As the source seems to be from 2009 it might even be the case that it was correct back then. Have you checked whether this has changed from older versions? The real shame is that this is not more clearly documented... $\endgroup$ – Albert Retey Jan 23 '16 at 22:14
  • 1
    $\begingroup$ I was referring to the comment within the web page linked by the comment. Sorry if it appears as if I impugned MarcoB. As for my comment on the comment in the web page linked by the comment, the two things noted as wrong are forever wrong. They are not time dependent. My second comment may be time dependent, hence my use of "currently". If someone has an example of old Compress[]'ed data, then I can look at what it was using then. $\endgroup$ – Mark Adler Jan 23 '16 at 23:21
20
$\begingroup$

It is using the zlib format followed by Base64 coding, and then preceding the resulting string with "1:". So to use it externally, you can strip the "1:", do Base64 decoding, and feed the result of that to a zlib decoder.

However what you get out may not be immediately useful. I compressed the result of D[x^x, {x,9}], like one of the examples in the Compress[] documentation, and then decompressed (successfully) with zlib. I got what appears to be some sort of internal encoding. E.g. "!boRf" 0xa0, 0, 0, 0, "s", 0x04, 0, 0, 0, "Plusf", 0x03, ... (where the numbers are unprintable bytes).

If you want something interoperable, then use "GZIP" or "BZIP2" in ImportString and ExportString. For example, using a 100,000,000 byte excerpt of English from Wikipedia:

ExportString[enwik8,"GZIP"]//StringLength
36548933
ExportString[enwik8,"BZIP2"]//StringLength
29008736

Then you will also get to control the encoding of the data into a string to be compressed. And you can decide whether or not to encode the compressed data into a printable form, or leave it as binary.

$\endgroup$
  • $\begingroup$ Thank you! Python's zlib module decompresses it just fine. The binary format (magic !boRS) is indeed another internal undocumented thing, and neither Import[] nor TrID have any idea what it is. $\endgroup$ – Andy C. Jan 23 '16 at 10:00
  • $\begingroup$ It should be noted that Mark is in the best position to talk about zlib. ;) $\endgroup$ – J. M. will be back soon Nov 10 '17 at 13:59
20
$\begingroup$

After a bit of poking around, it looks like the binary format is pretty simple to parse. Mark Adler's answer is correct - the strings Compress[] returns are just zlib-compressed data. If you have Python installed, this function should take a compressed string and return the actual serialized bytes:

pyDecompress[c_] := StringDrop[StringDrop[StringTrim[RunProcess[{
  "python", "-c", 
  "import sys,zlib,base64; \
   print(zlib.decompress(base64.b64decode(sys.stdin.read().strip()[2:])))"
  }, "StandardOutput", c]], 2], -1]

Binary data starts with the header !boR (21 62 6f 52), followed by the serialized objects. There are apparently only eight types of objects that get serialized (unless I'm missing something):

  • Machine-precision integers up to 32 bits: i followed by a reversed (that is, little-endian encoded) 32-bit value. The integer 192635 (0x2f07b), for instance, gets encoded as 7b f0 02 00.

  • Strings: S followed by a reversed 32-bit value for size and the actual ASCII string. 8-bit non-ASCII characters are encoded as \\ followed by a three-digit number. It doesn't appear to be a Unicode offset (e.g. U+00BF encodes as 277, U+00C0 encodes as 300...). Everything else is encoded as UTF-16 in hexadecimal, preceded by \\: (e.g. U+057B becomes \\:057B and the astral plane character U+1F4A3 becomes \\:D83D\\:DCA3).

  • Symbols: encoded just like strings, but with the lowercase prefix s instead of S.

  • Arbitrary-precision integers: the actual base-10 digits encoded as a string, with the prefix I.

  • Machine-precision real numbers: r followed by a reversed IEEE binary64 encoded floating point number. 1.0/3.0, for instance, encodes to 55 55 55 55 55 55 d5 3f.

  • Arbitrary-precision real numbers: R followed by another string-style encoding: a reversed 32-bit length and the number in an expanded format. The number 13530274.2118781153, for instance, becomes the string 1.35302742118781153`17.131306598334415*^7.

  • Expressions: f followed by a reversed 32-bit value for the number of parts the expression has, the head of the expression encoded as a symbol, and the parts themselves. A[1,2], for instance, would be encoded as f<02 00 00 00>[A][3][12], with [A] being s<01 00 00 00>A, [3] being i<03 00 00 00> and [12] being i<0c 00 00 00>.

  • Real matrices: a special encoding is used for large (>249 values) n-dimensional matrices (that is, lists or nested lists) of machine-precision real numbers. Starts with e, followed by a reversed 32-bit value for the n number, n more values for each dimension and then the binary64 encoded real numbers themselves, without any spacing or prefixes. There doesn't seem to be an equivalent for integers or arbitrary-precision reals.

Update: here is my attempt at a JavaScript parser for this format. Requires a fairly new browser.

$\endgroup$
  • $\begingroup$ I think all of the reversed quantities are not "reversed" as such, but just stored in little-endian format. Probably on other platforms a big-endian coding would have been used instead. $\endgroup$ – Oleksandr R. Jan 24 '16 at 7:05
  • $\begingroup$ @OleksandrR. The format should be platform-independent - as mentioned in the question, it's used in notebook files to store 3D graphics. $\endgroup$ – Andy C. Jan 24 '16 at 9:39
  • 1
    $\begingroup$ The "1:" may be a version and/or endianess indicator. Oleksandr is correct in that calling those "reversed" is just a personal bias on your part. They are in the correct and proper little-endian order. (Note that the use of "correct and proper" is a personal bias on my part.) $\endgroup$ – Mark Adler Jan 24 '16 at 17:42
  • $\begingroup$ There isn't a separate representation for integer arrays? Can you try compressing a packed integer array, e.g. RandomInteger[100, {10, 5}]? This is interesting also because it is likely some sort of serialization of MathLink data (potentially even the exact same thing MathLink uses). It would be interesting to investigate that too (i.e. capture what MathLink is sending through the network when using TCP/IP). $\endgroup$ – Szabolcs Jan 24 '16 at 22:30
  • 1
    $\begingroup$ I tried to capture some MathLink traffic with tcpflow. It's not the same as what you decode from Compress. $\endgroup$ – Szabolcs Jan 25 '16 at 14:07

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.