Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!tut.cis.ohio-state.edu!ucbvax!tardis.computer-science.edinburgh.ac.uk!gtoal From: gtoal@tardis.computer-science.edinburgh.ac.uk Newsgroups: comp.os.msdos.misc Subject: Re: WANTED : Searching Algorithms to search in a dictionary Message-ID: <9105081944.AA04038@ucbvax.Berkeley.EDU> Date: 8 May 91 07:17:34 GMT References: <91125.142221GELDREIC@FRECP12.BITNET> Sender: daemon@ucbvax.BERKELEY.EDU Organization: Unix Anarchy, Edinburgh University. Lines: 40 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 --- Excuse late responses fom this site - we get News 4 days late on average.