Hacker News Reader

Comment by pklausler | Hacker News Reader

If you like hash functions and Bloom filters, you'll also enjoy Jon Bentley's description of the original UNIX spell(1) utility, which ran in 64KB by representing its dictionary as a sparse bitmap.

View on HN

I did something like that in my "Obvious password detector"[1] in 1984. This is for use in password-changing programs, to detect if a password is too obvious. It uses a 3D array of bits, 27x27,27, representing trigraphs seen in the UNIX dictionary, plus a few extras such as "aaa", "bbb", etc. Only about 30% of the possible trigraphs are used in English, so most strings that aren't a word will pass. This provides simple protection against most dictionary attacks.

[1] http://www.animats.com/source/obvious/obvious.c

Marissa Mayer's interview at Google was using Bloom filter for spell check.

Is this in programming pearls? Otherwise where?

I saw it in a column in Comm. of the ACM a long time ago, sorry.

McIlroy's "Development of a Spelling List" (1982) paper is doi:10.1109/TCOM.1982.1095395 available at https://web.archive.org/web/20120324185456/http://unix-spell... . I found it from https://code.google.com/archive/p/unix-spell/ , which also says:

> It is interesting to note that one of the world's best compressor (paq8l) can compress the 250kb word list down to 48.5kb, less than the space taken by the lossy compression methods proposed in the paper! For comparison, regular modern compression methods (such as gzip, lzma etc) only achieve twice that size (85-90kb).

Bentley's commentary is in "A Spelling Checker", CACM 28(5): 456-462 (1985), doi:10.1145/3532.315102 , behind the paywall at http://dl.acm.org/citation.cfm?id=315102&dl=ACM&coll=DL&CFID... and in the book "Programming Pearls", Second Edition, according to http://www.linuxjournal.com/article/3846 .

Reply on news.ycombinator.com