Maximum Matching

Let's remove the spaces from our example sentence. We may still recognise the words because we know English, though some passages can become ambiguous. A space-based program has no such knowledge. We will give it a word list and ask how it could use that list to propose boundaries.

Dr. Alvarez didn't expect the low-cost re-analysis.

The sentence is 51 characters of which six are spaces, and a rule that splits on those spaces finds seven words. Removing them leaves 45 characters and the same seven words, and the five rules from earlier in this section find between one and ten pieces in it, not one of which is a word of English.

…

Removing spaces takes away a major cue used by the earlier rules. Some punctuation is still present: the language-model pattern returns ten pieces because it can split around those characters. But it has no dictionary or learned boundary model with which to recover all the intended words from the remaining letter runs.

How many possible boundary patterns are there before we consult a dictionary? Each gap between adjacent characters has two choices, cut or continue. There is one fewer gap than characters. These are combinatorial choices; we have not assumed that linguistic boundaries are probabilistically independent.

readings of n characters  =  2^(n − 1)

For our sentence with its spaces gone that is two to the forty-fourth, which comes to 17,592,186,044,416. A word list rules almost all of those out, since a reading whose pieces are not words is not a reading anybody wants, but nothing about the problem is small.

Nine characters give 256 and that is enumerable by hand. The interesting thing about this table is how quickly that stops being true, and the whole family of methods this section covers is a series of answers to it. This page’s answer is the cheapest one there is, which is to decide each boundary as you reach it and never reconsider.

English with the spaces taken out is a good way to feel the problem and a bad way to study the method, and the reason is that it is artificial. The spaces were there and I removed them, so there is one right answer and I know it. Chinese is written this way, which changes the question, because the ambiguity that turns up is not damage somebody did to the text.

研究生命起源

Those six characters read as research, life, origin, and they also read as graduate student, fate, origin. Both readings are built out of real Chinese words, both are grammatical, and nothing in the six characters chooses. That is the shape of the problem a segmenter is actually solving, and no amount of removing spaces from English produces it.

So the rest of the page works on the two Chinese sentences this method is classically shown on, each with the small word list that goes with it. The one above is the tie, and the other, which reads as we play at the wildlife park, is the one it is usually shown failing. Both are nine characters or fewer, so both can be checked by hand, and the English sentence comes back in sections 7, 10 and 14, where it makes points a Chinese fixture cannot.

The knowledge has to be carried in some form and the oldest form is a list of words. That is all this method is given. It can ask whether some run of characters is on the list and it can ask nothing else, so it has no way of knowing that one word is common and another rare, or that one reading is more plausible than another.

Two properties of the list matter and both come up later. Its longest entry bounds every question the method asks, since there is no point offering a candidate longer than anything the list holds. And whatever is not on the list does not exist as far as the method is concerned, which is the whole subject of the fourteenth section below.

One rule sits underneath all of this and is easy to miss. Whitespace still ends a run before any matching begins, so a match can never reach across a space. Handed the two words the cat with a space in them, a list holding thecat as an entry will not produce it, because the space closed the run first. That is what keeps the method usable on a page of Chinese that quotes an English name, or on anything with a line break in it.

Stand at the start of the text. Look for the longest run of characters beginning where you stand that the word list holds. Cut there, move past what you took, and do the same again. If no entry at all begins where you stand, take one character and move on by one.

take  =  the longest w with  text[i : i + |w|] = w  and  w in the list

That is the whole method, and the two names it goes by each describe half of it. Maximum matching names the choice at a position, which is the longest available match. Greedy longest match names the discipline about the whole text, which is that the choice is made once and never revisited, whatever it turns out to have cost further along.

Here is the whole method on the wildlife park sentence, with a list of nine words beside it. At each position it offers the longest candidate the list could possibly hold, then the next longest, and stops at the first one it finds. Every question it asks is shown, so the answer can be checked against the list without taking anything on trust.

…

Run it on our English sentence with the spaces gone, against a list of 810 common English words. It comes back with 24 pieces where a space would have given seven, and eighteen of those 24 are single characters that no entry covered.

Here the dictionary is the limiting factor. An exhaustive search using its entries and lone-character fallbacks also needs at least 24 pieces. Exactly one path reaches that minimum, and the greedy method found it. A better search cannot return a shorter path until the available pieces change.

The failure is the list. Alvarez is a surname and an ordinary word list holds no surnames, so its seven letters come back as seven pieces. Dr is an abbreviation and lists hold no abbreviations. The full stop, the apostrophe and the two hyphens are punctuation and lists hold no punctuation. What the method could find, it found; expect, the, low, cost and analysis all came back whole.

At each position the method offers at most as many candidates as the longest entry in the list is long, and each candidate is one lookup. So a run of n characters against a list whose longest entry is L characters costs at most n multiplied by L lookups, and every one of them is a membership test.

lookups  ≤  n × L

Measured, our 45 characters against a list whose longest entry is ten characters cost 191 lookups scanning from the left and 156 scanning from the right, against a bound of 450. The wildlife park sentence cost nine. Those nine questions stand against the 256 readings that sentence admits, and the 191 against 17,592,186,044,416, which is why a rule with this many faults is still the thing every learned segmenter is measured against.

There is one honest gap in what I can report here. The usual claim about maximum matching is that it is right far more often than a rule this crude deserves, on ordinary Chinese prose with a real dictionary behind it. I have no annotated Chinese corpus on this site to check that against, so no accuracy figure appears anywhere on this page. What is measured here is what the method does on texts small enough to verify by hand.

Nothing in the rule said which end to start from. Stand at the end of the text instead, take the longest entry that ends where you are standing, move back past it, and repeat. That is the identical rule reflected, it costs about the same to run, and it can give a different answer.

take  =  the longest w with  text[j − |w| : j] = w  and  w in the list

These are forward and backward maximum matching. Both make a greedy longest-match choice, but they begin at opposite ends. Neither direction is inherently the reference answer. We can compare the segmentations they produce on the same text.

The clearest demonstration of this is in English and is the one everybody uses. Take four ordinary words, run them together, and hand the result to the same list of 810 words scanning each way.

…

From the left, the longest entry beginning at the start is not the three-letter one. It is theta, the Greek letter, which the list holds like any other word, and taking it leaves bledownthere behind. That reads out as bled, own, there, all three of them entries, and the answer is four pieces of four real English words that nobody would write. From the right, every take is the intended word and the answer is the sentence.

Both answers use four pieces, both use four entries of the list, and neither uses a single lone character. Counting cannot separate them, and the widget above says so from the other side. Searching every reading of those seventeen characters, exactly two of them use as few as four pieces, and those two are these two.

The same disagreement on the wildlife park sentence is sharper, because there the two answers are not even the same length. Scanning from the left gives six pieces and scanning from the right gives five, and the five are what a reader answers.

…

Moving from the right, the first thing the scan meets is 动物园, the word for zoo, whole. Having taken it, everything in front falls into place, and the two words that led the other scan astray never come up because the positions they begin at are never visited. The usual argument for why that happens more often than chance is about the language rather than about this sentence.

Chinese compounds tend to carry their head at the end, so a scan coming from the right meets the whole compound before it meets a fragment that begins inside it, where a scan coming from the left meets the fragment first. That is an argument about Chinese and it is not something nine characters can confirm.

Which puts the usual default in an awkward position. Scanning from the left is what maximum matching ordinarily means, and on both texts here where the two disagree it gives the worse answer while asking slightly more questions to get it, 191 against 156 lookups on our English sentence, nine against eight on this one, twenty against eighteen on the four English words. Three texts are a small sample and they point the same way on both counts.

We can run both scans and apply a preference rule when they disagree. That is the bidirectional heuristic. The rules below are chosen preferences, so we should test their consequences rather than treat them as guarantees of a correct segmentation.

On the wildlife park sentence the first rule settles it, since five pieces beat six. On the tied sentence from section 3 the first rule cannot, because both scans answer three pieces, and the second decides it. Scanning from the left gives 研究生, 命, 起源, the graduate student reading, which strands 命 on its own; scanning from the right gives 研究, 生命, 起源 with no lone characters at all.

…

And on the four English words both counts tie, four pieces and no lone characters either way, so the third rule decides, and the answer it lands on is right for a reason that has nothing to do with English. Searching every reading of those characters turns up exactly two that reach four pieces, so the two counts had genuinely nothing to work with and what settled it was the convention.

The failure at the centre of this method is not that it sometimes picks the wrong word. It is that a choice made at one position determines which positions are visited afterwards, so a slightly greedy take early can leave the rest of the text with nothing good to do.

On the wildlife park sentence, scanning from the left, the second take is 在野 rather than 在. Both are entries, 在野 is longer, so the rule takes it. That moves the cursor one character further along than it should be, and from there the characters 生动 line up as an entry when they are the end of one word and the start of another, and after that there is nothing left but three single characters.

This is worth separating from the direction question of the previous part, since the two look similar and are not. There, two answers were level on every count and something had to break a tie. Here one answer is a piece longer than a reading the same list permits, and taking that extra character at position two is what cost it, since no amount of care at the later positions could undo a cut already made.

The other thing the rule has to answer for is what to do when nothing fits at all. There is only one available answer. Take one character, call it a word, and carry on. Nobody chose that, since a method whose entire vocabulary is a list has nothing else it could possibly say about a character the list lacks.

Here is our own sentence contributing to the Chinese half of the page. Put Alvarez in front of the sentence about the origin of life, written the way Chinese writes a foreign name, and hand the result to the same five-word list.

…

The five characters of the surname come back as five separate pieces, so a text a reader answers in four words comes back in eight, and only three of the eight are entries. Nothing has gone wrong here in the sense of the previous section; eight is also the fewest pieces any reading against that list could have used, and both scans reach it. The method did everything it could and the answer is still five characters of noise in front of three words.

A run of lone characters at least looks like something. The harder case is the one where a word is missing from the list and the answer that comes back is made entirely of entries, because then there is no mark on it anywhere.

Take the word for zoo out of the nine-word list and run both scans on the wildlife park sentence again. The right-hand scan, which was the one that got the sentence right, now produces the same six pieces the left-hand scan produced, and all six of them are entries.

…

The English case shows the two halves of it. Take table out of the 810 words and the scan from the left answers exactly what it answered before, theta, bled, own, there, four pieces and four entries, so losing the word changed nothing about the answer or about how finished it looks. The scan from the right falls apart visibly instead, to six pieces of which three are lone characters, so on that side there is at least something to see.

Which of those two happens is settled by where the missing word sat relative to the direction of the scan, and there is nothing in either answer that says a word went missing.

The rule says to take the longest entry that fits where you are standing. It does not say where to stand first, and the text does not say either, because a line of characters has two ends and finding the words in it is not a directional question. The method is therefore not one method. It is two, and they are equally faithful to the rule as written.

What turns on that is not small. On the four English words the two answers are theta, bled, own, there and the, table, down, there, which agree on the last piece and on nothing else, and every count you could compare them by is level. On the wildlife park sentence they differ by a whole piece. Anything that reports a segmentation has to say which scan produced it, in the same way that anything reporting a measurement has to say in what units.

Running both and keeping one does not close this, it only moves it. Where the two answers tie on both counts, and they do tie on the English text here, the answer is decided by a standing preference that has no argument behind it except a generalisation about the shape of Chinese words. Applied to English that generalisation means nothing whatever, and it is still what decides.

There is a difference between a method that can be wrong about a word and a method that cannot express the word at all, and this one is the second. The set of readings available to it is exactly the set that can be spelled out of the list plus lone characters, and a segmentation containing a word the list does not hold is not a poor answer here. It is not in the space of answers.

The consequence is that the method cannot tell you when it has gone wrong for this reason, because being unable to represent something and being unable to detect its absence are the same fact. Nothing comes back as a residual or as a probability that came out low, since the method computes neither. With the word for zoo taken out of the list, the answer is six pieces every one of which is an entry, which is exactly what a correct answer looks like.

There is a genuine decision attached here, and it is the one the rest of this section is made of. If every piece must be an entry, this is the only way the method can fail. If readings are scored instead, a small amount of probability can be held back for a word nobody has seen, and the method gains the ability to answer with a degree of doubt rather than with a wrong answer stated flatly.

The price is that the score has to be estimated from counts, and counts have to come from a corpus somebody segmented.

Underneath everything on this page is one substitution. What anybody wants is the most plausible reading of the text. What the method optimises is the length of the piece it is looking at right now, and the two are related only by the rough observation that long matches tend to be intended matches.

Where they come apart the method has no defence, and it has no defence in a specific way that is worth stating. Both readings of 研究生命起源 use three pieces and both are built of real words, so length has nothing to say about them, and the arithmetic that would say something is a comparison of how often those words occur.

Both readings of the four English words use four pieces of four real words, and the same is true there. Neither tie is a coincidence. Length is a coarse quantity that takes few values, so on a short text several readings land on the same value of it and the method has run out of things to compare.

That is where the next method starts. Give every entry a frequency, lay out every reading the list permits rather than committing at each step, and score a whole reading by the words it used. Scoring a reading only by how few pieces it has recovers something close to the greedy answer, so the rule on this page turns out to be a particular choice of score, and the ties above stop being ties.

The longest-match rule still needs a direction, a dictionary and a way to handle unknown text. Each choice can change the resulting words even though every local step follows the rule correctly.