i have half of a diatribe written regarding the matter of "lempel-ziv" encoding. to give an idea of my thoughts regarding its ostensible "universality", i will relate that until last week i believed it was just one of several distinct stream encoding mechanisms that zstd could employ. it turns out to my dismay and absolutely not to my surprise that the reason ziv and lempel's approach is attractive is because it lets you throw slop into the slop machine
Discussion
Loading...
ziv is first author for both papers but the more curious lexicographic tendency beyond the arbitrary selection of the "LZ" initialism is their desire to reuse the term "universal" like that's a special characteristic. i thought facebook was bad at citing their sources but the 1977 paper has one of the truly most impressive examples of defining your hypothesis in terms of your results i've seen in a long while
for some reason ziv and lempel really do not want to cite claude shannon. the scan i'm reading is from a journal which concludes the lz77 paper with the beginning of another paper "on binary sliding block codes". it directly begins with the words:
Shannon's development of the theory of source coding subject to a fidelity criterion
to describe the "code book" terminology that ziv and lempel adapted but absolutely 100% refused to cite in any way
i found by about 2-3 wiki hops that the voyager golden record was also "published" in 1977. diffie-hellman's "new directions in cryptography" (an example of a great name for a paper which you know contains the juice) would be published in 1976. roe v wade would be "decided" in 1973
i was able to limit myself to a discussion of two paragraphs on the regularity of the cosmic microwave background as justification for the "universe's" bias towards encoding distinct and important context. lz77 is, like much research, developed back to front, where the authors identify their desired hypothesis and work very hard to disprove the alternative
the key thing i had immediately noticed is of course their derogation of statistical distributions by invoking the incantation a priori ad nauseam. they write it with a medium oblique slant and slightly bolder than the surrounding text every single time. they also demonstrate a very impressive degree of conviction that their description of block coding does not rely upon said a priori distributional assumptions
claude shannon's probability distributions over symbol frequencies are portrayed as if they were arbitrary, yet the encoding of sources in lz77 manages to achieve something beyond even gödel by demonstrating a characterization of symbol distributions that cannot be interpreted probabilistically. in their immense modesty, the authors reject the "ranking" of their universal scheme against alternatives "for lack of adequate criteria". yet the final two pages are devoted to a comparison to optimal prefix encoding
~60 more replies (not shown)
there are many fascinating things about it but the entire ordeal is more obfuscatory than nuclear fallout on a geiger counter. it is proposed that an infinite lookback window would be an optimal encoding of the input. this is finally where i started being able to wrap my head around how to compare the memoryless system to the interwoven graphs of composable context i'd like to produce instead
the obvious point not made here in the authors' description of optimality is that they assume the single message represents the totality of the message stream, and then apply this linear relationship of window size to the optimal encoding as a way to continue speaking of "compression ratio" even though they have introduced several subtly different interpretations of those terms. it's not obvious to me that just by having demonstrated that your mechanism generalizes into optimality that you have necessarily then described a novel approach, particularly when the authors make it a point to reject comparisons to the existing literature upon principle
it's very fascinating to me that DEFLATE is just phil katz divining a data-dependent decision process to mediate between local and central references. zstd is just DEFLATE that uses duda's tANS entropy coding (that's a priori by ziv's nomenclature) to compress the canonical prefix codes. it makes sense that working on an archive format like katz's PKZIP would indicate that it behooves the encoder to apply distinct strategies for data with more global context
fundamentally i am kind of opposed to the architectural approach that ziv and lempel were going for. i don't really care much for shannon taking the credit for inventing the idea of information either, and his exposition of "information" in terms of distinguishing messages from one another is actually kind of a political determination. this is my shared concern with the lz approach which leads to compression being something you just throw your data into and not something you design with the data
https://2014.igem.org/Team:Vanderbilt_Software/Project/Results i was looking for c++ code doing a prefix tree from 2013 the first year i started writing code. i haven't been able to find it. i believe it is likely on one of my five dead hard drives. but i did find i wrote quite a bit more documentation than i had remembered for the git wrapper i developed for DNA/RNA sequences
Results
We produced software which implemented the algorithms described in our novel approach on specially cleaned input files and ran them through a typical version control system. We performed experimentation on transformations between iterations 3-6 of our wetware team's yeast plasmids. As a control, we compared darwin's output running through the git version control system to simple processing with git (vanilla_git). We expected darwin to run faster and show fewer changed lines in the diff output than vanilla_git.
As expected, darwin's preprocessing produced a significantly faster diff, with an average speed of 5.763 seconds per file, as opposed to 10.640 seconds for the vanilla_git. However, against our assumptions, that performance did not seem to rely upon the reduction of changed lines reported by git, since darwin actually produced more changed lines. More research is required to find the correlation between the number of changed lines reported by git and the number of lines actually changed in the file.
Future Work
Future work mostly revolves around bringing darwin from a standalone diff-producing executable to an integrated system with a GUI usable by novices. The major challenge with that is parsing the plethora of different file types used to represent DNA although the implementation of other formats such as SBOL, ApE, etc., could be done easily by extracting the actual genetic sequence from the file.
In addition, the current algorithms are unable to deal with introns of any sort in the input DNA sequence, and will attempt to split the file into ORFs regardless. The ability to correctly identify non-coding regions like this would create a far more valuable piece of software, able to deal with prokaryotes and eukaryotes alike.
ccing @jamiejennings to highlight that i have always been terribly fascinated by systems of measurement and the will-o-wisp of computer performance:
As expected, darwin's preprocessing produced a significantly faster diff, with an average speed of 5.763 seconds per file, as opposed to 10.640 seconds for the vanilla_git. However, against our assumptions, that performance did not seem to rely upon the reduction of changed lines reported by git, since darwin actually produced more changed lines. More research is required to find the correlation between the number of changed lines reported by git and the number of lines actually changed in the file.
i don't believe i understood at the time how to generate profiling data. this wasn't even in the "future work" section
i forgot how much i adore writing "future work" sections. that's where the magic happens
i ended up taking a detour learning about OCR knobs by attempting to extract and align a text layer for shannon's 1948 bell labs paper. i observed a variety of fascinating characteristics:
- you would not believe how much "easier" it is to re-run tesseract hundreds of times to get it to prefer uniformly sized and cased dictionary terms which would be obvious to any human reader, than it is to edit a single character misclassified by the machine
- pdf documents and images more generally are a curious middle ground between source code and opaque binary media. images, like text, are the subject of human artistic and creative labor. occasionally they will also be the focus of funding and investment
so i rewrote this entire python project because it was "slow", and the slowness was on account of tesseract being an opaque externally compiled c++ program without even an attempt at documentation. two curious points here:
- uv quite literally uses the exact rich console output presentation i created several years ago for pip to achieve parallel downloads.
i think if you rip off the exact heuristic sorting i developed because i was still building for people with slow internet connections in the global south you have clearly demonstrated you're afraid to do anything i haven't done first. it also means you're not actually optimizing for most users of python.
i moved past that because this project (which you'll recall is slow because tesseract is shockingly inept) said "oh we need to move this into rust for performance" and i was like damn bet? and then i also fixed their creatively terrible signal handling so the user can exit the program which is very useful when the program takes a very long time and is frequently wrong
developing d@nny's universal theory of source coding where everything is a form of build tooling except for the parts which are about packaging. compression? believe it or not that's a build concern not a packaging one. archive formats? that's packaging
parsing on the other hand demonstrates characteristics of genderfluidity within the dichotomous build/pkg framework. where parsing mediates political divisions, this is the very essence of packaging.
the construction of grammars however becomes very fraught with what are often characterized as "practical" considerations, which somehow seems to asymptotically retreat from solving practical problems
as a classic example: parsing html with regex affords the potential for buffering and pipelining across the input. this is a classic technique of build tools, which generally seek to identify data and logical relationships that variously structure the input (source code, compiled binary container formats) and the mechanism that transforms these into outputs. this is by necessity recursive, which is to say that the data informs the mechanism as much as the mechanism informs the data
regular expressions however are some of the more curiously constrained abstractions. the term "backtracking" is used to smear formalisms which do not hew to the precise constraints robert pike envisions, but forget about mere propaganda for a moment. vectorized instructions are (outside of some specific cases the hyperscan project has worked very hard on and deserves more credit for) quite literally incompatible with the standard automaton model
what does "incompatible" mean? it's a strong word but correct here. it means the automaton model does not support unifying computation performed across distinct components of the input. this is so obvious and basic that it's hard to describe.
if you are at all interested in this subject actually i would love to collaborate with you because it remains deeply mysterious to me why e.g. overlapping parallel parse forests (and related constructions to infer partially-ordered graphical relations across various magnitudes of distance spanning sequential input, which admit astronomically parallelizable and vectorizable mechanisms to combine orthogonal results) are not yet the subject of even a single doctoral thesis if not a goddamn turing award
text search remains very much like the constructed house of mirrors in the lz77 paper in that text search and data compression are essentially dual problems and both "fields" of study seek to ablate the deeply domain-specific context inherent in practical realizations of the "information" they pretend to codify.
much like with compression, when the input is fixed (or if it can be approximated somehow), there will exist a family of optimal encodings for search operations to minimize any desired metric. a "generic" search is very reasonably analogized to a "universal" coding system such as lz77
i don't believe that optimality is easy to define here yet. with analogy to the delightful proof for the $n log n$ omega (lower) bound for sorting via a sequence of pairwise comparisons (each of which provides exactly one unique bit of unknown information), we can impose basic operations like reidemeister moves from knot theory and minimize those
radix sorting does not impose the same maximum of one unique unknown bit per basic operation (pairwise comparison), and can therefore surpass this bound. analogously, the standard optimal prefix code for a "message" (i.e. a fixed-size seekable data stream) is limited to a minimum of 1 bit per symbol in the encoded output stream: https://github.com/Cyan4973/FiniteStateEntropy/
By design, Huffman can't break the "1 bit per symbol" limit, hence loses efficiency on squeezed distributions, such as Proba80.
exercise for the reader:
why does 1 bit per symbol impose a maximum compression ratio asymptotically approaching the exact integer 8?
i consider this a trick question, because it requires the imposition of a separate constraint: that the alphabet contains exactly 256 entries. this is a common heuristic for universal coding, because that's the number of distinct bytes, and computers use multiples of 8 for reasons no one has ever bothered to explain to me. an arbitrary bit sequence can be losslessly translated to and from an arbitrary byte sequence modulo <= 7 padding bits, so prefix codes with a minimum interval of 1 full bit between states can losslessly encode the translated byte sequence with at most 1/8 the length (this is not a hard bound but a back of the envelope—this sounds like a proof i could figure out)
that paragraph btw is the first time i ever recall learning something from yann collet. after my bizarre experience reading the zstd rfc, (which ends with the remarkably concise passage):
Acknowledgements
zstd was developed by Yann Collet.
i quickly realized this is not the behavior of any form of guru, genie, demigod, or even someone bold and decisive enough to negotiate a contract with the devil as featured in the hollywood blockbuster of the christian religion
9.2. Informative References
[ANS]
Duda, J., "Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding", January 2014, <https://arxiv.org/pdf/1311.2540>.
[CRIME]
"CRIME", June 2018, <https://en.wikipedia.org/w/index.php?title=CRIME&oldid=844538656>.
[DICT-SEC]
Handte, F., "Security Considerations Regarding Compression Dictionaries", Work in Progress, Internet-Draft, draft-handte-httpbis-dict-sec-00, 29 October 2019, <https://tools.ietf.org/html/draft-handte-httpbis-dict-sec-00>.
[Err5786]
RFC Errata, "Erratum ID 5786", RFC 8478, <https://www.rfc-editor.org/errata/eid5786>.
[Err6303]
RFC Errata, "Erratum ID 6303", RFC 8478, <https://www.rfc-editor.org/errata/eid6303>.
[FSE]
"FiniteStateEntropy", commit 12a533a, July 2020, <https://github.com/Cyan4973/FiniteStateEntropy/>.
[LZ4]
"LZ4 Frame Format Description", commit ec735ac, January 2019, <https://github.com/lz4/lz4/blob/master/doc/lz4_Frame_format.md>.
[RFC1952]
Deutsch, P., "GZIP file format specification version 4.3", RFC 1952, DOI 10.17487/RFC1952, May 1996, <https://www.rfc-editor.org/info/rfc1952>.
[XXHASH]
"xxHash", <http://www.xxhash.org>.
that's:
- 1 citation of the duda paper (which itself refers back to collet's c code repeatedly, to the point of effectively constituting a combined work)
- 1 self-cite of said c code itself (somewhat less opaque than the zstd c code, but not enough to be useful to anyone)
- 1 citation of a completely unrelated bit stream encoding from collet which he calls "lz4" and describes as having a "similar" frame format. (that repo does not cite or explain that it uses lz encoding)
then 1 citation to a great IETF document https://datatracker.ietf.org/doc/html/draft-handte-httpbis-dict-sec-00 that explains laboriously how you can introduce a buffer overflow into your code if you use a buffer in conjunction with computer instructions to load or store data with that buffer
however, it goes further:
- using dictionaries not found in the data stream means the stream cannot be unambiguously decoded without a form of cryptanalysis. (this also makes data shorter)
- however, vint cerf may also experience slightly greater difficulty in silently refragmenting your packets to break TLS via replay attacks
- this is a classic example of an engineering tradeoff
the "CRIME" attack is mentioned again, where compression of a message containing both attacker-controlled + secret data is used for cryptanalysis
- this is one of the techniques turing used against the nazis by way of weather reports
- this is a result of HTTP encoding cookies as header values in a single message along with the remote content
- google/IETF/w3c has not moved to deprecate this for some reason
instead, google's best and brightest join facebook in encouraging against employing any form of compression in a context with secret data:
Dictionary-based compression enables better performance, but brings state into the process of compression
the state? in my compression context? it's more likely than you'd think.
Dictionaries make compression stateful,
now that's a quote
oh man this is so good. better than TLS 1.3
some compression algorithms can accept arbitrary, unstructured inputs as dictionaries. These unstructured dictionaries do not require an explicit generation step; users can simply repurpose existing messages as dictionaries.
that's called reduce reuse recycle! a compost bin for your messages!