Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How Unix spell ran in 64kb RAM

blog.codingconfessions.com

Post reply on HN
Print view View original

41–50 of 53 posts

Re: How Unix spell ran in 64kb RAM

#41

Post by yencabulator »

stevekemp wrote: post #29
eichin wrote: post #17

For perspective, in 1983 or so, Grammatik on CP/M ran in under 64k and did "grammar checking" (spell checking, plus a bunch of expert system rules) on an 8-bit system. (It sticks in my memory because of the time spent poking at the really interesting part: that it was so compact because it was in Forth, and there was enough of an outer interpreter in the product that with a little hex editing you could just use it as…

The Wordstar editor I run on my own CP/M system, with 64k of RAM, contains the 2023-byte long "SPELL.COM" spell-checker. I've not decompiled it to see how it works, but it's small and fast, and works well.

You have to count the size of the dictionary too. See "DICT.DIC".

https://dflund.se/~pi/cpm/files/ftp.mayn.de/pub/cpm/archive/...

Re: How Unix spell ran in 64kb RAM

#42

Post by yencabulator »

MarkusWandel wrote: post #4

Marginally related... has anyone ever ported the "typo" program to modern C?

How about Go? I think that counts as "modern C" ;-)

This is pretty much the real thing: https://github.com/robpike/typo

(If you're crabby about it, this is similar: https://github.com/crate-ci/typos/)

Re: How Unix spell ran in 64kb RAM

#43

Post by Theodores »

I can remember using UNIX spell with the '-b' option, because I am British. There were only two language options, and now I want to know what the decision making was behind that, how the code catered for that and where the respective dictionaries came from. Did Australians and New Zealanders use British spelling or American?

UNIX spell was the 'ZX81 1K chess' of spelling, and, on home computers, we did not have a lot of spell checking going on until MS Word for Windows 3.1. Before then, in offices, secretaries did the typing with WordPerfect. They were human spell checkers for their respective managers and teams.

Meanwhile, at home, with our dot matrix printers and flickery screens, we were winging it with paper dictionaries for all of those early years of computing. I can't remember spell checking as being that important back then as everyone could spell. I was in a school of a thousand and there was only one kid that claimed to be dyslexic, a plausible excuse for not being able to spell. Maybe the 1980s was literacy's golden age with there being a clear start date for the decline in our spelling ability, that being the day UNIX spell was written.

I like to play Scrabble. Although a very different problem to spell checking, the process shares some steps with UNIX spell. Common word prefixes and suffixes are identified and bolted together in the rack or on the board with other components. Then a Scrabble dictionary is a bit like UNIX spell as it is just a big dictionary of words with no meanings provided. All that matters is whether a given word is in the book or not. It also has a few special look up tables such as the 102 two letter words.

Re: How Unix spell ran in 64kb RAM

#44

Post by 1vuio0pswjnm7 »

"In order to secure funding for Unix, Ken Thompson and Dennis Ritchie pitched Unix as a text processing system for the patents department to AT&T. Naturally, a text processing system needed a spell checker as well."

I still use UNIX every day primarily for text processing.

Re: How Unix spell ran in 64kb RAM

#45

Post by MatthiasWandel »

Theodores wrote: post #43

I can remember using UNIX spell with the '-b' option, because I am British. There were only two language options, and now I want to know what the decision making was behind that, how the code catered for that and where the respective dictionaries came from. Did Australians and New Zealanders use British spelling or American? UNIX spell was the 'ZX81 1K chess' of spelling, and, on home computers, we did not have a lot…

I remember spell checking my essays for high school on the commodore 64, using Paperclip 64, in 1984, Before there was ANY Microsoft windows. Spell check took a few minutes, because it read the dictionary from disk as it checked, and after that you could go thru all the words that it couldn't match.

Re: How Unix spell ran in 64kb RAM

#46

Post by cb321 »

probably_wrong wrote: post #37
PaulHoule wrote: post #12

You can write an external memory spell checker with a tiny amount of RAM: something like - sort the words in the document - eliminate unique words (they sort together) - merge the sorted words with the sorted dictionary and keep only the missing words I saw this in BASIC in Creative Computing and got it working in on my TRS-80 Color Computer which had much less than 32k of available RAM, so that was the first thing I…

Worth noting that the article mentions this alternative as their first PoC and its drawbacks: "Because of its simplistic implementation, it was not very accurate, and also slow because of dictionary lookups on the disk."

I have a feeling the algorithm used was not the smart merge mentioned in the grandparent. That "slower" spell was in v6 Unix { https://en.wikipedia.org/wiki/Spell_(Unix) } which came out in 1975 and by 1973 there were already Winchester drives doing 885 kB/s with 25ms seeks { https://en.wikipedia.org/wiki/History_of_IBM_magnetic_disk_d... }. A 250e3 word dictionary with average word length of 10 bytes would have only taken about 2500e3/885e3 = 2.8 seconds to scan and the unique words in most documents in practice would have easily fit in RAM (as mentioned in Doug's 1982 paper). Not great, but not so bad, either. People didn't spell check on every key press for another 10 years. ;-)

Someone probably could look all this up in the "unified version control of all Unix" history, but the way Doug describes it in the 1982 paper linked in the article, it sounds like the v6 spell did a "doc word at a time loop" instead of "sort all doc words at once and merge against a pre-sorted dictionary", and in fact it sounds like Johnson selected a small dictionary to facilitate that instead of "merging".

Re: How Unix spell ran in 64kb RAM

#47

Post by PaulHoule »

cb321 wrote: post #46
probably_wrong wrote: post #37

Earlier quoted context omitted.

Worth noting that the article mentions this alternative as their first PoC and its drawbacks: "Because of its simplistic implementation, it was not very accurate, and also slow because of dictionary lookups on the disk."

I have a feeling the algorithm used was not the smart merge mentioned in the grandparent. That "slower" spell was in v6 Unix { https://en.wikipedia.org/wiki/Spell_(Unix) } which came out in 1975 and by 1973 there were already Winchester drives doing 885 kB/s with 25ms seeks { https://en.wikipedia.org/wiki/History_of_IBM_magnetic_disk_d... }. A 250e3 word dictionary with average word length of 10 bytes would have only…

It's easy to compress a sorted dictionary by turning something like

  a
  ab
  abc
to

  a
  1b
  2c
where the prefix is the number of characters shared with the last word (and might be coded as a byte as opposed to a digit like you're thinking there. This would be a simple form of compression to code up in BASIC unlike Huffman or most LZW variants which involve bit twiddling and maintaining tree data structures... Though I do remember writing SQ and USQ [1] in BASIC)

[1] https://techtinkering.com/articles/compression-and-archiving...

Re: How Unix spell ran in 64kb RAM

#48

Post by Theodores »

MatthiasWandel wrote: post #45
Theodores wrote: post #43

I can remember using UNIX spell with the '-b' option, because I am British. There were only two language options, and now I want to know what the decision making was behind that, how the code catered for that and where the respective dictionaries came from. Did Australians and New Zealanders use British spelling or American? UNIX spell was the 'ZX81 1K chess' of spelling, and, on home computers, we did not have a lot…

I remember spell checking my essays for high school on the commodore 64, using Paperclip 64, in 1984, Before there was ANY Microsoft windows. Spell check took a few minutes, because it read the dictionary from disk as it checked, and after that you could go thru all the words that it couldn't match.

Was your copy of Paperclip 64 pirated?

Re: How Unix spell ran in 64kb RAM

#50

Post by svat »

Just finished reading the article finally (thanks!). The crux of it for me was:

- They had a "dictionary" of 30000 words, and accepting a ~1/4000 rate of false positives meant that if they hashed each word to a 27-bit string (integer), they could throw away the dictionary and the problem reduces to storing a set of 30000 27-bit strings.

- Somewhat surprisingly, information theory tells us that 30000 27-bit strings can be stored using not 27 but just ~13.57 bits per word. I understand the math (it's straightforward: https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+3... ) but it will probably take me a while to stop finding this counterintuitive, as 30000 is so small compared to 2^27 (which is ~134 million) that it is hard to see where the gains come from.

- To encode this 30000-sized subset of 27-bit hashes, they used hash differences, which turn out to be geometrically distributed, and a coding scheme tuned for geometrically distributed input (Golomb coding), to actually achieve ~13.6 bits per word.

I've tried to think of how one could do better, even in principle and with infinite time, along the lines of “perfect hashing” — maybe there should be a function that will take an alphabetic word, do some transformations on it, and the resulting hash will be easy to verify for being in the good set vs not. But thinking about it a bit more, the fact that we need that false-positive rate (non-dictionary words shouldn't get mapped to anything in the "good" set) requires us to use at least 27 bits for the hash. What they did seems basically theoretically optimal? Or can there exist a way to map each word to a 27-bit integer, such that the good strings are those with values less than 30000, say?

Post reply on HN