On Compression
Compression is a research area with many branches. I will focus on lossless compression; lossy compression has a huge history with its recent renaissance thanks to compressed sensing, not-too-recent resurgence due to wavelets for image and video standards, and other constant hums.
In lossless compression, there was the early pioneering work of Lempel-Ziv (LZ) in 70's. Since then there have been various extensions: Ziv worked on extending the"context" into various forms of universality; LZ method got applied to objects other than strings, from file versions to tables, graphs, web, grammars, etc; heuristics were developed using different chunking techniques or suitable dictionaries; and so on. But the general consensus when you spoke to people is that at the highest level, compression involved replacing copies of an object with references to a single copy, and you can perhaps eke out some small constant factor tradeoffs, but no further.
Are there major breakthroughs in compression? Doubtless one breakthrough has been the Burrows-Wheeler (BW) approach. The first time I saw it was in mid 90's and it was very unusual, almost magical. I couldnt tell how far this method will go. Now, not only is this a commonly used compression scheme based on BW (bzip), but we have clear theoretical analysis of its compression ratio which is asymptotically better than LZ, and interestingly, it has been used for indexing and made available in far more applications than LZ or simply compression. That is a good story of Algorithms in the Field.
I am working on next steps following the last year's workshop on Algorithms in the Field (8F), and to determine if there are other brewing new ideas in compression.
In lossless compression, there was the early pioneering work of Lempel-Ziv (LZ) in 70's. Since then there have been various extensions: Ziv worked on extending the"context" into various forms of universality; LZ method got applied to objects other than strings, from file versions to tables, graphs, web, grammars, etc; heuristics were developed using different chunking techniques or suitable dictionaries; and so on. But the general consensus when you spoke to people is that at the highest level, compression involved replacing copies of an object with references to a single copy, and you can perhaps eke out some small constant factor tradeoffs, but no further.
Are there major breakthroughs in compression? Doubtless one breakthrough has been the Burrows-Wheeler (BW) approach. The first time I saw it was in mid 90's and it was very unusual, almost magical. I couldnt tell how far this method will go. Now, not only is this a commonly used compression scheme based on BW (bzip), but we have clear theoretical analysis of its compression ratio which is asymptotically better than LZ, and interestingly, it has been used for indexing and made available in far more applications than LZ or simply compression. That is a good story of Algorithms in the Field.
I am working on next steps following the last year's workshop on Algorithms in the Field (8F), and to determine if there are other brewing new ideas in compression.
Labels: aggregator
posted by metoo at 10:22 AM
2 Comments:
Not necessarily new, but defintevely brewing. While "Grammar-based compression" can be traced back to LZ78, there is some recent advances in this field, in particular with regard to compressed indexes.
Great, looking forward to seeing the new results.
-- Metoo
Post a Comment
<< Home