8 ms·
Burrows–Wheeler Transform
- mcint 4y agoSomeone's been reading about string matching algorithms, or compression. For biology?
- Ultimatt 4y agoSure since biology is generating vast volumes of data in national genomics and digital pathology programs around the world. Bit of a bias on HN for genomics, which is maybe 250GB for a person but you do it once, typically. But slide imagery is petabytes a year per hospital type scales, with lossless compression needs not just jpeg. If you're interested in string search algorithms one of the cooler ones to come from genomics needs is Bitap as it has some scaling by alphabet size but DNA has a small alphabet https://en.wikipedia.org/wiki/Bitap_algorithm https://en.wikipedia.org/wiki/Bitap_algorithm
- tdido 4y agoThis is used in both bwa [1] and bowtie [2], two of the most popular DNA sequence aligners. [1] https://github.com/lh3/bwa https://github.com/lh3/bwa [2] https://github.com/BenLangmead/bowtie https://github.com/BenLangmead/bowtie
- unlikelymordant 4y agoAlso bzip2! Which is just data compression, not sequence alignment.
- epistasis 4y agoThe full text search idea is also called the FM Index: https://en.wikipedia.org/wiki/FM-index https://en.wikipedia.org/wiki/FM-index The BWT is one of those almost magical tools for compression. But using it for speedy string search is a whole other amazing invention too.
- beagle3 4y agoIt is an incredibly elegant scheme for bringing Markov context outputs together without actually trying to figure out what those contexts are.
- dkbrk 4y agoHonestly, the inverse Burrows-Wheeler transform seems like some sort of Voodoo black magic to me. It reminds be of the 100 prisoners problem [0]. Yes, I understand why it works. I can see how it works mathematically. But it still feels like it shouldn't work, that we're somehow getting something for free. [0]: https://en.wikipedia.org/wiki/100_prisoners_problem https://en.wikipedia.org/wiki/100_prisoners_problem
- _0ffh 4y agoI clicked this thing on the front page just to leave this precise remark (minus reference to the 100 prisoners). As you already did that, it seems my only sensible option is to voice my agreement.
- pointernil 4y agoSame here. m2^2 ;) toying around with these kind of indices to detect / find repetitions for years already. Btw: what's the best source for these kind of one of a kind, contra-intuitive algos and datastructures? Be it online, be it books... BWT can't be the only one, right?
- wpietri 4y agoHaving read through the (very good!) Wikipedia explanations a few times, I'm left with a different troubling intuition: if this works to improve compression, then I feel like there must be something wrong with the compression algorithms!
- superjan 4y agoNot necessarily. After the transform, there are more runs of characters, but it could be that this comes at the expense of recognizable patters (like common words) in the input. It likely helps simple compression algorithms more than sophisticated ones.
- jltsiren 4y agoGeneral-purpose compression algorithms tend to be conceptually simple. They must be fast, so they can't try many different approaches to see what works best. And because they are general-purpose, they can't assume much about the data. The typical data compression algorithm starts with a combinatorial transformation of the data. Then it creates a statistical model of the transformed data and encodes it according to the model. There are two successful families of combinatorial transformations: Lempel–Ziv and Burrows–Wheeler. Neither of them is superior to the other, but the compression performance depends on the properties of the data. Lempel–Ziv parsing replaces copies of repeated substrings with references to an earlier copy. It works best when there are long repeated substrings in the data. The modeling/encoding parts of an LZ compressor are usually pretty simple. Burrows-Wheeler transform reorders the symbols according to the context they occur in. It's often but not always followed by run-length encoding. Because the symbols are reordered by context, BWT-based compressors work best when there are many copies of each repeated substring. Unlike the LZ, the BWT does not compress the data on its own. It relies entirely on statistical compression. Because the symbols are ordered by context, the BWT is an order-n model for every n simultaneously. Hence you get something similar to PPM by simply partitioning the BWT into blocks and encoding each block independently with an order-0 encoder.
- dang 4y agoRelated: Burrows-Wheeler Transform [video] - https://news.ycombinator.com/item?id=10721401 https://news.ycombinator.com/item?id=10721401 - Dec 2015 (5 comments) Compression with the Burrows-Wheeler Transform - https://news.ycombinator.com/item?id=1112845 https://news.ycombinator.com/item?id=1112845 - Feb 2010 (6 comments) https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=%22burrows-wheeler%22&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
- skrebbel 4y agoCan anyone explain to me why this is said to be O(n) when it heavily relies on sorting?
- rullelito 4y agoWiki mentions https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array is used for performance.
- Lichtso 4y agoNot only that, the suffix array [1] is using counting sort O(n) instead of a comparison based O(n log n) sort. That is because they assume integer alphabets. For general alphabets they can only achieve O(n log n). [1] https://arxiv.org/abs/1610.08305 https://arxiv.org/abs/1610.08305
- ur-whale 4y agoI still remember when I first read the first C implementation of this, which was IIRC by Mike Burrows. Apparently, back in the days, Mike had some sort of philosophical opposition to indenting his C code. I was impressed he managed to write such a complex piece of code without ever indenting anything.
- ignoramous 4y ago> Apparently, back in the days, Mike had some sort of philosophical opposition to indenting his C code. That explains his aversion to Python back then: https://archive.is/OFmNT https://archive.is/OFmNT imo, Mike Burrows' impact on the industry rivals that of the Turing awardees. Ex A from 2008: https://archive.is/ZPd4f https://archive.is/ZPd4f
- chubot 4y agoHm, it seems obvious that Guido and Python have more impact on the industry (and I'm aware of Burrows' antipathy toward Python, which was well known at Google. As far as I remember it was due to debugging a syntax error caused by indentation in SWIG/Python) JPL and Google were early Python users. Google's crawler and the home page started out in Python (trivia: the ancient asyncore stdlib module and its author played some role, as far as I remember) Pretty much all AI and self driving cars use Python, BitTorrent was written in Python, Python is embedded in GDB, embedded in huge commercial applications like Maya for visual effects, etc. I think Ethereum had an early Python implementation Python's design achieved Guy Steele's "growing a language" vision in his famous talk, i.e. using operator overloading to allow scientists to create their own lingua franca -- https://news.ycombinator.com/item?id=29171519 https://news.ycombinator.com/item?id=29171519 (i.e. the talk was about adding operator overloading to Java, as well "generics" and value types) Mike Burrows is a great (even legendary) programmer and computer scientist, but if you're talking about "impact on the industry", there are levels :) I have to say I'm a big Alta Vista fan though
- lokar 4y agoAnd a really nice person to work with
- 4y ago
- lancefisher 4y agoThis is a fun video from a series on compression that explains it well, and features Mike Burrows: https://youtu.be/4WRANhDiSHM https://youtu.be/4WRANhDiSHM He shares the origin of the algorithm as well as a story about how it was first published. The Compressor Head video series is the best introduction to compression that I’ve found.
- visarga 4y agoThat was great. It's one of the greatest things about YouTube that you can find such videos on it.
- frozencell 4y agoSo even the inventors quite misunderstand how they came up with this marvel. (we are lost ^^)
- GordonS 4y agoHas anyone here found uses for it, perhaps for domain-specific string compression?
- billfruit 4y agoIs there any analogous method for images?
- Lichtso 4y agoIf you are asking if the algorithm can be generalized from 1D to 2D or even higher, then the answer is yes. For example, one could take the BWT of all rows and then all columns (using a different terminal symbol for each dimension), and that would be reversible. Question is if that is useful for compression.
- djha-skin 4y agoIt's fascinating to me that xz's algorithm[1] beats bzip2 (Burrows-Wheeler) in both time and space, but it's a much simpler algorithm. 1: https://en.m.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm https://en.m.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93M...
- gliptic 4y agoThat is because of other weaknesses of bzip2, not because BWT is worse. BWT generally beats LZ-based algorithms. I would also dispute that LZMA is simpler, at least in compression. Good LZ parsing is not easy.
- djha-skin 4y agoCan you provide examples of other BWT implementations, and instructions and perhaps some of the weaknesses of bzip2? Genuinely interested.
- gliptic 4y agoCheck out http://mattmahoney.net/dc/text.html http://mattmahoney.net/dc/text.html . The top BWT performer is #22. What it comes down to is the way the BWT output is transformed and entropy-coded afterwards, and various other tricks. bzip2 only does very basic MTF transformation and Huffman coding, which are not very bit efficient.
- quag 4y agobzip2 often beats xz for highly regular data, like a big csv or jsonl file. So I usually try both approaches on those sorts of files. For everything else my go to is zstd or xz. Xz usually wins by a little, but is a lot slower. Zstd is great in practice. Just yesterday I had a file where bzip2 won. I would love to see a modern version with the first few stages of bwt feeding into xz or zstd.
- aidenn0 4y agobzip2 beats xz for 1gb of zeros as well.
- lofatdairy 4y agoFor biologists reading this, I recommend the following series from a mathematical biologist in Spain (maybe Toronto by now): http://blog.thegrandlocus.com/tag/burrows-wheeler-transform http://blog.thegrandlocus.com/tag/burrows-wheeler-transform
- bumblebritches5 4y ago
- personjerry 4y agoHow is it that this doesn't violate the pidgeonhole principle?
- ducaale 4y agoFun fact, burrows-wheeler is one of the assignments in coursera's algorthims course.
- tehjoker 4y agoIf you were applying a first pass of compression to integer data and then applying gzip, would adding BWT in the middle still be beneficial?