• 1 Post
  • 65 Comments
Joined 2 years ago
Cake day: July 1st, 2023
  • NoSpotOfGround@lemmy.worldtoTechnology@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 todayEnglish
    891·
    4 days ago

    The 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.

  • NoSpotOfGround@lemmy.worldtoAsk Lemmy@lemmy.world•times you've been called out that stuck with you?
    2·
    5 days ago

    No, never did find it… But I’m pretty sure now that pen really was his. It was just a mildly unlikely coincidence that he had one just like mine.

    The way I felt at the time that I’d been conned out of some things in the past had me set a bit too hard on “not being fooled again”, and I overdid it.

    One particular case I remember is exchanging toy cars with someone, and them claiming later that day that they lost the car i just gave them. So I spent a good few minutes looking for it with them. I even insisted “no, let’s look again” when they suggested we give up. I felt bad that they’d lost out on our exchange, so I gave them back the car they’d given me, just to ease their misfortune. Only to hear the next day how they’d been bragging about fooling me. Gah.

  • NoSpotOfGround@lemmy.worldtoAsk Lemmy@lemmy.world•times you've been called out that stuck with you?
    6·
    5 days ago

    I had a similar thing with a pen, the very same year I think… I had a mildly special pen which one day I lost. Went looking for it and found it sitting on a (slightly older) classmate’s desk, so i grabbed it and said “hey, that’s mine”. He tried to pretend that no, it was his, and he sounded very convincing about it, and even got the teacher involved. They both looked at me with infuriatingly condescending expressions as I explained how it was mine.

    The teacher suggested “just let him have it” to the classmate, who conceded.

    I went back to my desk fuming and scratched my initials into it before returning to show them, "look, see, it was mine! The classmate immediately pointed out “you scratched those in just now” and I think I mumbled something incoherent before going back to my desk, to the teacher’s mortification with the whole situation.

    It had already begun dawning on me at this point that the classmate was right… This wasn’t my pen. It was his and just looked like mine. But it was too late at this point and I didn’t know how to handle it other than to keep quiet and try to forget about it.