Silly Lossy Text Compression Idea | Hacker News Reader

Silly Lossy Text Compression Idea

snufk.in

87 pointsTomte52 comments

Haha, even less effective than I expected but enjoyed the read nonetheless.

I think if you have the luxury of assuming every token is a dictionary word, you can do much better by simply encoding each word as its index in the dictionary. Using the pidgeonhole principle, you can probably prove that this is at least as good as the autocorrect approach no matter how sophisticated the autocorrect is.

> I think if you have the luxury of assuming every token is a dictionary word, you can do much better by simply encoding each word as its index in the dictionary.

Then you have to store the dictionary.

The entire English dictionary (being very generous on what a "word" is) is around 4MB - nothing nowadays.

Not to mention of course that your computer probably already has 50 copies of it somewhere if you really don't want to bundle it

The vast majority of text objects anybody generates won't exceed 4MB though. 4MB is 4 million ascii/utf8 characters, if we assume a typical word in English is 4 characters for simplicity, that's 1 million words without spaces. A quick Google search for "Novel that is 1 million words" yields the fact that this is twice the word count of Lord of the Ring and the word count of the first 3 A Song of Ice and Fire (Game of Thrones) books. Accounting for whitespace, longer common words, and inefficient encoding schemes would bring that overestimate down to, what, 150K words? a 300-page or 600-page book (depending on the spacing) according to Google, still massive.

I see it only working where there's massive pooling, like you say. An OS or a tool provides a known dictionary service and you call into it with a text string and get back an array of indices that you can then decode with another call. That amortizes the dictionary cost among all possible uses of the service, which is a lot if it's a standard well-known service. Another scenario is perhaps in a database\cloud storage\social media, any single text object might be small but the total text they store overall is massive.

Except that the corpus doesn't need to be stored as part of the compressed message, and can be considered part of the compression algorithm. It increases the size of the decoder by ~4MB, but doesn't increase the size of each message.

It's the standard pool/index tradeoff : instead of storing an array of possibly-duplicate objects, you simply store all unique objects once in a pool and store the array as an array of references into that pool.

You win if the original array of duplicate objects was so long or so duplicated that replacing it with references into the pool is a worthwhile reduction. The objectSize/indexSize ratio also plays some role.

The autocorrect method also uses a dictionary, and then some.

There once was a group of old friends who would get together on a regular basis for social interaction, telling stories and making jokes. As these folks aged, they ended up telling pretty much the same old stories and jokes again and again until they reached the point where they just assigned a number to each.

Decades later, they would gather and sit in silence for long periods until one or the other of them would just say something like "47" and all the other would laugh.

When I tried my luck and approached that group and said a random number, no one laughed. Apparently it's all in the delivery.

Or you picked the puppy story.

ObXkcd: https://xkcd.com/794/

You just described marriage

I’m not so sure it’s “at least as good” as sophisticated autocorrect. If you have a sufficiently advanced prediction model, it seems to me that you could make better guesses on context, which might, just by chance, outperform this approach. If you narrowed it down to only words that matches using this approach, but still used some kind of prediction based on context to pick which, I’d expect it to likely perform much better.

The autocorrect system might be able to do better if it had an understanding of grammar and proper english like GPT3, and could actually fill in missing words, replace words, etc

yes, like replace qck with quick instead of ack.

I don’t expect that would work. It would compress long words, but most short words would be encoded with numbers longer than the word themselves, and those typically make up most of the words.

The trick is to encode the numbers in binary, not plaintext. But still you'd probably want to use a Huffman coding rather than plain indexes so that the common words are shorter.

Build a decoder that knows just the vowels are missing, and you can make a simple dictionary of all the candidate words for each compressed word. Then if you know the probabilities of different word pairs, you can probably pick the correct word almost all the time.

The downside is that by reducing redundancy, you reduce your resilience to errors. A single typo could even propagate decoding errors to neighboring words. So maybe get fancier, and include at least one-letter errors in the list of possible words, with lower initial probabilities.

One way to do this would be to use the Viterbi algorithm: https://en.wikipedia.org/wiki/Viterbi_algorithm

https://github.com/darius/languagetoys/blob/master/emvowel.p...

Removing characters for lossy text compression is only a silly idea if trying to solve a conventionally practical problem.

Spoken and written languages have roughly a 3x overhead for channel coding. You can get a message across while losing characters and even whole words. Does lossless compression to entropy of text really capture all of the data saving possible? What if you undid some of the channel coding by dropping sets of characters or words then compressing? We don't need to do it (bits are quite cheap), so we don't, but it is an interesting problem that helps think about other problems.

Years ago when I was into keyboard layouts, text expansion, that kind of thing ("efficiency!"), I realized what's the point of typing the same letters faster, if most of what I'm typing is redundant, ie. pure overhead?

How many letters could be removed from a word and still uniquely identify it? eg. typing -> typg, uniquely -> unqy.

So I thought of applying this process of iterative letter removal to the entire English language: keep removing letters until you conflict with an existing (shortened) word. You'd start with the most commonly used words, so they would be assigned the shortest words.

(Though perhaps a better measure would be typing effort, ie. how much of a pain it is to reach for each key...)

Of course you wouldn't actually communicate in this language, you'd use a text expander software to replace them on the fly with the full words (this exists and works great).

I never ended up doing this, and forgot about it until now. (It would probably only take half an hour though, might do it this afternoon :)

Other fun ideas: make a crappy speech synthesizer, made up of tiny samples of your voice, and a codec that compresses audio of your speech by converting it to a sequence of those samples. (Also works for eg. music, see also: MOD files, which are like MIDI but with custom drum and instrument audio embedded!)

---

Edit: Here's a first draft https://gist.github.com/avelican/fa34a425770c3a8f914c96d75e2...

Used a naive approach, just start with the first letter and see if that's taken, then the first two letters and so on. The output is not optimal and be compressed further (but my lunch break's almost over ;)

Also this one is based on a word frequency list based on Wikipedia, which results in a weird word list and unusual words (that Wikipedia really likes) being near the top of the list. I'll have to collect some of my own conversations and run it on those.

Here's the code if anyone's interested... less than 20 lines of Python (what a great language)

https://gist.github.com/avelican/58f1468df04c3ff542e03288bfd...

You're describing stenography, see for example https://blog.zsa.io/2107-steno-tutorial/

I'm describing more efficient input methods, of which stenography is one. The amount of work involved in hardware, setup, and retraining muscle memory isn't really worth it for me. (Or it might be, but I'm too lazy to get over that activation-energy hill.)

Whereas what I'm looking at is a way to put in less effort immediately, ie. just stop typing words (very) early because I have already given my computer enough information to complete them for me.

Here's my comment parsed through my experimental browser extension https://i.imgur.com/CNtaK3u.png

Update: working on a browser extension :)

https://i.imgur.com/0LwWzum.png

The trick is to close the loop and remove every letter that the spell checker can correct.

People are actually pretty good at reading text where only the first and last letters are correct.

This suggests using a {first letter}#{last letter} encoding for words where the decompression replaces # with that number of letters chosen randomly.

I#m n#t so s##e t##t w###d be r######e. W##l, I g###s t##t w#s p####y r######e.

I wdoenr waht hpaepns if you jsut mix up the oderr of the lteetrs indsie ecah wrod.

Even better, it turns out.

It's easier to read, but not as good to compress since you'd have to store those letters. If the letters in the middle are the same, you only have to store the count of replaced letters. One byte should be enough for that.

If you sort the inner letters instead of randomize then you only need to keep track of the distance from one letter to the next.

byte -> btye -> bt5e

letters -> leertts -> le0,13,2,0s

You'd need to encode the offsets differently of course.

There's probably other compression you can do when order doesn't matter.

I'm not so sure that would be readable. Well, I guess that was pretty readable.

Interestingly, I decoded it as:

"I'm not so sure that would be reliable. Well, I guess that was pretty reliable."

Maybe we are both partially right:

"I'm not so sure that would be reliable. Well, I guess that was pretty readable."

Okay, so maybe # of characters and index of the word that starts and ends with the specified character and has that many letters.

That reduces almost every English word to 4 bytes.

However, it might be possible to do the same trick with pairs of words.

Or perhaps: "I'm not so sure that would be resolute. Well, I guess that was pretty remolade."

I used a crossword helper this time though.

Ism net so site test world be recourse. Will, I glass test was policy recourse.

If you used autocorrect/autocomplete instead of a basic spell checker, it'd be a proper compressor. Autocorrect picks the most likely word, so words fitting prediction can be encoded using shorter "symbols", and uncommon words have to get longer "symbols". Proper compression algorithms with entropy coding work like that, except at the level of bits and bytes.

Lossless should be possible, except for unknown words that are less than the maximum number of corrections away from a dictionary word. Compression rate will be low, though. It can be pre-computed for known words: replace each word by its compressed version. And that is a very old, and more flexible idea.

> It can be pre-computed for known words: replace each word by its compressed version. And that is a very old, and more flexible idea.

Can you link me some resources on those optimizations?

It is dictionary compression: https://en.m.wikibooks.org/wiki/Data_Compression/Dictionary_...

Humans are pretty good understanding texts with missing letters. I guess that if it considers also the context it would be possible to predict better the destroyed words.

But basically, we would be storing the missing information in the decoder, not in the data (which is not bad idea, considering that most most languages are used more than once). If we also only modify the letters that can be recovered successfully...

And also, this would not contradict the pigeonhole principle. Some words would be impossible to store, like a text full of typos. It would require escaping the word somehow, producing documents longer than the original.

Cool :) I made a little script that uses a thesaurus to try to shorten text https://github.com/anfractuosity/lossytextcompressor

haha.. Silly, but an enjoyable read, nonetheless.

>> In the banning go crate the hens and the earth no the earth was formless and empty darkness was or the surface of the dept and the sort of God was hovering ver the worse

They should encode the original word length and use a decoder that can take word length as an API. Then the result would be much much better and have real world uses

Please help!! , there is something fundamental I don't know how to achieve: Let's say you have a word. You want to compress it by making the smallest possible hash/UUID while being conflict free. Let's say we wanna compress the word "eating". I propose the following scheme: eating become: 1abc But it doesn't mean 1abc, let me explain: Here the 1 would be a char indicating a Metadata, this Metadata would denote a specific alphabet, such as Egyptian hieroglyphs. 1abc abc are the actual hash and a here denote the first letter of the hieroglyph alphabet. So first question: how to generate minimal hashes that leverage UTF8 symbols for reducing length. Also UTF8 non-base symbols weight 3-4 bytes which is not great and this is perfectly avoidable!! What a shame this concept is not widespread.. My goal is to have a string encoding that allow 255 distinct "ASCII tables", dynamically switched via the first letter encoding which table it refer to. Therefore any character in my encoding stay in one byte. The only limit is that therefore not all hieroglyphs can be encoded, only the 255 firsts but I don't care! I don't want to encode Egyptian, I want to generate maximally small hashes/UUID for normal text by going far beyond the standard alphabet symbols. How to achieve this?? This musy have already been done!

(note ideally you could specify more that one character for language selection, which would massively increase the encoding compression but jjst one would be a good start!) Plz help

TL;DR ASCII char encoding can only represent 255 1 byte characters My proposed scheme enable to have N * 255 * 255 1 byte characters. With a constant cost per string of 1 byte. This seems revolutionary.

It is impossible to create a perfect hash function, unless you have the complete dictionary (otherwise there is collision risk). If you have the full dictionary then there are perfect hash algorithms.

So, in essence, you want to add metadata to switch dictionaries, it is feasible: {Dictionary}{id}. You would have to consider out of dictionary words too.

By the way, note that UTF-8 is "compressed" (unlike UTF-32). Some languages don't use spaces to separate words, so you would have metadata problems in common languages like Chinese.

What I have done, and works pretty well, is using dictionary compression: sort a dictionary by frequency, replace the word with the rank in the dictionary (in base64 or something high), use spaces to separate words and use a dedicated symbol to escape out of dictionary words. Oh, and I was compressing lower case, mostly Spanish words. It gave me around 50% compression AND it can be used to run NLP algorithms without decompressing the data (like word2vec or TF-IDF).

Great answer, do you have a resource(tutorial)/code to share? (note that I assume I have the full dictiotnnary)

https://arxiv.org/abs/1311.2540

> The modern data compression is mainly based on two approaches to entropy coding: Huffman (HC) and arithmetic/range coding (AC). The former is much faster, but approximates probabilities with powers of 2, usually leading to relatively low compression rates. The latter uses nearly exact probabilities - easily approaching theoretical compression rate limit (Shannon entropy), but at cost of much larger computational cost. Asymmetric numeral systems (ANS) is a new approach to accurate entropy coding, which allows to end this trade-off between speed and rate: the recent implementation [1] provides about 50% faster decoding than HC for 256 size alphabet, with compression rate similar to provided by AC. This advantage is due to being simpler than AC: using single natural number as the state, instead of two to represent a range. Beside simplifying renormalization, it allows to put the entire behavior for given probability distribution into a relatively small table: defining entropy coding automaton. The memory cost of such table for 256 size alphabet is a few kilobytes. There is a large freedom while choosing a specific table - using pseudorandom number generator initialized with cryptographic key for this purpose allows to simultaneously encrypt the data. This article also introduces and discusses many other variants of this new entropy coding approach, which can provide direct alternatives for standard AC, for large alphabet range coding, or for approximated quasi arithmetic coding.

Check out his other papers / the github project (looked super interesting and similar).

Great find! At first glance this looks similar! I wonder if he has explored the idea of using multiple numbers for increasing the number of distinct "ASCII" tables.

Re leveraging UTF-8 for encoding text to be visually small: if you have your conflict-free hash as a binary number, you could do this fairly easily by making an 'empty' UTF8 char of the right length and replacing all the data bits with your hash, and it would be converted to a potentially invalid, but still transmissible, character for you (if you have to make the characters valid, you may need a lookup table to jump over these)

> My proposed scheme enable to have N * 255 * 255 1 byte characters. With a constant cost per string of 1 byte. This seems revolutionary.

The main issue in this context would be limitations in encoding enough languages - there are too many characters (144k in unicode) to encode in 256 code pages (16k max). Additionally, frequently switching code pages (for example swapping back to ascii to use Latin chars / numbers) would incur a large cost on the size of the string

Also note that some of the 'earlier' unicode symbols that don't fit into ascii are in 2 bytes as well, it's not just 1/3/4!

This is a basic version of many commonly used ideas for string compression in golfing languages. Jelly [0] is a good example of a more practical and versatile approach that builds on ideas such as this.

[0] https://github.com/DennisMitchell/jellylanguage/wiki/Tutoria...

Reply on news.ycombinator.com