Slashdot Log In
Jean-loup Gailly On gzip, go, And Mandrake
from the ships-and-sealing-wax-and-kings-and-Linux dept.
1) bzip2 Support
by Aaron M. Renn
When is gzip going to provide (transparent) support for bzip2 files and the Burrows-Wheeler algorithm?
Will BW be an algorithm option within the gzip file format itself ever?
Gailly:
I have worked very closely with Julian Seward, the author of bzip and bzip2. The goal was to integrate a Burrows-Wheeler algorithm inside zlib 2.0 (upon which gzip 2.0 is based). One of the requirements was to avoid the kind of arithmetic coding used in bzip because of both patent and decoding speed concerns, so Julian wrote the Huffman coding code now used in bzip2. Another requirement was to put the code in library form and Julian did that too.
Unfortunately, Julian decided to release bzip2 independently instead of staying within the gzip 2.0 project. It was mainly my fault, since I couldn't spend enough time on the other parts of the project, and the project was not advancing fast enough. Since Julian left, the project progressed even more slowly, and new blood is obviously necessary, because other responsibilities no longer leave me enough time for gzip. If you're an expert in data compression, e-mail me to convince me that you are the most qualified person to turn the zlib/gzip 2.0 project into an overwhelming success :-)
2) The Data Compression Book
by drudd
I am a happy owner of The Data Compression Book (2nd Ed). With the increasing availability of compression routines within libraries (Java's GZIP streams spring to mind), does this make your book a little unnecessary?
Should software authors continue to write their own compression routines, or simply trust the versions available to them in library form?
I can see some definite advantages to library code, i.e. the ability to upgrade routines, and having standardized algorithms which can be read by any program which utilizes the library.
Gailly:
The compression routines in The Data Compression Book were written mainly for clarity, not for efficiency. The source code is present to help understand how the compression algorithms work. It is not designed to be used as is in other software packages, although it does work if efficiency is not a concern. Consider the book as teaching material, not as a data compression library distributed in printed form.
This doesn't mean that the book is unnecessary. Good data compression libraries don't appear magically; their authors had to learn compression techniques one day. If the book helps one person to get started in the data compression area and this person later writes a great compression library, the book will have been useful.
Judging by the success of my zlib data compression library, I think that a vast majority of software authors prefer using an existing library rather than reinventing the wheel. This is how the open-source model works: building upon the work of others is far more efficient than rewriting everything.
3) Compression patents
by Stephen
The compression world has many patents, notably for Lempel-Ziv compression as used in GIF. What is your view on companies patenting non-obvious algorithms for such processes as data compression?
Gailly:
The worst problem is companies patenting obvious algorithms. There are far more patents on obvious ideas than patents on really innovative ideas. In the data compression area, even something as basic as run-length encoding (replace "aaaaa" with a special code indicating repeat "a" 5 times) has been patented at a time where this technique had been well known and widely used for many years.
It is distressing to see the U.S. patent office granting such patents, in contradiction with the law requiring an idea to be both novel and non-obvious to be patentable. Philip Karn has made a good analysis of the problem.
Patents on non-obvious algorithms are a different matter. One view is that algorithms should not be patentable at all, whether obvious or not. This used to be the case, until the US patent office started to grant patents on methods which were nothing else than pure algorithms. I'm afraid that a switch back to the original situation is extremely unlikely.
Several reforms are necessary:
- The patent term should be significantly shortened, at least for algorithms. The patent system was designed to benefit society as a whole, ensuring that new ideas would eventually be made public after a limited period of time instead of being kept as trade secrets. But 20 years is incredibly long in the software area. Granting a monopoly for such a long time no longer benefits society.
- The non-obviousness requirement should be applied much more strictly. A little bit of common sense would avoid a lot of patents on trivial ideas.
- Prior art should be checked more thoroughly. Even non-obvious ideas should not be patented if they have been in use for several years already.
4) A question about Mandrake...
by Mr. Penguin
As we all know, at first Mandrake was little more than a repackaged version of Red Hat. That's changed a bit with the newer versions. My question is this: to what degree will Mandrake continue to differ from RedHat and will there ever be a "developer" version (i.e. one that is centered towards those who are a bit more technically competant)?
Gailly:
That's changed more than a bit. Our distribution is now completely made by us. Believe me, doing everything ourselves represents a significant amount of work. Few people understand how much work is involved in making an independent distribution. We have our own development teams producing things like our graphical install DrakX, our disk partionner DiskDrake, management of security levels in msec, hardware detection with Lothar, etc... Our packages are more recent than those of Red Hat and have more functionality (such as supermount support in the kernel). Red Hat is now even copying packages made by MandrakeSoft (e.g. rpmlint). I hate having to speak like a salesman here, but it is really unfair to say that Mandrake just repackages RedHat; this is simply not true anymore.
Have you looked at Linux-Mandrake 7.0? It does include a developer version. At install time, select the option "Custom" then "Development". You will get all necessary development tools. We, as developers, use our own distribution :-)
5)Why is Mandrake better than Red Hat?
I guess that you have at least a little something to say about this.
Is the 586 optimization enough to justify Mandrake's position? Are you especially proud of any of the architectural differences between the distributions (from what I have been told, the Apache-PHP layout is quite a bit different).
How do feel about the steps that Red Hat has taken to change their distribution in reaction to yours?
Gailly:
Mandrake is far more than Red Hat plus 586 optimization. It is an independent distribution. (See the answer to A question about Mandrake above.) We have enhanced some packages (such as the kernel or Apache) to provide additional functionality for users.
It's clear that Mandrake pushes Red Hat to improve its own version and nowdays Red Hat includes some development from Mandrakesoft. There is a coopetition: Red Hat and MandrakeSoft both benefit from the same open-source community, but they compete for the customer. This coopetition is fully beneficial for the Linux users since we both need to constantly improve our version. We just make sure that Mandrake stays ahead :-)
6)Winzip
by Uruk
I noticed that you allowed the people who make the Winzip product to incorporate code written for Gzip. I think it's cool that you did that, because it would be horrible if winzip couldn't handle the gzip format, but at the same time, what are your thoughts about allowing free software code to be included in closed-source products?
Just out of curiosity, (tell me it's none of my business if you want to and I'll be OK with that) did you receive a licensure fee from the company that makes Winzip for the code?
Gailly:
I started writing compression code simply because my 20 MB hard disk, the biggest size one could get at the time, was always full. I didn't write it for money. Even after I got a bigger hard disk, I continued writing compression code for fun. In particular I was not interested in writing a Windows interface. This is why I allowed my code to be used in Winzip. I received exactly 0$ for this.
The zlib license also allows it to be used in closed-source products. This was an absolute requirement for the success of the PNG image format, which relies on zlib for data compression. If we had used a GPL license, Netscape and Microsoft Explorer wouldn't support PNG, and the PNG format would be dead by now. I also received 0$ for zlib, if you're curious...
Even though I allowed my code to be used in closed-source products, I am a strong supporter of the open-source model. That's also why I work for MandrakeSoft. The open-source model is getting so much momentum that it will in the end dominate the software industry.
7) What about wavelets? by Tom Womack
The Data Compression Book was an excellent reference when it came out, but there are some hot topics in compression that it doesn't cover - frequency-domain lossy audio techniques (MP3), video techniques (MPEG2 and especially MPEG4), wavelets (Sorenson video uses these, I believe, and JPEG2000 will), and the Burrows-Wheeler transform from bzip.
Do you have any plans for a new edition of the book, or good Web references for these techniques? BZip is covered well by a Digital research note, but documentation for MPEG2 seems only to exist as source code and I can't find anything concrete about using wavelets for compression. The data is all there on the comp.compression FAQ, but the excellent exposition of the book is sorely lacking.
Gailly:
These are all very worthy topics, and Mark Nelson and I would like to incorporate them into a new version of the book someday. However, the decision to produce a new version is taken by the publisher, not us.
Note also that these are all very big topics, and it would be quite easy to write an entire book on each one. I don't think they will fit well in a chapter or two. Covering JPEG in one chapter was difficult, and Mark Nelson has been criticized for not describing the specifics of the standard algorithm.
You can find some Web references here and there, in addition to the comp.compression FAQ.
8) Compression software
by jd
It is a "truism" in the Free Software community that code should be released early and released often.
However, much of the software you've written has started gathering a few grey hairs. Gzip, for example, has been at 1.2.4 for many, many moons, and looks about ready to collect it's gold watch.
Is compression software in a category that inherently plateus quickly, so that significant further work simply isn't possible? Or is there some other reason, such as Real Life(tm) intruding and preventing any substantial development?
(I noticed, for example, a patch for >4Gb files for gzip, which could have been rolled into the master sources to make a 1.2.5. This hasn't happened.)
Gailly:
I knew this question would come when I accepted a Slashdot interview. But I had to face it :-(
In short, you are completely right. While working on gzip 2.0, I continued to maintain gzip 1.x, accumulating small patches, and answering a lot of e-mail. But I was hoping to be able to release gzip 2.0 directly, without having to make an intermediate 1.x release. See my answer to the question bzip2 support concerning the state of gzip 2.0 and the Real Life interference. I'd be glad to hand over all my patches for 1.2.4 to the person who can help me getting the gzip 2.0 project to full speed.
9) Proprietary algorithms
by Tom Womack
The field of compression has been thronged with patents for a long time - but patents at least reveal the algorithm.
What do you think of the expansion of trade-secret algorithms (MP3 quantisation tables, Sorensen, RealAudio and RealVideo, Microsoft Streaming Media) where the format of the data stream is not documented anywhere?
Gailly:
The hardware specifications for some video cards were kept as trade secrets. As a result, the XFree86 project couldn't support these cards. Increasing pressure from users who didn't buy those cards because they couldn't be supported has led the manufacturers to release the hardware specifications, and those cards are now well supported.
Similarly, I think that pressure from the open-source community can become strong enough to force companies to open their formats. We're not completely there yet, but I believe that the open-source model will win in the end. Even a giant like Microsoft starts considering Linux as a real threat.
10) Go and Compression
by Inquisiter
When I think of a game like go or chess, I think that each player develops there own algorithm to beat their opponent. If you agree, what relationships or similarities do you see between your intrest in Go and your intrest in compression?
Gailly:
What a nice question!
Even though the rules of go are very simple, the complexity of go is astonishing. The best go programs can be beaten by a human beginner. The search space in go is so large that is impossible to apply the techniques that are so successful in chess. Professional go players never evaluate all possible moves. They are able to compress an enormous amount of information into a relatively small number of concepts.
Where a human beginner would have to painfully examine many possibilities to realize that a certain group is doomed, and would most likely fail in the process, a go expert can immediately recognize certain shapes and can very quickly determine the status of a group. One gets stronger at the game by reaching higher levels of abstraction, which are in effect better compression ratios. A professional go player can elaborate concepts that an average player would have great difficulties to understand.
Current go programs are overwhelmed by the amount of information present in a game of go. They are unable to understand what is really going on. Since brute force techniques can't work in go, programs will only improve by compressing the available information down to a manageable level.
Slashdot Hall of Fame? (Score:5)
Maybe the slashdot effect will help these folks get some well-deserved attention.
Please Allow me to rephrase (Score:5)
When I asked if there would ever be a "developer" version of Mandrake, I didn't mean a distribution that automatically included all of the developer tools. I do use Mandrake 7.0, and I do have all of the developer tools installed. What I was referring to would be something a bit more like Debian, where things are quite so user-friendly and "windowsish". In other words, a distribution that would be more fun for developers to play around with.
I realize that Debian exists for this purpose, but I would like to see a variety of developer platforms of Linux. I think that the community as a whole seems to be forgetting that Linux started as Linus's hobby, and grew to be the hobby of dedicated hackers everywhere. Now, Linux has moved to the corporate world (even though I do love the new "business Tux" /. icon) and the roots and history are really gone.
Brad Johnson
--We are the Music Makers, and we
are the Dreamers of Dreams
Re:Slashdot Hall of Fame? (Score:3)
--
Nuts and bolts. Cool =:-) (Score:3)
One of my russian friends when talking about the programmers that write all the little bits of useful code translated (akwardly) a proverb that i cannot remember. It said basically that there is just as much dignity in being a farmer as [some high profile occupation] because without them we would all starve.
If anybody knows the correct wording and or translation for this...
(red) Hats off to J-L! (Score:4)
Compression algorithms should be patentable, but for a 2-year period. This way, the company that develops a new one will have a temporary monopoly to make their money, but it can be included in other programs and libs after it is opened to public use. Developing new algorithms is great, but useless if they're not used because of a 20-year lock on them.
I think that Mandrake is pushing RH to innovate. Remember, RH is used more by the newbies because it is more 'commercial' and it does some of their work for them. No, I'm not slamming RH, I'm just saying it's probably the most used by newcomers who, after they get used to Linux, can then either stay with RH or try the other flavors.
I'm also quite pleased that J-L released the gz lib to Winzip. Even though he's allowing them to make money from his work, he is actually pushing the acceptability and openness of Linux. The man is to be commended for looking at the whole picture and truly accepting open-source GPL.
Go! (Score:3)
Of course, his "compression" is generally expressed in terms of "rules", and even some tips from image compression might help here. (recognize similar configurations, whether they be rotated, translated, etc., and adjust your strategy accordingly)
bzip2 is a really great program, generally offering better compression than gzip at least for large bodies of text. What I'd really like to see is a meta-compression format that has some heuristic to identify the type of file, and use the appropriate (optimal) algorithm. I know most modern compression programs do something like this already, (like RAR and its multimedia compression) but it's still neat. The few bits to identify the compression methods can be well worth it...
Also, hopefully those compression patches will eventually make it into Linux; it'd be great to see something like that working at the VFS level.
If it used something like LZO [uni-linz.ac.at], there'd be up to gzip levels of compression with practically no performance hit on even a modest system. Maybe even speed improvements would be possible, due to having to read less data from the disk...
Under those situations, I'd advocate comressing swap (and even memory!) where it would help (not recently used data), and maybe merging more of that into the filesystem too...
---
pb Reply or e-mail; don't vaguely moderate [152.7.41.11].
Mandrake extras (Score:4)
I was a bit disappointed that Jean-Loup didn't mention the inclusion of quite a number of localization [linux-mandrake.com] packages into their release, and actively soliciting additional translations into any language they can find translators for [linux-mandrake.com]. In the spirit of full disclosure, my name does appear there, and I did receive a copy in exchange for some late-night translation efforts.
Speaking of unsung heroes. I'd be interested in seeing an interview with one of the people who have kept the internationalization and localization of open source moving forward such as François Pinard of the Free Translation Project [umontreal.ca] or Pablo Saratxaga of MandrakeSoft who is also running the Linux i18n Project [linuxi18n.org].
Re:Go! (Score:3)
Yikes! Tell your brain "It's okay, you only thought it was a good idea".
The TIFF image format does exactly this, which is why nobody uses it. The problem with a meta-format is that it can never be completely implemented by anybody. So user Joe downloads all of Project Gutenberg in a the tiny 500 kb file compressed by meta-zip, only to discover he doesn't have the GutenSquash codec. he then has to go hunt down the codec and install it, exactly as if he had to download and install a whole new compression tool.
The problem can be reduced by having an auto-download feature like Windows Media, but the basic problem is the standard format is really just a standard container for unstandard things.
Also, with fewer compression methods out there you stand a much better chance of finding something that can decompress your thesis 10 years from now.
Pattern Recognition, AI, and Compression (Score:3)
- Go is severly complex to a computer. To play requires a combination of looking "n" moves ahead(which a computer does well) but regonizing patterns(which a computer doesn't do so well). The combination is way out of the reach of current computer AI.
- Computers can't regonize what is in a digital image without massive hardware and even then the results aren't inspiring(think abstract art or oil painting). Yet humans can easily grasp the concept around images.
- Computers can't regonize the content in text either. There are spell checking programs out there that can check grammer but none can actually know what they are doing...and "spell checking" is pattern matching! Humans can easily judge whether a sentance is "clever" or "stupid" but computer can not nor can the computer tell the difference between a sonnet or a memo.
- We all know how poorly game AI tends to be. A computer can easily outplayed because it can not regonize between the good time to attack/defend and the bad time to attack/defend. The best it can do is guess(I've got "n" number, they've got "m"...my number is bigger so I should attack). Position and disposition are completely lost to a computer.
I believe the Holy Grail in AI has to be real human like "recognition"**. Pattern recognition is something a computer does well but that really isn't the whole problem. Humans recognize "things" and instantly has memories associated with that "thing". Both steps seem to be compressed together. To a computer, recognition is an exhuastive, brute force search of its set of knowledge(ie a database) and the assocition is another exhuastive, brute force search through a different kind of set of knowledge(ie another database). Both steps are impossible to implement or maintain with our current methods and algorithms for pattern matching and searching. Something new has to be invented and I believe that "compression" and "hashing" will be a key to creating a true AI like sytem.
** note: for a computer to have "real human like recognition" it must also have the ability to be "mistaken".
Patents on algorithms (and software) (Score:4)
Algorithms are patentable. In a sense, Algorithms have always been patentable. You just had to have a good patent attorney. Here's how it works:
1. Submit application for algorithm patent
2. Get laughed at by patent office clerk
3. Hire good attorney to write application
4. Submit application for a DEVICE which implements the algorithm
5. Rake in the big bucks
Anyone can implement your algorithm, as long as they don't manufacture a device that implements the algorithm. So if I had a compression algorithm, I would patent a device, consisting of CPU, memory, and disk drive that compresses data by (insert algorithm here). You would be free to implement the algorithm by hand, or maybe in a device made up of steam-powered wheels, cams, and rods. For all practical purposes, my algorithm would be patented.
BTW, this same technique could be used to get around five year limits on software patents. Bezos is almost certainly aware of this, so I found his open letter to be quite disingenuous.
Re:Slashdot Hall of Fame? (Score:3)
And no one should be allowed in simply because they were Open Source. For instance, GNOME and KDE developers are great contributors to the Open Source scene, but they're not doing anything innovative. New Xerox-PARC-based interfaces have been springing up since the 80s, there is no reason to accolade something that should be described as YAGUI.
E.