home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1513 < prev    next >
Internet Message Format  |  1990-12-28  |  42KB
  1. From: gtoal@tharr.UUCP (Graham Toal)
  2. Newsgroups: alt.sources
  3. Subject: Spelling utilities in C (Part 1 of 3)
  4. Message-ID: <807@tharr.UUCP>
  5. Date: 28 Jun 90 07:01:49 GMT
  6.  
  7. #!/bin/sh-----cut here-----cut here-----cut here-----cut here-----
  8. # shar:    Shell Archiver
  9. #    Run the following text with /bin/sh to create:
  10. #    README #    copyr.h #    dawg.h #    dictlib.h #    grope.h 
  11. cat - << \SHAR_EOF > README
  12.  
  13. This is a suite of programs for working with words.  I am releasing
  14. it to alt.sources primarily to invite people to test it on as many
  15. platforms as possible (mail me back any bug reports please!) so that
  16. the final code will be completely portable.
  17.  
  18. Unpack with unshar or sh < part1; sh < part2; sh < part3
  19.  
  20. Utilities for spelling checking and correction are supplied, but
  21. the ultimate aim is to support all sorts of word-manipulation activities
  22. such as a writers workbench and assorted word games (See PS).
  23.  
  24. This news posting is in three parts; part1: this file + headers;
  25. part2: utility modules in .c files to be #include'd; part3: main
  26. programs; just CC these and they should work -- no fancy makefiles
  27. or link commands.
  28.  
  29. The code here doesn't have much of a user interface; I'm rather hoping
  30. that people who pick it up will hook it in to their favourite operating
  31. system as smoothly as they can.  Perhaps someone with the time to
  32. spare (who am I kidding :-( ) might integrate it with ispell for instance.
  33.  
  34. I've experimented with various interfaces already; I can accept TeX
  35. input and write output suitable for correcting text in either emacs
  36. or uEmacs.  I'm not going to release these though, until I'm happy
  37. with the internal code.  Incidentally, the code will be totally
  38. public domain - meaning that I've no objection to its being used
  39. in commercial projects.  HOWEVER I would appreciate if you didn't do so
  40. until it is officially released (probably through comp.sources.misc)
  41. because I would prefer to define portable file-formats and magic numbers
  42. first.
  43.  
  44. OK, enough babble; here's how it all works:
  45.  
  46. 1) acquire a list of words for yourself; I have one but at 690K it is
  47.    too big to post. (actually even these sources come to around 120K
  48.    so I hope they make it through OK.  I don't think I have a shar
  49.    that splits, so I've divided into three shars myself.)
  50.    The word list should be sorted by ascii order.
  51.  
  52. 2) cc dawg.c
  53.    I've deliberately made main programs into one source file, by
  54.    including *.c for utility modules; I know this is bad style but
  55.    it helps make compiling and porting easier (no worries about
  56.    long external names for instance, or non-case-sensitive linkers)
  57.  
  58. 3) dawg yourdict dict
  59.    'yourdict' is your wordlist; but the second parameter should
  60.    be 'dict' at least while testing.  This will generate dict.dwg
  61.    which is a compacted and *FAST* data structure for word access.
  62.  
  63.    Building a dawg[See next section for meaning of name] from a word
  64.    list is a real memory pig; so I've written code which will let you
  65.    generate the dawg in chunks (traded off against a small loss of
  66.    compression density).  (Interestingly enough it isn't a time-pig;
  67.    using a hash-table for node merging gives almost linear time - thanks
  68.    to Richard Hooker for that one).
  69.  
  70.       If you don't have enough memory (say 2Mb?) you'll get a run-time
  71.    message suggesting that you recompile with cc -DSMALL_MEMORY dawg.c
  72.    (OK, so one day I'll make it select this mode itself at run-time)
  73.  
  74.    IBM PC's and Mac's will get this mode by default. [See FOOTNOTE]
  75.  
  76.     If you want to check that the data structure generated is ok,
  77.     3a) cc pdawg.c
  78.     3b) pdawg dict.dwg
  79.         This should decompile the data and print out the
  80.         original word list
  81.  
  82. 4) cc dwgcheck.c
  83.    Compile a Mickey Mouse spelling checker
  84.  
  85. 5) dwgcheck a few wurdz on the comand line ?
  86.    ... and test it.
  87.  
  88. 6) cc tell.c
  89.    Now try the 'advanced' stuff! - soundex correction... (I hates it :-()
  90.  
  91. 7) tell me sume wrongli speld werds
  92.    and test it...
  93.  
  94.    If you're getting into this stuff, here's another incidental
  95.    hack you might want to try...
  96.     7a)  cc proot.c
  97.     7b)  proot root
  98.          print out all words of form 'root*'
  99.          One day I'll hook this stuff into regexp; but not today :-)
  100.  
  101. ----------
  102.  
  103. Enough examples for now.  If that all worked you are doing well!
  104. If it didn't, and you have the time, please find out what went wrong;
  105. If you can fix it, mail me the fix please, else mail me a log of
  106. the symptoms, such as compiler error messages.
  107.  
  108. By the way, I know that the spelling correction uses a tacky algorithm;
  109. don't worry about it -- I'm working on some red hot stuff which will
  110. put soundex to shame (which isn't hard :) )  [Late note; it now works
  111. (apparently well) but I need a phonetic dictionary before it is useful :-(
  112. Anyone got a phonetic dictionary?  Alvey people out there?]
  113.  
  114. You might be interested in the data structures used; the main one is
  115. a dawg - a 'Directed Acyclic Word Graph' -- it's essentially a
  116. Directed Acyclic Graph implementing an FSM which describes the set of
  117. all words in your lexicon.  The name DAWG comes from Appel's in his paper
  118. on Scrabble (although none of the code or algorithms do).
  119.  
  120. The second most important data structure is superimposed on this
  121. one; it is a packing algorithm due to Liang (of TeX hyphenation
  122. fame) which allows you to convert an implicitly linked trie
  123. into an indexed trie *without* taking any more space.  Liang is
  124. a real smart cookie & it is a shame this technique of his is
  125. not better known... (it should be up there among binary tree and
  126. linked lists!)
  127.  
  128. OK, more examples:
  129.  
  130. 8)  cc pack.c
  131.     compile the packing code
  132.  
  133. 9)  pack  dict.dwg dict.pck
  134.     this takes rather a long time; you'll get messages saying '1000 nodes'
  135.     '2000 nodes' etc roughly 1 every 20 seconds +/- 50%.  There shouldn't
  136.     be more than a couple of screenfuls of these :-)  I'll speed it up one
  137.     day.
  138.  
  139.  
  140.     If you want to check that this data structure generated is ok too,
  141.     9a) cc ppack.c
  142.     9b) ppack dict.pck
  143.         Just as you did for (3)
  144.  
  145. 10) cc pckcheck.c
  146.     Just like dwgcheck but using the other type of data.
  147.  
  148. 11) pckcheck sume moar possibly incorrectly speld woards
  149.     boring, huh?
  150.  
  151. 12) Tha Tha Thats all folks!
  152.  
  153. ---------------
  154.  
  155. Unless I've made some major cockup at the last minute, you should
  156. actually have a reasonable chance of getting these working on your
  157. machine, whatever it is. (Dec 20's and EBCDIC machines *possibly*
  158. excepted - attempts welcome!)
  159.  
  160. As I said, please mail me your bugfixes, problems, suggestions etc.
  161. By the way, the standard of coding isn't exceptionally high; this
  162. implementation was always intended to be a prototype.  A rewrite
  163. of dawg.c and pack.c is definitely high on the priority list...
  164. The actual application programs aren't too bad, but the interfaces
  165. to the various utility routines are liable to change on an hour-by-hour
  166. basis! (I've been trying to make them more consistent -- you should have
  167. seen the last lot ;-) ).
  168.  
  169. However, the algorithms are all complete now; anyone who has ever needed
  170. to convert a tree to a dag might be interested in the linear-time solution
  171. in dawg.c - most other solutions I've seen have been NlogN or N^2.
  172.  
  173. If you're interested, there's a file dictlib.h which is a proposed interface
  174. for the next iteration; comments are invited.
  175.  
  176. Share & Enjoy,
  177.  
  178. Graham Toal <gtoal@uk.ac.ed>
  179.  
  180. <FOOTNOTE>
  181.    I'm experimenting in this code with ways of finding out at compile
  182. time various parameters needed for portability.  There's a file
  183. grope.h which does this.  If things all work first time, great;
  184. if not, you may have to change various #define's.  The best way
  185. to do that is to add code to grope.h which identifies your system,
  186. and only make changes of the form:
  187.  
  188. #ifdef SYS_MYSYSTEM
  189. #undef something
  190. #define something (a different value)
  191. #endif /* my system */
  192.  
  193. There are instructions for customising in grope.h itself.  My overall
  194. aim is to avoid special makefiles and special command line options.
  195. (A bit ambitious I know, but nice idea if it works...)
  196. (Steve Pemberton's config.c might be useful to you too if you are
  197. hacking grope.h.  It was reposted on usenet recently.)
  198.  
  199. </FOOTNOTE>
  200.  
  201. <PS>
  202.  
  203. Future hacks:
  204.    1) Anagrams
  205.    2) Crosswords
  206.    3) Scrabble
  207.    4) Anything where a text key can be used to lookup another
  208.       piece of text.  This is implemented with the 'dawg_locate_prefix'
  209.       routine; it is effectively a cheap substitute for btrees etc.
  210.       (and better than a hash table because you can *do* things with it!)
  211.  
  212.       4a) Reverse phone book      1234567=Fred Bloggs
  213.       4b) house style enforcer    stupid=infelicitous
  214.       4c) uk/us spelling advisor  sidewalk=pavement
  215.       4d) shorthand/macro expander   f.y.i.=for your information
  216.       etc etc... (Most of wwb in fact)
  217.  
  218.    5) Anything you can suggest! (or *implement* :-) )
  219.  
  220. </PS>
  221.  
  222. <MEMO>
  223.  
  224. Archive-name: dawgutils/part[1-3].shar
  225. Reply-to: Graham Toal <gtoal%uk.ac.ed@nsfnet-relay.ac.uk>
  226.  
  227. 1) Upload fixed version of dyntrie.c - remember bug with signed chars
  228.    being used as an index [comment rule in dawg.c?]
  229.  
  230. 2) known design flaw: can't handle strings with 0 in them
  231.  
  232. 3) known bug: dyntrie.c has problems if you enter a string
  233.    which *starts* with 255.  This is due to sending 'end_of_node'
  234.    bit rather hackily.  Can be fixed.
  235.  
  236. 4) Test version to be posted to alt.sources by running on machine
  237.    with signed chars (eg MSDOS)
  238.  
  239. 5) Remove hacky Malloc debugging macros in utils.c -- there might be
  240.    a problem if compiled on MSDOS but not under MICROSOFT C
  241.  
  242. 6) Check that LIB_STRINGS is *not* defined when UX63 is set.
  243.  
  244. 7) tweak the constants in pack.c to speed it up a lot
  245.  
  246. 8) hack the pack.c heuristics into dyntrie.c to speed it up too.
  247.  
  248. </MEMO>
  249. SHAR_EOF
  250. cat - << \SHAR_EOF > copyr.h
  251. /*
  252.  * Copyright 1989 Graham Toal & Richard Hooker
  253.  *
  254.  * Permission to use, copy, modify, and distribute this software and its
  255.  * documentation for any purpose with or without fee is hereby granted provided
  256.  * that the above copyright notice appear in all copies and that both that
  257.  * copyright notice and this permission notice appear in supporting
  258.  * documentation.
  259.  *
  260.  * This program is publicly available, but is NOT in the public domain.  The 
  261.  * difference is that copyrights granting rights for unrestricted use and 
  262.  * redistribution have been placed on the software to identify its 
  263.  * authors.  You are allowed and encouraged to take this software and
  264.  * build commercial products, freeware products, shareware products, and
  265.  * any other kind of product you can think up, with the following restriction:
  266.  *
  267.  * If you redistribute the source to this program, or a derivitive of that
  268.  * source, you must include this copyright notice intact. If the system
  269.  * this source is distributed with is under a stricter license (such as
  270.  * a commercial license, the typical freeware "no commercial use" license,
  271.  * or the FSF copyleft) then you must provide the original source under the
  272.  * original terms.
  273.  *
  274.  * Edinburgh Software Products (E.S.P.) makes no representations about the
  275.  * suitability of this software for any purpose.  It is provided "as is"
  276.  * without express or implied warranty.
  277.  *
  278.  * E.S.P. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  279.  * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  280.  * E.S.P. BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  281.  * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
  282.  * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  283.  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  284.  *
  285.  * Authors:  Graham Toal & Richard Hooker, Edinburgh Software Products,
  286.  *           6 Pypers Wynd, Prestonpans, East Lothian, Scotland.
  287.  */
  288. SHAR_EOF
  289. cat - << \SHAR_EOF > dawg.h
  290. /**
  291. *
  292. *       DAWG.H
  293. *
  294. *       Header file for Directed Acyclic Word Graph access
  295. *
  296. *       The format of a DAWG node (8-bit arbitrary data) is:
  297. *
  298. *        31                24 23  22  21                                     0
  299. *       +--------------------+---+---+--+-------------------------------------+
  300. *       |      Letter        | W | N |??|            Node pointer             |
  301. *       +--------------------+---+---+--+-------------------------------------+
  302. *
  303. *      where N flags the last edge in a node and W flags an edge as the
  304. *      end of a word. 21 bits are used to store the node pointer, so the
  305. *      dawg can contain up to 262143 edges. (and ?? is reserved - all code
  306. *      generating dawgs should set this bit to 0 for now)
  307. *
  308. *      The root node of the dawg is at address 1 (because node 0 is reserved
  309. *      for the node with no edges).
  310. *
  311. *      **** PACKED tries do other things, still to be documented!
  312. *
  313. **/
  314.  
  315. #define TRUE (0==0)
  316. #define FALSE (0!=0)
  317.  
  318. #define DAWG_MAGIC 0x01234567
  319. #define PACK_MAGIC 0x34567890
  320.  
  321. #define TERMINAL_NODE 0
  322. #define ROOT_NODE 1
  323.  
  324. #define V_END_OF_WORD   23
  325. #define M_END_OF_WORD   (1L << V_END_OF_WORD)
  326. #define V_END_OF_NODE   22                     /* Bit number of N */
  327. #define M_END_OF_NODE   (1L << V_END_OF_NODE)   /* Can be tested for by <0 */
  328.  
  329.  
  330. #define V_FREE          22             /* Overloading this bit, as
  331.                                           packed tries need no end-of-node */
  332. #define M_FREE          (1L << V_FREE)
  333.  
  334. #define V_LETTER        24
  335. #define M_LETTER        0xFF
  336. #define M_NODE_POINTER  0x1FFFFFL     /* Bit mask for node pointer */
  337.  
  338. /* max_chars and base_chars are a hangover from the days when this
  339.    was trying to save space, and dawgs were only able to contain
  340.    characters in the range 'a'..'z' 'A'..'Z' (squeezed into 6 bits).
  341.    Now that we're '8-bit clean' we no longer need these.  Later code
  342.    in fact doesn't support the old style; but some procedures still
  343.    subtract 'BASE_CHAR' from the character to normalize it.  Since it
  344.    is now 0 it is a no-op... */
  345. #define MAX_CHARS       256
  346. #define BASE_CHAR       0
  347.  
  348. /* Enough? */
  349. #define MAX_WORD_LEN    256
  350.  
  351. #define MAX_LINE        256
  352.  
  353. typedef long NODE;
  354. typedef long INDEX;
  355.  
  356. SHAR_EOF
  357. cat - << \SHAR_EOF > dictlib.h
  358. /* This header file does not describe any of the code in the
  359.    accompanying files; it is a rough sketch of the NEXT iteration
  360.    of the spelling/word utilities.  Comments are invited.  Missing
  361.    functionality or bits that won't work should be pointed out
  362.    please!   Send mail to gtoal@ed.ac.uk  (via nsfnet-relay.ac.uk
  363.    from US sites)
  364.    many thanks.
  365.  
  366.       Graham Toal 23/06/90
  367.  */
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374. typedef long INDEX;
  375. typedef long NODE;
  376. #define ROOTNODE 1L
  377.  
  378. typedef struct DICT {
  379.  
  380.   /* Although primitive procedures will be provided for handling the
  381.      basic dawg array, by using this interface applications can
  382.      remain independent of the implementation details of the
  383.      dictionary. */
  384.  
  385.   /* So far there are three forms of dict; 1: a simple dawg with edges
  386.      as 4-byte integers; each node (a set of branches) is stored
  387.      sequentially.  2: An *indexed* form of the above -- much faster
  388.      to lookup in, but slower to walk through.  Although indexing
  389.      would normally be heavy on space, this uses Liang's packed
  390.      overlapping tries, thus using almost exactly the same space as
  391.      method 1.  3: A form of 1, but with all the stops pulled out
  392.      to get as much bit-level compaction as possible; edges can
  393.      be two bytes instead of 4. (by Keith Bostic) */
  394.  
  395.   /* This struct contains both access procedures and information;
  396.      most fields will be filled in by our code when the dictionary
  397.      is loaded by load_dict().  The fields may be added to in
  398.      later releases, but they will always be upwards compatible;
  399.      none of this data is saved to disk in this format, so changing
  400.      the struct layout will not cause problems as long as the names
  401.      remain the same. */
  402.  
  403.   /* Note that some procedures take a user-supplied 'apply' parameter;
  404.      This 'apply' procedure has a 'context' parameter which is merely
  405.      a handle to allow the user to pass data in to his code without
  406.      having to use global variables.  If the user's apply procedure
  407.      returns anything other than 0, it will cause an early exit, with
  408.      the users return code being returned from the calling function. */
  409.  
  410.   /* It is intended that these are used in an object-oriented way;
  411.      although we will supply an external dict_check(word, dict) procedure, for
  412.      instance, all it will do is call dict->check(word, dict->dawg) */
  413.  
  414.   NODE *dawg;
  415.                                    /* Root of the dictionary tree */
  416.   char *dict_name,                 /* "smiths" - used in command lines etc. */
  417.        *dict_info,                 /* "Johns Smiths Rhyming Dictionary,\n
  418.                                        (c) Smith & Jones, 1892\n
  419.                                        Whitechapel, London.\n" */
  420.        *dict_fname,                /* "/usr/dict/smiths" */
  421.  
  422.        *lang_charset;              /* "ISO 8859/1 Latin 1" */
  423.  
  424.   /* These are filled in by us to make life easier for the applications
  425.      programmer.  We'll supply a default table for simple 7-bit ascii
  426.      dawgs; but this mechanism allows us the option of including all
  427.      the salient points about the character set used in a dictionary
  428.      in the dictionary itself.  Because they are char*'s, we'll probably
  429.      end up sharing the same table between multiple dictionaries --
  430.      so don't write to them. (Although you may replace the _pointer_
  431.      with one to a table of your own. */
  432.  
  433.   /* Later note: I've just found out about LOCALE.H etc.  This stuff
  434.      may therefore change... */
  435.  
  436.   int *chartype;
  437.                                     /*  1             whitespace           */
  438.                                     /*  2             punctuation          */
  439.                                     /*  4             blank                */
  440.                                     /*  8             lower case letter    */
  441.                                     /*  16            upper case letter    */
  442.                                     /*  32            (decimal) digit      */
  443.                                     /*  64            underscore           */
  444.                                     /*  128           A-F and a-f          */
  445.                                     /*  256           Ignore words starting
  446.                                                       with this char       */
  447.                                     /*  512           Include in definition
  448.                                                       of a word -- mainly
  449.                                                       alpha but also hyphen
  450.                                                       and apostrophe       */
  451.  
  452. char   *lower,                     /* personal implementation of tolower() */
  453.        *unaccented,                /* map accented chars to non-accenmted */
  454.        *lexorder;                  /* an arbitrary ordering for sorting:
  455.                                       e-acute would come after e and before f
  456.                                       */
  457.  
  458.   int  (* check)  (NODE *base, INDEX state, struct DICT *d, char *word);
  459.                      /* Check a word - exact match; return true/false */
  460.  
  461.   int  (* fuzzy)  (NODE *base, INDEX state, struct DICT *d, char *word,
  462.                    char *value);
  463.      /* Check a word - fuzzy case, accents, hyphens etc; return true/false */
  464.      /* value is filled in with the dictionary's idea of what the
  465.         word should look like. */
  466.  
  467.   /* Fancier correction procedures may be synthesised out of user code and
  468.      'walk' */
  469.   int  (* correct) (
  470.                 char *word,
  471.                 NODE *base, INDEX state,
  472.                                 /* Normally dict's root, but may be subtree */
  473.                 struct DICT *d,   /* lowercase/accent information from here */
  474.                 int   maxwords,
  475.                 int   order,                /* 0: by alpha
  476.                                                1: by highest score first
  477.                                                2: by lexical ordering
  478.                                             (ignores case, accents, hyphens)
  479.                                              */
  480.                 int   (* apply) (
  481.                       char *word,     /* Corrected word */
  482.                             int   score,    /* Normalised to range 0..255 */
  483.                             void *context),
  484.                 void  *context);
  485.                                    /* Offer spelling corrections for the
  486.                                       given word.  If maxwords > 0, return
  487.                                       the best <maxwords> words in order
  488.                                       of most-likely first; otherwise
  489.                                       many words may be returned, in
  490.                                       alphabetical order, coupled with
  491.                                       a score: 255 means exact match; 0
  492.                                       means totally different */
  493.  
  494.                                     /* returns 0 if user returned 0 for
  495.                                        all applications */
  496.   int  (* walk) (
  497.                NODE *base, INDEX state,
  498.                int   (* apply) (char *word, void *context),
  499.                void  *context);
  500.                                    /* Apply the procedure given to every
  501.                                       word in the dictionary tree or subtree,
  502.                                       passing in the user-supplied context */
  503.  
  504.                                     /* returns 0 if user returned 0 for
  505.                                        all applications */
  506.  
  507.   int (* lookup) (
  508.               NODE *base, INDEX state,
  509.               char  *key,
  510.               /* Out */
  511.               INDEX values);
  512.                                    /* Return the index of the subtree of the
  513.                                       dictionary which has 'key' as a prefix;
  514.                                       for instance, in a reverse telephone
  515.                                       book, you might find entries:
  516.                                          0874=Anytown
  517.                                          0875=Cockenzie
  518.                                          0875=Port Seton
  519.                                          0875=Prestonpans
  520.                                          0876=Toytown
  521.                                        In this case, if searching for "0875=",
  522.                                        a subtree would be returned containing:
  523.                                          Cockenzie
  524.                                          Port Seton
  525.                                          Prestonpans
  526.                                        This subtree would then be walked
  527.                                        using the 'walk' function and a user-
  528.                                        written 'apply' procedure. */
  529.  
  530.                                     /* returns 0 if successful */
  531.  
  532.   /* The following two are performance hints ONLY.  They should not
  533.      affect the correct functioning of a program. */
  534.  
  535.   int  (* uncache) (struct DICT *d);/* The space a dictionary uses may be
  536.                                        reclaimed by calling this.  If the
  537.                                        dictionary is subsequently accessed,
  538.                                        there *may* be a performance penalty --
  539.                                        for instance the dictionary may be
  540.                                        accessed off disk.  However on a machine
  541.                                        with sufficient memory, the system
  542.                                        may choose to leave the data in ram
  543.                                        until, say, malloc runs out of space.
  544.                                          If there is no convenient mechanism
  545.                                        for organising the demand-recacheing,
  546.                                        this may be a no-op. */
  547.  
  548.                                     /* returns 0 if successful */
  549.  
  550.   int  (* recache) (struct DICT *d);/* The data of the dictionary is reloaded
  551.                                        into active memory where it will stay */
  552.  
  553.                                     /* returns 0 if successful */
  554.   /* May be extended in the future */
  555. } DICT;
  556.  
  557.  
  558.  
  559. /*
  560.                             dict_load
  561.  
  562.    This is provided as a primitive so that dictionaries can be loaded
  563. in the most efficient way the machine supports.  The space for the dict
  564. is supplied *by* this procedure - not *to* it.  This allows a Mach (or Emas)
  565. implementation to mmap (or Connect) the file in memory - the connection
  566. address being chosen by the OS and outside our control.  It also allows
  567. systems like RISC OS on the Acorn Archimedes to use an optimised whole-
  568. file load call to pull the file off disk into real ram in a single disk
  569. operation.
  570.  
  571.    Since the data parts of the type 1 & 2 dicts are just a set of 4-byte
  572. integers, it is easy to correct a faulty byte-sex by running down this
  573. array *once at start-up* to reverse the order.  This is easy if the
  574. data is loaded into physical ram.  If it is connected as a file by a VM system
  575. however, the VM system must support copy-on-write; if it only has read-only
  576. mapping there must be two files available -- one of each sex.
  577.  
  578.    A *possible* scheme on VM systems is to byte-sex-reverse a whole
  579. page the first time that page is touched.  This may be a lot of unneccesary
  580. work - I'd recommend keeping a correct-sex file on-line.
  581.  
  582.    This code will create the DICT struct, and fill in the various fields,
  583. either from the dictionary file itself or from private knowledge if not available.
  584.  
  585. */
  586.  
  587. int dict_load_file(char *fname, DICT **dict_struct);
  588.  
  589.                                    /* fname is the literal file name */
  590.  
  591.                                    /* dict_struct is allocated by us,
  592.                                       not by the user. */
  593.  
  594.                                    /* returns 0 if successfully loaded */
  595.  
  596. int dict_load_dict(char *dname, DICT **dict_struct);
  597.  
  598.                                    /* dname is the dictionary name,
  599.                                       e.g. "words", or "web2" etc.
  600.                                       The corresponding file will be searched
  601.                                       for via a system-dependent path, logical
  602.                                       variable, or fixed place. */
  603.  
  604.                                    /* dict_struct is allocated by us,
  605.                                       not by the user. */
  606.  
  607.                                    /* returns 0 if successfully loaded */
  608.  
  609.  int dict_unload(DICT *d);         /*  Use when totally finished with data */
  610.  
  611.  /* These are user-level veneers for the internal procedures used above.
  612.     Use them in preference to the above.  Use the above only if
  613.     you are a speed-freak! (but disguise them in macros such as:
  614.  
  615.   #define  dict_check(dawg, dict, word) dict->check(dict->dawg, dict, word)
  616.  
  617.    These macros will of course go 'Bang!' if dict ptr is unassigned or NULL.
  618.  */
  619.  
  620.  /* In the worst case, if a machine has a poor quality compiler which
  621.     doesn't support procedure variables well, these routines could be
  622.     the *acual* implementation rather than just a pointer to it. */
  623.  
  624.  int  check  (NODE *base, INDEX state, DICT *d, char *word);
  625.  int  fuzzy  (NODE *base, INDEX state, DICT *d, char *word, char *value);
  626.  int  correct (char *word,
  627.                NODE *base, INDEX state,
  628.                            /* Normally dictionary root, but may be subtree */
  629.                DICT *d,          /* lowercase/accent information from here */
  630.                int   maxwords,
  631.                int   order,                /* 0: by alpha
  632.                                               1: by highest score first
  633.                                               2: by lexical ordering
  634.                                             */
  635.                int   apply(char *word,     /* Corrected word */
  636.                            int   score,    /* Normalised to range 0..255 */
  637.                            void *context),
  638.                void  *context);
  639.  int  walk   (NODE *base, INDEX state,     /* Yoyo fanatics will be pleased
  640.                                  to learn that they can 'walk the dawg'... :-) */
  641.               int    apply(char *word, void *context),
  642.               void  *context);
  643.  int lookup (NODE *base, INDEX state,
  644.              char  *key,
  645.              /* Out */
  646.              INDEX values);
  647.  
  648.  
  649. /* Now here come the fast internal procedures which the above eventually call */
  650. int dawg_check(NODE *base, INDEX state, char *word);
  651.   /* Standard dawg */
  652. int pack_check(NODE *base, INDEX state, char *word);
  653.   /* Overlapped indexed dawg */
  654. int bsd_check(NODE *base, INDEX state, char *word);
  655.   /* Space-optimised dawg (called bsd because Keith Bostic is working
  656.                    on this format for the next bsd4.4 spelling checker) */
  657. /* Must make the internl procs agree with these... save the macros for later... 
  658. #define dict_check(word,dict) \
  659.           (dict != NULL ? (dict->check(dict->dawg, ROOTNODE, word)) : -1)
  660. */
  661. int dawg_walk(NODE *base, INDEX state,
  662.               int    apply(char *word, void *context),
  663.               void  *context);
  664. int pack_walk(NODE *base, INDEX state,
  665.               int    apply(char *word, void *context),
  666.               void  *context);
  667. int bsd_walk(NODE *base, INDEX state,
  668.               int    apply(char *word, void *context),
  669.               void  *context);
  670. /*
  671. #define dict_walk(dict, apply, context) \
  672.           (dict != NULL ? (dict->walk(dict->dawg, ROOTNODE, apply, context)) : -1)
  673. */
  674.  
  675. int dawg_lookup(NODE *base, INDEX state, char  *key, /* Out */ INDEX values);
  676. int pack_lookup(NODE *base, INDEX state, char  *key, /* Out */ INDEX values);
  677. int bsd_lookup(NODE *base, INDEX state, char  *key, /* Out */ INDEX values);
  678. /* etc... */
  679.  
  680. /* Get list of possible next characters from this point in the tree,
  681.    put it into user-supplied array branch[256].  Filled with
  682.    NULL if no branch, or an INDEX if it points to more of the tree.
  683.    Words which may terminate on a particular letter have terminate[let] != 0
  684.  
  685.    The user-supplied terminate array is deliberately a long array to allow
  686.    for expansion; it may be used one day to return arbitrary codes such as
  687.   'Noun' etc...
  688.  
  689.  */
  690.  
  691. void dawg_branch(NODE *base, INDEX state, NODE *branch, long *terminate);
  692. void pack_branch(NODE *base, INDEX state, NODE *branch, long *terminate);
  693. void bsd_branch(NODE *base, INDEX state, NODE *branch, long *terminate);
  694. /* No internal proc yet... add it in the morning. */
  695.  
  696. /* In fact there will be even simpler procedures which can be used by
  697.    people who prefer to include the whole source of this package rather
  698.    than just the library interface parts.  In applications where utmost
  699.    speed is a neccessity (eg Scrabble(tm)) you could use these, or write
  700.    your own.  But most of us can use this clean interface with unnoticable
  701.    overhead. */
  702. SHAR_EOF
  703. cat - << \SHAR_EOF > grope.h
  704. #ifndef grope_h
  705. #define grope_h 1
  706.  
  707. #ifdef TESTING_DEFS
  708. /*###################################################################*/
  709. /*
  710.  * This is an exercise to assist in writing portable programs.
  711.  *
  712.  * To use as a header file, eg "grope.h", just leave this file
  713.  * as it is.  To use it to define new entries, rename it as
  714.  * "grope.c" and compile it as "cc -DTESTING_DEFS grope".
  715.  *
  716.  * To customise this test program for your system, I have set it up
  717.  * so that all features are enabled.  If you find that one feature
  718.  * causes a compile-time error, test a suitable set of '#ifdef's for
  719.  * your machine and #undef the values below which are not appropriate.
  720.  *
  721.  * Please do your best to see that your tests are unique, and that
  722.  * you do not undo any tests already implemented.
  723.  *
  724.  * One last request; PLEASE PLEASE PLEASE send me any updates you
  725.  * may make. If you cannot get through to me on email, send me a
  726.  * paper copy (or even better, a floppy copy :-)) to Grahan Toal,
  727.  * c/o 6 Pypers wynd, Prestonpans, East Lothian, Scotland EH32 9AH.
  728.  *
  729.  *   Graham Toal <gtoal@uk.ac.ed>
  730.  * [PS: I can read DOS and RISC OS floppies only]
  731.  */
  732. #define STDLIBS 1
  733. #define PROTOTYPES 1
  734. #define KNOWS_VOID 1
  735. #define KNOWS_LINE 1
  736. #define KNOWS_REGISTER 1
  737. #endif /* TESTING_DEFS */
  738. /*###################################################################*/
  739. #define SYS_ANY 1
  740. #define COMPILER_ANY 1
  741.   /* Don't yet know what machine it is.  Add a test once identified. */
  742. /*--------------------------*/
  743. #ifdef MSDOS
  744. #define SYS_MSDOS 1
  745. #endif
  746. /*--------------------------*/
  747. #ifdef __STDC__
  748. #define STDLIBS 1
  749. #define PROTOTYPES 1
  750. #define KNOWS_VOID 1
  751.   /* If the compiler defines STDC it should have these. We can undef
  752.      them later if the compiler was telling lies! */
  753. #endif
  754. /*--------------------------*/
  755. #ifdef MPU8086
  756. #define SYS_MSDOS 1
  757.   /* Aztec does not #define MSDOS.
  758.      We assume it is Aztec on MSDOS from the MPU8086.
  759.    */
  760. #ifdef __STDC__
  761. #define COMPILER_AZTEC 1
  762.   /* Aztec is known to also define __STDC__ (illegally).  Therefore if
  763.      __STDC__ is not defined, it is probably not Aztec */
  764. #endif
  765. #endif
  766.  
  767. #ifdef SYS_MSDOS
  768. /*--------------------------*/
  769. #ifdef __STDC__
  770. /*----------------------*/
  771. #define COMPILER_MICROSOFT 1
  772.   /* I assume that the combination of #define MSDOS and #define __STDC__
  773.      without any other collaboration means MICROSOFT.  (Who, incidentally,
  774.      are being naughty by declaring __STDC__) */
  775. #define KNOWS_LINE 1
  776. #else
  777. /*----------------------*/
  778. #ifdef __ZTC__
  779. /*------------------*/
  780. #define COMPILER_ZORTECH 1
  781. #undef STDLIBS
  782.   /* Another system without locale.h */
  783. #define PROTOTYPES 1
  784. #else
  785. /*------------------*/
  786. /* A non-std msdos compiler */
  787. #undef STDLIBS
  788. #undef PROTOTYPES
  789. /*------------------*/
  790. #endif
  791. /*----------------------*/
  792. #endif
  793. /*--------------------------*/
  794. #endif
  795. #ifdef TURBOC
  796.   /* Although Turbo C correctly does not define __STDC__, it has SOME
  797.      standard libraries (but not all - locale.h?) and accepts prototypes. */
  798. #undef STDLIBS
  799. #define PROTOTYPES 1
  800. #define SYS_MSDOS 1
  801. #define COMPILER_TURBOC 1
  802.   /* TURBOC is defined, but has no value.  This allows it to be tested
  803.      with #if as well as #ifdef. */
  804. #endif
  805. /*--------------------------*/
  806. #ifdef COMPILER_MICROSOFT
  807. #undef STDLIBS
  808.   /* Again, like Turbo C, does not know locale.h */
  809. #define PROTOTYPES 1
  810. #endif
  811. /*--------------------------*/
  812. #ifdef SYS_MSDOS
  813. #define MEMMODELS 1
  814.   /* We assume ALL MSDOS machines use memory models */
  815. #endif
  816. /*--------------------------*/
  817. #ifdef UX63
  818. #undef STDLIBS
  819. #undef PROTOTYPES
  820. #define SYS_UX63 1
  821. #define COMPILER_PCC 1
  822. /*#define LIB_STRINGS 1 - apparently not... */
  823. #endif
  824. /*--------------------------*/
  825. #ifdef sun
  826. #undef STDLIBS
  827. #undef PROTOTYPES
  828. #define SYS_SUN 1
  829. #define COMPILER_PCC 1
  830. #endif
  831. /*--------------------------*/
  832. #ifdef THINK_C
  833. #define SYS_MAC 1
  834. #define COMPILER_THINKC 1
  835. #define KNOWS_VOID 1
  836. #endif
  837. /*--------------------------*/
  838. #ifdef sparc
  839. #undef STDLIBS
  840. #undef PROTOTYPES
  841. #define SYS_SPARC 1
  842. #define COMPILER_PCC 1
  843. #endif
  844. /*--------------------------*/
  845. #ifdef ARM
  846. #define SYS_RISCOS 1
  847.   /* I fear Acorn may define 'ARM' on both unix and risc os versions.
  848.      Should find out whether they define others as well, to differentiate. */
  849. #endif
  850. #ifdef __ARM__
  851. #define SYS_RISCOS 1
  852.   /* I fear Acorn may define 'ARM' on both unix and risc os versions.
  853.      Should find out whether they define others as well, to differentiate. */
  854. #endif
  855. /*--------------------------*/
  856. #ifdef SYS_RISCOS
  857. #define COMPILER_NORCROFT 1
  858. #define KNOWS_REGISTER 1
  859. #define KNOWS_LINE 1
  860. #endif
  861. /*--------------------------*/
  862. #ifdef vms
  863. #define SYS_VMS 1
  864. #endif
  865. /*--------------------------*/
  866.  
  867. /*--------------------------*/
  868. #ifdef SYS_UX63
  869. #undef SYS_ANY
  870. #endif
  871. #ifdef SYS_ARM
  872. #undef SYS_ANY
  873. #endif
  874. #ifdef SYS_MSDOS
  875. #undef SYS_ANY
  876. #endif
  877. #ifdef SYS_SUN
  878. #undef SYS_ANY
  879. #endif
  880. #ifdef SYS_SPARC
  881. #undef SYS_ANY
  882. #endif
  883. #ifdef SYS_RISCOS
  884. #undef SYS_ANY
  885. #endif
  886. #ifdef SYS_MAC
  887. #undef SYS_ANY
  888. #endif
  889. #ifdef SYS_VMS
  890. #undef SYS_ANY
  891. #endif
  892. /*--------------------------*/
  893. #ifdef COMPILER_PCC
  894. #undef COMPILER_ANY
  895. #endif
  896. #ifdef COMPILER_MICROSOFT
  897. #undef COMPILER_ANY
  898. #endif
  899. #ifdef COMPILER_TURBOC
  900. #undef COMPILER_ANY
  901. #endif
  902. #ifdef COMPILER_ZORTECH
  903. #undef COMPILER_ANY
  904. #endif
  905. #ifdef COMPILER_AZTEC
  906. #undef COMPILER_ANY
  907. #endif
  908. #ifdef COMPILER_NORCROFT
  909. #undef COMPILER_ANY
  910. #endif
  911. #ifdef COMPILER_THINKC
  912. #undef COMPILER_ANY
  913. #endif
  914. /*--------------------------*/
  915. /* ##################################################################### */
  916. #ifdef TESTING_DEFS
  917. #include <stdio.h>
  918. /* ======================================================================= */
  919. #ifdef STDLIBS
  920.               /* If any of these fail, make sure STDLIBS is not
  921.                  defined for your machine. */
  922. #include <stdlib.h>      /* STDLIBS should not be defined. */
  923. #include <time.h>        /* STDLIBS should not be defined. */
  924. #include <locale.h>      /* STDLIBS should not be defined. */
  925. #endif
  926. /* ======================================================================= */
  927. #ifdef KNOWS_VOID
  928. void test() {            /* KNOWS_VOID should not be defined */
  929.   /* Make sure your ifdef's don't #define KNOWS_VOID if this fails */
  930. }
  931. #endif
  932. /* ======================================================================= */
  933. #ifdef KNOWS_REGISTER
  934. int regtest() {
  935. register int i = 0;          /* KNOWS_REGISTER should not be defined */
  936.   /* Make sure your ifdef's don't #define KNOWS_REGISTER if this fails */
  937.   return(i);
  938. }
  939. #endif
  940. /* ======================================================================= */
  941. #ifdef PROTOTYPES
  942. int main(int argc, char **argv)   /* PROTOTYPES should not be defined */
  943. /* If this fails, make sure PROTOTYPES is not defined for your machine. */
  944. #else
  945. int main(argc,argv)
  946. int argc;
  947. char **argv;
  948. #endif
  949. {
  950. /*-------------------------------------------------------------------------*/
  951.   printf("We should know just what the machine is, or 'SYS_ANY':\n");
  952. #ifdef SYS_UX63
  953.   printf("#define SYS_UX63 %d\n", SYS_UX63);
  954. #endif
  955. #ifdef SYS_ARM
  956.   printf("#define SYS_ARM %d\n", SYS_ARM);
  957. #endif
  958. #ifdef SYS_MSDOS
  959.   printf("#define SYS_MSDOS %d\n", SYS_MSDOS);
  960. #endif
  961. #ifdef SYS_SUN
  962.   printf("#define SYS_SUN %d\n", SYS_SUN);
  963. #endif
  964. #ifdef SYS_SPARC
  965.   printf("#define SYS_SPARC %d\n", SYS_SPARC);
  966. #endif
  967. #ifdef SYS_RISCOS
  968.   printf("#define SYS_RISCOS %d\n", SYS_RISCOS);
  969. #endif
  970. #ifdef SYS_MAC
  971.   printf("#define SYS_MAC %d\n", SYS_MAC);
  972. #endif
  973. #ifdef SYS_VMS
  974.   printf("#define SYS_VMS %d\n", SYS_VMS);
  975. #endif
  976. #ifdef SYS_ANY
  977.   printf("#define SYS_ANY %d\n", SYS_ANY);
  978. #endif
  979. /*-------------------------------------------------------------------------*/
  980.   printf("Either the machine has different memory models or not:\n");
  981. #ifdef MEMMODELS
  982.   printf("#define MEMMODELS %d\n", MEMMODELS);
  983. #else
  984.   printf("#undef MEMMODELS\n");
  985. #endif
  986. /*-------------------------------------------------------------------------*/
  987.   printf("One compiler name should be given, or 'COMPILER_ANY':\n");
  988. #ifdef COMPILER_PCC
  989.   printf("#define COMPILER_PCC %d\n", COMPILER_PCC);
  990. #endif
  991. #ifdef COMPILER_MICROSOFT
  992.   printf("#define COMPILER_MICROSOFT %d\n", COMPILER_MICROSOFT);
  993. #endif
  994. #ifdef COMPILER_TURBOC
  995.   printf("#define COMPILER_TURBOC %d\n", COMPILER_TURBOC);
  996. #endif
  997. #ifdef COMPILER_ZORTECH
  998.   printf("#define COMPILER_ZORTECH %d\n", COMPILER_ZORTECH);
  999. #endif
  1000. #ifdef COMPILER_AZTEC
  1001.   printf("#define COMPILER_AZTEC %d\n", COMPILER_AZTEC);
  1002.   /* Can exist on other machines as well as MSDOS */
  1003. #endif
  1004. #ifdef COMPILER_LATTICE
  1005.   /* Currently coming through as 'COMPILER_ANY' - haven't found one to test */
  1006.   /* Can exist on other machines as well as MSDOS. Meanwhile pass it in     */
  1007.   /* on the command_line?                                                   */
  1008.   printf("#define COMPILER_LATTICE %d\n", COMPILER_LATTICE);
  1009. #endif
  1010. #ifdef COMPILER_GCC
  1011.   /* Ditto. Test in appropriate places for each machine. */
  1012.   printf("#define COMPILER_GCC %d\n", COMPILER_GCC);
  1013. #endif
  1014. #ifdef COMPILER_NORCROFT
  1015.   printf("#define COMPILER_NORCROFT %d\n", COMPILER_NORCROFT);
  1016. #endif
  1017. #ifdef COMPILER_THINKC
  1018.   printf("#define COMPILER_THINKC %d\n", COMPILER_THINKC);
  1019. #endif
  1020. #ifdef COMPILER_ANY
  1021.   printf("#define COMPILER_ANY %d\n", COMPILER_ANY);
  1022. #endif
  1023. /*-------------------------------------------------------------------------*/
  1024.   printf("Either the compiler accepts ANSI-like libraries or not:\n");
  1025. #ifdef STDLIBS
  1026.   printf("#define STDLIBS %d\n",STDLIBS);
  1027. #else
  1028.   printf("#undef STDLIBS\n");
  1029. #endif
  1030. /*-------------------------------------------------------------------------*/
  1031.   printf("Either the machine accepts ANSI prototypes or not:\n");
  1032. #ifdef PROTOTYPES
  1033.   printf("#define PROTOTYPES %d\n", PROTOTYPES);
  1034. #else
  1035.   printf("#undef PROTOTYPES\n");
  1036. #endif
  1037. /*-------------------------------------------------------------------------*/
  1038.   printf("Either the machine needs nonstandard #include <strings.h> or not:\n");
  1039. #ifdef LIB_STRINGS
  1040.   printf("#define LIB_STRINGS %d\n", LIB_STRINGS);
  1041. #else
  1042.   printf("#undef LIB_STRINGS\n");
  1043. #endif
  1044. /*-------------------------------------------------------------------------*/
  1045.   printf("Either the machine accepts the 'void' keyword or not:\n");
  1046. #ifdef KNOWS_VOID
  1047.   printf("#define KNOWS_VOID %d\n", KNOWS_VOID);
  1048. #else
  1049.   printf("#undef KNOWS_VOID\n");
  1050. #endif
  1051.   printf("Either the machine accepts the 'register' keyword or not:\n");
  1052. /*-------------------------------------------------------------------------*/
  1053.   printf("Either the compiler accepts the '__LINE__' directive or not:\n");
  1054. #ifdef KNOWS_LINE
  1055.   printf("#define KNOWS_LINE %d\n", KNOWS_LINE);
  1056. #else
  1057.   printf("#undef KNOWS_LINE\n");
  1058. #endif
  1059. /*-------------------------------------------------------------------------*/
  1060.   printf("Either the machine accepts the 'register' keyword or not:\n");
  1061. #ifdef KNOWS_REGISTER
  1062.   printf("#define KNOWS_REGISTER %d\n", KNOWS_REGISTER);
  1063. #else
  1064.   printf("#undef KNOWS_REGISTER\n");
  1065. #endif
  1066.   /* Note - this is intended to be used only if your compiler accepts
  1067.      'register' *AND* compiles code with it correctly!  Some compilers
  1068.      show up bugs when register optimisations are attempted! */
  1069. /*-------------------------------------------------------------------------*/
  1070.   if (argv[argc] != 0) printf("Warning! argv[argc] != NULL !!! (Non ansii)\n");
  1071. }
  1072. #endif /* TESTING_DEFS */
  1073. #endif /* Already seen? */
  1074.  
  1075. SHAR_EOF
  1076.