Source Code 1994 March/Source_Code_CD-ROM_Walnut_Creek_March_1994.iso/compsrcs/unix/volume26/phlspl10/part01

Text File | 1993-04-30 | 20.5 KB | 676 lines

Newsgroups: comp.sources.unix
From: [e-mail] (Phillip Nunez)
Subject: v26i200: philspell - correct problematic spelling in text files, Part01/01
Sender: [e-mail]
Approved: [e-mail]

Submitted-By: [e-mail] (Phillip Nunez)
Posting-Number: Volume 26, Issue 200
Archive-Name: philspell-1.0/part01

Name
       philspell - correct problematic spelling in text files

Syntax
       philspell [-v] [-f file]

Description
       The  command  collects  words  from the standard input and
       looks them up in a spelling list.  Words that are  not  on
       the spelling list and are not deriveable from words on the
       list (by applying certain inflections,  prefixes  or  suf-
       fixes)  are corrected.  To the standard output, prints the
       original text with all misspelled words corrected.

        [e-mail] (Phillip Nunez)

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 1 (of 1)."
# Contents:  MANIFEST Makefile README main.c philspell.man
#   philspell.test skiplist.c skiplist.h
# Wrapped by [e-mail] on Sat May  1 17:05:52 1993
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'MANIFEST' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'MANIFEST'\"
else
echo shar: Extracting \"'MANIFEST'\" \(362 characters\)
sed "s/^X//" >'MANIFEST' <<'END_OF_FILE'
X   File Name        Archive #    Description
X-----------------------------------------------------------
X MANIFEST                   1    This shipping list
X Makefile                   1
X README                     1
X main.c                     1
X philspell.man              1
X philspell.test             1
X skiplist.c                 1
X skiplist.h                 1
END_OF_FILE
if test 362 -ne `wc -c <'MANIFEST'`; then
    echo shar: \"'MANIFEST'\" unpacked with wrong size!
fi
# end of 'MANIFEST'
fi
if test -f 'Makefile' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(321 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
X#CC = philcc
X
X# Change the above to something like gcc or cc if you don't have philcc.
X
XCFLAGS = -g -DNDEBUG
X
XSOURCES = main.c skiplist.c
XOBJECTS = main.o skiplist.o
X
Xall: philspell
X
Xphilspell: $(OBJECTS)
X    $(CC) $(OBJECTS) -o philspell
X
Xmain.c: skiplist.h
Xskiplist.c: skiplist.h
X
Xclean:
X    /bin/rm -rf $(OBJECTS) philspell
END_OF_FILE
if test 321 -ne `wc -c <'Makefile'`; then
    echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(1350 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
XFrom: [e-mail] (Phillip "Edward" Nunez)
XSubject: philspell 1.0 source code
XDate: 17 Jun 1992 21:18:13 GMT
X
XHi everybody!!  I was recently trying to proofread some of the short stories
Xthat I write a lot and found it really hard to do under UNIX without
Xspecialized software.  I mean, even if you use "spell" to check a document,
Xyou then have to go through by hand and change all the misspelled words to
Xbe correct, and then to be safe you have to run it through "spell" again to
Xmake sure you didn't make any mistakes, and that's all a big pain!
X
XI will keep this awful lack of UNIX word versatility in mind when I write
XPhilOS, but until then -- while we all still have to use UNIX or system V or
XMS-DOS or something like that -- I have written this really cool new utility
Xcalled "philspell".
X
XPHILSPELL uses a words file (default /usr/dict/words) and a lot of
Xcomplicated English grammar heuristics to spell-check a file-- but it is
Xeven better than that!  Because, as its output, PHILSPELL prints the
Xoriginal document, but with all spelling *correct*!!!  This is a lot cooler
Xthan the output of more kludgey programs like "spell".
X
XThe source code for PHILSPELL is here at the end of this post.  Oh yeah, you
Xcan also get it via ftp from soda.berkeley.edu in ~ftp/pub/phillip.
X
XBye for now everyone!!!
X
X    Phillip "Edward" Nunez
END_OF_FILE
if test 1350 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'main.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'main.c'\"
else
echo shar: Extracting \"'main.c'\" \(7509 characters\)
sed "s/^X//" >'main.c' <<'END_OF_FILE'
X/*
X *
X * main.c for "philspell"
X *
X * This file is Copyright (c) 1992 Phillip "Edward" Nunez.  Phillip grants
X * you full permission to copy and distribute this code provided you do not
X * interfere with any of the copyrights (c)s installed therein.
X *
X * Phillip grants permission to extract portions of this code for use in
X * other code provided you give full credit to him in all documentation
X * pertaining to your program, preserve copyrights in files from which code
X * is extracted, and put his name in your program's output.
X *
X *
X * This header automatically generated by the UNIX program philcopyright,
X * Copyright (c) 1991 Phillip "Edward" Nunez.  For information regarding
X * philcopyright, mail [e-mail].
X *
X */
X
X#include <stdio.h>
X#include <ctype.h>
X
X#include "skiplist.h"
X
Xstatic char philSCCSid[] = "@(#)main.c          1.0     Phillip `Edward' Nunez";
X
X#define DEFAULT_FILENAME "/usr/dict/words"
X#define SKIPMAX 16
X
Xstatic char  scratchbuf[BUFSIZ];
Xstatic char *philsProgramName;
X
Xstatic char *philExists = "Phillip \"Edward\" Nunez";
X
Xtypedef skipnode philSkipNode;
Xtypedef skipnode philSkipList;
X
Xchar *suffixes[] = {
X    "ive", /**/ "ion", "tion", "en", /**/ "ions", "ications", "ens", /**/
X    "th", "ieth", /**/ "ly", /**/ "ing", /**/ "ings", /**/ "ed", /**/
X    "est", /**/ "er", /**/ "ers", /**/ "ers", /**/ "s", "es", "ies", /**/
X    "ness", "iness", /****/ "ment", "al", "ally", "able", "speak"
X};
Xunsigned int *suffix_lens;
X
Xchar *prefixes[] = {
X    "non", "anti", "un", "in", "re", "en", "ex", "im", "de", "phil"
X};
Xunsigned int *prefix_lens;
X
Xchar *muties[] = {
X    "able", "tion", "sion", "tion", "ing", "ily", "ed", "ier", "ly", "tions",
X    "tions", "ies", "ied"
X};
Xchar *mutie_results[] = {
X    "e",    "te",   "de",   "t",    "e",   "y",   "e",  "y",   "le", "tion",
X    "te",   "y",    "y"
X};
Xunsigned int *mutie_lens;
X
X/*
X * Someone actually had the nerve to tell me today that the "right" way to
X * impelment all the lists of prefixes and suffixes and stuff was to use
X * a backward-indexed trie with type/data records stored at the nodes.  I
X * think that's really dumb because who wants to spell all their words
X * backwards?
X *
X * She said this part of the program was really pathetic because it was O(n).
X * But I like O(N)-- N for Nunez!  That starts with N and that's next to O and
X * that's next to P and that stands for "Pool" and that rhymes with "Cool!"
X *
X *                                                         -Phillip
X */
X
X#define NUMSUFFIXES (sizeof(suffixes) / sizeof(char *))
X#define NUMPREFIXES (sizeof(prefixes) / sizeof(char *))
X#define NUMMUTIES   (sizeof(muties)   / sizeof(char *))
X
Xunsigned int funny = 0;
X
Xvoid philPerror(char *s) {
X    fprintf(stderr, "Error in Phillip's program \"%s\":\n>\t%s\n",
X                philsProgramName, s);
X}
X
Xchar *philLowerizeAndStrdup(char *t) {
X    unsigned int len = strlen(t);
X    char *start, *s;
X
X    start = s = (char *)malloc(len + 1);
X
X    do *s++ = (isupper(*t) ? tolower(*t) : *t);
X        while (*t++);
X
X    return start;
X}
X
XphilSkipNode philLookupNoPrefix(char *word, philSkipList list) {
X    philSkipNode n;
X    unsigned int i, l, m;
X    char newtrybuf[BUFSIZ];
X
X    n = skip_lookup(word, list, SKIPMAX, NULL);
X
X    if (!n) {
X        i = 0;
X    l = strlen(word);
X    while (!n && (i < NUMSUFFIXES)) {
X        if (l > (m = suffix_lens[i])) {
X            if (strcasecmp(word + (l - m), suffixes[i]) == 0) {
X            strncpy(newtrybuf, word, l - m);
X            newtrybuf[l - m] = '\0';
X            if (funny) printf("\nTrying suffix '%s':  %s -> %s\n",
X                          suffixes[i], word, newtrybuf);
X            n = skip_lookup(newtrybuf, list, SKIPMAX, NULL);
X        }
X        }
X        i++;
X    }
X        if (!n) {
X        i = 0;
X        while (!n && (i < NUMMUTIES)) {
X            if (l > (m = mutie_lens[i])) {
X            if (strcasecmp(word + (l - m), muties[i]) == 0) {
X                strncpy(newtrybuf, word, l - m);
X                strcpy(newtrybuf + l - m, mutie_results[i]);
X            if (funny) printf("\nTrying mutie '%s/%s': %s -> %s\n",
X                      muties[i], mutie_results[i],
X                      word, newtrybuf);
X            n = skip_lookup(newtrybuf, list, SKIPMAX, NULL);
X            }
X        }
X        i++;
X        }
X    }
X    }
X    return n;
X}
X
Xvoid philSpellCheckWord(char *word, philSkipList list) {
X    philSkipNode n;
X    unsigned int i, l, m;
X    char newtrybuf[BUFSIZ];
X
X    n = skip_lookup(word, list, SKIPMAX, NULL);
X
X    if (!n) {
X        i = 0;
X    l = strlen(word);
X    while (!n && (i < NUMPREFIXES)) {
X        if (l > (m = prefix_lens[i])) {
X            if (strncasecmp(word, prefixes[i], m) == 0) {
X            strcpy(newtrybuf, word + m);
X            if (funny) printf("\nTrying prefix '%s':  %s -> %s\n",
X                      prefixes[i], word, newtrybuf);
X            n = philLookupNoPrefix(newtrybuf, list);
X        }
X        }
X        i++;
X    }
X    if (!n) n = philLookupNoPrefix(word, list);
X    }
X    fprintf(stdout, "%s%s", word, n ? "" : " (sic)");
X}
X
Xvoid philSpellCheck(philSkipList list) {
X    char *res;
X    char wordbuf[BUFSIZ], *s;
X
X    while (res = gets(scratchbuf)) {
X    while (*res) {
X        while (*res && !isalpha(*res)) fputc(*res++, stdout);
X        s = wordbuf;
X        while (isalpha(*res)) *s++ = *res++;
X        *s = '\0';
X        if (*wordbuf) philSpellCheckWord(wordbuf, list);
X    }
X    fputc('\n', stdout);
X    }
X}
X
Xvoid philLoadAndGo(FILE *f) {
X    philSkipList s = skip_create(SKIPMAX);
X    unsigned int i;
X
X    suffix_lens = (unsigned int *)malloc(NUMSUFFIXES * sizeof(char *));
X    i = 0;
X    while (i < NUMSUFFIXES) (suffix_lens[i] = strlen(suffixes[i])), i++;
X
X    prefix_lens = (unsigned int *)malloc(NUMPREFIXES * sizeof(char *));
X    i = 0;
X    while (i < NUMPREFIXES) (prefix_lens[i] = strlen(prefixes[i])), i++;
X
X    mutie_lens = (unsigned int *)malloc(NUMMUTIES * sizeof(char *));
X    i = 0;
X    while (i < NUMMUTIES) (mutie_lens[i] = strlen(muties[i])), i++;
X
X    while (fgets(scratchbuf, BUFSIZ, f)) {
X        scratchbuf[strlen(scratchbuf) - 1] = '\0';
X        skip_add(philLowerizeAndStrdup(scratchbuf), philExists, s, SKIPMAX);
X    }
X
X    fclose(f);
X
X    philSpellCheck(s);
X}
X
Xstatic char *filename = DEFAULT_FILENAME;
X
Xvoid philParseCLA(int argc, char *argv[]) {
X    unsigned int n = 1;
X    char *s;
X
X    while (n < argc) {
X        s = argv[n];
X    if (*s++ != '-') {
X        sprintf(scratchbuf, "Argument #%d doesn't start with a dash.", n);
X        philPerror(scratchbuf);
X    } else if (*s == 'v') funny = 1;
X      else if (*s == 'f') {
X          n++;
X          if (n == argc) philPerror("Missing filename for option f.");
X          else filename = argv[n];
X      } else {
X          sprintf(scratchbuf, "Unknown option: %s.", s);
X          philPerror(scratchbuf);
X      }
X    n++;
X    }
X}
X
Xvoid philMain(int argc, char *argv[]) {
X    FILE *f;
X
X    philsProgramName = argv[0];
X
X    philParseCLA(argc, argv);
X
X    f = fopen(filename, "r");
X    if (f == NULL) {
X        sprintf(scratchbuf, "Unable to open file \"%s\".", filename);
X        philPerror(scratchbuf);
X    exit(1);
X    }
X
X    philLoadAndGo(f);
X    exit(0);
X}
X
X
Xvoid main(int argc, char *argv[]) {
X                                        /*
X                                         *  This is just a hook to make the
X                                         *  program work even on compilers not
X                                         *  smart enough to make philMain()
X                                         *  the entry procedure instead of
X                     *  main(), when philMain() exists.
X                                         *  [gcc requires this, for example.]
X                                         *
X                                         */
X    philMain(argc, argv);
X}
END_OF_FILE
if test 7509 -ne `wc -c <'main.c'`; then
    echo shar: \"'main.c'\" unpacked with wrong size!
fi
# end of 'main.c'
fi
if test -f 'philspell.man' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'philspell.man'\"
else
echo shar: Extracting \"'philspell.man'\" \(1800 characters\)
sed "s/^X//" >'philspell.man' <<'END_OF_FILE'
X.\" philSCCSid: @(#)philspell.man    1.0    6/16/92
X.TH philspell 1
X.SH Name
Xphilspell \- correct problematic spelling in text files
X.SH Syntax
X.B philspell
X[\fB\-v\fR] [\fB\-f\fI file\fR\|]
X.SH Description
X.NXR "philspell command"
XThe
X.PN philspell
Xcommand collects words from the standard input
Xand looks them up in a spelling list.
XWords that are not on the spelling list and
Xare not deriveable from words on the list
X(by applying certain inflections, prefixes or suffixes)
Xare corrected.
XTo the standard output,
X.PN philspell
Xprints the original text with all misspelled words corrected.
X.SH Options
X.NXR "philspell command" "options"
X.IP \fB\-v\fR 15
XVerbose mode; causes
X.B philspell
Xto output a description of the actions it performs when attempting
Xto convert the input words into dictionary-bound forms.  This output
Xis printed to stderr.
X.IP "\fB\-\|f\fI file\fR"
XSpecifys the file used for the spelling list; the default is
X/usr/dict/words.  The list specified here must be in the same format.
X.SH Restrictions
X.NXR "philspell command" "restricted"
XBecause of the intricate nature of the calculations performed,
Xspelling correction can be a very CPU intensive process.  On slow
Xmachines with long files or big dictionarys,
X.PN philspell
Xcan take a few minutes to run.
X.PP
XThe coverage of the spelling list (dictionary) is uneven;
Xnew installations will probably wish to
Xmonitor the output for several months to gather
Xlocal additions.
X.PP
XThe
X.PN philspell
Xcommand works only with ASCII text
Xfiles.
X.SH Files
X.ta 2.0i
X\f(CW/usr/dict/words\fR    spelling list, default for \fB\-f
X.SH AUTHOR
X.NXR "philspell author"
XPhillip "Edward" Nunez, [e-mail].
X.SH See Also
Xphilcc(1), philshar(1), philsort(1), philtee(1), ppp(1), philbiff(1X),
Xowlspeak(6), propagandaspeak(6), philsccs(1)
END_OF_FILE
if test 1800 -ne `wc -c <'philspell.man'`; then
    echo shar: \"'philspell.man'\" unpacked with wrong size!
fi
# end of 'philspell.man'
fi
if test -f 'philspell.test' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'philspell.test'\"
else
echo shar: Extracting \"'philspell.test'\" \(477 characters\)
sed "s/^X//" >'philspell.test' <<'END_OF_FILE'
XYou know, you should submit the design of PHILTRAN to SIGPLAN.
XLots of really *lame* programming language designs get published there,
Xand I think this one's much cooler than the other ones.  You should really
Xconsider this, because it will make it lots easier to get into graduate
Xschool if you get a paper published before you apply! (REALLY!)  If
Xyou're not sure as to how to submit a paper, ask Kathy to help you ---
Xshe's really nice and I'm sure will be willing to help.
END_OF_FILE
if test 477 -ne `wc -c <'philspell.test'`; then
    echo shar: \"'philspell.test'\" unpacked with wrong size!
fi
# end of 'philspell.test'
fi
if test -f 'skiplist.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'skiplist.c'\"
else
echo shar: Extracting \"'skiplist.c'\" \(3508 characters\)
sed "s/^X//" >'skiplist.c' <<'END_OF_FILE'
X/*
X * Skiplist library COPYRIGHT (c) 1992, 1991, 1990, 1989, 1988, 1987 by
X * Phillip "Edward" Nunez.  I wrote all this stuff and had it copyrighted
X * and don't let anyone ever tell you any different!
X *
X */
X
X#include <stdio.h>
X#include <assert.h>
X
X#include "skiplist.h"
X
X#define PROBABILITY 4
X
X/*
X * The definition of PROBABILITY determines how many pointers per node an
X * element of a skiplist has.  A PROBABILITY of 4 means each node will have
X * (3/4)1 + (1/4)(3/4)2 + (1/4)(1/4)(3/4)3... ~~ 1.31 pointers per node.
X * A PROBABILITY of 5 yields (4/5)1 + (1/5)(4/5)2... ~~ 1.24 p/node.
X */
X
X#define RANDOM rand
X
X/*
X * The RANDOM function you define here should be seeded in your main program.
X */
X
X/*
X * skip_create creates the header node for a skiplist.  The pointer to this
X * node is what you should use to refer to the skiplist.  The argument 'max'
X * determines the maximum height of any node in the skiplist; the head is
X * always this high.  Skiplists can store on the order of 2^n elements
X * efficiently where n is that maximum height.
X */
X
Xskipnode skip_create(int max) {
X
X    skipnode newnode;
X    int i;
X
X    newnode = (skipnode)malloc(sizeof(struct skipnode) + sizeof(skipnode) * max);
X    assert(newnode != NULL);
X
X    newnode->name = "";
X    newnode->ptr = NULL;
X
X    for (i = 0; i <= max; i++) newnode->next[i] = newnode;
X    return newnode;
X}
X
X/*
X * skip_add adds an item to the skiplist.  'name' is the name (key)
X * to the data; 'ptr' is the data; level is the maximum level (the same
X * as used in the call to skip_create) and 'node' is the skiplist you're
X * looking things up in.
X *
X * The 'name' parameter must have been allocated with 'malloc' or somesimilar.
X * It will be freed when the node disappears.
X */
X
Xvoid skip_add(char *name, void *ptr, skipnode node, int level) {
X
X    skipnode newnode;
X    int size, newlevel;
X
X    newlevel = 0;
X    while (RANDOM() % PROBABILITY) newlevel++;
X    if (newlevel > level) newlevel = level;
X
X        size = sizeof(struct skipnode) + sizeof(skipnode) * newlevel;
X        newnode = (skipnode)malloc(size);
X    newnode->name = name;
X    newnode->ptr = ptr;
X
X    while (level >= 0) {
X        while (strcasecmp(name, node->next[level]->name) < 0)
X            node = node->next[level];
X        if (level <= newlevel) {
X            newnode->next[level] = node->next[level];
X            node->next[level] = newnode;
X        }
X        level--;
X    }
X}
X
X/*
X * skip_lookup: Given the name of the data, the skiplist, the
X * max level, and the default to return if the data cannot be found,
X * look up the data in the list.
X */
X
Xvoid *skip_lookup(char *name, skipnode node, int level, void *def) {
X        int d;
X
X        while (level >= 0) {
X                while ((d = strcasecmp(name, node->next[level]->name)) < 0)
X                        node = node->next[level];
X                if (!d) return node->next[level]->ptr;
X                level--;
X        }
X        return def;
X}
X
X/*
X * skip_remove: remove a skipnode from a the skiplist given.  'name'
X * is the key, 'level' is the max level.
X */
X
Xvoid skip_remove(char *name, skipnode node, int level) {
X    int cmpsav;
X    skipnode n;
X
X    while (level >= 0) {
X        while ((cmpsav = strcasecmp(name, node->next[level]->name)) < 0)
X            node = node->next[level];
X        if (cmpsav == 0)
X            n = node->next[level];
X            node->next[level] = node->next[level]->next[level];
X        level--;
X    }
X    free(n->name);
X    free(n);
X}
X
X/*
X * skip_free: free an entire skiplist.
X */
X
Xvoid skip_free(skipnode node) {
X    skipnode m, n = node->next[0];
X    while (n != node) {
X        free(n->name);
X        m = n->next[0];
X        free(n);
X        n = m;
X    }
X    free(node);
X}
END_OF_FILE
if test 3508 -ne `wc -c <'skiplist.c'`; then
    echo shar: \"'skiplist.c'\" unpacked with wrong size!
fi
# end of 'skiplist.c'
fi
if test -f 'skiplist.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'skiplist.h'\"
else
echo shar: Extracting \"'skiplist.h'\" \(363 characters\)
sed "s/^X//" >'skiplist.h' <<'END_OF_FILE'
Xtypedef struct skipnode {
X        char *name;
X        void *ptr;
X        struct skipnode *next[1];
X} *skipnode;
X
Xvoid skip_remove(char *name, skipnode node, int level);
Xvoid skip_free(skipnode node);
Xvoid *skip_lookup(char *name, skipnode node, int level, void *def);
Xvoid skip_add(char *name, void *ptr, skipnode node, int level);
Xskipnode skip_create(int max);
END_OF_FILE
if test 363 -ne `wc -c <'skiplist.h'`; then
    echo shar: \"'skiplist.h'\" unpacked with wrong size!
fi
# end of 'skiplist.h'
fi
echo shar: End of archive 1 \(of 1\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have the archive.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0