3.9.1 Segmentation in Chinese

We mentioned above that some languages, including Chinese, Japanese, and Thai, do not use spaces to mark potential word-boundaries. Alternative segmentation methods are used for these languages.

In Chinese, for example, words are composed of characters known as hanzi. Each character generally represents a single morpheme and is pronounceable as a single syllable. Words on average are about 2.4 characters long. A simple algorithm that does remarkably well for segmenting Chinese, and is often used as a baseline comparison for more advanced methods, is a version of greedy search called \textit{maximum matching} or sometimes \textit{maxmatch}. The algorithm requires a dictionary (wordlist) of the language.

The maximum matching algorithm starts by pointing at the beginning of a string. It chooses the longest word in the dictionary that matches the input at the current position. The pointer is then advanced past each character in that word. If no word matches, the pointer is instead advanced one character (creating a one-character word). The algorithm is then iteratively applied again starting from the new pointer position. To help visualize this algorithm, Palmer (2000) gives an English analogy, which approximates the Chinese situation by removing the spaces from the English sentence the table down there to produce the tabledownthere. The maximum match algorithm (given a long English dictionary) would first match the word $ \theta $ in the input, since that is the longest sequence of letters that matches a dictionary word. Starting from the end of $ \theta $, the longest matching dictionary word is $ \theta $ followed by the own and then there, producing the incorrect sequence $ \theta $ is the same word.

The algorithm seems to work better in Chinese (with such short words) than in languages like English with long words, as our failed example shows. Even in Chinese, however, maxmatch has a number of weakness, particularly with unknown words (words not in the dictionary) or unknown genres (genres which differ a lot from the assumptions made by the dictionary builder).

There is an annual competition (technically called a bakeoff) for Chinese segmentation algorithms. These most successful modern algorithms for Chinese word segmentation are based on machine learning from hand-segmented training sets. We will return to these algorithms after we introduce probabilistic methods in Ch. 5.

3.10 DETECTING AND CORRECTING SPELLING ERRORS

ALGERNON: But my own sweet Cecily, I have never written you any letters.

CECILY: You need hardly remind me of that, Ernest. I remember only too well that I was forced to write your letters for you. I wrote always three times a week, and sometimes oftener.

ALGERNON: Oh, do let me read them, Cecily?

CECILY: Oh, I couldn't possibly. They would make you far too conceited. The three you wrote me after I had broken off the engagement are so beautiful, and so badly spelled, that even now I can hardly read them without crying a little.

Oscar Wilde, The Importance of being Earnest

Like Oscar Wilde's fabulous Cecily, a lot of people were thinking about spelling during the last turn of the century. Gilbert and Sullivan provide many examples. The Gondoliers' Giuseppe, for example, worries that his private secretary is "shaky in his spelling" while Iolanthe's Phyllis can "spell every word that she uses". Thorstein Veblen's explanation (in his 1899 classic The Theory of the Leisure Class) was that a main purpose of the "archaic, cumbrous, and ineffective" English spelling system was to be difficult enough to provide a test of membership in the leisure class. Whatever the social role of spelling, we can certainly agree that many more of us are like Cecily than like Phyllis. Estimates for the frequency of spelling errors in human typed text vary from 0.05% of the words in carefully edited newswire text to 38% in difficult applications like telephone directory lookup (Kukich, 1992).

In this section we introduce the problem of detecting and correcting spelling errors. Since the standard algorithm for spelling error correction is probabilistic, we will continue our spell-checking discussion later in Ch. 5 after we define the probabilistic noisy channel model.

The detection and correction of spelling errors is an integral part of modern word-processors and search engines, and is also important in correcting errors in optical character recognition (OCR), the automatic recognition of machine or hand-printed characters, and on-line handwriting recognition, the recognition of human printed or cursive handwriting as the user is writing.

Following Kukich (1992), we can distinguish three increasingly broader problems:

1. non-word error detection: detecting spelling errors that result in non-words (like graffe for giraffe).

2. isolated-word error correction: correcting spelling errors that result in nonwords, for example correcting graffe to giraffe, but looking only at the word in isolation.

3. context-dependent error detection and correction: using the context to help detect and correct spelling errors even if they accidentally result in an actual word of English (real-word errors). This can happen from typographical errors (insertion, deletion, transposition) which accidentally produce a real word (e.g., there for three), or because the writer substituted the wrong spelling of a

homophone or near-homophone (e.g., dessert for desert, or piece for peace).

Detecting non-word errors is generally done by marking any word that is not found in a dictionary. For example, the misspelling graffe above would not occur in a dictionary. Some early research (Peterson, 1986) had suggested that such spelling dictionaries would need to be kept small, because large dictionaries contain very rare words that resemble misspellings of other words. For example the rare words wont or veery are also common misspelling of won't and very. In practice, Damerau and Mays (1989) found that while some misspellings were hidden by real words in a larger dictionary, the larger dictionary proved more help than harm by avoiding marking rare words as errors. This is especially true with probabilistic spell-correction algorithms that can use word frequency as a factor. Thus modern spell-checking systems tend to be based on large dictionaries.

The finite-state morphological parsers described throughout this chapter provide a technology for implementing such large dictionaries. By giving a morphological parser for a word, an FST parser is inherently a word recognizer. Indeed, an FST morphological parser can be turned into an even more efficient FSA word recognizer by using the projection operation to extract the lower-side language graph. Such FST dictionaries also have the advantage of representing productive morphology like the English -s and -ed inflections. This is important for dealing with new legitimate combinations of stems and inflection. For example, a new stem can be easily added to the dictionary, and then all the inflected forms are easily recognized. This makes FST dictionaries especially powerful for spell-checking in morphologically rich languages where a single stem can have tens or hundreds of possible surface forms.⁵

FST dictionaries can thus help with non-word error detection. But how about error correction? Algorithms for isolated-word error correction operate by finding words which are the likely source of the errorful form. For example, correcting the spelling error graffe requires searching through all possible words like giraffe, graff, craft, grail, etc, to pick the most likely source. To choose among these potential sources we need a distance metric between the source and the surface error. Intuitively, giraffe is a more likely source than grail for graffe, because giraffe is closer in spelling to graffe than grail is to graffe. The most powerful way to capture this similarity intuition requires the use of probability theory and will be discussed in Ch. 4. The algorithm underlying this solution, however, is the non-probabilistic minimum edit distance algorithm that we introduce in the next section.

3.11 MINIMUM EDIT DISTANCE

Deciding which of two words is closer to some third word in spelling is a special case of the general problem of string distance. The distance between two strings is a measure of how alike two strings are to each other.

Many important algorithms for finding string distance rely on some version of the minimum edit distance algorithm, named by Wagner and Fischer (1974) but independently discovered by many people; see the History section of Ch. 6 for a discussion of the history of these algorithms. The minimum edit distance between two strings is the minimum number of editing operations (insertion, deletion, substitution) needed to transform one string into another. For example the gap between the words intention and execution is five operations, shown in Fig. 3.23 as an alignment between the two strings. Given two sequences, an alignment is a correspondence between substrings of the two sequences. Thus I aligns with the empty string, N with E, T with X, and so on. Beneath the aligned strings is another representation; a series of symbols expressing an operation list for converting the top string into the bottom string; d for deletion, s for substitution, i for insertion.

We can also assign a particular cost or weight to each of these operations. The Levenshtein distance between two sequences is the simplest weighting factor in which each of the three operations has a cost of 1 (Levenshtein, 1966). $ ^6 $ Thus the Levenshtein distance between intention and execution is 5. Levenshtein also proposed an alternate version of his metric in which each insertion or deletion has a cost of one, and substitutions are not allowed (equivalent to allowing substitution, but giving each substitution a cost of 2, since any substitution can be represented by one insertion and one deletion). Using this version, the Levenshtein distance between intention and execution is 8.

The minimum edit distance is computed by dynamic programming. Dynamic programming is the name for a class of algorithms, first introduced by Bellman (1957), that apply a table-driven method to solve problems by combining solutions to subproblems. This class of algorithms includes the most commonly-used algorithms in speech and language processing; besides minimum edit distance, these include the Viterbi and forward algorithms (Ch. 6), and the CYK and Earley algorithm (Ch. 13).

The intuition of a dynamic programming problem is that a large problem can be solved by properly combining the solutions to various subproblems. For example, consider the sequence or “path” of transformed words that comprise the minimum edit distance between the strings intention and execution shown in Fig. 3.24.

Imagine some string (perhaps it is exention) that is in this optimal path (whatever it is). The intuition of dynamic programming is that if exention is in the optimal

| delete i $ \rightarrow $ | i $ \uparrow $ | t $ \uparrow $ | e $ \uparrow $ | t $ \uparrow $ | i $ \uparrow $ | o $ \downarrow $ |

| --- | --- | --- | --- | --- | --- | --- |

| substitute n by e $ \rightarrow $ | n $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | t $ \uparrow $ | i $ \downarrow $ |

| substitute t by x $ \rightarrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | t $ \uparrow $ | i $ \downarrow $ |

| insert u $ \rightarrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | n $ \downarrow $ |

| substitute n by c $ \rightarrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | u $ \uparrow $ |

| | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | u $ \downarrow $ |

| | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \uparrow $ | e $ \ | |

operation-list, then the optimal sequence must also include the optimal path from intention to exention. Why? If there were a shorter path from intention to exention then we could use it instead, resulting in a shorter overall path, and the optimal sequence wouldn't be optimal, thus leading to a contradiction.

Dynamic programming algorithms for sequence comparison work by creating a distance matrix with one column for each symbol in the target sequence and one row for each symbol in the source sequence (i.e., target along the bottom, source along the side). For minimum edit distance, this matrix is the edit-distance matrix. Each cell edit-distance $ [i,j] $ contains the distance between the first i characters of the target and the first j characters of the source. Each cell can be computed as a simple function of the surrounding cells; thus starting from the beginning of the matrix it is possible to fill in every entry. The value in each cell is computed by taking the minimum of the three possible paths through the matrix which arrive there:

$$ distance[i,j]=\min\left\{\begin{array}{l}distance[i-1,j]+ins-cost(target_{i-1})\\ distance[i-1,j-1]+subst-cost(source_{j-1},target_{i-1})\\ distance[i,j-1]+del-cost(source_{j-1})\end{array}\right. $$

The algorithm itself is summarized in Fig. 3.25, while Fig. 3.26 shows the results of applying the algorithm to the distance between intention and execution assuming the version of Levenshtein distance in which the insertions and deletions each have a cost of 1 (ins-cost( $ \cdot $) = del-cost( $ \cdot $) = 1), and substitutions have a cost of 2 (except substitution of identical letters has zero cost).

Knowing the minimum edit distance is useful for algorithms like finding potential spelling error corrections. But the edit distance algorithm is important in another way; with a small change, it can also provide the minimum cost alignment between two strings. Aligning two strings is useful throughout speech and language processing. In speech recognition, minimum edit distance alignment is used to compute word error rate in speech recognition (Ch. 9). Alignment plays a role in machine translation, in which sentences in a parallel corpus (a corpus with a text in two languages) need to be matched up to each other.

In order to extend the edit distance algorithm to produce an alignment, we can start by visualizing an alignment as a path through the edit distance matrix. Fig. 3.27 shows

function MIN-EDIT-DISTANCE(target, source) returns min-distance

n←LENGTH(target)

m←LENGTH(source)

Create a distance matrix distance[n+1,m+1]

Initialize the zeroth row and column to be the distance from the empty string

distance[0,0]=0

for each column i from 1 to n do

distance[i,0]←distance[i-1,0]+ins-cost(target[i])

for each row j from 1 to m do

distance[0,j]←distance[0,j-1]+del-cost(source[j])

for each column i from 1 to n do

for each row j from 1 to m do

distance[i,j]←MIN(distance[i-1,j]+ins-cost(target_{i-1}),

distance[i-1,j-1]+subst-cost(source_{j-1},target_{i-1}),

distance[i,j-1]+del-cost(source_{j-1}))

return distance[n,m]

this path with the boldfaced cell. Each boldfaced cell represents an alignment of a pair of letters in the two strings. If two boldfaced cells occur in the same row, there will be an insertion in going from the source to the target; two boldfaced cells in the same column indicates a deletion.

Fig. 3.27 also shows the intuition of how to compute this alignment path. The com-

putation proceeds in two steps. In the first step, we augment the minimum edit distance algorithm to store backpointers in each cell. The backpointer from a cell points to the previous cell (or cells) that were extended from in entering the current cell. We've shown a schematic of these backpointers in Fig. 3.27, after a similar diagram in Gusfield (1997). Some cells have multiple backpointers, because the minimum extension could have come from multiple previous cells. In the second step, we perform a backtrace. In a backtrace, we start from the last cell (at the final row and column), and follow the pointers back through the dynamic programming matrix. Each complete path between the final cell and the initial cell is a minimum distance alignment. Exercise 3.12 asks you to modify the minimum edit distance algorithm to store the pointers and compute the backtrace to output an alignment.

There are various publicly available packages to compute edit distance, including UNIX diff, and the NIST sclite program (NIST, 2005); Minimum edit distance can also be augmented in various ways. The Viterbi algorithm, for example, is an extension of minimum edit distance which uses probabilistic definitions of the operations. In this case instead of computing the “minimum edit distance” between two strings, we are interested in the “maximum probability alignment” of one string with another. The Viterbi algorithm is crucial in probabilistic tasks like speech recognition and part-of-speech tagging.

3.12 HUMAN MORPHOLOGICAL PROCESSING

In this section we briefly survey psycholinguistic studies on how multi-morphemic words are represented in the minds of speakers of English. For example, consider the word walk and its inflected forms walks, and walked. Are all three in the human lexicon? Or merely walk along with -ed and -s? How about the word happy and its derived

forms happily and happiness? We can imagine two ends of a theoretical spectrum of representations. The full listing hypothesis proposes that all words of a language are listed in the mental lexicon without any internal morphological structure. On this view, morphological structure is simply an epiphenomenon, and walk, walks, walked, happy, and happily are all separately listed in the lexicon. This hypothesis is certainly untenable for morphologically complex languages like Turkish. The minimum redundancy hypothesis suggests that only the constituent morphemes are represented in the lexicon, and when processing walks, (whether for reading, listening, or talking) we must access both morphemes (walk and -s) and combine them.

Some of the earliest evidence that the human lexicon represents at least some morphological structure comes from speech errors, also called slips of the tongue. In conversational speech, speakers often mix up the order of the words or sounds:

if you $ \underline{break} $ it it'll $ \underline{drop} $

In slips of the tongue collected by Fromkin and Ratner (1998) and Garrett (1975), inflectional and derivational affixes can appear separately from their stems. The ability of these affixes to be produced separately from their stem suggests that the mental lexicon contains some representation of morphological structure.

it's not only us who have screw $ \underline{\text{looses}} $ (for "screws loose")

word $ \underline{s} $ of rule formation (for "rules of word formation")

easy enough $ \underline{ly} $ (for "easily enough")

More recent experimental evidence suggests that neither the full listing nor the minimum redundancy hypotheses may be completely true. Instead, it's possible that some but not all morphological relationships are mentally represented. Stanners et al. (1979), for example, found that some derived forms (happiness, happily) seem to be stored separately from their stem (happy), but that regularly inflected forms (pouring) are not distinct in the lexicon from their stems (pour). They did this by using a repetition priming experiment. In short, repetition priming takes advantage of the fact that a word is recognized faster if it has been seen before (if it is primed). They found that lifting primed lift, and burned primed burn, but for example selective didn't prime select. Marslen-Wilson et al. (1994) found that spoken derived words can prime their stems, but only if the meaning of the derived form is closely related to the stem. For example, government primes govern, but department does not prime depart. Marslen-Wilson et al. (1994) represent a model compatible with their own findings as follows:

In summary, these early results suggest that (at least) productive morphology like inflection does play an online role in the human lexicon. More recent studies have

shown effects of non-inflectional morphological structure on word reading time as well, such as the morphological family size. The morphological family size of a word is the number of other multimorphemic words and compounds in which it appears; the family for fear, for example, includes fearful, fearfully, fearfulness, fearless, fearlessly, fearlessness, fearsome, and godfearing (according to the CELEX database), for a total size of 9. Baayen and colleagues (Baayen et al., 1997; De Jong et al., 2002; Moscoso del Prado Martín et al., 2004) have shown that words with a larger morphological family size are recognized faster. Recent work has further shown that word recognition speed is effected by the total amount of information (or entropy) contained by the morphological paradigm (Moscoso del Prado Martín et al., 2004); entropy will be introduced in the next chapter.

3.13 SUMMARY

This chapter introduced morphology, the arena of language processing dealing with the subparts of words, and the finite-state transducer, the computational device that is important for morphology but will also play a role in many other tasks in later chapters. We also introduced stemming, word and sentence tokenization, and spelling error detection.

Here's a summary of the main points we covered about these ideas:

Morphological parsing is the process of finding the constituent morphemes in a word (e.g., cat +N +PL for cats).

• English mainly uses prefixes and suffixes to express inflectional and derivational morphology.

• English inflectional morphology is relatively simple and includes person and number agreement (-s) and tense markings (-ed and -ing).

• English derivational morphology is more complex and includes suffixes like -ation, -ness, -able as well as prefixes like co- and re-.

• Many constraints on the English morphotactics (allowable morpheme sequences) can be represented by finite automata.

• Finite-state transducers are an extension of finite-state automata that can generate output symbols.

• Important operations for FSTs include composition, projection, and intersection.

• Finite-state morphology and two-level morphology are applications of finite-state transducers to morphological representation and parsing.

• Spelling rules can be implemented as transducers.

There are automatic transducer-compilers that can produce a transducer for any simple rewrite rule.

• The lexicon and spelling rules can be combined by composing and intersecting various transducers.

• The Porter algorithm is a simple and efficient way to do stemming, stripping off affixes. It is not as accurate as a transducer model that includes a lexicon,

but may be preferable for applications like information retrieval in which exact morphological structure is not needed.

• Word tokenization can be done by simple regular expressions substitutions or by transducers.

• Spelling error detection is normally done by finding words which are not in a dictionary; an FST dictionary can be useful for this.

• The minimum edit distance between two strings is the minimum number of operations it takes to edit one into the other. Minimum edit distance can be computed by dynamic programming, which also results in an alignment of the two strings.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Despite the close mathematical similarity of finite-state transducers to finite-state automata, the two models grew out of somewhat different traditions. Ch. 2 described how the finite automaton grew out of Turing's (1936) model of algorithmic computation, and McCulloch and Pitts finite-state-like models of the neuron. The influence of the Turing machine on the transducer was somewhat more indirect. Huffman (1954) proposed what was essentially a state-transition table to model the behavior of sequential circuits, based on the work of Shannon (1938) on an algebraic model of relay circuits. Based on Turing and Shannon's work, and unaware of Huffman's work, Moore (1956) introduced the term finite automaton for a machine with a finite number of states with an alphabet of input symbols and an alphabet of output symbols. Mealy (1955) extended and synthesized the work of Moore and Huffman.

The finite automata in Moore’s original paper, and the extension by Mealy differed in an important way. In a Mealy machine, the input/output symbols are associated with the transitions between states. In a Moore machine, the input/output symbols are associated with the state. The two types of transducers are equivalent; any Moore machine can be converted into an equivalent Mealy machine and vice versa. Further early work on finite-state transducers, sequential transducers, and so on, was conducted by Salomaa (1973), Schützenberger (1977).

Early algorithms for morphological parsing used either the bottom-up or top-down methods that we will discuss when we turn to parsing in Ch. 13. An early bottom-up affix-stripping approach as Packard's (1973) parser for ancient Greek which iteratively stripped prefixes and suffixes off the input word, making note of them, and then looked up the remainder in a lexicon. It returned any root that was compatible with the stripped-off affixes. AMPLE (A Morphological Parser for Linguistic Exploration) (Weber and Mann, 1981; Weber et al., 1988; Hankamer and Black, 1991) is another early bottom-up morphological parser. Hankamer's (1986) keCi is an early top-down generate-and-test or analysis-by-synthesis morphological parser for Turkish which is guided by a finite-state representation of Turkish morphemes. The program begins with a morpheme that might match the left edge of the word, and applies every possible phonological rule to it, checking each result against the input. If one of the outputs

succeeds, the program then follows the finite-state morphotactics to the next morpheme and tries to continue matching the input.

The idea of modeling spelling rules as finite-state transducers is really based on Johnson's (1972) early idea that phonological rules (to be discussed in Ch. 7) have finite-state properties. Johnson's insight unfortunately did not attract the attention of the community, and was independently discovered by Ronald Kaplan and Martin Kay, first in an unpublished talk (Kaplan and Kay, 1981) and then finally in print (Kaplan and Kay, 1994) (see page ?? for a discussion of multiple independent discoveries). Kaplan and Kay's work was followed up and most fully worked out by Koskenniemi (1983), who described finite-state morphological rules for Finnish. Karttunen (1983) built a program called KIMMO based on Koskenniemi's models. Antworth (1990) gives many details of two-level morphology and its application to English. Besides Koskenniemi's work on Finnish and that of Antworth (1990) on English, two-level or other finite-state models of morphology have been worked out for many languages, such as Turkish (Oflazer, 1993) and Arabic (Beesley, 1996). Barton et al. (1987) bring up some computational complexity problems with two-level models, which are responded to by Koskenniemi and Church (1988). Readers with further interest in finite-state morphology should turn to Beesley and Karttunen (2003). Readers with further interest in computational models of Arabic and Semitic morphology should see Smrz (1998), Kiraz (2001), Habash et al. (2005).

A number of practical implementations of sentence segmentation were available by the 1990s. Summaries of sentence segmentation history and various algorithms can be found in Palmer (2000), Grefenstette (1999), and Mikheev (2003). Word segmentation has been studied especially in Japanese and Chinese. While the max-match algorithm we describe is very commonly used as a baseline, or when a simple but accurate algorithm is required, more recent algorithms rely on stochastic and machine learning algorithms; see for example such algorithms as Sproat et al. (1996), Xue and Shen (2003), and Tseng et al. (2005).

Gusfield (1997) is an excellent book covering everything you could want to know about string distance, minimum edit distance, and related areas.

Students interested in further details of the fundamental mathematics of automata theory should see Hopcroft and Ullman (1979) or Lewis and Papadimitriou (1988). Roche and Schabes (1997) is the definitive mathematical introduction to finite-state transducers for language applications, and together with Mohri (1997) and Mohri (2000) give many useful algorithms such as those for transducer minimization and determination.

The CELEX dictionary is an extremely useful database for morphological analysis, containing full morphological parses of a large lexicon of English, German, and Dutch (Baayen et al., 1995).

Roark and Sproat (2007) is a general introduction to computational issues in morphology and syntax. Sproat (1993) is an older general introduction to computational morphology.

EXERCISES

3.1 Give examples of each of the noun and verb classes in Fig. 3.6, and find some exceptions to the rules.

3.2 Extend the transducer in Fig. 3.17 to deal with sh and ch.

3.3 Write a transducer(s) for the K insertion spelling rule in English.

3.4 Write a transducer(s) for the consonant doubling spelling rule in English.

3.5 The Soundex algorithm (Odell and Russell, 1922; Knuth, 1973) is a method commonly used in libraries and older Census records for representing people's names. It has the advantage that versions of the names that are slightly misspelled or otherwise modified (common, for example, in hand-written census records) will still have the same representation as correctly-spelled names. (e.g., Jurafsky, Jarofsky, Jarovsky, and Jarovski all map to J612).

a. Keep the first letter of the name, and drop all occurrences of non-initial a, e, h, i, o, u, w, y

b. Replace the remaining letters with the following numbers:

b, f, p, v $ \rightarrow $ 1

c, g, j, k, q, s, x, z $ \rightarrow $ 2

d, t $ \rightarrow $ 3

l $ \rightarrow $ 4

m, n $ \rightarrow $ 5

r $ \rightarrow $ 6

c. Replace any sequences of identical numbers, only if they derive from two or more letters that were adjacent in the original name, with a single number (i.e., $ 666 \rightarrow 6 $).

d. Convert to the form Letter Digit Digit Digit by dropping digits past the third (if necessary) or padding with trailing zeros (if necessary).

The exercise: write a FST to implement the Soundex algorithm.

3.6 Implement one of the steps of the Porter Stemmer as a transducer.

3.7 Write the algorithm for parsing a finite-state transducer, using the pseudo-code introduced in Chapter 2. You should do this by modifying the algorithm ND-RECOGNIZE in Fig. ?? in Chapter 2.

3.8 Write a program that takes a word and, using an on-line dictionary, computes possible anagrams of the word, each of which is a legal word.

3.9 In Fig. 3.17, why is there a z, s, x arc from q5 to q1?

3.10 Computing minimum edit distances by hand, figure out whether drive is closer to brief or to divers, and what the edit distance is. You may use any version of distance that you like.

3.11 Now implement a minimum edit distance algorithm and use your hand-computed results to check your code.

3.12 Augment the minimum edit distance algorithm to output an alignment; you will need to store pointers and add a stage to compute the backtrace.

Antworth, E. L. (1990). PC-KIMMO: A Two-level Processor for Morphological Analysis. Summer Institute of Linguistics, Dallas, TX.

Baayen, R. H., Piepenbrock, R., and Gulikers, L. (1995). The CELEX Lexical Database (Release 2) [CD-ROM]. Linguistic Data Consortium, University of Pennsylvania [Distributor], Philadelphia, PA.

Baayen, R. H., Lieber, R., and Schreuder, R. (1997). The morphological complexity of simplex nouns. Linguistics, 35(5), 861–877.

Barton, Jr., G. E., Berwick, R. C., and Ristad, E. S. (1987). Computational Complexity and Natural Language. MIT Press.

Bauer, L. (1983). English word-formation. Cambridge University Press.

Beesley, K. R. (1996). Arabic finite-state morphological analysis and generation. In COLING-96, Copenhagen, pp. 89–94.

Beesley, K. R. and Karttunen, L. (2003). Finite-State Morphology. CSLI Publications, Stanford University.

Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.

Chomsky, N. and Halle, M. (1968). The Sound Pattern of English. Harper and Row.

Damerau, F. J. and Mays, E. (1989). An examination of undetected typing errors. Information Processing and Management, 25(6), 659–664.

De Jong, N. H., Feldman, L. B., Schreuder, R., Pastizzo, M., and Baayen, R. H. (2002). The processing and representation of Dutch and English compounds: Peripheral morphological, and central orthographic effects. Brain and Language, 81, 555–567.

Fromkin, V. and Ratner, N. B. (1998). Speech production. In Gleason, J. B. and Ratner, N. B. (Eds.), Psycholinguistics. Harcourt Brace, Fort Worth, TX.

Garrett, M. F. (1975). The analysis of sentence production. In Bower, G. H. (Ed.), The Psychology of Learning and Motivation, Vol. 9. Academic.

Grefenstette, G. (1999). Tokenization. In van Halteren, H. (Ed.), Syntactic Wordclass Tagging. Kluwer.

Gusfield, D. (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press.

Habash, N., Rambow, O., and Kiraz, G. A. (2005). Morphological analysis and generation for arabic dialects. In ACL Workshop on Computational Approaches to Semitic Languages, pp. 17–24.

Hankamer, J. (1986). Finite state morphology and left to right phonology. In Proceedings of the Fifth West Coast Conference on Formal Linguistics, pp. 29–34.

Hankamer, J. and Black, H. A. (1991). Current approaches to computational morphology. Unpublished manuscript.

Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA.

Huffman, D. A. (1954). The synthesis of sequential switching circuits. Journal of the Franklin Institute, 3, 161–191. Continued in Volume 4.

Johnson, C. D. (1972). Formal Aspects of Phonological Description. Mouton, The Hague. Monographs on Linguistic Analysis No. 3.

Kaplan, R. M. and Kay, M. (1981). Phonological rules and finite-state transducers. Paper presented at the Annual meeting of the Linguistics Society of America. New York.

Kaplan, R. M. and Kay, M. (1994). Regular models of phonological rule systems. Computational Linguistics, 20(3), 331–378.

Karttunen, L., Chanod, J., Grefenstette, G., and Schiller, A. (1996). Regular expressions for language engineering. Natural Language Engineering, 2(4), 305–238.

Karttunen, L. (1983). KIMMO: A general morphological processor. In Texas Linguistics Forum 22, pp. 165–186.

Kiraz, G. A. (2001). Computational Nonlinear Morphology with Emphasis on Semitic Languages. Cambridge University Press.

Knuth, D. E. (1973). Sorting and Searching: The Art of Computer Programming Volume 3. Addison-Wesley, Reading, MA.

Koskenniemi, K. (1983). Two-level morphology: A general computational model of word-form recognition and production. Tech. rep. Publication No. 11, Department of General Linguistics, University of Helsinki.

Koskenniemi, K. and Church, K. W. (1988). Complexity, two-level morphology, and Finnish. In COLING-88, Budapest, pp. 335–339.

Krovetz, R. (1993). Viewing morphology as an inference process. In SIGIR-93, pp. 191–202. ACM.

Kruskal, J. B. (1983). An overview of sequence comparison. In Sankoff, D. and Kruskal, J. B. (Eds.), Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, pp. 1–44. Addison-Wesley, Reading, MA.

Kukich, K. (1992). Techniques for automatically correcting words in text. ACM Computing Surveys, 24(4), 377–439.

Lerner, A. J. (1978). The Street Where I Live. Da Capo Press, New York.

Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Cybernetics and Control Theory, 10(8), 707–710. Original in Doklady Akademii Nauk SSSR 163(4): 845–848 (1965).

Lewis, H. and Papadimitriou, C. (1988). Elements of the Theory of Computation. Prentice-Hall. Second edition.

Marslen-Wilson, W., Tyler, L. K., Waksler, R., and Older, L. (1994). Morphology and meaning in the English mental lexicon. Psychological Review, 101(1), 3–33.

McCawley, J. D. (1978). Where you can shove infixes. In Bell, A. and Hooper, J. B. (Eds.), Syllables and Segments, pp. 213–221. North-Holland, Amsterdam.

Mealy, G. H. (1955). A method for synthesizing sequential circuits. Bell System Technical Journal, 34(5), 1045–1079.

Mikheev, A. (2003). Text segmentation. In Mitkov, R. (Ed.), Oxford Handbook of Computational Linguistics. Oxford University Press, Oxford.

Mohri, M. (1996). On some applications of finite-state automata theory to natural language processing. Natural Language Engineering, 2(1), 61–80.

Mohri, M. (1997). Finite-state transducers in language and speech processing. Computational Linguistics, 23(2), 269–312.

Mohri, M. (2000). Minimization algorithms for sequential transducers. Theoretical Computer Science, 234, 177–201.

Moore, E. F. (1956). Gedanken-experiments on sequential machines. In Shannon, C. and McCarthy, J. (Eds.), Automata Studies, pp. 129–153. Princeton University Press, Princeton, NJ.

Moscoso del Prado Martín, F., Bertram, R., Häikiö, T., Schreuder, R., and Baayen, R. H. (2004). Morphological family size in a morphologically rich language: The case of Finnish compared to Dutch and Hebrew. Journal of Experimental Psychology: Learning, Memory, and Cognition, 30, 1271–1278.

NIST (2005). Speech recognition scoring toolkit (sctk) version 2.1. Available at http://www.nist.gov/speech/tools/.

Odell, M. K. and Russell, R. C. (1918/1922). U.S. Patents 1261167 (1918), 1435663 (1922)†. Cited in Knuth (1973).

Oflazer, K. (1993). Two-level description of Turkish morphology. In Proceedings, Sixth Conference of the European Chapter of the ACL.

Packard, D. W. (1973). Computer-assisted morphological analysis of ancient Greek. In Zampolli, A. and Calzolari, N. (Eds.), Computational and Mathematical Linguistics: Proceedings of the International Conference on Computational Linguistics, Pisa, pp. 343–355. Leo S. Olschki.

Palmer, D. D. (2000). Tokenisation and sentence segmentation. In Dale, R., Somers, H. L., and Moisl, H. (Eds.), Handbook of Natural Language Processing. Marcel Dekker.

Peterson, J. L. (1986). A note on undetected typing errors. Communications of the ACM, 29(7), 633–637.

Porter, M. F. (1980). An algorithm for suffix stripping. Program, 14(3), 130–127.

Quirk, R., Greenbaum, S., Leech, G., and Svartvik, J. (1985). A Comprehensive Grammar of the English Language. Longman, London.

Roark, B. and Sproat, R. (2007). Computational Approaches to Morphology and Syntax. Oxford University Press.

Roche, E. and Schabes, Y. (1997). Introduction. In Roche, E. and Schabes, Y. (Eds.), Finite-State Language Processing, pp. 1–65. MIT Press.

Salomaa, A. (1973). Formal Languages. Academic.

Schützenberger, M. P. (1977). Sur une variante des fonctions sequentielles. Theoretical Computer Science, 4, 47–57.

Seuss, D. (1960). One Fish Two Fish Red Fish Blue Fish. Random House, New York.

Shannon, C. E. (1938). A symbolic analysis of relay and switching circuits. Transactions of the American Institute of Electrical Engineers, 57, 713–723.

Smrž, O. (1998). Functional Arabic Morphology. Ph.D. thesis, Charles University in Prague.

Sproat, R. (1993). Morphology and Computation. MIT Press.

Sproat, R., Shih, C., Gale, W. A., and Chang, N. (1996). A stochastic finite-state word-segmentation algorithm for Chinese. Computational Linguistics, 22(3), 377–404.

Stanners, R. F., Neiser, J., Hernon, W. P., and Hall, R. (1979). Memory representation for morphologically related words. Journal of Verbal Learning and Verbal Behavior, 18, 399–412.

Tseng, H., Chang, P., Andrew, G., Jurafsky, D., and Manning, C. D. (2005). Conditional random field word segmenter. In Proceedings of the Fourth SIGHAN Workshop on Chinese Language Processing.

Veblen, T. (1899). Theory of the Leisure Class. Macmillan Company, New York.

Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. Journal of the Association for Computing Machinery, 21, 168–173.

Weber, D. J., Black, H. A., and McConnell, S. R. (1988). AMPLE: A tool for exploring morphology. Tech. rep. Occasional Publications in Academic Computing No. 12, Summer Institute of Linguistics, Dallas.

Weber, D. J. and Mann, W. C. (1981). Prospects for computer-assisted dialect adaptation. American Journal of Computational Linguistics, 7, 165–177. Abridged from Summer Institute of Linguistics Notes on Linguistics Special Publication 1, 1979.

Xue, N. and Shen, L. (2003). Chinese word segmentation as lmr tagging. In Proceedings of the 2nd SIGHAN Workshop on Chinese Language Processing, Sapporo, Japan.

Speech and Language Processing: An introduction to speech recognition, computational linguistics and natural language processing. Daniel Jurafsky & James H. Martin. Copyright © 2007, All rights reserved. Draft of October 7, 2007. Do not cite without permission.

4

N-GRAMS

But it must be recognized that the notion “probability of a sentence” is an entirely useless one, under any known interpretation of this term.

Noam Chomsky (1969, p. 57)

Anytime a linguist leaves the group the recognition rate goes up.

Fred Jelinek (then of the IBM speech group) (1988) $ ^{1} $

Being able to predict the future is not always a good thing. Cassandra of Troy had the gift of fore-seeing, but was cursed by Apollo that her predictions would never be believed. Her warnings of the destruction of Troy were ignored and to simplify, let's just say that things just didn't go well for her later.

Predicting words seems somewhat less fraught, and in this chapter we take up this idea of word prediction. What word, for example, is likely to follow:

Please turn your homework ...

WORD PREDICTION N-GRAM MODELS LANGUAGE MODELS

Hopefully most of you concluded that a very likely word is in, or possibly over, but probably not the. We formalize this idea of word prediction with probabilistic models called N-gram models, which predict the next word from the previous N-1 words. Such statistical models of word sequences are also called language models or LMs. Computing the probability of the next word will turn out to be closely related to computing the probability of a sequence of words. The following sequence, for example, has a non-zero probability of appearing in a text:

...all of a sudden I notice three guys standing on the sidewalk...

while this same set of words in a different order has a very low probability:

on guys all I of notice sidewalk three a sudden standing the

As we will see, estimators like N-grams that assign a conditional probability to possible next words can be used to assign a joint probability to an entire sentence. Whether estimating probabilities of next words or of whole sequences, the N-gram model is one of the most important tools in speech and language processing.

N-grams are essential in any task in which we have to identify words in noisy, ambiguous input. In speech recognition, for example, the input speech sounds are very confusable and many words sound extremely similar. Russell and Norvig (2002) give an intuition from handwriting recognition for how probabilities of word sequences can help. In the movie Take the Money and Run, Woody Allen tries to rob a bank with a sloppily written hold-up note that the teller incorrectly reads as “I have a gub”. Any speech and language processing system could avoid making this mistake by using the knowledge that the sequence “I have a gun” is far more probable than the non-word “I have a gub” or even “I have a gull”.

N-gram models are also essential in statistical machine translation. Suppose we are translating a Chinese source sentence 他向记者介绍了该声明的主要内容 and as part of the process we have a set of potential rough English translations:

he briefed to reporters on the chief contents of the statement

he briefed reporters on the chief contents of the statement

he briefed to reporters on the main contents of the statement

he briefed reporters on the main contents of the statement

An N-gram grammar might tell us that, even after controlling for length, briefed reporters is more likely than briefed to reporters, and main contents is more likely than chief contents. This lets us select the bold-faced sentence above as the most fluent translation sentence, i.e. the one that has the highest probability.

In spelling correction, we need to find and correct spelling errors like the following (from Kukich (1992)) that accidentally result in real English words:

They are leaving in about fifteen minuets to go to her house.

The design an construction of the system will take more than a year.

Since these errors have real words, we can't find them by just flagging words that are not in the dictionary. But note that in about fifteen minuets is a much less probable sequence than in about fifteen minutes. A spellchecker can use a probability estimator both to detect these errors and to suggest higher-probability corrections.

Word prediction is also important for augmentative communication (Newell et al., 1998) systems that help the disabled. People who are unable to use speech or sign-language to communicate, like the physicist Steven Hawking, can communicate by using simple body movements to select words from a menu that are spoken by the system. Word prediction can be used to suggest likely words for the menu.

Besides these sample areas, N-grams are also crucial in NLP tasks like part-of-speech tagging, natural language generation, and word similarity, as well as in applications from authorship identification and sentiment extraction to predictive text input systems for cell phones.

4.1 COUNTING WORDS IN CORPORA

[upon being asked if there weren't enough words in the English language for him]:

“Yes, there are enough, but they aren't the right ones.”

James Joyce, reported in Bates (1997)

Probabilities are based on counting things. Before we talk about probabilities, we need to decide what we are going to count. Counting of things in natural language is based on a corpus (plural corpora), an on-line collection of text or speech. Let's look at two popular corpora, Brown and Switchboard. The Brown corpus is a 1 million word collection of samples from 500 written texts from different genres (newspaper, novels, non-fiction, academic, etc.), assembled at Brown University in 1963-64 (Kucera and Francis, 1967; Francis, 1979; Francis and Kucera, 1982). How many words are in the following Brown sentence?

(4.1) He stepped out into the hall, was delighted to encounter a water brother.

Example (4.1) has 13 words if we don't count punctuation marks as words, 15 if we count punctuation. Whether we treat period (“.”), comma (“.”), and so on as words depends on the task. Punctuation is critical for finding boundaries of things (commas, periods, colours), and for identifying some aspects of meaning (question marks, exclamation marks, quotation marks). For some tasks, like part-of-speech tagging or parsing or speech synthesis, we sometimes treat punctuation marks as if they were separate words.

The Switchboard corpus of telephone conversations between strangers was collected in the early 1990s and contains 2430 conversations averaging 6 minutes each, totaling 240 hours of speech and about 3 million words (Godfrey et al., 1992). Such corpora of spoken language don't have punctuation, but do introduce other complications with regard to defining words. Let's look at one utterance from Switchboard; an utterance is the spoken correlate of a sentence:

(4.2) I do uh main- mainly business data processing

This utterance has two kinds of disfluencies. The broken-off word main- is called a fragment. Words like uh and um are called fillers or filled pauses. Should we consider these to be words? Again, it depends on the application. If we are building an automatic dictation system based on automatic speech recognition, we might want to eventually strip out the disfluencies.

But we also sometimes keep disfluencies around. How disfluent a person is can be used to identify them, or to detect whether they are stressed or confused. Disfluencies also often occur with particular syntactic structures, so they may help in parsing and word prediction. Stolcke and Shriberg (1996) found for example that treating uh as a word improves next-word prediction (why might this be?), and so most speech recognition systems treat uh and um as words. $ ^{2} $

Are capitalized tokens like They and uncapitalized tokens like they the same word? These are lumped together in speech recognition, while for part-of-speech-tagging cap-

italization is retained as a separate feature. For the rest of this chapter we will assume our models are not case-sensitive.

How about inflected forms like cats versus cat? These two words have the same lemma cat but are different wordforms. Recall from Ch. 3 that a lemma is a set of lexical forms having the same stem, the same major part-of-speech, and the same word-sense. The wordform is the full inflected or derived form of the word. For morphologically complex languages like Arabic we often need to deal with lemmatization. N-grams for speech recognition in English, however, and all the examples in this chapter, are based on wordforms.

As we can see, N-gram models, and counting words in general, requires that we do the kind of tokenization or text normalization that we introduced in the previous chapter: separating out punctuation, dealing with abbreviations like m.p.h., normalizing spelling, and so on.

How many words are there in English? To answer this question we need to distinguish types, the number of distinct words in a corpus or vocabulary size V, from tokens, the total number N of running words. The following Brown sentence has 16 tokens and 14 types (not counting punctuation):

(4.3) They picnicked by the pool, then lay back on the grass and looked at the stars.

The Switchboard corpus has about 20,000 wordform types (from about 3 million wordform tokens) Shakespeare's complete works have 29,066 wordform types (from 884,647 wordform tokens) (Kücera, 1992) The Brown corpus has 61,805 wordform types from 37,851 lemma types (from 1 million wordform tokens). Looking at a very large corpus of 583 million wordform tokens, Brown et al. (1992a) found that it included 293,181 different wordform types. Dictionaries can help in giving lemma counts; dictionary entries, or boldface forms are a very rough upper bound on the number of lemmas (since some lemmas have multiple boldface forms). The American Heritage Dictionary lists 200,000 boldface forms. It seems like the larger corpora we look at, the more word types we find. In general (Gale and Church, 1990) suggest that the vocabulary size (the number of types) grows with at least the square root of the number of tokens (i.e. $ V > O(\sqrt{N}) $).

In the rest of this chapter we will continue to distinguish between types and tokens, using “types” to mean wordform types.

4.2 SIMPLE (UNSMOOTHED) N-GRAMS

Let's start with some intuitive motivations for $N$-grams. We assume that the reader has acquired some very basic background in probability theory. Our goal is to compute the probability of a word $w$ given some history $h$, or $P(w|h)$. Suppose the history $h$ is “its water is so transparent that” and we want to know the probability that the next word is the:

$$ P(t h e|i t s\;w a t e r\;i s\;s o\;t r a n s p a r e n t\;t h a t). $$

How can we compute this probability? One way is to estimate it from relative frequency counts. For example, we could take a very large corpus, count the number of times we

see the water is so transparent that, and count the number of times this is followed by the. This would be answering the question "Out of the times we saw the history h, how many times was it followed by the word w", as follows:

$$ P(the|its~water~is~so~transparent~that)={\frac{C(its~water~is~so~transparent~that~the)}{C(its~water~is~so~transparent~that)}} $$

With a large enough corpus, such as the web, we can compute these counts, and estimate the probability from Equation (4.5). You should pause now, go to the web and compute this estimate for yourself.

While this method of estimating probabilities directly from counts works fine in many cases, it turns out that even the web isn't big enough to give us good estimates in most cases. This is because language is creative; new sentences are created all the time, and we won't always be able to count entire sentences. Even simple extensions of the example sentence may have counts of zero on the web (such as “Walden Pond’s water is so transparent that the”).

Similarly, if we wanted to know the joint probability of an entire sequence of words like its water is so transparent, we could do it by asking “out of all possible sequences of 5 words, how many of them are its water is so transparent?” We would have to get the count of its water is so transparent, and divide by the sum of the counts of all possible 5 word sequences. That seems rather a lot to estimate!

For this reason, we’ll need to introduce cleverer ways of estimating the probability of a word w given a history h, or the probability of an entire word sequence W. Let’s start with a little formalizing of notation. In order to represent the probability of a particular random variable $X_i$ taking on the value “the”, or $P(X_i = \text{“the”})$, we will use the simplification $P(\text{the})$. We’ll represent a sequence of $N$ words either as $w_1 \ldots w_n$ or $w_1^n$. For the joint probability of each word in a sequence having a particular value $P(X = w_1, Y = w_2, Z = w_3, \ldots)$ we’ll use $P(w_1, w_2, \ldots, w_n)$.

Now how can we compute probabilities of entire sequences like $P(w_{1}, w_{2}, ..., w_{n})$? One thing we can do is to decompose this probability using the chain rule of probability:

$$ \begin{align*}P(X_{1}\ldots X_{n})~&=~P(X_{1})P(X_{2}|X_{1})P(X_{3}|X_{1}^{2})\ldots P(X_{n}|X_{1}^{n-1})\\&=~\prod_{k=1}^{n} P(X_{k}|X_{1}^{k-1})\end{align*} $$

Applying the chain rule to words, we get:

$$ \begin{align*}P(w^{n}_{1})&=P(w_{1})P(w_{2}|w_{1})P(w_{3}|w^{2}_{1})\ldots P(w_{n}|w^{n-1}_{1})\\&=\prod_{k=1}^{n}P(w_{k}|w^{k-1}_{1})\end{align*} $$

The chain rule shows the link between computing the joint probability of a sequence and computing the conditional probability of a word given previous words. Equation

(4.7) suggests that we could estimate the joint probability of an entire sequence of words by multiplying together a number of conditional probabilities. But using the chain rule doesn’t really seem to help us! We don’t know any way to compute the exact probability of a word given a long sequence of preceding words, $ P(w_n | w_1^{n-1}) $. As we said above, we can’t just estimate by counting the number of times every word occurs following every long string, because language is creative and any particular context might have never occurred before!

The intuition of the N-gram model is that instead of computing the probability of a word given its entire history, we will approximate the history by just the last few words.

The bigram model, for example, approximates the probability of a word given all the previous words $ P(w_n | w_1^{n-1}) $ by using only the conditional probability of the preceding word $ P(w_n | w_{n-1}) $. In other words, instead of computing the probability

P(the Walden Pond's water is so transparent that)

we approximate it with the probability

$$ P(the|that) $$

When we use a bigram model to predict the conditional probability of the next word we are thus making the following approximation:

$$ P\big(w_{n}|w_{1}^{n-1}\big)\approx P\big(w_{n}|w_{n-1}\big) $$

This assumption that the probability of a word depends only on the previous word is called a Markov assumption. Markov models are the class of probabilistic models that assume that we can predict the probability of some future unit without looking too far into the past. We can generalize the bigram (which looks one word into the past) to the trigram (which looks two words into the past) and thus to the N-gram (which looks $ N-1 $ words into the past).

Thus the general equation for this N-gram approximation to the conditional probability of the next word in a sequence is:

$$ P(w_{n}|w_{1}^{n-1})\approx P(w_{n}|w_{n-N+1}^{n-1}) $$

Given the bigram assumption for the probability of an individual word, we can compute the probability of a complete word sequence by substituting Equation (4.10) into Equation (4.7):

$$ P(w_{1}^{n})\approx\prod_{k=1}^{n}P(w_{k}|w_{k-1}) $$

How do we estimate these bigram or N-gram probabilities? The simplest and most intuitive way to estimate probabilities is called Maximum Likelihood Estimation, or MLE. We get the MLE estimate for the parameters of an N-gram model by taking counts from a corpus, and normalizing them so they lie between 0 and $ 1.^{3} $

For example, to compute a particular bigram probability of a word y given a previous word x, we'll compute the count of the bigram $ C(xy) $ and normalize by the sum of all the bigrams that share the same first word x:

$$ P(w_{n}|w_{n-1})=\frac{C(w_{n-1}w_{n})}{\sum_{w}C(w_{n-1}w)} $$

We can simplify this equation, since the sum of all bigram counts that start with a given word $ w_{n-1} $ must be equal to the unigram count for that word $ w_{n-1} $. (The reader should take a moment to be convinced of this):

$$ P(w_{n}|w_{n-1})=\frac{C(w_{n-1}w_{n})}{C(w_{n-1})} $$

Let's work through an example using a mini-corpus of three sentences. We'll first need to augment each sentence with a special symbol $ $ at the beginning of the sentence, to give us the bigram context of the first word. We'll also need a special end-symbol $ $.^{4}

$$ \begin{array}{l}I\quad am\quad\div\\ \\\quad\cdot/s>\end{array} $$