home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource5 / 360_01 / readme < prev    next >
Encoding:
Text File  |  1992-02-17  |  4.1 KB  |  104 lines
  1.        Uspell files 
  2.  
  3.  
  4.        wpdict.nl (divided into wpdict.nl1 and wpdict.nl2)
  5.  
  6.        ASCII dictionary, sorted and delimited by newline.  The original
  7.        dictionary was inconsistent with respect to delimiters and
  8.        carried a CR that was not needed.  It was out of ASCII sequence
  9.        because apostrophe was sorted high.  This file was prepared using
  10.        rmcr and sort.  
  11.  
  12.  
  13.        dctcvt.c 
  14.  
  15.        This program reads the ASCII dictionary and writes a compressed
  16.        binary dictionary and index.  When constructing the index, the
  17.        shortest spelling in a dictionary granule is selected for
  18.        inclusion.  
  19.  
  20.  
  21.        wpdict.dat 
  22.  
  23.        This is the compressed dictionary.  It uses 5 bit characters vs.
  24.        8 bit.  Apostrophe is binary 1.  Letters of the alphabet are 2
  25.        through 27.  A flag byte providing 8 bit fields corresponding to
  26.        the most common suffixes is set aside for each root word.  Where
  27.        the root of a suffixed form exists in the dictionary, we flip the
  28.        flag bit on the root word rather than including the suffixed form
  29.        in the dictionary.  Spellings are null terminated.  Logical
  30.        entries are not delimited.  
  31.  
  32.  
  33.        wpdict.idx 
  34.  
  35.        This is the compressed index.  Each entry consists of a null
  36.        terminated string of 5 bit characters and a 24 bit binary
  37.        address.  The entries themselves are not delimited.  
  38.  
  39.  
  40.        uspell.c 
  41.  
  42.        Spell checker optimized for UNIX.  The best improvement was
  43.        gained from reading the index with a single read vs. scanf per
  44.        line.  This in turn eliminated the need to malloc storage for
  45.        each key, since the whole index is now resident.  Other items
  46.        which may be of interest follow.  
  47.  
  48.        Words are converted to 5 bit format before spell checking.  This
  49.        effectively puts them in folded case.  
  50.  
  51.        The dictionary is read in increments of file system blocks and
  52.        cached locally.  A bitmap of blocks already read is maintained. 
  53.  
  54.        The text file is read with a single read vs. separate reads per
  55.        line.  Stdio functions are eliminated, shedding some baggage.  
  56.  
  57.  
  58.        Comments 
  59.  
  60.        The thing with the suffix flags helped to achieve some
  61.        significant file compression.  Perhaps more important is the fact
  62.        that many suffixed forms are not currently present in the
  63.        dictionary.  Using these flags will ultimately allow the
  64.        dictionary to be more complete with a minimal impact on size.  
  65.  
  66.        The dictionary is weak on possessives.  I put a dirty trick in
  67.        the spell checker to make "'s" a legal suffix for any
  68.        properly-spelled root word.  "s'" will generally not check. 
  69.        Ultimately, I think legal possessives should be added to the
  70.        dictionary.  At this point, "'s" and "s'" would be added to the
  71.        list of common suffixes.  "es" and "ers" would be removed, since
  72.        they are the least commonly used of the suffixes currently on the
  73.        list.  
  74.  
  75.        The common suffixes were determined with a dictionary analysis
  76.        program that checked for common suffixes and then checked to see
  77.        if the de-suffixed root would be included in the compressed
  78.        dictionary.  The number of occurrences of various compressable
  79.        suffixes was as follows: 
  80.  
  81.                s       5521 
  82.                ed      1693 
  83.                ing     1501 
  84.                d       1242 
  85.                ly      1116 
  86.                er       518 
  87.                es       394 
  88.                ers      300 
  89.  
  90.        Further checking showed that another flag byte providing for
  91.        another 8 common suffixes would have made the dictionary larger. 
  92.  
  93.        We could have done away with the index altogether.  In order to
  94.        do this the dictionary itself would have to be searched using
  95.        intuitive techniques and some "learn by doing" type logic.  
  96.  
  97.        Another trick that could be employed would be to put the
  98.        dictionary, bitmap and index in shared memory vs. locally
  99.        malloced space.  In this way, they would only have to be read
  100.        once per system boot.  
  101.  
  102.  
  103.  
  104.