Comment by jll29
6 days ago
Yes: you can classify a test file by topic with gzip as follows:
gzip -9 sports.txt testfile.txt
gzip -9 politics.txt testfile.txt
gzip -9 business.txt testfile.txt
(ass. sports.txt politics.txt and business.txt are text docs pertaining from the sports, politics and business domains, respectively, and have equal size)
The test file belongs to the topic with the smallest size *.gz file.
Witten's group at Waikato uni were perhaps the first to work on this.
Also check out the Hutter prize if you are interested in this.
Back in the day - maybe two decades ago - I implemented language detection like this.
I seeded gzip compressors’ dictionaries with Wikipedia articles in different languages.
I would then try to use said dictionaries on any random text, and the one that was best able to compress it, was the correct language.
Absolutely totally not the best approach, but very fast and super simple to implement.
Or maybe make a list of the most used 1000 words in each language. And see which list has the most occurrences.
That requires you to decide what a "word" is, which is not trivial (if you think that ignoring punctuation gets you to a clean "letters surrounded by spaces" you will get lots of issues with various Asian languages)
Also some languages have a lot of prefixes and suffixes on their verbs or even nouns, which dilutes your list of 1000 words by just adding the same common words over and over again with different suffixes designating grammatical tense, grammatical gender, etc.
The gzip version sounds more general and more obviously correct
9 replies →
See: Fast Static Symbol Table: https://github.com/duckdb/duckdb/pull/4366
FSST is based on a fixed size (255 items) dictionary of high frequency variable length strings/substrings (learned from the corpus) encoded as one byte.
Just collect common bi- and trigrams and a naive bayesian classifier.
Sounds like the best approach. :)
There are some deep connections between machine learning, compression, and cryptography with information theory as a common thread.
Also, I’ve never seen “ass.” Used to shorten “aside” — I typically use N.B. but perhaps only for important ones.
For anyone wanting an introductory text for information theory & that explores some of these connections & applications, it's worth checking out the late David MacKay's 2003 textbook Information Theory, Inference & Learning Algorithms https://www.inference.org.uk/itila/
The "ass." more likely stands for "assuming".
Yeah, I read it as "assuming" too.
3Blue1Brown has a good video about this: https://www.youtube.com/watch?v=l6DKRf-fAAM
Nitpick: Doing it exactly like this is flawed because you let the compressibility of your references taint the result; what you would prefer is the compressed size of testfile given sports.txt/... as a dictionary without accounting for the compressed size of that, no?
Really interesting approach though.
You're right, you should subtract off the compressed sizes of the respective reference files before comparing. (This suffices if we assume that later input data does not influence the compression of earlier input data, which is true except for certain unusual conditions like a repeated substring at the end of the reference data that also appears at the beginning of the test data.)
aka Normalized compression distance (NCD). Its close cousin: Normalized Google distance (NGD) is also super interesting!
https://en.wikipedia.org/wiki/Normalized_compression_distanc...
We used a similar technique for a class project (N decades ago) to test this:
https://en.wikipedia.org/wiki/Baconian_theory_of_Shakespeare...
By looking at mutual information from different authors on the same topic vs same author on different topics. As I recall, it convincingly disproved the hypothesis.
You might also want the topic files to be compressed against each other to get a baseline matrix and then multiply any results by the inverse, assuming equal priors on the topics.
I seem to remember it being shown for character recognition via JBIG. Maybe in Managing Gigabytes?
There would be some overlap with business sports analogies - eg team huddle.
we were doing this in Qualcomm 20 years ago
Is pigz faster?
[dead]