Meh. He only had $23.50 in his account.
NoSpotOfGround
- 4 Posts
- 4 Comments
NoSpotOfGround@lemmy.worldto Technology@lemmy.world•Blocking real-world ads: is the future here?English11·14 days agoI’m all for the “SLEEP 8 HOURS” bit though. I need more of that in my life.
NoSpotOfGround@lemmy.worldto Technology@lemmy.world•AI search finds publishers starved of referral trafficEnglish7·20 days agoYou had one job.
NoSpotOfGround@lemmy.worldto Technology@lemmy.world•Implementing a spellchecker on 64 kB of RAM back in the 1970s led to a compression algorithm that's technically unbeaten and part of it is still in use todayEnglish1·3 months agoThe real meat of the story is in the referenced blog post: https://blog.codingconfessions.com/p/how-unix-spell-ran-in-64kb-ram
TL;DR
If you’re short on time, here’s the key engineering story:
-
McIlroy’s first innovation was a clever linguistics-based stemming algorithm that reduced the dictionary to just 25,000 words while improving accuracy.
-
For fast lookups, he initially used a Bloom filter—perhaps one of its first production uses. Interestingly, Dennis Ritchie provided the implementation. They tuned it to have such a low false positive rate that they could skip actual dictionary lookups.
-
When the dictionary grew to 30,000 words, the Bloom filter approach became impractical, leading to innovative hash compression techniques.
-
They computed that 27-bit hash codes would keep collision probability acceptably low, but needed compression.
-
McIlroy’s solution was to store differences between sorted hash codes, after discovering these differences followed a geometric distribution.
-
Using Golomb’s code, a compression scheme designed for geometric distributions, he achieved 13.60 bits per word—remarkably close to the theoretical minimum of 13.57 bits.
-
Finally, he partitioned the compressed data to speed up lookups, trading a small memory increase (final size ~14 bits per word) for significantly faster performance.
-
deleted by creator