Re: Dictionary

On 2005-10-29 07:01:08 +0100, Karstens Rage <karstens@xxxxxxxx> 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)

.

Relevant Pages

  • Re: merits of Lisp vs Python
    ... The prefix position needs of more abstraction ... LISP form is confusing. ... region in the hypersurface and localization is 'infix'. ... I am not trying to convince some LISPer to change the chip; ...
    (comp.lang.lisp)
  • Re: Why is LISP syntax superior?
    ... mathematical notation, when it is really related to the own LISP ... have some kind of prefix-based syntax for handling declarations, ... once you have a language defined entirely by this prefix ...
    (comp.lang.lisp)
  • Re: merits of Lisp vs Python
    ... So chemists will use an infix package, ... As already said any infix Lisp ... boy/girl and confront him/her his/her life with mostly prefix syntax. ... people does in math, science, enginnering, almost any programming ...
    (comp.lang.lisp)
  • Re: merits of Lisp vs Python
    ... Whereas i wait that a core of LISP ... in lisp prefix notation for mathematical formula? ... For instance, Python uses explicit * for products, but Mathematica ... syntax assumes product for two adjacent tokens. ...
    (comp.lang.lisp)
  • Re: efficiently accumulating values
    ... Python version as well. ... Here is the lisp I wrote when I fisrt came with my questions. ... Just to store a prefix we first cons up an entire copy of the prefix? ... but it seems to me you need some costless way to take a full word and hand increasingly long subsequences to gethash just by incrementing a pointer. ...
    (comp.lang.lisp)