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