Live data from Hacker News

Removing newlines in FASTA file increases ZSTD compression ratio by 10x

log.bede.im

71–80 of 118 posts

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#71
post #24

Earlier quoted context omitted.

It is stored in the metadata [1], but anything larger than 8 MiB is not guaranteed to be supported. So there has to be an out-of-band agreement between compressor and decompressor. [1] https://datatracker.ietf.org/doc/html/rfc8878#name-window-de...

Seems useful for games marketplaces like Steam and Xbox. You control the CDN and client, so you can use tricky but effective compression settings all day long.

For internal use like that you can also use the library feature. The downside of using long=31 is increased memory usage, which might not be desirable for customer facing applications like Steam.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#72
post #65

FASTA is a candidate for the stupidest file format ever invented and a testament to the massive gap in perceived vs actual programming ability of the average bioinformatician.

It might be the stupidest, but stupid in the sense of "the simplest thing that could possibly work." When FASTA was invented, Sanger sequencing reads would be around a thousand bases in length. Even back then, disk space wasn't so precious that you couldn't spend several kilobytes on the results of your experiment. Plus, being able to view your results with `more` is a useful feature when you're working with data of…

FASTA was invented in late 1980s. At that time, unix tools often limited line length. Even in early 2000s, some unix tools (on AIX as I remember) still had this limit.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#73

This is because Zstd's long-distance matcher looks for matching sequences of 64 bytes [0]. Because long matching sequences of the data will likely have the newlines inserted in different offsets in the run, this totally breaks Zstd's ability to find the long-distance match. Ultimately, Zstd is a byte-oriented compressor that doesn't understand the semantics of the data it compresses. Improvements are certainly possib…

That is fascinating. I wonder if you could layer a Levenshtein State Machine on the strings so you can apply n-edits to the text to get longer matches.

I absolutely adore ZSTD, it has worked so well for me compressing json metadata for a knowledge engine.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#74
post #19

The FASTA format looks like: > title bases with optional newlines > title bases with optional newlines ... The author is talking about removing the non-semantic optional newlines (hard wrapping), not all the newlines in the file. It makes a lot of sense that this would work: bacteria have many subsequences in common, but if you insert non-semantic newlines at effectively random offsets then compression tools will not…

this is also the insight that the bwa developer had, to use the burrows-wheeler transform which is part of bzip2 due to it's compression properties being particularly good for genomic sequences.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#75
post #41

Looking forward to the relegation of FASTQ and FASTA to the depths of hell where they belong. Incredibly inefficient and poorly designed formats.

How so? As long as you remove the hard wrapping and use compression aren't they in the same range as other options? (I currently store a lot of data as FASTQ, and smaller file sizes could save us a bunch of money. But FASTQ + zstd is very good.)

https://www.biorxiv.org/content/10.1101/2025.04.08.647863v1....

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#76

FASTA is a candidate for the stupidest file format ever invented and a testament to the massive gap in perceived vs actual programming ability of the average bioinformatician.

I think the prevalence of the format vs something more widely used should be part of that metric.

On those grounds, the lack of pre-tokenization in html/css/js ranks at this point as a planet killing level of poor choices.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#78
post #38

Earlier quoted context omitted.

This is a dataset of bacterial DNA. Any two related bacteria will have long strings of the same letters. But it won't be neatly aligned, so the line breaks will mess up pattern matching.

And the compressor does not think: "how can I make these two sequences align better without wasting a lot of space?"

The compressor doesn't think about anything. Also, Zstd doesn't have the goal of reaching the highest possible compression ratio. It's more geared toward lowest overhead, high bandwidth compress/decompress.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#79
post #38

Earlier quoted context omitted.

This is a dataset of bacterial DNA. Any two related bacteria will have long strings of the same letters. But it won't be neatly aligned, so the line breaks will mess up pattern matching.

And the compressor does not think: "how can I make these two sequences align better without wasting a lot of space?"

No, because alignment, in the general case, is O(n^2). It is ironically one of the more tractable and well solved problems in bioinformatics.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#80

This is because Zstd's long-distance matcher looks for matching sequences of 64 bytes [0]. Because long matching sequences of the data will likely have the newlines inserted in different offsets in the run, this totally breaks Zstd's ability to find the long-distance match. Ultimately, Zstd is a byte-oriented compressor that doesn't understand the semantics of the data it compresses. Improvements are certainly possib…

That is fascinating. I wonder if you could layer a Levenshtein State Machine on the strings so you can apply n-edits to the text to get longer matches. I absolutely adore ZSTD, it has worked so well for me compressing json metadata for a knowledge engine.

Zstd has a similar-ish capability called "repetition codes" [0].

The first stage of Zstd does LZ77 matching, which transforms the input into "sequences", a series of instructions each of which describes some literals and one match. The literals component of the instruction says "the next L bytes of the message are these L bytes". The match component says "the next M bytes of the input are the M bytes N bytes ago".

If you want to construct a match between two strings that differ by one character, rather than saying "the next N bytes are the N bytes M bytes ago except for this one byte here which is X instead", Zstd just breaks it up into two sequences, the first part of the match, and then a single literal byte describing the changed byte, and then the rest of the match, which is described as being at offset 0. The encoding rules for Zstd define offset 0 to mean "the previously used match offset". This isn't as powerful as a Levenshtein edit, but it's a reasonable approximation.

The big advantage of this approach is that it doesn't require much additional machinery on the encoder or decoder, and thus remains very fast. Whereas implementing a whole edit description state machine would (I think) slow down decompression and especially compression enormously.

[0] https://datatracker.ietf.org/doc/html/rfc8878#name-repeat-of...

Post reply on HN