Maximum Matching

We have been carrying one sentence through this section, and every rule so far has begun by looking for whitespace in it. Take the whitespace away and the sentence is still perfectly readable, since a reader finds the words from knowing English rather than from the gaps, and every rule we have written stops working at once.

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.

…

It is worth being precise about what has gone. The rules were never reading the language. They were reading a mark the writer put in, and doing an increasingly careful job of deciding what belongs on either side of that mark. With the mark gone there is nothing left for them to be careful about, and the pattern language models use, which is the most elaborate of the five, answers ten pieces because it still finds the punctuation.

Before reaching for a method it is worth knowing how large the problem is. Between any two neighbouring characters there is either a boundary or there is not, and those choices are independent, so a text has one fewer place to decide about than it has characters, and two ways to decide each of them.

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.

It is worth being careful about whose fault that is, because the obvious reading of the number is the wrong one. The failure is not greed. Searching every reading whose pieces are either entries or lone characters, the fewest any of them uses is also 24, and exactly one reading reaches it, which is the one the method found. There was no better answer available and the method did not pass one by.

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

The two are usually called forward and backward maximum matching, and it is worth resisting the idea that one of them is the method and the other is a variation on it. They are the same greedy discipline applied along a text that has two ends. Neither has a claim on being first.

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.

Since both scans are cheap, the obvious move is to run both and keep whichever answer looks more like a segmentation. That is the bidirectional heuristic, and it is worth writing its rules down in full because they look like principles and are not.

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.

Gathered in one place, these are the inputs and questions on which the method stops being defined rather than becoming approximate, with what has to be decided in each case and what turns on the decision. The ones worth a reader’s attention are the decisions, since those are what anybody setting this up has to make and nothing in the method makes them.