Trailing-Edge
-
PDP-10 Archives
-
decuslib20-05
-
decus/20-0148/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
1.0 INTRODUCTION
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 and Marshall Abrams of NBS.
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:
1. 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.
2. 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.
3. 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:
4. 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.
5. 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.
6. SPELL keeps track of all word spellings which were
corrected by the user. Subsequent occurrences of
such are automatically corrected by the program.
Page 2
This is reported to the user by a typeout of
"MISSPELLING ==> CORRECTION".
7. 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).
2.0 USING SPELL
2.1 Starting 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.) (TOPS-10 accepts ^U, DEL, and, depending on
MONGEN parameters, BS.)
2.2 Augmenting The Built-in Dictionary
The non-TENEX version will first attempt to load the default
private dictionary file WORDS.DIC into dictionary 1 with
incremental insertion set (see Incremental Insertion below).
Next, SPELL will ask: "Do you want to augment the
dictionary?" If you wish to use only the main dictionary
(plus WORDS.DIC) presently in memory, type <cr>. You can
then skip the next paragraph.
2.2.1 Private Auxiliary Dictionary - If in fact you have an
additional 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 the dictionary
file.
2.2.1.1 Incremental Insertions - 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
Page 3
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.)
2.2.1.2 Additional Dictionaries - 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).
2.2.1.3 Dictionary Format - 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".
2.3 Switches
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.
Page 4
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").
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.
2.4 File To Be Corrected
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).
Page 5
2.5 Output File
You will be next asked to name the output file. Enter a
file name, or just a <cr> if you wish to use the default
(see next paragraph).
2.5.1 Default Output File(s) - In the TENEX version there
are always output and exception files; by 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 the default output is
to rename the input file with extension .BAK and to place
the corrected text in the (previous) input file name. The
exception file may be omitted.
2.5.2 Exception File - 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.
2.6 Checking And Correcting
After you have specified all the files, the program will
respond with "Working..." and start checking the input file
for spelling errors.
2.6.1 Choices When An Unknown Word Is Found - 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.
In general, when a word is found that is not in the
dictionary, a brief message 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, you
will be given the choice of typing C to accept the "guess"
or any other option. The options are:
C The "guess" is correct. Correct the word in the
text. Enter misspelling in dictionary so that it
will be corrected if it appears again.
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
Page 6
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
Page 7
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.
<esc> Escape from this submode and return to the
outer command mode.
Note that when you make a correction via the C command or by
selection from the list presented by the S command, that
correction is entered in the misspelling-correction list and
subsequent occurrences of the same misspelling will be
corrected automatically.
2.7 Finished Processing The File
When the input file is exhausted, all files are closed, the
program types "Finished.", and the exit sequence is entered.
Except on TENEX, you will be asked if you want the default
dictionary WORDS.DIC dumped. Answer "yes" or "no" (actually
only a single letter answer is required). 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 read in from a private dictionary and marked with
an I plus those inserted while running the program are
dumped to a file. The user specifies a file name (the
default is WORDS.DIC). 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.
Page 8
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.
3.0 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.
3.1 Dictionaries 0 And 1
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.
3.2 Specifying A Dictionary
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.
Page 9
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.
3.3 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).
3.4 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.
4.0 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
Page 10
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.
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.
Page 11
5.0 INTERNAL WORKINGS
5.1 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.
5.2 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
Page 12
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 space obtained by deleting misspellings
is not reutilized at present, although that feature could be
added without great difficulty.
5.3 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.
Page 13
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.
6.0 ASSEMBLY & LOADING INSTRUCTIONS
There are three assembly time switches, 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. Compile the
program using MACRO or FAIL and load it. The non-TENEX
versions will produce a sharable high segment and a
non-sharable low segment. When you start the program the
first time after loading, it will demand a dictionary. This
dictionary will be read in as dictionary zero, which is the
built-in dictionary for future use. In the non-TENEX
versions dictionary zero is read into the sharable high
segment. Use the largest dictionary you have which meets
your storage limitations. The file SPELLD.ALL is
recommended.
When dictionary zero is loaded, SPELL will ask "Do you wish
to save this core image?" Answer "Yes" and save the
resulting core image. On non-TENEX systems, do an SSAVE to
produce a sharable high segment containing dictionary zero.
There are various other assembly switches, but they default
to reasonable settings, and you meddle with them at your
peril.
7.0 POSSIBLE EXPANSIONS
No program that is still in use is complete. The following
paragraphs include suggestions of possible future work in
this area.
For non-paged systems, the main dictionary (0) should be in
the sharable segment and the private additions in the
non-sharable segment. This would require adjusting the hash
chains to point across the gap.
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.
Page 14
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.