home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / rec / puzzles / 8503 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  3.8 KB
  1. Path: sparky!uunet!munnari.oz.au!bunyip.cc.uq.oz.au!uqcspe!cs.uq.oz.au!warwick
  2. From: warwick@cs.uq.oz.au (Warwick Allison)
  3. Newsgroups: rec.puzzles
  4. Subject: Re: Computer Dictionary Searches
  5. Message-ID: <11811@uqcspe.cs.uq.oz.au>
  6. Date: 22 Jan 93 01:12:09 GMT
  7. References: <1993Jan20.185756.16017@njitgw.njit.edu>
  8. Sender: news@cs.uq.oz.au
  9. Reply-To: warwick@cs.uq.oz.au
  10. Lines: 88
  11.  
  12. jpk2581@hertz.njit.edu (joseph p kisenwether apmt stnt) writes:
  13.  
  14. >I am trying to create some original word puzzles and need to find 
  15. >words with certain characteristsics:
  16. >For example
  17. > two words of more than ten letters which differ by only one 
  18. >stictly internal letter such that there exist two other letter
  19. >(one to the left and one to the right) such that in word one
  20. >there exists no sub-word containing both the changable letter 
  21. >and the one to the left while in word two there exists no sub-word 
  22. >conatining both the changable letter and the one to the right.
  23.  
  24. >Needless to say, this could most easily be done by computer search,
  25. >and as I have seen people here refer to them before, I'd like to know;
  26.  
  27. >a) what dictionary I should use (is there a standard)
  28.  
  29. Standard list of English words?  Blasphemy!
  30.  
  31. >b) where to get a copy of it
  32.  
  33. arthur.cs.purdue.edu in /pub/pcert/dict - ALL LANGUAGES!
  34.  
  35. >c) what the format is so that I can right the appropriate search 
  36. >    program
  37.  
  38. A Trie.  You could use a DAWG, but we (Paul Dale & I) have found that
  39. a Trie is better, because you can store suplementary data for arcs
  40. in the tree.
  41.  
  42. A Trie is a word-tree where each arc represents the addition of a letter
  43. to the ancestral path of letters.  The arc also stores a bit that defines
  44. whether the addition of that arc makes a valid word. eg, below is a simple
  45. Trie that stores the words "AT", "AXE", "BE", and "BI".  The upper-case
  46. letters on the arcs are those with the "is a word" bit set.
  47.  
  48.   (root node)
  49.      |
  50.      +-a-> (node)
  51.      |       |
  52.      |       +-T-> (node)
  53.      |       |
  54.      |       +-x-> (node)
  55.      |               |
  56.      |               +-E-> (node)
  57.      |
  58.      +-b-> (node)
  59.              |
  60.              +-E-> (node)
  61.              |
  62.              +-I-> (node)
  63.  
  64. >d) anything else that the more experienced think is relevant
  65.  
  66. Storing the Trie efficiently is very important, since there are a LOT
  67. of words.  By packing the information into a single 32-bit value for
  68. each arc, you can get great efficiency.  For more restricted word-
  69. processing algorithms (in the true sense of word-processing), a DAWG
  70. acan be used, which optimizes the tree into a graph (so, for example,
  71. many of the "i -> n -> g" arc sequences in the Trie appear as a single
  72. "i -> n -> g" arc sequence in a DAWG.
  73.  
  74.  
  75. Reference:
  76.  
  77. -----------------------------------------------------------------------------
  78. Journal:   Communications of the ACM  May 1988 v31 n5 p572(8)
  79.            * Full Text COPYRIGHT Assn. for Computing Machinery, Inc. 1988.
  80. -----------------------------------------------------------------------------
  81. Title:     The world's fastest Scrabble program. (technical)
  82. Author:    Appel, Andrew W.; Jacobson, Guy J.
  83.  
  84. Summary:   An efficient backtracking algorithm is used to make a very fast
  85.            program that plays the Scrabble crossword game.  Creating data
  86.            structures before the backtracking search begins makes the
  87.            algorithm efficient by focusing the search and making each step of
  88.            the search fast.
  89. -----------------------------------------------------------------------------
  90.  
  91. (This can be found using WAIS, in the cacm.src, using keyword "scrabble")
  92.  
  93.  
  94. --
  95. Warwick
  96.   _-_|\      warwick@cs.uq.oz.au            /____ Man's agar ____ /
  97.  /     * <-- Computer Science Department,  /  alerting altering  /
  98.  \_.-._/     University of Queensland,    /  integral relating  /
  99.       v      Brisbane, Australia.        /  tanglier triangle  /
  100.