The Results
By now you are no doubt dying to see some results from the program. But first, to scope the size of the problem, here's the output from the program as the good_words hashes are populated on a run against SINGLE.TXT, a 354,985 word database:
Loading words from: SINGLE.TXT
Loaded 354985 words from SINGLE.TXT
Found 431 eligible words out of 431 total at length 2
Found 2075 eligible words out of 2092 total at length 3
Found 6213 eligible words out of 6758 total at length 4
Found 11322 eligible words out of 15047 total at length 5
Found 12495 eligible words out of 28473 total at length 6
Found 8939 eligible words out of 40094 total at length 7
Found 4295 eligible words out of 49528 total at length 8
Found 1210 eligible words out of 51216 total at length 9
Found 174 eligible words out of 43964 total at length 10
Found 20 eligible words out of 36082 total at length 11
Found 0 eligible words out of 28009 total at length 12
So that means about 13 percent of the words in this vocabulary were good words. I'm a little surprised that it's that high. To add some sanity to the mix, I removed all the single character words from SINGLE.TXT with the exception of a and i, and the ratio went down to a more reasonable 8 percent.
You can also see, as you would expect, that the proportion of good words goes down at each level. At lengths 2, 3, and 4 nearly all words are good words, but by the time we get to length 11, we're down to less than one-tenth of one percent good.
Even with my modified version of SINGLE.TXT, you're bound to get plenty of esoteric words when working your way through the derivation of an 11 or 10 character good word. Of the 18 words of eleven characters, the derivation that works best with my vocabulary would be the following:
sparklingly
sparkingly
sparingly
springly
springy
spring
sprig
prig
pig
pi
i
With the more manageable scrabble.dict dictionary, containing 79,340 words, some of the first sequences that pop out include:
shopping hopping hoping oping ping pig pi i
breaches beaches baches aches aces ace ae a
marchese marches arches aches aces ace ae a
prawning pawning awning awing wing win in i
stablest stalest stales tales ales als as a
bravoing braving raving ravin rain ain in i
failings filings flings lings lins ins is i
relaters elaters elates elate late ate ae a
roadster roaster raster rater rate ate ae a
semioses semises seises seise seis sis is i
clambers lambers lamber lamer lame lam am a
claviers clavers lavers avers aves ave ae a
shrieves shrives shives hives hies his is i
stalkier talkier talker taker take tae ae a
statutes statues states tates ates ate ae a
swarming warming waring wring ring rin in i
brambled rambled ambled amble able ale ae a
stratous stratus status stats tats tas as a
paddlers paddles padles pales ales als as a
thirling tirling tiring iring ring rin in i
trucking trucing truing ruing ring rin in i
brawlier brawler bawler baler bale ale ae a
frilling filling filing fling ling lin in i
carouses arouses arouse arose arse are ae a
No doubt there are still plenty of obscure words here, but remember, this dictionary is probably composed of at least 50 percent words that aren't in your working vocabulary.
Efficiency
When run against a word list with 350K+ entries on my anemic notebook computer, it takes almost 10 seconds for the program to terminate, including display time. The vast majority of that time is spent checking words for goodness, which requires removing characters one at a time, then checking to see if their small descendants are in the word list.
Obviously, if you want to optimize this program for better performance, that's the place to do it. My guess would be that the std::string class member to erase characters from a word is probably far from optimal, and could be replaced by a hand-coded routine designed to do the same task with much greater speed.
Issues With Non-Standard Library Functions
Because hashed containers did not make it into the original C++ standard, there is a somewhat higher level of peril when using them. Problems ranging from syntactic inconsistency to lack of performance guarantees definitely make hash_set and hash_map second class citizens compared to the other standard containers. I saw a good example of this when I first started work on this article.
When solving this problem, the first thing that seemed obvious to me was that we were going to be storing references to dictionary words in hash tables. And I thought it might be interesting to see how well the C++ hash classes were going to be able to handle input data with hundreds of thousands of words.
I thought a good test program would be one that simply reads in the text file and adds it to a hash set:
hash_set<std::string> words;
while ( input ) {
std::string word;
input>> word;
words.insert( word );
count++;
if ( ( count % 100 ) == 0 )
std::cout <<count <<"\r";
}
Under Visual C++ .NET 2005 on a fairly slow laptop, I immediately saw a nasty problem with the Microsoft implementation of hash_set. Every time the counter hit a an even power of two, there was a bit of a pause. The pause grew longer and longer as the count grew larger, until by the time I was up to 128K words, it stretched out to many seconds.
Lesson learned. Hash table resizing can be expensive under some implementations of this non-standard class. Just resizing hash tables in any implementation can be difficult, but the additional requirements imposed on C++ library containers adds significantly to the work that must be done at this point.
I hoped that I would find a reserve() method or a constructor option that would let me preallocate a hash_set with perhaps 200K buckets, but this doesn't seem to be possible with Microsoft's implementation. The good news is that the hash_set replacement in TR1, unordered_set, will impose a requirement that conforming libraries allow for a bucket count as part of the container's constructor.
It turned out to not be too important, however. As I worked on the implementation of the algorithm, I drastically reduced the number of strings that were stored in any one hash, making this a moot point.
Source Code
You can download the source code here or here, including project files for Visual Studio 2003 and 2005, and a simple Makefile for gcc. The code has been checked under gcc 3.4, but I make no claims that it will work with all later versions of the library.
References
Ward, Grady. "Moby Word Lists by Grady Ward - Project Gutenberg." Main Page - Gutenberg. 12 Nov. 2007 www.gutenberg.org/etext/3201.
"ISO/IEC JTC1/SC22/WG21 - The C++ Standards Committee." Open Standards. 13 Nov. 2007 www.open-std.org/jtc1/sc22/wg21/.
