How would one represent a dictionary? This is not specifically LISP but
I am trying to think of it in terms of LISP. What I want to do is create
a dictionary of words where I can look words up by the first letter and
then successive letters until I either hit a word or no such prefix of
the word exists.
So for example, if I passed in "c" it would return "yes, there are 'c'
words." Then if I passed in "cr" it would return "yes, there are 'cr'
words." And so on until either "cruft" returns the word "cruft" or
"crunt" returns "no words begin with "crunt."
What would be the best way to represent this data?
k
--------------------------------------
The last good thing written in C was Franz Schubert's Symphony number 9.
-- Erwin Dieterich
Karstens Rage wrote:
> How would one represent a dictionary? This is not specifically LISP but
> I am trying to think of it in terms of LISP. What I want to do is create
> a dictionary of words where I can look words up by the first letter and
> then successive letters until I either hit a word or no such prefix of
> the word exists.
>
> What would be the best way to represent this data?
>
Try "Ternary Search Trees"
http://www.cs.princeton.edu/~rs/strings/
On Fri, 28 Oct 2005 23:01:08 -0700, Karstens Rage <········@rage.com>
tried to confuse everyone with this message:
>How would one represent a dictionary? This is not specifically LISP but
>I am trying to think of it in terms of LISP. What I want to do is create
>a dictionary of words where I can look words up by the first letter and
>then successive letters until I either hit a word or no such prefix of
>the word exists.
>
>So for example, if I passed in "c" it would return "yes, there are 'c'
>words." Then if I passed in "cr" it would return "yes, there are 'cr'
>words." And so on until either "cruft" returns the word "cruft" or
>"crunt" returns "no words begin with "crunt."
>
>What would be the best way to represent this data?
>
Sorting it alphabetically with a red-black tree or B-tree.
--
|a\o/r|,-------------.,---------- Timofei Shatrov aka Grue ------------.
| m"a ||FC AMKAR PERM|| mail: grue at mail.ru http://grue3.tripod.com |
| k || PWNZ J00 || Kingdom of Loathing: Grue3 lvl 18 Seal Clubber |
`-----'`-------------'`-------------------------------------------[4*72]
On 2005-10-29 07:01:08 +0100, Karstens Rage <········@rage.com> said:
> How would one represent a dictionary? This is not specifically LISP but
> I am trying to think of it in terms of LISP. What I want to do is create
> a dictionary of words where I can look words up by the first letter and
> then successive letters until I either hit a word or no such prefix of
> the word exists.
>
> So for example, if I passed in "c" it would return "yes, there are 'c'
> words." Then if I passed in "cr" it would return "yes, there are 'cr'
> words." And so on until either "cruft" returns the word "cruft" or
> "crunt" returns "no words begin with "crunt."
>
> What would be the best way to represent this data?
The "best" way is probably more a matter of actual measurements
than of opinion ...
If you are interested in accessing your dictionary with prefix
only queries, then a not too bad idea is simply:
- have your dictionary sorted alphabetically as a unique list
of words (array of strings)
- when you want to know whether the word with prefix "xyz"
is in the dictionary, use a binary-search. It will return
the index of the first such word, or the index of where
such word would need to be "inserted" if no such word
exist.
- when the binary search returns you only have to check whether
the word at that index really starts with your prefix.
For a 100,000 words dictionary, telling you the answer will
involve at most 17 attempts (log(100000)/log(2))
--
JFB (defun is more fun than define is fine)
On Fri, 28 Oct 2005 23:01:08 -0700, Karstens Rage wrote:
> How would one represent a dictionary? This is not specifically LISP but
> I am trying to think of it in terms of LISP. What I want to do is create
> a dictionary of words where I can look words up by the first letter and
> then successive letters until I either hit a word or no such prefix of
> the word exists.
Not exactly the same problem, but along the same lines...
http://www.livejournal.com/users/abstractstuff/1642.html
Might give you some inspiration.
Oh, BTW, most people spell it "Lisp" rather than "LISP" these days.
Best wishes,
Bill.