4 ms·

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 representi

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.

drchickensalad 10y ago
Is this in programming pearls? Otherwise where?
- pklausler 10y ago
  I saw it in a column in Comm. of the ACM a long time ago, sorry.
  - dalke 10y ago
    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.googlecode.com/svn/trunk/McIlroy_spell_1982.pdf https://web.archive.org/web/20120324185456/http://unix-spell... . I found it from https://code.google.com/archive/p/unix-spell/ 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=803658785&CFTOKEN=18698707 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 http://www.linuxjournal.com/article/3846 .
warrenmar 10y ago
Marissa Mayer's interview at Google was using Bloom filter for spell check.
Animats 10y ago
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 http://www.animats.com/source/obvious/obvious.c

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.

drchickensalad 10y ago

Is this in programming pearls? Otherwise where?

pklausler 10y ago
I saw it in a column in Comm. of the ACM a long time ago, sorry.
- dalke 10y ago
  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.googlecode.com/svn/trunk/McIlroy_spell_1982.pdf https://web.archive.org/web/20120324185456/http://unix-spell... . I found it from https://code.google.com/archive/p/unix-spell/ 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=803658785&CFTOKEN=18698707 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 http://www.linuxjournal.com/article/3846 .

warrenmar 10y ago

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

Animats 10y ago

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 http://www.animats.com/source/obvious/obvious.c