Path: utzoo!utgpu!water!watmath!clyde!rutgers!umd5!purdue!i.cc.purdue.edu!j.cc.purdue.edu!h.cc.purdue.edu!s.cc.purdue.edu!rsk
From: rsk@s.cc.purdue.edu (Frozen Wombat)
Newsgroups: comp.unix.wizards
Subject: How to increase wordlist size in spell? (4.3BSD)
Keywords: spell, wordlist, hash
Message-ID: <1921@s.cc.purdue.edu>
Date: 12 Jan 88 20:48:39 GMT
Organization: Purdue Computing Center Unix Systems Staff
Lines: 47

I've recently tripled the size of the wordlist used by spell, and now
I'm running into problems with it; I strongly suspect that I'll have
to change some of the constants used to hash the wordlist, but I haven't
been able to nail down precisely what to do.

Here is what I believe to be the relevant code from spell.h:

#else (if unix is defined)
#define SHIFT	4
#define TABSIZE 25000	/*(int)(400000/(1<<shift))--pdp11 compiler deficiency*/
short	tab[TABSIZE];
#endif
long	p[] = { 399871, 399887, 399899, 399911, 399913,
	399937, 399941, 399953, 399979, 399983, 399989, };

#define	NP	(sizeof(p)/sizeof(p[0]))
#define	NW	30

/*
* Hash table for spelling checker has n bits.
* Each word w is hashed by k different (modular) hash functions, hi.
* The bits hi(w), i=1..k, are set for words in the dictionary.
* Assuming independence, the probability that no word of a d-word
* dictionary sets a particular bit is given by the Poisson formula
* P = exp(-y)*y**0/0!, where y=d*k/n.
* The probability that a random string is recognized as a word is then
* (1-P)**k.  For given n and d this is minimum when y=log(2), P=1/2,
* whence one finds, for example, that a 25000-word dictionary in a
* 400000-bit table works best with k=11.
*/

Now, the old spelling list had just under 25000 words; the new one
has just under 80000.  I figured that changing TABSIZE would do the
trick, but it doesn't appear to work.  Then I noticed that the table
p[] seems to be composed of primes close to 400000--and the 400000
comes into the picture because of the comment on TABSIZE.  I think,
but am not sure, that I'll have to come up with some new primes...but
honestly, I'm very confused.  I don't really understand the long comment
in the source, which is unfortunate, 'cause I suspect that the key
I need is there.

Can anyone explain this to me in a little more detail and/or tell me
what I need to do?  The users are gathered outside my office with torches
and things are getting ugly...

Thanks,
Rich Kulawiec, rsk@s.cc.purdue.edu, s.cc.purdue.edu!rsk