| |
Home
|
|
 |
Messages
|
|
| |
Chat
|
|
| |
Links
|
|
| |
Database
|
|
| |
Polls
|
|
| |
Calendar
|
|
| |
| |
| |
Promote
|
|
| |
| |
| |  = Owner | |
| |  = Moderator | |
| |  = Online | |
|
|
|
From:
Eric House <fixin@p...>
Date: Sun Sep 22, 2002 6:17
am
Subject: Re: [wgp] Boggle dictionary algorithm
|
> Yes, otherwise the tree would be larger than the word list... I've
> put the source at http://people.debian.org/~falk/dawg.tar.gz. It
> exploits the fact that the words come in in alphabetical order. I
> think that is also a known technique... I hope the source is
> understandable, if not, feel free to ask.
Some years ago when I started coding A&J's algorithm for Crosswords
(my PalmOS scrabble-like game) I had a conversation with one of the
authors (Jacobsen, I think) that resulted in my getting some
dawg-building code that was nearly instantaneous, but also
incomprehensible (to me). I stuck with the stuff I'd already written,
though it was maybe 100x slower.
Falk's algorighm is pretty much the same, but somehow now I can follow
it. I've recoded the compression part in perl, and while it's slower
than the C++ that inspired it it's still *much* faster (at least 20x)
and much less resource-hungry than my version. It's certainly fast
enough to use for an online dictionary-builder -- and so I'm on my
way. Thanks for sharing the code!
I'm posting my version here:
http://www.peak.org/~fixin/dict2dawg.pl.gz
It's not a complete replacement for Falk's app. There's no lookup
facility. More importantly, it doesn't yet output a binary
representation of the trie array. But that's a trivial change. I'm
posting now because the changes I make down the line will be in the
direction of Crossword's (and PalmOS's) requirements. I think it'll
be more useful to others while still in this form.
Thanks,
--Eric
******************************************************************************
* From the desktop of: Eric House, fixin@p... *
* Crosswords 4.0 for PalmOS is out!: <http://www.peak.org/~fixin/xwords> *
******************************************************************************
|
|
