an efficient C++/STL library for word puzzles and spell checking

• Download sourcecode
• Download dictionary

Introduction

This project started from a puzzle : There is a common English word that is nine letters long. Each time you remove a letter from it, it still remains an English word - from nine letters right down to a single letter. What is the original word, and what are the words that it becomes after removing one letter at a time? I wrote DicoLib to find the word, but since I stupidely translated "nine" by "8" in the code, I didn't find THE solution, but some others listed here DicoLib uses an original data structure that optimises the search of words which are "close" to a given one or contain the same letters. It is therefore suitable for spell checking, although this application hasn't (yet) been developed.

Data Structure

DicoLib's indexes words:

• by their length
• and by a bitset of 26 bits which describe which letters are present in the word

Actually, DicoLib stores a list of anagrams for each length/bitset pair. Finding anagrams of a given word therefore takes 0 time!

Finding words that are made of specified letters for Scrabble, or of a given length and contianing given letters is extremely fast as it requires mainly bitset operations and table lookup.

The whole data structure used in DicoLib is depicted in the schema below:

Source code

DicoLib is available on SourceForge You're welcome to contribute to the development of this project towards a very efficient spell-checker or any other application you may think of.

You must Sign In to use this message board.

FAQ    Noise Tolerance Very HighHighMediumLowVery Low   Layout Expand Posts & RepliesThread ViewNo JavascriptNo JS + Preview   Per page 102550

Msgs 1 to 2 of 2 (Total in Forum: 2) (Refresh) FirstPrevNext

Would have been valuable if a little more care were shown. WREY 9:49 16 Sep '05   Here's an example. You said, "... but since I stupidely translated "nine" by "8" in the code, I didn't find THE solution." IOW, you knew something was lacking, but still didn't correct it. I could not even get a clean compile from your code and the compiler itself quit after finding more than 30 errors!! Here's an example of one of the compiler's error which appeared at 6 different places, "WordList' : no appropriate default constructor available," which is true because you failed to include a constructor for the class. Draw your own conclusion, but if you had shown a little more care for this work, it would have shown, ... and it would have been more valuable. William Fortes in fide et opere! Sign In·View Thread·PermaLink 2.00/5 (1 vote) Broken link TheGlynn 1:15 14 Sep '05   The sourceforge link seems invalid. Couldnt you put the source on CP? Sign In·View Thread·PermaLink 5.00/5 (2 votes)

Last Visit: 13:10 23 Nov '09     Last Update: 13:10 23 Nov '09 1