{"id":14182,"date":"2025-08-20T11:23:01","date_gmt":"2025-08-20T18:23:01","guid":{"rendered":"https:\/\/mattfife.com\/?p=14182"},"modified":"2025-05-24T11:45:18","modified_gmt":"2025-05-24T18:45:18","slug":"putting-spell-check-in-64k-of-ram","status":"publish","type":"post","link":"https:\/\/mattfife.com\/?p=14182","title":{"rendered":"Putting spell check in 64k of RAM"},"content":{"rendered":"\n<p><a href=\"https:\/\/substack.com\/@abhinavupadhyay\">Abhinav Upadhyay<\/a> walks us through a wonderful bit of computer history. He talks about how <a href=\"https:\/\/blog.codingconfessions.com\/p\/how-unix-spell-ran-in-64kb-ram\" data-type=\"link\" data-id=\"https:\/\/blog.codingconfessions.com\/p\/how-unix-spell-ran-in-64kb-ram\">Steve Johnson at AT&amp;T wrote one of the first spell checkers<\/a>. His method could encode a word in just 14 bits of memory; so a dictionary with 30,000 entries would take up a fraction under 52 kB. This is even better compression than gzip &#8211; and it can perform fast lookups.<\/p>\n\n\n\n<p>Once the dictionary grew to 30,000 words, the <a href=\"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/362686.362692\" data-type=\"link\" data-id=\"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/362686.362692\">Bloom filter<\/a> approach became impractical. Douglas McIlroy&#8217;s solution was to store differences between sorted hash codes , after discovering these differences followed a geometric distribution. These followed a distribution that could be easily run length encoded with something called <a href=\"https:\/\/web.stanford.edu\/class\/ee398a\/handouts\/papers\/Golomb%20-%20Run-Length%20Codes%20-%20IT66.pdf\" data-type=\"link\" data-id=\"https:\/\/web.stanford.edu\/class\/ee398a\/handouts\/papers\/Golomb%20-%20Run-Length%20Codes%20-%20IT66.pdf\">Golomb&#8217;s code<\/a>.<\/p>\n\n\n\n<p>It&#8217;s a fantastic examination of applied computer science. Definitely worth a read<\/p>\n\n\n\n<p>Articles:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/blog.codingconfessions.com\/p\/how-unix-spell-ran-in-64kb-ram\">https:\/\/blog.codingconfessions.com\/p\/how-unix-spell-ran-in-64kb-ram<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/www.pcgamer.com\/software\/implementing-a-spellchecker-on-64-kb-of-ram-back-in-the-1970s-led-to-a-compression-algorithm-thats-technically-unbeaten-and-part-of-it-is-still-in-use-today\/\">https:\/\/www.pcgamer.com\/software\/implementing-a-spellchecker-on-64-kb-of-ram-back-in-the-1970s-led-to-a-compression-algorithm-thats-technically-unbeaten-and-part-of-it-is-still-in-use-today\/<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Abhinav Upadhyay walks us through a wonderful bit of computer history. He talks about how Steve Johnson at AT&amp;T wrote one of the first spell checkers. His method could encode a word in just 14 bits of memory; so a dictionary with 30,000 entries would take up a fraction under 52 kB. This is even better compression than gzip &#8211; and it can perform fast lookups. Once the dictionary grew to 30,000 words, the Bloom filter approach became impractical. Douglas&#8230;<\/p>\n<p class=\"read-more\"><a class=\"btn btn-default\" href=\"https:\/\/mattfife.com\/?p=14182\"> Read More<span class=\"screen-reader-text\">  Read More<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[9,7,5],"tags":[],"class_list":["post-14182","post","type-post","status-publish","format-standard","hentry","category-cool","category-technicalprogramming","category-technical"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p4WECr-3GK","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/mattfife.com\/index.php?rest_route=\/wp\/v2\/posts\/14182","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mattfife.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mattfife.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mattfife.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mattfife.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=14182"}],"version-history":[{"count":5,"href":"https:\/\/mattfife.com\/index.php?rest_route=\/wp\/v2\/posts\/14182\/revisions"}],"predecessor-version":[{"id":14187,"href":"https:\/\/mattfife.com\/index.php?rest_route=\/wp\/v2\/posts\/14182\/revisions\/14187"}],"wp:attachment":[{"href":"https:\/\/mattfife.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=14182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mattfife.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=14182"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mattfife.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=14182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}