Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!apple!casseres@apple.com From: casseres@apple.com (David Casseres) Newsgroups: comp.sys.mac.misc Subject: Re: Font Naming Substitution (was Mac Draw Problem) Message-ID: <13413@goofy.Apple.COM> Date: 9 May 91 00:49:56 GMT References: <009480F2.1F0C0720@uclapp.physics.ucla.edu> <6361@crystal9.UUCP> <13396@goofy.Apple.COM> <1991May8.182323.29189@netcom.COM> Sender: usenet@Apple.COM Distribution: usa Organization: Apple Computer Lines: 45 In article <1991May8.182323.29189@netcom.COM>, chas@netcom.COM (Chuck Fisher) writes: > Times Roman comes from the *London Times* and not the New York Times. > Helvetica did not originate from Switzerland, but was named by it's > creator for that country. I stand corrected; thanks. David Casseres 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.