Post by @hipsterelectron@circumstances.run

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

build tool is now blocked on file-based checksum and i am L O C K E D the fuck in

15 Replies

5 Boosts

This comment is unavailable — it may have been deleted or is not visible to you.

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

that's why it's so deceptive to say "a hash function produces a smaller output". no it doesn't!!!!

; printf '' | wc -c
0
; printf '' | sha256sum 
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 -

that's an encryption! and that sucks if i actually want to know what my data is, as opposed to wanting my data to be secret. using the same construct for cryptographic signatures is completely fucked when applying it to data integrity

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

and it's also just completely not the way hashes are used literally ANYWHERE else. the reason bloom filters work is because the hash functions are crafted to achieve collisions without having to calculate pairwise bit-for-bit equality over each pair of database entries!

radix sort gets better than n log n runtime for this exact reason!

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

so i refuse to call it a "hash". it's a "checksum" at best

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

i fervently believe that describing an actual literal parse forest for the file content that comes from actually parsing the data in an application-specific context is the correct way to achieve both data compression as well as integrity.

if the value of a single bit modifies the semantics of the entire rest of the file, that's information you kinda do need to know!

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

i actually refer to it as a "parse graph" to be fully general, because in fact most data serialization formats do not neatly compose into nested paired delimiters and a single "parse tree".

once you describe the relationships between atomic data blocks, you can directly use the parse graph to record checksum values that summarize not just the bits in your data, but what the bits mean.

and you (the application developer with domain expertise) can and should be able to construct a hash function that clearly summarizes the important facets of your data structure

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

"compression" is such a curious problem statement and it deserves some lambasting. see my diatribe on UTF-8 at https://codeberg.org/cosmicexplorer/corporeal.

the reason i prefer the term "coding theory" over "information theory" is that a "code" at least is designed to solve a problem.

the problems of "compression" and "integrity" are quite literally just variant encodings of the same set of assumptions.

Codeberg.org

corporeal

String library that uses corpus dictionaries to produce a more efficient encoding than UTF-8.

somebody

@somebody@circumstances.run 1 hr. ago

@hipsterelectron asymmetric numeral systems are maybe the most elegant statement of this fact I know of

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

@somebody i'm getting there!!!!!

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

@somebody have you perused my (slightly out of date atp) literature review around this https://codeberg.org/cosmicexplorer/corporeal/src/branch/main/literature

Codeberg.org

corporeal

String library that uses corpus dictionaries to produce a more efficient encoding than UTF-8.

somebody

@somebody@circumstances.run 1 hr. ago

@hipsterelectron no, but it is now bookmarked!

I have too much to read and my brain spends more time on waking up to fake gunshots than actually thinking these days. but I'm still working, a little

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

@somebody note in the readme there i have identified duda's cute little c++ workbook https://codeberg.org/cosmicexplorer/AsymmetricNumeralSystemsToolkit this is useful because yann collet only writes bad code

Codeberg.org

AsymmetricNumeralSystemsToolkit

Testing various methods for choosing tANS entropy coding automata

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

@somebody i think one thing the quantization of tANS does REALLY well is reframing the problem domain entirely:

given a fixed amount of auxiliary memory,
produce a representation of the input distribution,
that can be decoded into the original message.

this is a framework COMPLETELY missing from "huffman" coding

d@nny disc@

@hipsterelectron@circumstances.run 59 min. ago

@somebody i would argue that just by that framing alone you almost necessarily end up with a lot of the assumptions of ANS

d@nny disc@

@hipsterelectron@circumstances.run 52 min. ago

@somebody however i unfortunately have kind of a negative view of the probabilistic assumptions employed. i think duda is actually a genuinely good scientist and is doing his best but there's so much more depth than this.

to wit, from the pyramid vector quantizer paper he cites in the paper on generating probability distributions for tANS:

In the case of the mean-square error performance criterion, a construction analogous to 1)-3) (using (9) for X and selecting the representation regions as spheres instead of pyramids) can be shown to provide asymptotically (in L) optimum performance in the small distortion case.
For either performance measure, however, the construction is based on a random assignment of points to S(L, L/λ) and leads to designs which are extremely difficult to implement.

and they do a whole bunch of gaussian bullshit which i just hate

Cookie monster! (PDF)

View (PDF)

d@nny disc@

@hipsterelectron@circumstances.run 50 min. ago

@somebody but again duda himself seems to get this shit. from the tANS probability distribution paper, final page:

Generally finding the optimal symbol spread seems to require exponential cost, but such iterative tuning, or maybe just searching permutations of neighboring symbols, could lead to some improvements - practical especially for optimizations of tANS automata for fixed distributions.

that is exactly what i think the answer is. an exponential algorithm that tries merging and splitting every single symbol that occurs in sequence together

Discussion

Discussion