Comparison of compression

I recently wrote an email with an attached LZMA archive. It was immediately answered with something like:

What are you doing? I had to boot linux to open the file!

First of all I don’t care whether user of proprietary systems are able to read open formats, but this answer made me curious to know about the differences between some compression mechanisms regarding compression ratio and time. So I had to test it!

This is nothing scientific! I just took standard parameters, you might optimize each method on its own to save more space or time. Just have a look at the parameter -1..-9 of zip. But all in all this might give you a feeling for the methods.

Candidates

I’ve chosen some usual compression methods, here is a short digest (more or less copy&paste from the man pages):

• gzip: uses Lempel-Ziv coding (LZ77), cmd: tar czf $1.pack.tar.gz$1
• bzip2: uses the Burrows-Wheeler block sorting text compression algorithm and Huffman coding, cmd: tar cjf $1.pack.tar.bz2$1
• zip: analogous to a combination of the Unix commands tar(1) and compress(1) and is compatible with PKZIP (Phil Katz’s ZIP for MSDOS systems), cmd: zip -r $1.pack.zip$1
• rar: proprietary archive file format, cmd: rar a $1.pack.rar$1
• lha: based on Lempel-Ziv-Storer-Szymanski-Algorithm (LZSS) and Huffman coding, cmd: lha a $1.pack.lha$1
• lzma: Lempel-Ziv-Markov chain algorithm, cmd: tar --lzma -cf $1.pack.tar.lzma$1
• lzop: imilar to gzip but favors speed over compression ratio, cmd: tar --lzop -cf $1.pack.tar.lzop$1

All times are user times, measured by the unix time command. To visualize the results I plotted them using R, compression efficiency at X vs. time at Y. The best results are of course located near to the origin.

Data

To test the different algorithms I collected different types of data, so one might choose a method depending on the file types.

Binaries

The first category is called binaries. A collection of files in human-not-readable format. I copied all files from /bin and /usr/bin , created a gpg encrypted file of a big document and added a copy of grml64-small_2010.12.iso. All in all 176.753.125 Bytes.

MethodCompressed Size% of originalTime in s
gzip161.999.80491.6510.18
bzip2161.634.68591.4571.76
zip179.273.428101.4313.51
rar175.085.41199.06156.46
lha180.357.628102.0435.82
lzma157.031.05288.84129.22
lzop165.533.60993.654.16

Media

This is a bunch of media files. Some audio data like the I have a dream-speech of Martin-Luther King and some music. Also video files like the The Free Software Song and Clinton’s I did not have sexual relations with that woman are integrated. I attached importance to different formats, so here are audio files of the type ogg, mp3 mid, ram, smil and wav, and video files like avi, ogv and mp4. Altogether 95.393.277 Bytes.

MethodCompressed Size% of originalTime in s
gzip88.454.00292.736.04
bzip287.855.90692.1037.82
zip88.453.92692.736.17
rar87.917.40692.1670.69
lha88.885.32593.1814.22
lzma87.564.03291.7974.76
lzop90.691.76495.072.28

Office

The next category is office. Here are some PDF from different journals and office files from LibreOffice and Microsoft’s Office (special thanks to @chschmelzer for providing MS files). The complete size of these files is 10.168.755 Bytes.

MethodCompressed Size% of originalTime in s
gzip8.091.87679.580.55
bzip28.175.62980.408.58
zip8.092.68279.580.54
rar7.880.71577.503.72
lha8.236.42281.003.29
lzma7.802.41676.735.62
lzop8.358.34382.200.21

Pictures

To test the compression of pictures I downloaded 10 files of each format bmp, eps, gif, jpg, png, svg and tif. That are the first ones I found with google’s image search engine. In total 29’417’414 Bytes.

MethodCompressed Size% of originalTime in s
gzip20.685.80970.321.65
bzip218.523.09162.9710.71
zip20.668.60270.261.72
rar18.052.68861.378.58
lha20.927.94971.145.97
lzma18.310.03262.2421.09
lzop23.489.61179.850.57

Plain

This is the main category. As you know, ASCII content is not saved really space efficient. Here the tools can riot! I downloaded some books from Project Gutenberg, for example Jules Verne’s Around the World in 80 Days and Homer’s The Odyssey, source code of moon-buggy and OpenLDAP, and copied all text files from /var/log . Altogether 40.040.854 Bytes.

MethodCompressed Size% of originalTime in s
gzip11.363.93128.381.88
bzip29.615.92924.0213.63
zip12.986.15332.431.6
rar11.942.20129.838.68
lha13.067.74632.648.86
lzma8.562.96821.3930.21
lzop15.384.62438.420.38

Rand

This category is just to test random generators. Compressing random content shouldn’t decrease the size of the files. Here I used two files from random.org and dumped some bytes from /dev/urandom. 4.198.400 Bytes.

MethodCompressed Size% of originalTime in s
gzip4.195.64699.930.23
bzip24.213.356100.361.83
zip4.195.75899.940.2
rar4.205.389100.171.65
lha4.194.56699.912.04
lzma4.197.25699.971.98
lzop4.197.13499.970.1

Everything

All files of the previous catergories compressed together. Since the categories aren’t of same size it is of course not really fair. Nevertheless it might be interesting. All files together require 355.971.825 Bytes.

MethodCompressed Size% of originalTime in s
gzip294.793.25582.8120.43
bzip2290.093.00781.49141.89
zip313.670.43988.1223.78
rar305.083.64885.70246.63
lha315.669.63188.6864.81
lzma283.475.56879.63258.05
lzop307.644.07686.427.89

Conclusion

As you can see, the violet lzma-dot is always located at the left side, meaning very good compression. But unfortunately it’s also always at the top, so it’s very slow. But if you want to compress files to send it via mail you won’t bother about longer compression times, the file size might be the crucial factor. At the other hand black, green and grey (gzip, zip and lzop) are often found at the bottom of the plots, so they are faster but don’t decrease the size that effectively.

All in all you have to choose the method on your own. Also think about compatibility, not everybody is able to unpack lzma or lzop.. My upshot is to use lzma if I want to transfer data through networks and for attachments to advanced people, and to use gzip for everything else like backups of configs or mails to windows user.

A Synapt - or something like that...

As I mentioned, our university bought a Synapt G2 HDMS with an upstream 2D-UPLC. And what should I say, we are not amused.. But let’s start with the good things.

The innovative

As far as I know Waters is the first manufacturer who joined the IMS- and QTOF-technologies to combine all well known benefits from the QTOF instruments plus the advantages of separating ions by their shape and size. They developed a Triwave technology, consisting of a trap cell, the new IMS cell and a transfer cell. Trap and transfer cell are able to fragment the ions, so you can produce fragment ions before and/or after separation by ion mobility. Producing fragments is nothing new, most of the MS instruments out there are able to do so. The innovation is located at the IMS. In front of this cell you can find a Helium chamber, working as a gate. During an IMS cycle no further ions are able to pass this gate. The IMS cell itself is flooded with nitrogen. Ions that want to pass this cell interact with those nitrogen molecules, so they will slow down. The bigger the ionshape the higher the braking force of nitrogen.

The energy inside isn’t that high that ions decay to further fragments. The energy beam transporting the ions through the IMS cell can be understood as a wave. You can define the wave height and the velocity to effectively separate your present ions. Don’t ask me why the call it height and velocity, and not amplitude and frequency, but what ever ;-) Waters provides some videos to visualize this technology, and here you can find some smart pictures of the Triwave system in a Synapt.

If you now think about an 4m IMS cell take a look at figures 2 and 3, it’s a bit more than half of a keyboard length.

The other very cool thing is their UPLC. Never seen a two-dimensional LC! In one dimension you’ll find one C18 column to separate your complex sample. With this UPLC you can also trap species in columns with different pH values, so they are also separated by their different pH-column-interactions. This is really great if you want to analyze incredible complex samples.

Looking at these very cute technologies, what are we arguing about!?

The annoying

First of all, the sales process did not run as smoothly as one might expect and took a very long time. But since I wasn’t involved I can’t tell you anymore.

The first thing we recognized when the machine arrived was a 4kDa RF generator. But we ordered a 8kDa generator! How could this happen? Waters guarantees that each instrument will be tested before it leaves their plant.. The next thing followed immediately. All configurations of the EPC were lost.. While delivering! Seems that the postman is a pickpocket..

And, to carry it too far, within the first tests the IMS cell crashed unrecoverably, have a look at figures 2 and 3. So we had to wait for a new one from Manchester. To also name the positives, the shipment took less then one day.

Even if some innocent people think they can operate a MS (who told them!? hope they got paid), it took the technicians about six weeks to get the Synapt operating… Always arguing about nano-ESI… They had big problems to install the 2D-LC, the peaks still look freaky tailing… (I don’t want to run down the technicians, they were always very committed and tried to help us as far as possible!)

Ok, so far, all is not lost if we can operate now! But can we?

For calibration you need exact masses. Calculating masses of molecules isn’t a problem for waters, but adding a proton (H+) is! Instead of a proton they add a hydrogen (H+ + e-)!? Assume you want to calibrate with Leucine Enkephaline (Leu-Enk). Leu-Enk is a peptide whose sequence is Tyr-Gly-Gly-Phe-Leu (C28H37N5O7) with a mass of $555.269297\text{u}$. Adding a proton results in a single charged ion with a mass of (Adam Ries told us!): $555.269297\text{u} + 1.007276\text{u} = 556.276573\text{u}$ When they add a hydrogen their mass becomes: $555.269297\text{u} + 1.007825\text{u} = 556.277122\text{u}$, that’s a diff of $0.000549\text{u}$ (it’s the mass of an electron). Seems to be small, but think in ppm: $\frac{0.000549\text{u} \cdot 10^6 }{555.269297\text{u}} \approx 0.9887\text{ppm}$. A systematic discrepancy of almost 1 ppm for an instrument specified for 1 ppm precision. Just because of a calculation error! And things become even worse at higher charge states, compare to the green part of figure 4. Do we (stupid scientists) really have to help them (MS specialists) summing up?

Playing a bit with the machine we figured out, that it is not constructed for static measurements. We had to be creative to get some backpreasure. You also have to unmount the whole static source block to load the needle with sample. Yes, they have these fluidics, but we have samples of few μl. Ok, prepared the system with some more handwork for static measurments, the results were disgusting. The acquired spectra had errors of more than 50 ppm (read box in figure 4)!? Calling Waters we found out that this is a known bug… Even if the acquisition-window leads to believe that the machine is calibrated and provides a button to start an acquisition, acquisitions have to be started from the MassLynx sample list. Not enough hands for face palms! It’s very complicated to create a sample for each static measurement, since you have to create a new method for each sample! Also the technicians weren’t able to tell us a lot about the working principle with IMS. But we, of course, want to try some things before running 9h experiments through LC just to see that the actual parameters for the IMS are crap…

Last but not least, they are not very cooperative when we call to tell them their faults…

If the policy of their company doesn’t change I don’t believe that we buy further instruments from Waters… Looking at the price for the machine I think buying some big cars to impress the girls would have been a much better investment ;-)

Very first time with a Synapt

Yesterday I had my first date with a SYNAPT™ from Waters. A workgroup from the biocentrum bought one, this week it was delivered.

So what’s a SYNAPT™? I would say it’s actually the cream of the crop of mass spectrometry platforms. It primarily differs from other platform in the feature of separation in terms of ion mobility.

Common platforms like QTof’s might distinguish between two peptides based on their mass, so they are separated in an Quadrupole, their mass over charge (m/z) is afterwards measured by their TOF. But there is a challenge with isobars. Since they have the same mass you’ll only get one peak for all of them. You are not able to differentiate between different elementary compositions with equal masses.

Waters now brings light to the dark. They developed a very new dimension of discovery. Their Triwave™ Technology allows you to dissolve different shapes of ions with equally mass. Actually I can’t tell you how it works, but take two sheets of paper, crush one of it and throw both out of your window. You see, there are some physics that let one of these papers reach the ground faster than the other one. With the SYNAPT™ you are able to distinguish between elements in your sample based on their shape.

With the upstream UPLC a species gives a peak in an spectrum, specified by retention time, m/z, shape and intensity. A new challenge to analyze and evaluate the resulting data.

(Fortunately) there was a small problem with the machine, so I was able to take a look inside. It was amazing to see the guts of this big box, stuffed with filigree technique!!

I think I felt in love with this machine.. Bad news for my wife, but that’s life ;-)

ShortCut[RegEx]: x-modifier

Independent of your programming experiences, you should have learned that regular expressions are more or less write-only.

Write-only? What is he talking about!? Actually I revisited some Perl code with a relatively short reg-ex. Do you think I was able to understand what I’ve thought when I created that piece of code? Not in the slightest!

But there is a smart modifier, that enables you to comment your regular expressions: x. With /x all white-spaces are ignored and with an unescaped # the rest of the line is treated as a comment. I found a nice example, what do you think is this expression for:

No idea? Don’t even bother, I’m also stumped… Here is the solution: It’s used to check for prime numbers ;-) Using the x-mod the explanation looks much more readable (via Neil Kandalgaonkar):

So you see, it’s really helpful to use the x-modifier. At least for your own understanding :-P

A bit more explanation can be found on Perl.com.

Talking R through Java

Today I played a bit with JRI as part of rJava, a Java-R-interface. Here you can learn how to setup for Debian/Ubuntu/akins.

Installation

Assuming you have a running version of Java and GNU’s R, you have to install r-cran-rjava :

Shell environment

To talk to R through Java you have to specify three more environmental variables. First of all you need to publish you R installation path, my R is found in /usr/lib64/R :

If you didn’t or the path is wrong you’ll fall into trouble:

Second the $CLASSPATH needs to get an update. Precisely you have to add the archives JRIEngine.jar , JRI.jar and REngine.jar . In my case all of them can be found in /usr/lib/R/site-library/rJava/jri/ , so the $CLASSPATH should be set like that:

If the $CLASSPATH isn’t defined correctly you won’t be able to compile your Java code. Last but not least you have to add the native JRI-library to your $LD_LIBRARY_PATH , by default this lib is located in the same directory like the jar’s:

Netbeans setup

Two of these three parts are also straight forward in Netbeans. First publish the location of the jar’s. Right-click on your project and choose Properties > Libraries. In the Compile-tab click Add JAR/Folder and search for the jar files. Next task is to adjust the library-path. Right-click on your project and choose Properties > Run. Add -Djava.library.path=.:/usr/lib/R/site-library/rJava/jri/ to the VM Options (modify the path to match your criteria). The third step is a little tricky. As far as I know there is no way to change the environment from within Netbeans, so you can’t create the variable R_HOME after Netbeans is started. In my opinion you have two options:

1. Export the variable before starting Netbeans:

you might want to write a wrapper script that does this step for you, or include the export in any of the resource files that are called before Netbeans starts (e.g. your .bashrc ).

1. Change the environment from within your project. At stackoverflow you can find a workaround, but I think this is a very lousy solution..

If you have further suggestions please let me know! Meanwhile George Bull published a setup guide for Netbeans on Windows hosts. Seems to be worthy to take a look at it ;-)

Testcase

If you defined your environment properly, you should be able to utilize the REngine. I have a small script for you to test whether all things are fine:

You should be able to compile and run it, afterwards you’ll see a random number from an uniform distribution. Congratulations, well done :-P

I have bad news for those of you trying to produce lucid code!

In his blog Radford M. Neal, Professor at the University of Toronto, published an article with the headline Two Surprising Things about R. He worked out, that parentheses in mathematical expression slow down the run-time dramatically! In contrast it seems to be less time consuming to use curly brackets. I verified these circumstances to be true:

As you can see adding extra parentheses is not really intelligent concerning run-time, and not in a negligible way. This fact shocked me, because I always tried to group expressions to increase the readability of my code! Using curly brackets speeds up the execution in comparison to parentheses. Both observations are also surprising to me! So the conclusion is: Try to avoid redundant parentheses and/or brackets!

To learn more about the why you are referred to his article. He also found a interesting observation about squares. In a further article he presents some patches to speed up R.

Damn scoping in R

Ok, R is very well-considered in certain respects, but there are also some things annoying me… This time it’s scoping…

Let’s have a look to the following code:

First it looks damn unspectacular. But wait, whats that:

Taking a closer look to the function shows that the returned value is randomly chosen from local ( runif(1) > .5 ) or global scope ( runif(1) <= .5 ). So you can’t expect a result from this function. Nasty, especially while debugging external code, isn’t it? :-)

So again my advise: Think about such specific features! This won’t happen in any sensible language…

Auth issues

Sitting on an almost well configured host, I experienced some authentication issues the last few days…

So for example I’m using xtrlock as default X locking mechanism, but if I try to run it on this machine I got the following error:

Mmh, that is crap. My workaround to temporarily avoid this problem: Connecting to another host via SSH, running xtrlock within a GNU screen session ;-) But that’s no solution for a longer time… So I started debugging. First of all I grabbed the sources from the apt repository and searched for this error message. Turned out to be this piece of code (beginning with line 94 of xtrlock.c ):

Ok, seems that the provided password(-hash) is shorter than 13 characters… Going on debugging, the content of pw comes from getpwuid(getuid()) and seems to be ok (matches my users profile like it can be found in /etc/passwd ). At this time (line 1) pw->pw_passwd contains only an single x , more information can’t be retrieved from the passwd -file.. Next the code checks whether SHADOW_PWD is defined, means whether we use an additional shadow -file. Since thats the case this code is executed and the variable sp gets the broken-out fields of the record in the shadow password database that matches the username pw->pw_name (validated, my user). Checking this sp variable I recognized that it is null ! So pw->pw_passwd won’t be updated and still contains the single x from the passwd entry… First I thought about a bug in the getspnam () function, such things might happen due to the Debian unstable release I’m using, but after some further thoughts I checked the shadow file itself:

In comparison with other systems with working xtrlock instances I figured out, that this file shouldn’t only be owned by root. Instead the group has to be shadow! So here is the solution to this issue:

And everything is working fine again. Have no idea what or who changed the permissions for the shadow-file…

Update: By the way, afterwards I tried to use Xscreensaver instead of xtrlock, but I wasn’t able to unlock the screen when the shadow rights are wrong. The /var/log/auth.log held messages like that:

But this is just for google-searchers ;-)

Open Source DNA

Yesterday I was a bit confused when I read this tweet. Manu Sporny, founder and CEO of Digital Bazaar, announced in his blog that he has published his genome..

He send some saliva to 23andme, they analyzed his DNA and provided his genetic code to him (let’s neglect the discussion whether data from 23andme-chips represent a fully sequenced genome..). This process is very smart and not expensive, so this part of his announcement is not spectacular. Lot’s of people are doing so.

The interesting part of this article: He published the results (roughly 1 million SNP markers) from 23andme as open source project to github, licensed under CC0! So he has released all his rights on this data.

In general a very impressing step, he might be the first person who published its DNA under such a license. His intentions are more than exemplary, providing access to genetic data to everyone that wants to work with it, i.e. researchers.

So far, so good, but there are some disadvantages, he still dealt with some of it. For example, what if anybody uses this information against him? I.e. healthcare provider, they might deny him to avoid high costs because they detected some pre-existing conditions in his DNA. It may also affect employment and can lead to discrimination. His reaction:

I’ve thought long and hard about each of those questions and the many more that you ask yourself before publishing this sort of personal data. There are large privacy implications in doing this. However, speaking solely for myself, I think the benefits outweigh the drawbacks.

Very nice, but there are also some ugly implications he apparently didn’t thought about! All these disadvantages don’t only affect himself, they may also affect relatives (children, parents, siblings..). Did they all agree with this publication?

I can’t see the advantages to an anonymously publication. Attach some demographic information like age, gender, educational background and everyone is satisfied. Then you don’t have to bear any consequences with bugs in your DNA.

With all due respect for his engagement, I think this step is not really sophisticated.

Valentine's Day

Yes, it’s that time again, Feb 14th.. It’s Valentine’s Day.

Don’t know who has told my wife, but now I have to do some love, uuurgh..

How ever, this one is for my little valentine:

Love you soo much, of course! ;-)

PS. If you are able to catch one of these flower or praline seller: beat the living daylights out of them!!