bking@nro.cs.athabascau.ca (Barry King) (05/04/91)
GELDREIC@FRECP12.BITNET (David GELDREICH) writes: > > Hi netland, > > I am currently trying to make a software to help people to resolve crosswor > . I would like to find an algorithm which will allow me to find all the words > atching, for example ??i?ing. > > I would like to know how can I index my dictionary to find easily a word kn > ing only some of its letters. And which algorithm would I use to access this > ctionary. > Are you familiar with the Soundex algorithm? It might not entirely fit the bill but it and related algortihms may help your quest. If you have access to Compuserve, I'm pretty sure I've seen sample code there. Other than that, it should be fairly easy to locate in a book somewhere... Barry King ersys!bking@nro.cs.athabascau.ca Edmonton Remote Systems: Serving Northern Alberta since 1982
GELDREIC@FRECP12.BITNET (David GELDREICH) (05/06/91)
Hi netland,
I am currently trying to make a software to help people to resolve crosswords
. I would like to find an algorithm which will allow me to find all the words m
atching, for example ??i?ing.
I would like to know how can I index my dictionary to find easily a word know
ing only some of its letters. And which algorithm would I use to access this di
ctionary.
(Any pointer to PD software of this kind would also be appreciated).
Thanx in advance.
David Geldreich (Ecole Centrale Paris)gtoal@tardis.computer-science.edinburgh.ac.uk (05/08/91)
In article <91125.142221GELDREIC@FRECP12.BITNET> GELDREIC@FRECP12.BITNET (David GELDREICH) writes: > >Hi netland, > > I am currently trying to make a software to help people to resolve crosswords >. I would like to find an algorithm which will allow me to find all the words m >atching, for example ??i?ing. > > I would like to know how can I index my dictionary to find easily a word know >ing only some of its letters. And which algorithm would I use to access this di >ctionary. > > (Any pointer to PD software of this kind would also be appreciated). > > Thanx in advance. > > David Geldreich (Ecole Centrale Paris) ---- The optimal data structure for this sort of work is called a 'dawg' - a Directed Acyclic Word Graph. As it happens, I've already written the exact prpgram you are looking for; and have hacked the dawg structure into other netlander's programs (in the word-game field) with promising results. I posted a set of routines to access dawgs on alt.sources just over a year ago ('dawgutils.*'), and Austin Code Works also include a copy in their Spell Pack' if you know someone who has that. Failing that, mail me & I'll mail them to you. The dawg structure is explained in Appel & Jacobson's CACM paper on 'The Fastest Scrabble Program in the World'. (Several years old, and don't have the ref to hand; I'll look it up for you if you're interested) Regards Graham <gtoal@ed.ac.uk> --- Excuse late responses fom this site - we get News 4 days late on average.