Trailing-Edge
-
PDP-10 Archives
-
walsh_goodStuff_1600
-
more-uns/spell.doc
There are 6 other files named spell.doc in the archive. Click here to see a list.
SPELL: Spelling Check and Correction Program
Ralph E. Gorin
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305
4 March 1971
11 March 1974 revision
Tenex Mods: March-October 1974
William Plummer, Jerry Wolf
14 December 1974 revision
CMU mods: April 9, 1975 by
Richard Johnsson and Philip Karlton
19 May 1975 revision
---------------------------------------------------------------------
SPELL is a program designed to read text files and check them for
correctness of spelling. In addition to the spelling check, the
program provides a means for correcting words that it thinks are
misspelled. This program was written by Ralph E. Gorin of Stanford
University Artificial Intelligence Laboratory. It has been augmented
by William Plummer and Jerry Wolf of BBN. The CMU interface was
written by Richard Johnsson and Philip Karlton.
In its normal mode of usage, SPELL reads through an input text file,
asks the user about each word it does not recognize, and creates an
output file in which corrections have been made. Provisions exist
for:
a. Loading, incrementally augmenting, and dumping special
dictionaries. Such dictionary files are ordinary text
files which may be listed and edited. Arbitrarily
many dictionaries may be loaded, subject only to
availability of (virtual) main memory.
b. Training modes where SPELL scans an input file and
makes a list of all words it does not recognize. Such
a list can be used as an auxiliary dictionary.
c. Termination of spelling checking part way through a
file and a way of picking up where you left off in a
later session.
Other features of the program are:
a. SPELL will read either SOS, TECO or E/TV files. The
corrected output will be written in the same mode,
except E/TV directories must be deleted. Dictionary
files may be SOS, TECO or E/TV format.
b. An exception file may also produced. This file
contains all words SPELL did not recognize (and their
contexts), all corrections, plus all words which SPELL
recognized by stripping off prefixes and/or suffixes.
This last class of words appears marked with "[" or
"]" to denote prefix- or suffix- removal. E.g.,
FOOING]
[PREFOOED]
The affix-stripping algorithms are not foolproof
(e.g., CHOSES] ), so this gives a quick way to scan
for the exceptions which may slip through.
c. SPELL keeps track of all word spellings which were
corrected by the user. Subsequent occurrences of such
are automatically corrected by the program. This is
reported to the user by a typeout of "MISSPELLING ==>
CORRECTION".
d. When a word is corrected, the output file will be
rewritten with either upper case, lower case, or mixed
(first letter upper, the remainder in lower),
depending on the cases of the first two letters in the
original word. Note: this will be incorrect in some
cases (e.g., McCarthy).
---------------------------------------------------------------------
Using SPELL
Type the command R SPELL (under TENEX, type "SPELL" to the EXEC).
All typeins to SPELL must be terminated by carriage return. (In the
TENEX version, editing by ^A, ^Q, and ^R may be done.)
It will first ask: "Do you want to augment the dictionary?" If you
wish to use only the main dictionary presently in memory, type "N"
<cr>. You can then skip the next paragraph.
If in fact you have an auxiliary dictionary (of specific terms,
infrequently used words, etc.) you wish to use, type "Y" <cr>. You
will then be asked for the name of your dictionary file. The format
of the file is one dictionary entry (word) on a line; words must be
composed of alphabetic characters or apostrophe and less than 40
letters long. The dictionary entries need not be in alphabetical
order. A misspelling-correction pair may occur one line in the form
"MISSPELLING>CORRECTION". After typing the file name you will be
given the option of marking the new entries as incremental
insertions. If the new entries are marked as incremental then they
will be included in an incremental dump of the dictionary. To have
the new entries marked as incremental, type "I" <cr>; otherwise, type
<cr>. (If any of the words in your auxiliary dictionary are already
in the main dictionary then no second copy of the word will be made.
Hence, if your words are marked as incremental then in a subsequent
incremental dump, any words that were already in the dictionary will
not be dumped.) After loading an auxiliary dictionary the program
will type the new total number of words in the dictionary (and,
except under TENEX, the amount of core used). You will then have an
opportunity to save the new core image (normally you won't do this).
You will again be asked, "Do you want to augment the dictionary?",
thus allowing you to enter a number of auxiliary dictionaries
(limited only by the availability of virtual core).
You will then be given an opportunity to specify zero or more switch
options. The meanings of the switches are:
T Training mode. SPELL will treat the input file as a
training set rather than a file to be corrected. All
words in the file which are unfamiliar to SPELL will be
entered in the dictionary as incremental insertions.
After SPELL finishes reading the file, the user has an
opportunity to dump all the words that were inserted in
this manner. The resulting list of words may be
edited, and any words which are incorrect may be
deleted. Then this file can be used as an auxiliary
dictionary while correcting the original source file.
This feature is provided for the purpose of easing the
problem of creating a specialized dictionary of jargon
and infrequently used words.
Q Q-Training mode. In this mode, all words in the source
file that are unfamiliar to SPELL will be added to the
dictionary; the difference is, if any "new" word is
"close to" some old word, the new word will be output
to the exception file. The exception file will contain
only such words. In this way, the spelling checker
calls to your attention the fact that these words may
be misspelled.
N No suffix removal. This switch suppresses the attempt
to remove suffixes to recognize a correctly spelled
root word. SPELL will then find many more questionable
words, but it will work more correctly than the
heuristic affix removal.
A No prefix removal. This switch suppresses the attempt
to remove prefixes to recognize a correctly spelled
root word.
U Accept Upper case mode. In this mode, all words that
are written entirely in upper case will be inserted in
the dictionary. This is useful when a manuscript file
contains jargon terms that are written in upper case,
and text-processor (e.g., PUB, TJ6, or RUNOFF) commands
in upper case. Before reading the input file, SPELL
will ask for a dictionary number to use for all words
inserted this way (see "How to Use Multiple
Dictionaries").
D PUB mode. In this mode, lines that begin with a period
(.) will be passed to the output without any attempt
at correction being made. Also, the percent character
(%) denotes a font change, so the character immediately
following the percent will be passed to the output and
will be considered as delimiting a word. Thus if the
text "%Bimportant%*" appears in the input the "%B" and
the "%*" are passed to the output and the "important"
is checked and, if necessary, corrected. If the D is
followed by some non-alphanumeric character that is not
a carriage control character (e.g., "!" or "+") then
that character will be treated as "%" was described and
"%" will be treated normally. In this way, if the text
file turns on some character other than "%" for font
selection then that file can be handled by SPELL. Note
that only one such character can be turned on in SPELL.
P Pickup mode. After specifying input and output file
names, you will be asked to specify a page and line
number for pickup. The effect is to suspend spelling
checking until the page and line specified. When a
user has a partially corrected file, this mode will
enable him to skip over the portion of the file that
has already been corrected. The input file will be
copied without checking to the output until the page
and line specified, at which point spelling checking
begins.
Next you will be asked for the name of the file that you want
to check for spelling errors. File names are specified in the usual
format of "name.ext[prj,prg]" where name is the filename, ext is the
file extension, and [prj,prg] is the name of the file owner, which
may be omitted if the file is on the present user's disk area. If you
omit the file name then you will immediately enter the exit sequence
(see below).
After specifying the switches, you will be asked to specify the names
of the file to be checked, the corrected file to be output, and the
exception file. In the TENEX version there are always output and
exception files. In the TENEX version, if no file names are
specified for the output and exception files they will default; the
output file will have the same name and extension as the input, and
the exception file will have the extension "EXCEPTIONS". In
non-TENEX versions there are no default names, and output or
exception files may be omitted.
The exception file, should you chose to make one, will contain each
line on which an error was found, the indication of the page and line
number, and the suspect word. Words accepted via the affix removal
heuristics will also appear in the exception file.
After you have specified all the files, the program will respond with
"Working..." and start checking the input file for spelling errors.
When the spelling checker encounters a word that isn't in the
dictionary, it will type the page and line number, the line in which
the word occurs, and the word itself. You will be given a choice of
actions to take:
A Accept this word, this one time.
I Accept this word and insert it in the dictionary so
that subsequent occurrences of this word will be
recognized and accepted. Words that are inserted this
way are marked as incremental insertions and they may
be dumped to form an auxiliary dictionary.
R Replace this word. Type "R" <cr> and the program will
ask you for the replacement word. If the replacement
word is not already in the dictionary, the program will
give you an opportunity to insert it.
If the misspelling is due to an omitted space between
words, use the "R" command to retype the words with the
space.
If the replacement word contains no spaces or illegal
characters, you will be asked if you wish to add this
replacement to the list of misspelling-correction
pairs. If you do add the replaced word as a misspelling
then all subsequent occurrences of that word will be
replaced with the replacement string.
X Accept this word and finish. The word will be
accepted. Then the remainder of the input file will be
copied without checking to the output file.
W Save my incremental insertions. After you type
"W" <cr> you will be asked for a file name. Then an
incremental dump of the dictionary will be written into
the file. After the dump is complete you may then
decide what to do with the excepted word.
L Load an auxiliary dictionary. The present word is
accepted and you will be asked for the name of the
dictionary file to load. This is useful if you
encounter a jargon term but forgot to load the
appropriate dictionary.
D Display the line and offending word again. The line
that is displayed will not have any corrections shown
in it. If a line has more than one error the line will
only be typed once. Subsequent errors on that line
will cause only the particular word to be typed, unless
this command is used.
S If this choice is offered then the spelling checker has
discovered several words that could be possible
corrections of this word. If you type "S" <cr> then
you will enter a mode where you can look at the words
that were found by the program and (optionally) select
one of the words from the list.
When you enter this selection submode, the first word
in the list of possible corrections will be typed
followed by an asterisk. Then you have the following
choices:
C<cr> Use this word as the Correction.
<cr> Show the next possible choice. When you
exhaust the choices you are returned to the
outer mode, and asked again.
^<cr> Back up in the list.
<alt mode> Escape from this submode and return to the
outer command mode.
In general, when a word is found that is not in the dictionary, a
brief message, either "Type A,I,R,X,W or D" or "Type A,I,R,X,W,D or
S" will be typed to remind you of the possible choices. In the
special case where the program finds precisely one possible
correction for the word, then the message, "I guess <word>. Type C
to make this correction or A,I,R,X,W or D" will be typed. If you
type "C" <cr> then the indicated substitution will be made; otherwise
you have the usual choices. In the CMU version, slow terminals (any
terminal not an INFOTON, BEEHIVE, GRAPICS or ARDS) will have these
messages shortened to "*", "S*", and "==><word> C*", respectively.
Also, on CMU slow terminals, the line on which an exception occurs is
not displayed (use the D command).
When the input file is exhausted, all files are closed, the program
types "Finished.", and the exit sequence is entered. The user then
has several options:
E Exit now.
S Save this core image.
C Go back and correct another file.
A Augment the dictionary, set new switches, and correct
another file.
D Complete dump of the dictionary. This will create a
very large file, and it is not usually recommended.
I Incremental dump of the dictionary. All the words that
were inserted while running the program are dumped to a
file. The user specifies a file name (the default is
WORDS.LST). This incremental file is in a format
suitable for editing or for use as an auxiliary
dictionary. The words in this file are in alphabetical
order.
X This command is used to get a trace count of the
program. It is for diagnostic purposes only, and is
displayed as a possible choice only if the program has
been assembled as a debugging program.
---------------------------------------------------------------------
How to Use Multiple Dictionaries
SPELL has a set of features whereby the user can cause the creation
of several disjoint incremental dictionaries. In this way, the user
may collect several dictionaries of special terms. Internally, all
dictionary entries are considered equivalent as regards word
searches. The distinction between dictionaries becomes relevant when
doing incremental dumps (the I command during the exit sequence or
the W command while in the middle of execution). When an incremental
dump is requested, the user may specify a number, e.g., W9, which
selects the particular incremental dictionary to be dumped. In this
example, dictionary 9 will be dumped.
Dictionary 0 is the main dictionary. Words cannot be added to this
dictionary, except by reading an auxiliary file. In general, words
that are inserted incrementally are marked as being in dictionary 1.
All words that are incremental insertions in the dictionary will be
marked in dictionary 1, unless the user specifies otherwise.
When requesting an incremental dump, the user may specify the
particular dictionary to dump. This is allowed in two cases:
The following places are where the user may specify which dictionary
to add to:
1. When loading an auxiliary dictionary, if the user
responds with "In" to the question about marking new
entries as incremental, then the new entries will be
marked in dictionary number n (where n is
interpreted as decimal and should be less than 31).
2. After a word has been rejected, type "In" to insert
the word in dictionary number n.
3. After replacing a word, if the replacement is not in
the dictionary, then type "In" to insert the
replacement into dictionary n.
When requesting an incremental dump, the user may specify the
particular dictionary to dump. This is allowed in two cases:
1. After some word has been rejected, the command "Wn"
will cause dictionary number n to be dumped.
2. During the exit sequence, the command "In" will
cause dictionary number n to be dumped.
In all five cases above, if n is either 0 or omitted, then it will be
taken as being 1.
Caution! There is no provision in SPELL for remembering which
dictionary numbers have been used. Therefore, it remains the
individual user's responsibility to remember the numbers of all the
dictionaries that he creates. (Forgetting the number will mean that
the forgotten dictionary can not be dumped incrementally. The words
in a forgotten dictionary will still be available, but the only way
to actually get them dumped out is to dump the entire dictionary).
Hint: In the course of correcting a file, it is likely that you will
be asked about words which you wish to have accepted during this
file, but which you don't wish to have saved in your incremental
dictionary(s). In these cases, simply insert them in a "throwaway"
incremental dictionary which you don't bother to dump when you're
finished.
---------------------------------------------------------------------
Abnormal Conditions
While the program is running it is possible that certain abnormal
conditions may obtain. The usual response of the program is to type
some sort of error message. The following is a list of the error
messages in SPELL, with an indication of the severity of the error.
Illegal dictionary entry: <word>
This error occurs if an entry in a dictionary file
exceeds 40 (decimal) characters. The word is
ignored.
0 LENGTH WORD AT HASHCP
Somebody just asked to compute the hash address of
an empty word. The program continues, but there
is a possibility of error.
HASHING ERROR
Somebody asked for the hash address of a word that
doesn't begin with letters or apostrophe as the
first two characters. This is a fatal error; the
program halts.
DEVICE DATA ERROR (OUTPUT)
This message means that while writing a file,
something screwed up. The program halts.
DEVICE ERROR (INPUT)
The input file is screwed up in some way. The
program halts.
Internal confusion in the spelling checker.
Called from location <loc>. The spelling checker
has discovered a (possible) bug in itself. The
program halts, but the user may type CONTINUE.
Please note the location mentioned and the
circumstances that evoked the message.
Dictionary number too large, Maximum is 30.
This message means that the user attempted to
select for insertion or dumping a dictionary
beyond the range of allowed numbers. The user
will get another chance to do the right thing.
Unrecognized switch.
The user asked for an unknown switch. He must
repeat the entire switch specification again.
The following messages occur only in the non-TENEX version:
Illegal Character in Scan.
This is a message from the routine that reads file
names. You will be asked to try retyping the name
(non-TENEX only).
File not Found. <filename>
The indicated file could not be found. The user
gets to specify some other file.
Enter failed on: <file name>
An enter uuo failed while trying to select the
indicated file for output. The user may specify
another name.
Open Failed on Device <dev>:
You asked for a device that doesn't exist or isn't
available to the program. You will get a chance to
ask for something else.
Insufficient Core Available.
SPELL requires more core while expanding the
dictionary but none is available. The program
exits.
---------------------------------------------------------------------
Appendix - Internal Workings
Data Structures - Hashing Function
The data structure is the heart of the program, and any efficiency in
the program operation is due primarily to this choice of data
structure. The data structure is basically a hash coding scheme
where dictionary entries are accessed by both their alphabetic order
and by their length. There is a base table that contains 26 * 26 *
10 halfwords; this table gives anchors for 6760 chains. Each chain
contains exactly all words with the same two first letters and some
given length. To be precise, the hashing function is:
(L1*26+L2)*10+min(WL-2,9),
where L1 and L2 are numeric representations of the first and second
letters (A=0, B=1, ... Z=25, and apostrophe also is 25), and WL is
the length of the word in characters.
This scheme was chosen since it provides both an efficient
way to probe the dictionary and a quick way to select a small subset
of all words that are close to a given input word.
Data Structures - Dictionary Entry Format
Entries are added to the appropriate hash chain by the INSERT
subroutine. Entries are added to the head of the chain, saving the
time and effort of searching to the end of the chain. This scheme
means that the last item entered on a chain is the first item seen by
a search. The format of the entry is given by:
Word 0: xwd flags,nextlk
Word 1: 5 bit representation
Word 2: 5 bit representation
...
There are precisely 1+ceiling(WL/7) machine words used for each
dictionary entry. WL is the length of the entry in characters.
Nextlk is the pointer to the next entry in the list, or zero if this
is the last in the chain. The left side contains flags; bits 13-17
specify the incremental dictionary number (0 for main, 1-30 for
incremental dictionaries, and 31 for misspellings). One can imagine
that bits 5-12 could be used to store semantic information about the
entry. The unused bytes in the last word of an entry must be zero,
since they are used to stop the routine that converts the five bit to
7 bit.
Misspellings are entered in the main dictionary with the incremental
dictionary number set to decimal 31. If a word is marked as a
misspelling then the word preceding the flags and link contains a
pointer to the flag and link word of the correction. Misspellings
may be deleted before the full dictionary is dumped, or whenever
SPELL asks about saving the core image. The spaced obtained by
deleting misspellings is not reutilized at present, although that
feature could be added without great difficulty.
Spelling Correction Heuristics
There are four kinds of errors that the program attempts to correct:
1. one wrong letter.
2. one missing letter.
3. one extra letter.
4. two transposed letters.
For a wrong letter in the third or subsequent character, all words
that are candidates must exist on the same chain that the suspect
word hashes to. Hence, each entry on that chain is inspected to
determine if the suspect differs from the entry by exactly one
character. This is accomplished by an exclusive-or (XOR) between the
suspect and the dictionary. Then a JFFO instruction selects the
first non zero byte in the XOR. This byte is zeroed and if the
result is all zero then the dictionary word differs from the suspect
in only one letter. All such words are listed at CANDBF, where they
can be inspected later.
For a wrong letter in the first or second character, the program
tries varying the second letter through all 26 possible values,
searching for an exact match. Then all 26 possible values of the
first letter are tried, after setting the second letter to its
original value. This means that 52 more chains are searched for
possible matches.
To correct transposed letters, all combinations of transposed letters
are tried. There are only WL-1 such combinations, so it is fairly
cheap to do that.
To correct one extra letter, wl copies of the word are made, each
with some letter removed. Each of these is looked up in the
dictionary. This takes WL searches.
To correct one missing letter, WL+1 copies of the word are made, each
time inserting a null character in a new position in the suspect.
The null character is never part of any word, so the suspect word
augmented by an embedded null can be thought of as a word with one
wrong letter (the null) then the algorithm for matching one wrong
letter is used. If the first character is omitted, all 26 possible
first characters are tried. Also, 26 more words are formed by
varying the second character in case that had been omitted.
---------------------------------------------------------------------
Appendix - Assembly Instructions
There are four assembly time switches, CMUSW, TENEX, STANSW and
SANSW. If STANSW is set then there are SIXBIT ppn's and the SWAP
UUO; if STANSW is zero, then normally there are octal ppn's except if
SANSW is set, in which case, there are decimal ppn's. If the TENEX
switch is set it overrides the others and TENEX style file names are
used. The CMUSW provides a CMU-style PPN scanner and provision for
CMU slow terminals.
Compile the program using MACRO or FAIL and load it. When you start
the program the first time after loading, it will demand a
dictionary. Use the file SLOVAR (at BBN, SPELL.SLOVAR), or anything
else that's handy.
Save the resulting core image when the dictionary load is complete.
There are various other assembly switches, but they default to
reasonable settings, and you meddle with them at your peril.
---------------------------------------------------------------------
Appendix - Possible Expansions
No program that is still in use is complete. The following
paragraphs include suggestions of possible future work in this area.
The dictionary should be expanded to include all suffixes for every
word. There is a feature that strips suffixes for the purpose of
finding the stem of the word in the dictionary, but this heuristic is
error prone and incompatible with later attempts to correct the word.
If semantic information were included in the dictionary, it could
help guide the selection of a correction.
Either of these would require a major restructuring of the program,
since the dictionary would no longer fit in core. Probably, the
dictionary should be kept on the disk, with a data structure similar
to the one used in core, but arranged to keep each hash chain in the
minimum number of disk pages, so that searches through the dictionary
can be made efficient.