Margana v1.1
------------

Thanks for choosing Margana. It is one-of-a-kind, as far as I can tell. I know
you will enjoy using it :)

ABOUT
-----
Margana is a general purpose interactive anagrammer, with the extra ability to
perform pattern-anchored anagramming. This feature is especially useful for
players of Scrabble and other word games.  

With Margana, I have included the Official Scrabble Player's Dictionary 3rd
edition wordlist (OSPD3) in the file called "words". This should save you some
time in finding a suitable wordlist.

See the technical details at the bottom for some banter about memory
management and tries


COMPILING
---------
Simply run 'make' in the directory you extracted from the tarball. You will
end up with an executable called "margana" in the current directory.


INVOKING
--------
Invoke margana with --help as its only commandline parameter for brief usage
information.

Margana needs to have a word list to operate. If no commandline parameters are
specified, it is assumed that the wordlist file is called "words" and is in
the current directory. To override this, you may specify an alternate filename
as the first commandline parameter to margana. Alternatively, this may be
changed permanently by changing the setting at the top of the source code, and
recompiling.


USING
-----
Margana prompts for a rack of letters, and a pattern of open letters and
surrounding spaces on the board. It then returns all words composed of at
least one letter on the board and at least one letter from your rack, that fit
_within_ the given pattern.

If the board pattern provided is a single * character, all possible anagrams
of any size, that can be made from your rack, will be shown.  If the board
pattern contains all ? characters, all anagrams of your letters that fit
within the number of spaces indicated will be shown.

To exit Margana, hit Ctrl-C.


EXAMPLE
-------
$ ./margana
Margana v1.0, (c) 2001 Moshe Jacobson <moshe@runslinux.net>
Invoke with --help for usage information.
Indexing dictionary . . . done.
Rack ('?' for blanks) []: margan?
Board pattern ('?' for open spaces), or * []: *
 aa      ab      ad      ae      ag      ah      ai      al      am      
 an      ar      as      at      aw      ax      ay      ba      em      
 . . .
 . . .
 bagman  barman  carman  engram  gagman  gasman  german  graham  gramas  
 granum  hangar  magian  manage  manger  mantra  margay  margin  marina  
 morgan  organa  parang  raglan  ragman  ragmen  sangar  anagram grandam 
 grandma manager tangram trangam 
Rack ('?' for blanks) [margan?]: ?a
Board pattern ('?' for open spaces), or * [*]: *
 aa ab ad ae ag ah ai al am an ar as at aw ax ay ba fa ha ka la ma na pa ta ya 
Rack ('?' for blanks) [a?]: testing
Board pattern ('?' for open spaces), or * [*]: ????p
 gip   nip   sip   tip   snip  step  genip 
Rack ('?' for blanks) [testing]: 
Board pattern ('?' for open spaces), or * [????p]: ???a?e????
 en      es      et      na      ta      age     ane     ate     eng     
 ens     eta     sea     tea     agee    ages    anes    ates    ease    
 egis    engs    etna    gane    gate    geta    sage    sane    sate    
 seta    tate    agene   agent   eaten   egest   enate   gates   nates   
 stage   stane   state   tates   tease   ageist  agenes  agents  enates  
 estate  ingate  negate  sateen  senate  tisane  ingates neatest negates 
Rack ('?' for blanks) [testing]: ^C
$


SUGGESTIONS
-----------
I welcome any suggestions, bug reports, etc. that you may have about Margana.
Please direct them to me at moshe@runslinux.net. 

I am especially looking for suggestions on how to minimize the memory usage of
Margana. Speed doesn't seem to be a problem now, but 13 megs of memory to
store a 1.7 meg dictionary file? Bah. Please let me know what you figure out.


OBTAINING
---------
The latest version of Margana is always available at:
http://runslinux.net/projects/margana


NOTES
-----
This program took a good bit of tweaking before it was released. If you'll
look at the source code, you'll notice that when the dictionary is indexed
into memory, it is stored into a data structure called a 'trie'. Each node in
this specialized tree represents a letter of a word. The head of the tree is
where you start when you want to look up a word. The head has (up to) 26
child nodes, each representing a letter of the alphabet. Say we wanted to look
up the word 'ace'. We would start at the head, and visit the 1st child node
(representing 'a'). From there, we'd visit the 3rd child node (representing
'c'). And finally, we'd go to the 5th child from there (representing 'e'). Now
we look at this node's boolean 'isword' indicator. If it is '1', 'ace' is a
word. If it is '0', 'ace' is not a word.

The problem with this trie structure, at first, was that most nodes in the
trie only had a small few children actually present, while the rest of the
child pointers were set to NULL. This lead to a huge waste in unused pointers.
When the program started up and indexed the dictionary, it would use 41 megs
of RAM! This, I felt, was unacceptable.

So I thought, what if there was a way not to allocate space for all those
unused pointers? Is there a way to make it so the most often used pointers
appear toward the start of the pointer array, so that I can allocate only as
much of the left side of the array as I needed? 

I decided to find the frequencies of each letter in the file, and use a
mapping from letters to their rankings, so that the most common letters would
appear toward the beginning of the child pointer arrays, and the least common
would appear toward the end, and I'd only malloc as much of the array as
neccessary. 

This took the program's memory footprint from 41 megs down to 16. I was
pleased, but I knew I could do better. I then decided to make the mapping
different for each letter. Indeed, there are different relative frequencies of
the letters in the alphabet when you consider them after each of the other
letters. So now we have a two dimensional array listing the rankings of each
letter after each other letter and at the start of words. Now the program took
only 13.5 megs of memory. 

Can I do better? I don't know. That's what I want YOU to figure out :)


Another interesting thing about this program is that it uses two different
algorithms for anagramming. The first that I wrote, which was quite easy,
would take in each dictionary word, one at a time, and see if it could make
that word with the letters on the rack. This always takes the same amount of
time to run, regardless of the size of your rack or how many blank tiles you
have. The only problem is that it can't do pattern anchored anagrams.

The 2nd algorithm used by Margana is to permute the rack letters into the
board space in all possible configurations, checking if each permutation is a
valid word. This is where the trie data structure comes in. Looking up words
in the trie is very fast. The time required to look up a word increases
linearly with the length of the word.  However, anagramming this way is very
slow nonetheless, especially when there are blank tiles on the rack. Each one
increases the running time by a factor of 26, as you can probably guess. This
is why I have disallowed this algorithm when the rack has over 2 blanks on it.


Anyway, that's about all I have to say. Enjoy the program!

- Moshe
