\documentstyle{article}

\title{A spelling corrector incorporating knowledge of English 
orthography and pronunciation\thanks{Many of the ideas in this
programme were inspired by discussions in a course taught at Stanford
University by Jared Bernstein of SRI and Andr\' as Kornai of CSLI and
the Hungarian Academy of Sciences.}}

\author{Brett Kessler}

\begin{document}

\maketitle

\bigskip

\begin{abstract}

I have developed a spelling corrector, {\tt correct,} based on a model
treating misspellings as flawed attempts to spell words using the
sound-spelling correspondences of English orthography.  On a common
test suite, it generates a correct guess for 97\% of the misspellings.
It ranks multiple guesses by the Levenshtein distance from the
misspelling, combined with the frequency of the sound-spelling
correspondences presumed to have generated the misspelling.  The
average rank of the correct respelling, using a complete English
dictionary as the universe of candidate respellings, is 1.1.  This
paper describes the development and structure of the {\tt correct}
programme.

\end{abstract}

\section{The problem}

Attempts at automatic spelling correction are dominated by
transformations and comparisons directly between misspellings and
candidate respellings.  Alberga \cite{Alberga} gives a thorough
overview of many such approaches (see also \cite{Pollock} for a more
recent project in this vein), and presents results of experiments
where he reports a 98\% success rate in using such techniques to
verify whether a misspelt word is an attempt at a particular target
spelling.  Automated spelling correctors are in general not nearly so
good, in part because it would be prohibitively expensive to apply
sophisticated string comparisons between a misspelling and all the
words in a dictionary.  But an influential paper,
\cite{Damerau}, showed that, following an early analysis by Gates
\cite{Gates}, a large majority of errors could be corrected by the
insertion, deletion or substitution of a single letter, or the
transposition of a single pair of letters -- the sort of
transformations which can be efficiently processed automatically.  As
a result of the popularity of this successful model, spelling
correctors tend to be better at correcting mechanical keystroke errors
-- which the typist could have easily corrected without any help
beyond flagging the error -- than at fixing correctly typed
misspellings which one can recognize as an attempt to spell out the
pronunciation of a word.  For example, the widely-used Unix spelling
corrector {\tt ispell}\footnote{Originally written by Pace Willisson.}
can easily correct the form {\em hpantom} to {\em phantom}, but not
the misspelling {\em fantom}.

Such systems have their niche, partly because selecting a correction
from a menu can be faster than editing text, and partly because many
true (conceptual) spelling errors are indistinguishable from such
mechanical errors.  For example, if the computer analyzes the
misspelling {\em recieve} as a simple mechanical transposition error,
the user is still grateful for the correction, even if what really
occurred was a spelling error influenced by analogy with {\em believe}
and a host of similar words.  But one might wonder whether a large
class of spelling errors might be more effectively handled if the
programme modeled the processes which led the human to make the error.
Although some misspellings surely arise from misremembering the
details of a memorized spelling (and therefore may be similar in many
ways to keystroke errors), others are clearly the product of trying to
spell out pronunciations, based on sound to spelling correspondences
the speller is familiar with from other words.  An unpublished PhD
thesis cited in \cite{Alberga}, namely \cite{Masters}, reported that
in a study of spelling errors made by pupils and students from eighth
grade through college, 65\% were phonetically correct and another 14\%
nearly so.  It is discouraging that Alberga goes on to state that in
following up on an unpublished suggestion by H. B. Savin of the
University of Pennsylvania to do just the sort of sound-spelling
analysis I am here suggesting, he got low performance: only 64\% of
the misspellings he paired with the correct spelling were verified as
matches by his programme.  Alberga unfortunately gives few details of
his algorithm, perhaps in part because it performed much worse than
every other algorithm he tried, but this does seem to confirm that
only about two thirds of all spelling errors use normal sound-spelling
correspondences.  I nevertheless undertook to develop an
orthographically based spelling corrector.  The intent was partly to
verify Alberga's results in actual use (he simply asked the programme
to verify whether two words might be intended to be the same).  But
even if the low results turned out to be sustained, it could be the
case that this approach covers a different set of words than
traditional spelling correctors, and so may complement their efficacy.

In summary, my approach assumes that the user is aware of the basic
rules of English orthography, but may be vague on some of the
exceptions and idiosyncrasies of particular words or morphemes.  If
the user types a {\em j}, this approach does not assume that this was
a random insertion, or possibly a substitution for {\em h} or {\em k}
or some other letter, but rather that the user meant to spell some
sound that is in some context spelt by a {\em j}, viz., /j/ (or
conceivably /y/ as in {\em hallelujah}).  The corresponding letter for
/j/ may turn out to be a {\em g, dg} or {\em d} as well as {\em
j}.\footnote{The phoneme notation used here is explained in section
2.1.1.  Although more intuitive phonemic representations could be
generated, even without the use of IPA founts, it was felt that the
reader who wishes to study the source code and dictionary files would
be better served if the representations used in this paper are the
same.} The system I have developed is aware of the true pronunciation
of English words, has a full inventory of the sound-spelling
correspondences used in English orthography, and knows how often such
correspondences are regularly employed in English spelling.  On
encountering a misspelling, it generates a list of possible
respellings and attempts to position the most likely guesses at the
top.  A prototype called {\tt correct} is now available and has
undergone preliminary evaluation of its effectiveness.

The next section of this report describes the product and its
implementation, and Chapter 3 presents the results of running
evaluation suites on it.  Chapter 4 concludes the report with some
details on how the system was developed.

\section{Product description}

The system consists of two major parts, the executable programme
proper, {\tt correct}, and a dictionary.

The main logical components of the system have been compiled into one
of these two components.  In particular, the dictionary is the
inventory of legal words; a repository of the legal spelling of words;
and an embodiment of knowledge of the correct spelling and pronunciation of
derived and inflected words.  The programme knows what sound-spelling
correspondences occur in the dictionary, and how often they occur; it
knows how to use them to generate pronunciations from (mis)spellings,
then use the dictionary to verify what pronunciations constitute
actual words and get their legal spellings, then sort the respellings
by the frequency of the inferred sound-spelling correspondences and/or
by the Levenshtein distance from the misspelling.

\subsection{Dictionary}

The dictionary resides on disk, and is composed of two parts: a seven
megabyte text file, which shows the spelling and pronunciation of
words, and a three megabyte index file, which allows the programme to
quickly look up a word by its pronunciation.

\subsubsection{Dictionary text file}

\begin{table}
\centering
\begin{verbatim}
AgranyxlOsIts   agranulocyte's  n
AgranyxlOsIts   agranulocytes   n
AgranyxlOsIts   agranulocytes'  n
Agret   aigrette        n
Agrets  aigrette's      n
Agrets  aigrettes       n
Agrets  aigrettes'      n
AgwE    aiguille        n
AgwEl   aiguille        n
AgwElz  aiguille's      n
AgwElz  aiguilles       n
AgwElz  aiguilles'      n
AgwExl  aiguille        n
AgwExlz aiguille's      n
AgwExlz aiguilles       n
AgwExlz aiguilles'      n
AgwEz   aiguille's      n
AgwEz   aiguilles       n
AgwEz   aiguilles'      n
Agwxlet aiguillette     n
Agwxlets        aiguillette's   n
Agwxlets        aiguillettes    n
Agwxlets        aiguillettes'   n
AgxmEt  agamete n
AgxmEts agamete's       n
AgxmEts agametes        n
AgxmEts agametes'       n
Agxn    egging  vt
AgyU    ague    n
AgyUiS  aguish  aj
AgyUiSlE        aguishly        av
AgyUz   ague's  n
AgyUz   agues   n
AgyUz   agues'  n
Agz     egg's   n
Agz     eggs    n
Agz     eggs'   n
Agz     eggs    vt
Ahab    Ahab    n
Ahabz   Ahab's  n

\end{verbatim}

\caption{A contiguous selection from the dictionary text file.}
\end{table}

The dictionary consists of the pronunciation, spelling, and major
class of a word.  In the text file, each line (separated by ASCII {\tt
NL}) consists of one such triplet, each field separated by ASCII {\tt
TAB.} The information basically agrees with that in \cite{Webster},
except that some pronunciations have been added, regular inflected
forms have been added, multi-word entries and abbreviations and
initialisms are omitted, spellings containing accent marks (anything
besides letters and apostrophe) are omitted, pronunciations containing
non-English phonemes (and ``broad a'') are omitted, and entries
lacking either spelling or (possibly synthesized) pronunciation are
omitted.  The source word list unfortunately does not include the
proper names from the back of the book, so I inserted the geographic
names required by the test suite.  Including multiple spellings or
pronunciations for the same word, the dictionary has 329,116 entries.

The pronunciations are strings whose elements are one of 39 phonemes,
as described in the table below.  The phoneme representations were
designed to be one-to-one mappings to the phones, and to use only
alphabetic symbols; these constraints greatly aided automatic
processing in a Unix environment.  Within these constraints, I stayed
as close as possible to the source text's transcription, which itself
stayed as close as possible to the transcription used in the book.
/hw/ as in {\em which} is here treated as a sequence of two
phonemes, as are the retroflex vowels as in {\em butter} (/xr/) and
{\em bird} (/Xr/) and syllabic consonants (/xl, xn/, etc.).  Note also
the distinction made here between unstressed /x/ and stressed /X/,
contra \cite{Webster}; this is done because they are spelt
differently, and the stress information is not carried in our
dictionary file.  Syllable divisions are not carried, either.

\begin{table}
\centering
\begin{tabular}{|l|l|l|l|l|} \hline
correct & IPA &  keyword &  W7 book      &  W7 file \\ \hline\hline
a    & \ae &    {\em a}nt   &    a          &    a     \\ \hline
A    &  e  &    {\em a}pe   &  \= a         &    A     \\ \hline
b    &  b  &    {\em b}ee   &    b          &    b     \\ \hline
c    & t   &  {\em ch}imp   &   ch          &    ch    \\ \hline
d    &  d  &   {\em d}og    &    d          &    d     \\ \hline
D    &     &  {\em th}en    &\underline{th} &    TH    \\ \hline
e    &     &  {\em e}lephant&    e          &    e     \\ \hline
E    &  i  &  {\em ea}gle   &  \= e         &    E     \\ \hline
f    &  f  &  {\em f}rog    &    f          &    f     \\ \hline
g    &  g  &  {\em g}oose   &    g          &    g     \\ \hline
h    &  h  &  {\em h}og     &    h          &    h     \\ \hline
H    &     &  {\em o}dd, sp{\em a}&  \" a         &    \&    \\ \hline
i    &     &  {\em i}t      &    i          &    i     \\ \hline
I    & a   &  {\em i}bis    & \= \i         &    I     \\ \hline
j    & d   &  {\em j}ungle  &     j         &    j     \\ \hline
k    & k   &  {\em k}ing    &     k         &    k     \\ \hline
l    & l   & {\em l}amb     &     l         &    l     \\ \hline
m    & m   & {\em m}ynah    &     m         &    m     \\ \hline
n    & n   & {\em n}ewt     &     n         &    n     \\ \hline
N    &     & so{\em ng}     &               &    N     \\ \hline
o    &     & {\em au}k      &     \. o      &    o     \\ \hline
O    & o   & {\em o}kra     &  \= o         &    O     \\ \hline
p    & p   & {\em p}ig      &     p         &    p     \\ \hline
r    &     & {\em r}am      &     r         &    r     \\ \hline
s    & s   & {\em s}in      &     s         &    s     \\ \hline
S    &     & {\em sh}eep    &    sh         &    sh    \\ \hline
t    & t   & {\em t}om      &     t         &    t     \\ \hline
T    &     & {\em th}ug     &    th         &    th    \\ \hline
u    &     & p{\em u}ll     &   \. u        &    u     \\ \hline
U    & u   & r{\em u}le     &    \" u       &    U     \\ \hline
v    & v   & {\em v}ine     &     v         &    v     \\ \hline
w    & w   & {\em w}eed     &     w         &    w     \\ \hline
W    & a   & {\em ow}l      &    a\. u      &   au     \\ \hline
x    &     & okr{\em a}     &               &    *     \\ \hline
X    &     & {\em u}gly     &               &    *     \\ \hline
y    & j   & {\em y}ak      &     y         &    y     \\ \hline
Y    &     & {\em oi}l      &     \. oi     &   oi     \\ \hline
z    & z   & {\em z}ebra    &     z         &   z      \\ \hline
Z    &     & mena{\em g}e   &     zh        &   zh     \\ \hline
\end{tabular}

\caption[Pronunciation codes used in the dictionary]{Pronunciation
 codes used in the dictionary text file, compared with that of
Webster's book and its transcription.}

\end{table}

Spellings are ASCII strings as from the dictionary, without
syllabification, and with capitalization distinctions preserved.  A
word may have more than one spelling as it may have more than one
pronunciation, but in such cases they simply appear in different
entries.  Since the text file is sorted by pronunciation, there are
blocks of entries that have the same pronunciations but different
spellings.

The last field in the text file entry consists of a one- or two-character
code for the major class of the word.  This is not used by the system
except to optionally display to the user the part of speech a particular
spelling is associated with, as an aid in distinguishing between 
candidate respellings.  This
may be omitted (in which case a ``?'' appears), or there may be more
than one code, separated by comma (no space).

\begin{table}
\centering
\begin{tabular}{|ll|}  \hline
aj & adjective \\  \hline
av & adverb \\  \hline
cj & conjunction \\  \hline
da & definite article \\  \hline
ia & indefinite article \\  \hline
ij & interjection \\  \hline
n  & noun \\  \hline
pn & pronoun \\  \hline
pp & preposition \\  \hline
tm & trademark \\  \hline
va & auxiliary verb \\  \hline
vb & verb \\  \hline
vi & intransitive verb \\  \hline
vm & modal verb \\  \hline
vp & imperative verb \\  \hline
vt & transitive verb \\  \hline
\end{tabular}

\caption{Word class codes used in the dictionary text file.}

\end{table}

It could also be of great assistance to a misspeller to include a
short definition or synonym, as an aid in picking out the correct
respelling.  Such data was not immediately available, however, and
has no impact on the rest of this study.

\subsubsection{Dictionary index file}

The dictionary is accessed via an index of pronunciations. The index
file is organized as a trie, with all paths fully pursued to the end.
For general information on trie structures, see \cite{Fredkin} or
\cite{Knuth}, section 6.3.  Briefly, the {\em root node} of the trie
points to another node for each of the 39 possible initial phonemes a
word may have.  Each of those nodes likewise contains a pointer to a
node for each possible second phoneme, and so forth.  These are here
called {\em continuations.} Although in many applications tries are
compressed to include only minimally distinctive differences, our trie
includes every phone in the pronunciation.  The continuation node for
the last phone of a word will contain a {\em termination}, which
points to the first dictionary text file entry which has the
pronunciation that was pursued.  Note that a node may have both
continuations and terminations, since some whole words are initial
segments of others.  For example, if one goes from the root node to
the /A/ node, the latter will have pointers to all possible phones that can
follow initial /A/, but it will also have a termination for /A/ as a
complete word ({\em a, ae, eh...}).

Physically, each node has a header: one byte is a binary number
telling how many different continuations there are; the next three
bytes are a binary number which, if the node has a termination,
constitute the byte offset from the beginning of the text file where
entries with the pursued pronunciation begin.  If the node has no such
termination, the number has all 1 bits.  If the node has continuations
(that is, that first one-byte binary number was non-zero), there
follow that many continuation pointers.  Each pointer contains a
one-byte binary number that tells which phoneme the continuation is
for.  This is an arbitrary number that is not the same as the ASCII
encoding of the phoneme codes shown above; the interested reader can
find the codes in programme file {\tt Phones.h}.  This byte is
followed by three bytes which are a binary number telling the byte
offset from the beginning of the (same) trie file where the
continuation node begins.  Note that nodes are of variable length, but
always some multiple of 4 bytes.

It might be noted that since the pronunciation is embodied in the
index, there is really no strict reason why it should also be included
in the text file.  It will be seen later that all that is really
needed is a flag indicating whether an entry has the same
pronunciation as the previous one.  Production units of {\tt correct}
could save a great deal of space (here, 2.7 Megabytes) by omitting the
pronunciation in the text.  This is an all-around win, because that
would also (marginally) speed up the programme.

If space is very critical, there are also two ways to save dictionary
text space that would however slow down the programme, perhaps
marginally.  One would be to compress it by Huffman encoding, which
would of course require time to decompress the entries at run time.
Another way would be to encode very common, regular affix patterns in
the index (such as regular inflexions and a few common derivational
affixes).  The trie could contain a path for the inflected form, but
have a pointer to the base from in the text, along with a code telling
the required inflexional pattern.  The full spelling would then of
course have to be generated on the fly, using code such as that in {\tt
AddInfl.c.}

\subsection{The programme}

In addition to the normal Unix C library, the programme is composed of
the following five modules: a control module {\tt correct} which
determines user options and reads standard input for words to be corrected;
{\tt ListCorrections}, which is responsible for ordering and
presenting respellings; {\tt Kruskal}, which determines the
Levenshtein distance between the misspelling and candidate
respellings; {\tt Respell}, which generates candidate respellings based
on sound-spelling rules and the dictionary; and {\tt DictTrie}, which 
accesses the dictionary.

Since the source code is fairly closely commented, there seems little point
in going into detail about the implementation here.  It does however seem
advantageous to explain the purpose and philosophy behind the various
modules, and to explain the most important algorithms.  The modules will
be discussed in bottom-up order, explaining modules used by other modules
before explaining the modules that make use of them.

\subsubsection{DictTrie}

{\tt DictTrie} provides the kind of access to the dictionary needed by
the respeller.  That is, it allows the client to look up a
pronunciation phoneme by phoneme.  At any point, the function {\tt
MoveUpTrie} either returns a failure indication, signifying that no
word has as its initial segment the series of phonemes that has been
pursued, or it returns the identifier for the proper continuation
node.  When the client has the next phoneme in hand, it calls {\tt
MoveUpTrie} with that continuation node ID and the next phoneme.  Thus
from the client's point of view, it is simply getting back a generator
state handle, whose value it is indifferent to.  If the client gets to
the end of the word without failing, it calls {\tt LookUp} to see if
there is a termination (a whole word matching the pursued phoneme
string).  If so, the dictionary text is positioned at the first such
entry, and {\tt GetEntry} can be called repeatedly to read in entries
as long as the pronunciation is of interest (matches).

The important feature about this organization is that it lets its client
prune candidate pronunciations as soon as an unattested initial segment
is generated.

\subsubsection{Respell}

This module uses the {\tt DictTrie} and its own knowledge of
sound-spelling rules to generate respellings for a misspelling. 

The guesses are generated by assuming that each letter in the input is
intended either to directly spell one or more phonemes, or to do so in
conjunction with one or more other letters.  Thus I assume the
existence of correspondences like {\em a} = /a/, {\em x} = /ks/, and
{\em sh} = /S/.  The hypothesis of {\em silent letters} is ruled out,
since there is effectively no way to distinguish a silent letter from
a partner in a digraph.  That is, one cannot say whether {\em sh} is a
digraph, or whether {\em s} spells /S/ before a silent {\em h}.
\cite{Lucassen} implicitly agrees on the issue, but went the other
way, saying that there are no digraphs, just silent letters.

{\tt Respell} contains (as {\tt include} file {\tt RuleTrie.c}) the full
set of 1,053 context-free graph\-eme to phon\-eme corre\-spond\-ences
found in the dictionary.\footnote{For a discussion of where these
correspondences come from, see Section 4.} These
correspondences are stored in a trie which branches on the spelling,
but is conceptually much like the {\tt DictTrie} index.  For example,
to find the phonemic correspondences for the spelling {\em ai}, one
begins at the root of the trie.  One would take the {\em a} branch to
get to the node for {\em a}, and take its {\em i} branch to get to the
node for {\em ai}.  This might have other continuation nodes, but it
also has a termination pointer to arrays of pronunciations and the
frequencies with which these pronunciations correspond to {\em ai}.
These frequencies represent the number of times the sound-spelling
correspondence occurs in the dictionary word types.  It is often
argued that such frequencies should be weighted by the frequency of
the words themselves in written text, since that would represent how
often the correspondence is encountered in daily life.  I hypothesize
however that in general humans analogize on the basis of word types
rather than tokens.  One rarely sees for example the letter {\em f}
used to spell the /v/ sound in misspelt words, even though that
correspondence appears in 4\% of words in running English text (in the
word {\em of}\ \cite{Brown}).

The {\tt Respell} algorithm in presented and explained in the attached
source code listings, but it is important enough to be sketched
briefly here.  The misspelt word is stored in global space while a
recursive procedure {\tt Recur} works its way through it with
pointers.  Briefly, each iteration of {\tt Recur} matches part of the
word with a pronunciation, based on a single sound-spelling
correspondence, then recurses to match the next part of the word.  On
reaching the end of the misspelling, the word(s) matching that string
of phonemes is looked up in the dictionary and passed on to the
client.  {\tt Recur} also passes along the number of correspondences
so far matched and the sum of their frequency, so that at the end the
average frequency can be reported along with the spellings.  As
discussed under {\tt DictTrie} above, pronunciations can be looked up
in the dictionary one phoneme at a time by moving from node to node
via {\tt MoveUpTrie}.  {\tt Respell} therefore merely passes the
current node on from one invocation to the next.  As soon as the
pronunciation it is generating begins to represent an initial segment
not found in English, {\tt Respell} can abort that path instead of
following fruitlessly to the end of the word.

Of course, as so far described, {\tt Recur} could be a simple
iterative procedure instead of a recursive one.  There are two
complications which explain the need for the overhead of recursion.
One is that for a given spelling segment, there may be more than one
corresponding pronunciation, a well-known feature of English
orthography.  The use of recursion allows us to follow multiple paths
through the dictionary index, branching at each alternative
pronunciation.  Thus {\tt Recur} is called again for each pronunciation
associated with a spelling.  The other complication is that a spelling
correspondence may have one or more letters, but there is no easy way
to predict whether a known multiletter string should be parsed as a
multiletter correspondence in a particular word (e.g., {\em sh} in
{\em bishop}) or as simpler letter correspondences that just happen to
be adjacent (e.g., {\em sh} in {\em mishap}).  {\tt Recur} addresses
this problem by trying all possibilities at each recursion.  For
example, when it works its way to the {\em sh} in a word, it first
checks out all pronunciations for {\em s} and calls itself recursively
with them, then checks out all the pronunciations of {\em sh} and
calls itself recursively with those.  The need to look at spelling
rules one letter at a time is just like the need to look
up pronunciations one phoneme at a time, and explains why the
correspondences are organized as a trie.

When {\tt Recur} gets to the end of a misspelling, the initial phoneme
segment generated may or might not be a complete word.  For example, 
processing the spelling {\em ka} to the end will successfully generate
/ka/ as a possible spelling, which won't have been pruned because it is
an initial segment of words like {\em cat} and {\em Kathy}, but there
won't actually be a word pronounced /ka/.  {\tt Respell} calls the
{\tt LookUp} routine of {\tt DictTrie} to see if the word exists.  If
not, it simply returns quietly from that invocation, backtracking to
pursue other paths.  If the word does exist, {\tt Respell} calls
{\tt GetEntry}, then calls the client's callback procedure with the
resultant spelling and word class.  It repeats this as long as it
gets from {\tt GetEntry} words with the same pronunciation.

\subsubsection{Kruskal}

Inasmuch as the theory behind {\tt correct} is that misspellings are
just perturbations in the normal process of generating spellings by
applying the rules of English sound-spelling correspondences, one
might hypothesize that misspellings are more likely to be fairly
similar to the correct word than widely different.  For if there is a
certain probability that a person would generate the wrong spelling
correspondence for any particular phoneme in the word, then the
probability that several or all should be wrong should be smaller.
Indeed, \cite{Pollock} reports that in keycoded text, 90-95\% of all
misspellings have but one error.  Therefore some measure of the
distance between a misspelling and a candidate respelling would seem
to be one good way of ranking among several candidate respellings.

The module {\tt Kruskal} calculates the Levenshtein distance between
two words.  It follows the algorithm set forth by Kruskal in
\cite{Kruskal}, under the simple set of assumptions that all insertions,
deletions, and substitutions are of equal weight.  Then it returns
an integer number telling the minimum number of such operations that
would be needed to transform the one word into the other.

\subsubsection{ListCorrections}

This module is responsible for sorting and displaying corrections
generated by {\tt Respell.}  The eponymous function receives a
mis\-spel\-ling from the control module, calls {\tt Re\-spell} to
generate respellings which are passed back to one of the callback
functions in {\tt ListCorrections}, optionally sorts the respellings
by any of various criteria, then displays the respellings in order on
standard output.

{\tt ListCorrections} can be set to display guesses in the order that
they are generated ({\tt dump} mode), but this is not necessarily the
most desirable order.\footnote{It does give precedence to the more
common pronunciations for a given string, but it also has the possibly
undesirable property of giving precedence to correspondences with
shorter spelling strings, especially on the left side of the word.}
Even more importantly, different parses of a misspelling can result in
the same respelling, which would therefore be printed multiple times.
Therefore in any serious mode of operation, {\tt ListCorrections} uses
a callback which stores the unique respellings in a list, along with
the number of times that respelling was generated, the word classes,
and the best average frequency of the presumed sound-spelling
correspondences for each unique respelling.  When {\tt Respell}
returns after generating all of its guesses, that list can then be
printed out directly, if it is only desired to suppress duplicates
({\tt unique} mode).  It can also be sorted first, in any of various
ways.  One can sort by the number of different parses that generated
each unique spelling ({\tt paths} mode), or by the average frequency
of the correspondences ({\tt ruleProb} mode).  It is also possible to
calculate the Levenshtein distance (via {\tt Kruskal}) and sort by
that ({\tt kruskal} mode).  Since that discrete measure results in many
ties, this mode also does a minor sort by the correspondence
frequencies.

The various modes of presentation are selected by the client module
on a per-word basis when calling the {\tt ListCorrections} function.
The client can also choose which dictionary to use for each word, although
this flexibility is not exploited by the current prototype.

\subsubsection{correct}

The main control module has the same name as the
programme itself.  {\tt correct} is responsible for determining user
options and for reading misspellings from standard input and passing
them on to {\tt ListCorrections}.

Several user options can be specified on the programme's command line.
{\tt -t} specifies the name of the text file of the dictionary, and
{\tt -i} can specify the name of its index file.  More interestingly,
the {\tt -o} option can be used to specify the sort order mode to be
used by {\tt ListCorrections: dump, unique, paths, ruleProb,} or {\tt
kruskal}.  Only the first character of the mode is read, so abbreviations
like {\tt -ok} are permissible.  One may also specify {\tt -m} to ask
that major word classes be displayed along with the misspellings.
{\tt -s} asks the programme to display relevant statistics: namely,
the average frequency of the presumed sound-spelling correspondences
for each respelling, and, in {\tt kruskal} mode, the Levenshtein
distance between each respelling and the misspelling.

Options not specified on the command line for a particular programme
run can be set via Unix environmental variables.  {\tt CORRECT\_TEXT,
CORRECT\_INDEX, CORRECT\_ORDER,} and {\tt CORRECT\_MAJOR} allow the
user to make a general declaration of his or her preferences, perhaps
in the {\tt .login} or {\tt .profile} file.

If the user gives no indication of personal preferences, options
default to {\tt -t} {\tt /usr/\-lo\-cal/\-dict/\-cor\-rect\-Text} {\tt -i}
{\tt /usr/\-lo\-cal/\-dict/\-cor\-rect\-In\-dex} {\tt -o kru\-skal}, and major
classes and statistics are not printed.

\section{Evaluation}

The most important metrics of a spelling corrector are how often it
guesses the correct spelling for a word, and how close that correct
spelling is to the top of the list of guesses.  In developing this
prototype, I was not particularly concerned with time and space
efficiency, except insofar as great wastage would be pointless and
easily correctable.  As for a source of errors with which to test, I
followed \cite{Damerau} in following \cite{Blair} in using a set of
117 ``spelling demons'' taken from \cite{Hutchinson}.  There is no
indication that these are gleaned from naturally found errors, and
they have been selected for a particular pedagogic purpose, but there
is value in using a test suite that has been employed on different
spelling correctors.  Perhaps a better approach would be to read a
large amount of prose and pick out the misspellings, as was done
recently in the spelling corrector work of \cite{Pollock}; better
still would be controlled experiments where one could distinguish
conceptual errors from unintentional typographic errors.  Such
approaches to evaluation will, however, have to wait for additional
sources of funding.

The test suite is included in the appendix.

To run the test suite, the first column (misspellings) was extracted
and fed into the standard input of {\tt correct}, using a particular
sorting option; a {\tt Makefile} is responsible for running the test suite
once with each option.  A programme called {\tt evalRun.nawk} then
evaluates each run to see which spellings were correctly guessed
(using the second column of the test suite, which shows the correct
form) and what the rank of the good guess was. Then it calculates
basic statistics across the run: the range of ranks and their average,
and the rank-weighted success rate, where correct guesses ranked {\em
n} are adjudged to have $1 / n$ of the correctness of a first-ranked
guess (and failures no weight at all).

Of course, all runs had the same unweighted success rate, since they
all make the same guesses, just in different order.  On this test
suite, {\tt correct} had a correct guess for 114 out of 117 errors
(97\%).  The three words it couldn't guess at all were {\em
heartrendering} as a spelling of {\em heartrending}, {\em
rhododrendon} for {\em rhododendron}, and {\em Wedensday} for {\em
Wednesday}.  The first two fail because they clearly reflect creative
pronunciations not found in the dictionary; the last seems to be an
arbitrary stab at remembering a unique spelling.

\begin{table}
\centering
\begin{tabular}{|l|r|r|r|r|}                                    \hline

Order & Success rate & Weighted & Lowest rank & Average rank \\ \hline\hline
dump     & 97          & 72        & 27          & 3.4 \\ \hline
unique   & 97          & 73        & 24          & 2.5 \\ \hline
paths    & 97          & 73        & 50          & 3.1 \\ \hline
ruleProb & 97          & 80        & 16          & 1.8 \\ \hline
kruskal  & 97          & 94        &  7          & 1.1 \\ \hline
ispell   & 68          & 64        &  4          & 1.1 \\ \hline
Damerau  & 74          & --        & --          & --  \\ \hline
Blair    & 76          & --        & --          & --  \\ \hline
\end{tabular}

\caption[Test suite results]{Test suite results using various sort
 orders for {\tt correct,} and compared with another corrector and two
research projects.  The success rates (percentages) are both absolute and
rank-weighted so that good guesses at rank $n$ are weighted $1 / n$.
The next two columns give the lowest and average rank of the correct
guess.}

\end{table}

In the {\tt dump} sort order, where respellings are presented in the
order guessed, the table shows that the rank-weighted success rate was
72\%, with the ranks averaging 3.4.  One might think that eliminating
duplicates (in {\tt unique} order) would improve the ranking, but
effects were small.

Along the way I wondered whether there might be some advantage to
ranking the words according to how many times they were generated as a
respelling.  After all, if several different ways of looking at a word
come up with the same pronunciation, it might seem more likely that
one of them is what the misspeller had in mind.  This technique, {\tt
paths}, turned out to be worse than {\tt unique,} with the lowest rank
plummeting to 50 (for {\em Britian/Britain}).

The preceding evaluations frankly were idle tests done largely because
they were easy to do.  The first trial of a sorting mechanism that I
thought had some chance of success was {\tt ruleProb}.  This
technique, it will be recalled, orders the respellings by the average
frequency of the sound-spelling correspondences inferred to contribute
to the misspelling.  The performance gain was not overwhelming, but
inspection of the test data shows that most low rankings rose
substantially. The rank-weighting formula so punishes ranks below
first place (it would take ten tenth-place guesses to equal one first
rank guess) that such efforts don't count for much more than failure.
The range of ranks is however promising: a standard 24-line terminal
would have enough lines to display enough guesses in {\tt
ispell}-style (one guess per line) that the correct word would appear
on the first screen.  Thus {\tt ruleProb} would be usable, though not
optimal, in a spelling corrector.

A final technique was to use Kruskal's algorithm to compute the
Levenshtein distance between the misspelling and candidate
respellings, then sort by increasing distance {\tt (kruskal).} In
other words, respellings most similar to the misspelling came out on
top.  We also minor sort by the correspondence frequencies, since
Levenshtein distance ties so often.  This method performed much better
than the others, with a rank-weighted success rate of 94\%, with good
guesses ranking no lower than seventh place.\footnote{Inspection
shows that many of the lower-ranked words, such as {\em duece/deuce},
could be described as a transposition.  If the {\tt Kruskal} algorithm
were modified to treat that as an atomic operation (weighted 1 instead
of 2), as is done in most systems inspired by \cite{Gates}, rankings
might perhaps be even better.}

This compares favourably with {\tt ispell}, which corrected only 79
misspellings (68\%).  This is a little lower than the figures from
Damerau's study, where using a perfect dictionary on the same test
suite enabled his programme to guess 74\% of the words correctly.
Blair's rather different technique, which involved comparing
tetragramme keys on correct and incorrect spellings in the same test
suite, achieved a similar success rate.

Such results are promising.  The overall success rate of 97\% is much
higher than the discouraging results reported for phonemic methods in
\cite{Alberga}.  The rankings of the correct guess are also particularly
impressive when one considers that a full dictionary containing
329,116 entries was used, thus giving ample opportunity for ambiguity.
On the other hand, the programme (which has not been tuned for
performance) is much slower than {\tt ispell:} it requires 2.6 seconds
to present all the respellings of a word on a Hewlett-Packard 9000/370
workstation (a Motorola 68030 machine), compared with 0.1 seconds for
{\tt ispell}.  More importantly, the test suite, although chosen
because it allowed comparison with earlier work, is decidedly friendly
to this application.  The test suite, like {\tt correct} itself,
addresses conceptual mistakes, and is clearly not intended to cover
mechanical, typographic errors.  {\tt ispell}, which obviously works
only on keyboarded text, is no doubt designed to handle all sorts of
errors, among which simple keystroke errors probably predominate
\cite{Pollock}.

It however was precisely my intent to cover only the conceptual
errors, and the evidence is that {\tt correct} does a good job of it.
One could well envision an application where {\tt Respell} and {\tt
Kruskal} are embedded in {\tt ispell} or a similar programme, which
would normally follow traditional techniques to detect misspellings
and present respellings based on the single-error model.  However,
when the user is dissatisfied with all the proferred choices and
requests more guesses, the programme could generate additional
pronunciation-based guesses and display them in {\tt kruskal} order.
This would be the best of both worlds and cover a significantly higher
percentage of misspellings than either system alone.


\section{Development history}

\subsection{Dictionary preprocessing}

The first step was to get a dictionary in usable machine-readable
form.  A database system like that of Celex \cite{Celex}, which was
designed from the beginning for machine use, would be ideal, but it is
not immediately available, and does not cover American pronunciations.
I have also experimented with using the datafile produced by the
Speech Communications Research Laboratory \cite{SCRL}, but it is so
riddled with errors and absurd pronunciations that I extrapolated that
about 300 days of work would be required to make it usable.  CSLI also
has a copy of Longman's dictionary (LDOCE) on-line.  This too was not
immediately accessible, and is primarily British, although it does
include American pronunciations too.  I finally decided on using a
locally-available copy of the single-word entries in Webster's 7th
collegiate dictionary \cite{Webster}, which contains spelling,
pronunciation, and major word class.  This was an extraction from a
keypunched transcription of the book, probably a descendent of the
transcription produced under government contract by System Development
Corporation in the early 1970's.

The dictionary is less than ideal.  Pronunciations are often
lacking or truncated, depending on human language expertise to resolve
the ``obvious'' pronunciation.  (Fully 28\% of the pronunciations are
fractional.)  Often these pronunciations depend on the pronunciation
in the previous entry, which is no longer there because multi-word
entries were deleted.  More seriously, the pronunciations of run-on
entries (derived forms not given a definition of their own) were
omitted when the extract was made, and the complete transcription did
not become available until too late in the project.  Also, inflected
forms are not given unless they are somehow irregular.

The most important thing to get into shape was the pronunciations.  I
estimated that it would require about 80 hours of work to hand-edit
the truncated pronunciations.  Instead, I wrote a programme that makes
guesses as to what is intended.\footnote{This and most similar
pre-processing tasks were undertaken using the Awk programming
language \cite{AWK} and standard Unix tools.  This particular
programme was convShPr.nawk.} Here is the algorithm for suffixed forms
(that is, fractional pronunciations of the form {\tt -X}): Find the
last syllable in the previous pronunciation whose first segmental
phoneme is the same as the first segmental phoneme of the suffix, and
replace it and subsequent syllables.  But if there is no such
syllable, or if that would be the first syllable of the word, replace
the last {\em m} syllables of the word, where {\em m} is the number of
syllables in the suffix.  But if the entry has no more than {\em m}
syllables, append the suffix to the end of the word.  For prefixes
({\tt X-} truncations), the rule was simply to replace the first {\em
m} syllables in the previous pronunciation, unless that would be the
whole word or more, in which case the truncation replaces the first
syllable.  This rule also worked for another kind of prefix, where the
last element of the prefix is simply the stress mark of the following
syllable; these cases were actually caught by a separate set of
programmes, {\tt runon2.nawk} and {\tt convShPr2.nawk.} For infixes
{\tt (-X-),} the programme substituted the first span of syllables of
which the first syllable had the same initial phoneme and the last
syllable had the same final phoneme as the infix.  If there was no
such span, it substituted from the first span of syllables that had
the same beginning; if none, then to the first span that had the same
ending; if none, then it substituted from the second syllable.  In all
of these cases, it tried to substitute a span of syllables of the same
length as the truncation, unless that would have involved going into
the first or last syllable.  Such relatively ad hoc rules enabled the
programme to expand approximately 90\% of the fractional
pronunciations correctly, leaving me with only about a 20 hour task to
edit that programme's output.  Instead of modifying the dictionary
directly, the programme worked with an intermediate file (generated by
{\tt runon.nawk}) that was easier to proof; the edited changes were
incorporated back into the dictionary via {\tt expandProns.nawk}.

I next addressed the problem of providing pronunciations for words
that do not have any at all. I began by writing Awk programmes to
extract the dictionary entries that have neither word class nor
pronunciation ({\tt getNoPos.nawk}), and those that have word class
but lack pronunciation ({\tt getNoPron.nawk}).  This revealed that
there are 35,828 such entries (31\% of all entries), of which 9,589
are lacking a word class.  A cursory examination showed that when both
word class and pronunciation are missing, it is either because the
entry is an inflected form whose spelling is not completely
straightforward (else the entry would have been omitted entirely), or
because it is a given name (e.g., Abby, Ada).  If a word class is
given but no pronunciation, it is because the word is derived from
another word whose pronunciation is given.  Sometimes this is through
zero-derivation, and so another entry has the required pronunciation;
at other times this is through the addition of suffixes.

First I addressed the entries that had a word class but no
pronunciation, since the entries lacking word class seem more often
dependent on other entries and therefore might be easier to expand if
the others were expanded first.  The programme {\tt matchSpell.nawk}
used {\tt look} on a sorted copy of the dictionary to extract entries
that have the same spelling as one of those entries, since such words
almost always have the same pronunciation.  If there were different
matches with the same spelling but different pronunciations, these
were flagged in the output file, so that I could edit them.  This
programme turned up 8,825 entries whose pronunciation could be
directly inferred from another entry.  The programme {\tt
putProns.nawk} put these expanded entries back into the dictionary.

Next I wrote a series of programmes to deal with suffixes that do not
shift stress.  Grepping the list of pronunciation-lacking words for
nouns ending in {\em -er}, I extracted 1,883 such words.  The
programme {\tt matchEr.nawk} (derived from {\tt matchSpell.nawk})
searched the dictionary for words matching the stem (e.g., {\em milk}
for {\em milker}), the stem plus {\em -e} (e.g., {\em love} for {\em
lover}), the stem with a final geminate consonant trimmed back (e.g.,
{\em step} for {\em stepper}), and the stem with final {\em -i}
replaced with {\em -y} (e.g., {\em carry} for {\em carrier}).  The
syllable /-xr/ was added to the pronunciations found in the
dictionary.  Again, multiple pronunciations were flagged, and the list
was edited then sifted back into the dictionary via {\tt
putProns.nawk}.  This covered 1,796 of the nominal {\em -er} words.
During this process it was learned that attention should also be
placed on the word class of the word sought in the dictionary (much
editing of multiple pronunciations could have been saved by accepting
only verbs), and on whether the found spelling would
derive to the affixed form (for example, there were many instances
where the programme wanted to derive words like {\em caner} from words
like {\em can}).  Such things were taken into consideration for the
follow-up programme {\tt match-all.nawk}, which could handle several
suffixes at once.  Derivation is blocked if the suffix starts with a
vowel, the dictionary spelling matches the derived word minus the
suffix, and that ends in a single vowel followed by a single consonant
(other than {\em h, j, q, v, w, x,} or {\em y}), and all the
pronunciations end in a short stressed vowel.  I also added the
possibility of giving multiple pronunciations for a suffix.  The
spelling rules were also systematised: {\em i/y} alternate except
before suffixes beginning with {\em i}; gemination and {\em -e}
dropping occur before suffixes that begin with vowels.  For Latinate
suffixes that can alternate with other suffixes without changing
stress, such as {\em -ism} and {\em -ist}, a mechanism was set up to
exploit such patterns, which are preferred to pure concatenation.
Subsequent iterations of {\tt match-all.nawk} handled cases of where
multiple suffixes were added to the same word.  After pronunciations
were generated for words which had a major class, a similar
programme, {\tt match-allNoPos.nawk}, did the same for words lacking
both pronunciation and major class; in this case, word class was
inferred from the suffix.

\begin{table}
\centering
\begin{tabular}{|l|l|l|l|} \hline
Suff. & Pronunciation & Classes & Alternates \\ \hline\hline
-able & /xbxl/ & adj $<$ vb  &\\   \hline
-ably & /xblE/ & adv $<$ vb & -able \\   \hline
-ac   & /ak/   & n $<$ n  &\\   \hline
-al & /xl/ & adj $<$ n,adj & -a \\   \hline
-ance & /xn(t)s/ & n $<$ v & \\   \hline
-ancy & /xnsE/ & n $<$ v  &\\   \hline
-ary & /erE/ & adj,n $<$ n & \\   \hline
-ate & /At/ & v $<$ n, adj & -ation \\   \hline
-atory & /xtOrE, xtorE/ & adj $<$ v & -ate \\   \hline
-dom & /dxm/ & n $<$ adj, n & \\   \hline
-ed & /d, t, xd/ & adj $<$ vb  & \\   \hline
-ee & /E/ & n $<$ v & \\   \hline
-en & /xn/ & adj, vb $<$ n, adj & \\   \hline
-ence & /xn(t)s/ & n $<$ vb  &\\   \hline
-ery & /(x)rE/ & n $<$ n, vb  &\\   \hline
-ful & /fxl/ & adj $<$ n & \\   \hline
-hood & /hud/ & n $<$ n, adj & \\   \hline
-ible & /xbxl/ & adj $<$ vb & \\   \hline
-ibly & /xblE/ & adv $<$ vb & -ible \\   \hline
-ic & /ik/ & adj, n $<$ n  &\\   \hline
-ing & /iN, in, xn/ & adj $<$ vb  & \\   \hline
-ish & /iS/ & adj $<$ adj, n & \\   \hline
-ism & /izxm/ & n $<$ n, adj & -ist \\   \hline
-ist & /xst/ & n,adj $<$ n,adj  & -ism \\   \hline
-ive & /iv/ & adj $<$ vb & \\   \hline
-ize & /Iz/ & vb $<$ n, adj  &\\   \hline
-less & /lxs/ & adj $<$ n & \\   \hline
-ly & /lE/ & adv $<$ adj. & \\   \hline
-ment &  /mxnt/ &  n $<$ vb.  &\\   \hline
-ness & /nxs/ & n $<$ adj & \\   \hline
-oid & /Yd/ & n, adj $<$ n  &\\   \hline
-or & /xr, o[x]r/ & n $<$ vb. & \\   \hline
-ous & /xs/ & adj $<$ n & \\   \hline
-ship & /Sip/ & n $<$ n & \\   \hline
-some & /sxm/ & adj, n $<$ n, vb, adj & \\   \hline
-ward & /wxrd/ & adj, adv $<$ n & \\   \hline
-wise & /wIz/ & adv $<$ n & \\   \hline
\end{tabular}

\caption{Suffixes used in predicting the pronunciation of derived words.}

\end{table}

After deriving as many pronunciations as possible, I ran a programme
called {\tt shortenProns.nawk} which converted some of the phoneme
codes in the SDC transcription to forms more suitable for manipulation
under Unix.  In particular, multiletter codes were reduced to
single-character codes, and special symbols like \& and * were changed
to alphabetic codes.  For the details about the codes, see section
2.1.1.

I also wrote a programme to add a column stating what inflected forms
a word could take {\tt (redClass.nawk).} These assignments were rather
generous, partly because I did not want to rule out rare but
permissible forms (such as the plurals of mass nouns), and partly
because I thought overgeneration would make it easier to catch
mistakes later: it is easier to spot a strange form like {\em
ferrouser} than to notice that one has never seen {\em redder}.  The
programme simply played off the major class found in Webster's.  Words
marked ``n'' were assumed to be able to take the full complement of
nominal inflexions, viz., plural, possessive singular, possessive
plural (coded {\em n}).  Words marked ``vb'', ``vi'' or ``vt'' (but
not ``va'', ``vp'' or ``vm'') were assumed to be able to take the full
complement of verbal inflexions, viz., third person present singular,
preterite = past participle, and present participle {\em (V).} Words
marked ``aj'' or ``av'' were marked as taking comparative and
superlative endings {\em (j)}, unless they were longer than two
syllables, or ended in {\em -ed, -ing} or {\em -ly.} (In retrospect,
that list of exclusions should have been longer; in particular, most
words with Latinate suffixes seem not to take such endings.)  All
other words were marked {\em 0.} Such codes are used by
subsequent programmes to generate inflections on the fly, without the
need to carry them in this base dictionary.  A few additional codes
were defined for the use of human editors, when it is observed that
illegal forms are generated: {\em s} means that the noun can take a
possessive singular, but no plural forms; {\em p} that a plural base
form can take a possessive plural; and {\em v} that a verb can
take the third person singular present ending and a present
participle, but no regular past form.

This concluded the one-shot programmes used to expand the Webster
dictionary file.  I should stress that no effort was made to
systematically check each entry for errors, and many remain, some of
which were introduced by these attempts to flesh out omitted
pronunciations and inflected forms.  Subsequent processing of the
dictionary was done in a fully automatic way by the programmes I will
describe next.  Since they have the property of sometimes deleting
information, I wanted to be able to focus all human editing on this
particular instantiation of the dictionary, which is called {\tt
dict}, so that corrections could also be used in other projects.  For
example, when automatic alignment would fail because the dictionary
had a mistranscribed pronunciation, then even though alignment was
operating on a derived form of {\tt dict}, I would go back and edit
{\tt dict}, then regenerate the derived dictionary.  A Unix {\tt
Makefile} made this process of regeneration fully automatic.

The first step in processing the dictionary is to apply {\tt remSup},
an executable compiled from an Awk programme.  This programme removes
words lacking pronunciations, pronunciations with non-English
phonemes, and spellings with accent marks.  It also inverts the
dictionary so that pronunciations come first, emphasizing the intended
ultimate use of the dictionary; entries with multiple pronunciations
now become multiple entries The pronunciations are also massaged.
Pronunciations with parentheses in them, enclosing optional
components, are expanded into all the alternatives expressed by that
notation.  Stress marks are shifted so that they immediately precede
the stressed vowel, making it easier to apply them to the one task
they are used for (seeing if a vowel is stressed in order to decide if
the final consonant should be doubled on adding a suffix).  Syllable
divisions are removed.  Stressed /x/, a symbol which in Webster covers
both unstressed schwa and the vowel in {\em sun}, is converted to /X/
so that the two may be distinguished after a later programme removes
accent marks.  Finally, syllabic consonants, marked in Webster by a
raised schwa, are remarked to have an ordinary schwa /x/.

Further processing is done by the C programme {\tt addInfl}.  Entries
marked with a non-zero inflectability code as discussed above under
{\tt redClass} are expanded into several entries, one for each
inflection.  Since this programme is the last module that needs word
stress information, stress marks are also removed.  In adding
inflectional affixes, care is taken to observe all the regular
spelling rules.  The details are in the file {\tt AddInfl.c}.  They
cover dropping of final {\em -e} before {\em -e;} also before {\em
-i,} unless the stem ends in {\em -ee, -oe} or {\em -ye;} changing {\em
-ie} to {\em -y-} before {\em -i;} inserting {\em -k-} after {\em -c}
before a front vowel; doubling final single consonant after a single
short vowel when adding a vocalic suffix; changing {\em -y} to {\em
-ie-} before {\em -s.} {\tt addInfl} also applies a few
morphophonological rules, such as restoring /g/ after /N/ when forming
comparatives and superlatives, and the choice of allomorphs when
adding {\tt -s} or {\tt -ed} after different phonemes.

The dictionary is then sorted by pronunciation, and redundant entries
are removed, using standard Unix utilities.  The result is stored as
{\tt oneDict}, which is the form used as the dictionary text file by
the {\tt correct} programme.

\subsection{Dictionary index}

The next task is to build the index file.  Because an index trie can
use large amounts of memory, this is not done all at once.  Rather,
the programme {\tt splitInv} first derives from {\tt oneDict} a set of
39 smaller dictionaries, one for each phoneme, and assigns the words
to a file, based on their initial.  For each of those text files, 
{\tt new-make-trie} then constructs a trie index.  This is in the same
format that {\tt correct} requires, but it would be inconvenient to have
to manipulate 39 index files.  Instead, the programme {\tt collapseDict}
joins the index files, making one large file.  The truly curious are
invited to look at the source files for further details.  The basic
idea is that {\tt new-make-trie} builds a trie in memory, then prints it out;
the only trick is that it prints all children before their parents, so that
the parents will know their children's location for use in continuation
pointers.  {\tt collapseDict} constructs a new master root node;
otherwise the tries for the subdictionaries are simply copied, adding to
the continuation and termination pointers an offset to account for the 
nodes and dictionary entries that were inserted before the subtrie.

\subsection{Sound-spelling correspondences}

A final task before constructing the spelling corrector is to determine
the sound-spelling correspondences.  Although some work has been done
on deriving these automatically \cite{Lucassen}, I preferred a semi-automated
(human-assisted) approach, as undertaken by Law\-rence and Kaye
\cite{Lawrence}.  A programme called {\tt align} used a list of {\tt rules}
to align the spellings and pronunciations in {\tt oneDict}.  The {\tt
rules} file was created by myself via successive refinement, as a
result of judging the alignments produced by previous iterations, with
particular attention given to the failures.  It was not of course
possible to check all 329,116 alignments, and many are no doubt
questionable, but by and large they appear adequate for this project.
The rules are essentially sound-spelling correspondences, but to
control somewhat their applicability, some rules add left or right
contexts to either the spelling or the pronunciation.  These contexts
are the immediately adjacent letters or phones required for a match,
and may include word boundaries and the symbols C or V (for any
consonant or vowel); but the contexts may be ignored if alignment
would otherwise fail entirely.  The applicability of rules can also be
controlled somewhat by ordering them: if two correspondences vary by
one being an initial segment of the other, and either would produce an
alignment, the first one listed will be used.  Alignment proceeds by a
recursive algorithm much like that described for {\tt Recur} in module
{\tt Respell}, except that the limiting factor is a particular
pronunciation (instead of the universe of legal words), and candidate
rules for any substring of the word are pursued in the order listed,
as just discussed, rather than in order of increasing length.

\begin{table}
\centering
\begin{verbatim}
aa      H       aardvark
aa      i       Isaac
aa      x       Isaac
aa      a       Aaronic
aa      A       Baal
aa      e       Aaronic
ae      A       ae
ae      E       aeolic
ae      I       thermae
ae      e       anaerobic
ae      x       anaerobe
ae      i       Aegean
ah      x       ephah
ah      H       ah
ah      o       shah
ah      a       bah
ah      A       brahma
s)ahi(b H       memsahib
aigh    A       laigh
ai      ax(r    altair
ai      a       questionnaire
ai      ex(r    airliner
ai      e       questionnaire
ai      Ax(l    airmailed
ai      A       aiblins
ai      x       Britain
ai      ux      buirdly
ai      Ix(l    faille
ai      Ix(r
ai      I       assai
ai      X       mohair
ail     I       serail
aille(# I       grisaille
aill(o  I       maillot
ais     Ix(l    aisle
ais(l   I       aisle
ait(#   A       distrait
aoh(#   O       Pharaoh
#)aou(d W       aoudad
ao      W       baobab
g)ao(l  A       gaol
\end{verbatim}

\caption{Extract from the rules file.}

\end{table}

After a file of alignments has been created, the programme {\tt
countAlignments} counts each sound-spelling correspondence to produce
a file which is called {\tt counts}.  This file is actually very much
like {\tt rules}, in that it lists all possible sound-spelling
correspondences.  The difference is that this file totally ignores
context and so is somewhat shorter (77 of the original 1130 rules
differed only in context or were not used), and it also contains a
count of how often each correspondence was used.  A programme called
{\tt genRuleTrie} takes this information and compiles it into C source
code for a static structure that embodies the information in trie form
for use by {\tt Respell.} This source is called {\tt RuleTrie.c} and
is a little byzantine, since it was necessary to express essentially
variable length structures (each spelling can have an indefinite
number of pronunciations) in fixed length arrays so that they could be
compiled into {\tt RuleTrie}, pre-initialized so that the {\tt correct}
programme can start up instantly.

At this point we can assemble the various component modules of {\tt correct}
and run the programme.

\begin{thebibliography}{Hutchinson 1956}

\bibitem[Aho 1987]{AWK}  Alfred V. Aho, et al.  {\em The AWK programming
language.}  Reading, Mass. : Addison-Wesley, 1987.

\bibitem[Alberga 1967]{Alberga} Cyril N. Alberga. 
``String similarity and misspellings'' in Communications of the ACM,
10, 5 (May 1967), 302-313.

\bibitem[Blair 1956]{Blair} Charles R. Blair. 
``A program for correcting spelling errors'' in Information and Control, 3
(Mar 1960), 60-67.

\bibitem[Celex 1988]{Celex} {\em Celex news.} Dec. 1988, newsletter no. 4.
-- Nijmegen : Centre for Lexical Information, University of Nijmegen. 

\bibitem[Damerau 1964]{Damerau}Fred J. Damerau. ``A technique for computer 
detection and correction of spelling errors'' in Communications of
the ACM, 7, 3 (March 1964), 171-176.

\bibitem[Francis 1982]{Brown} W. Nelson Francis and Henry Ku\v cera.
{\em Frequency analysis of English usage : lexicon and grammar.} 
Boston : Houghton Mifflin, 1982.

\bibitem[Fredkin 1960]{Fredkin} Edward Fredkin. 
``Trie memory'' in Communications of the ACM, 3 (1960), 490-499.

\bibitem[Gates 1937]{Gates}
Arthur Irving Gates.
{\em Spelling difficulties in 3867 words.}  New York : Teachers College,
Columbia University, 1937.

\bibitem[Hutchinson 1956]{Hutchinson} Lois Irene Hutchinson, {\em Standard
 handbook for secretaries}, 7th ed.  New York : McGraw-Hill, 1956.  p.
133-4.  Similarly in 8th ed., 1969.

\bibitem[Knuth 1973]{Knuth} Donald E. Knuth. {\em The art of computer
programming}.  Reading, Mass. : Addison-Wesley, 1973.

\bibitem[Lawrence 1986]{Lawrence} S. G. C. Lawrence and G. Kaye. 
``Alignment of phonemes with their corresponding orthography.''  In
Computer Speech and Language (1986) 1, 153-165.

\bibitem[Lucassen 1983]{Lucassen} J. M. Lucassen. 
``Discovering phonemic base forms automatically : an information
theoretical approach''.  IBM Research Report, RC 9833 (Feb 1983).

\bibitem[Masters 1927]{Masters} H. V. Masters. {\em A study of spelling
 errors.} Unpublished PhD thesis.  University of Iowa, 1927.

\bibitem[Pollock 1984]{Pollock} Joseph J. Pollock and Antonio Zamora.  
``Automatic spelling correction in scientific and scholarly text.''  In
Communications of the ACM, 27, 4 (Apr 1984), 358-68.

\bibitem[Sankoff 1983]{Kruskal} David Sankoff and Joseph B. Kruskal, ed.
{\em Time warps, string edits, and macromolecules : the theory and
practice of sequence comparison.} Reading, Mass. : Addison-Wesley, 1983.

\bibitem[SCRL 1973]{SCRL} Speech Communications Research Laboratory.  
{\em American English orthographic-phonemic dictionary.} 
Springfield, Va. : NTIS, 1973.  Air Force Office of Scientific
Research report AD-763 784.

\bibitem[Webster 1971]{Webster} 
{\em Webster's seventh new collegiate dictionary : based on Webster's
third new international dictionary.} Springfield : G. \& C.
Merriam, 1971.

\end{thebibliography}

\end{document}





