Greedy Coverage

We work on the same two corpora the merging pages use, so that nothing in the comparison is a difference of data. The small one is four words with their counts, low five times, lower twice, newest six times and widest three, sixteen occurrences in all. The large one is eighteen short sentences of ordinary English about reports and costs and analyses, 72 distinct words across 133 occurrences. Neither contains the sentence this section carries everywhere.

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

Each word is written out as its characters, and the last character of each word carries a mark saying a space follows it, which is what keeps a piece that ends a word apart from the same letters inside one. Counted that way the four words hold 79 positions, weighted by how often each word occurs, and the eighteen sentences hold 648. Those two numbers are what a vocabulary is being asked to cover, and they are the quantity every measurement below is a fraction of.

Merging scores a candidate by how many times two symbols sit next to each other, and it can only ever consider two symbols at a time, because that is what a merge is. On the eighteen sentences the winner of that contest is h followed by the marked e, adjacent 31 times, and the runners-up are t followed by h at 20, r followed by e at 17, and T followed by h at 12. Nothing longer is in the running, since nothing longer exists yet.

Coverage multiplies a candidate’s occurrence count by the number of symbol positions it covers.

he:      31 × 2 = 62
analys:   7 × 6 = 42
expecte:  5 × 7 = 35
re:      17 × 2 = 34

The most frequent pair still wins here, but the remaining order changes. Longer pieces can cover more text despite occurring less often.

The difference is not a refinement of the same idea. A merge count answers how many pieces one join removes from the corpus, which for a pair is how often the pair occurs; a coverage figure answers how much of the corpus a row of the table would account for, which is that occurrence count multiplied by the length of the piece.

Merging cannot ask the second question at all, because it has no candidate longer than two symbols to ask it about, and reaches analys only by making five separate joins and scoring each of them on its own.

So state the thing the vocabulary is for, and then choose to maximise it. Every position in every word should lie under some piece of more than one symbol, because a position left bare is a whole token spent on one character. A vocabulary of a given size is good to the extent that it covers those positions, and each word counts as often as it occurs.

covers(p)  =  Σ over words w   count(w) × (positions of w that p claims)

The rule is then the shortest one on this site. Take the candidate covering the most positions nothing has covered yet, add it to the vocabulary, and repeat until the budget is spent or nothing is left to cover. Candidates are every run of two or more symbols the corpus contains. Single symbols are not candidates, since the alphabet is in the vocabulary anyway and a single symbol covers nothing that was not already going to be its own token.

take   argmax over candidates p   covers(p) restricted to positions still bare

Applying a piece to a word is a scan from the left. Wherever the piece matches on positions nothing has claimed, claim them and skip past the match; otherwise move along one and look again. The pieces already chosen are applied first, in the order they were chosen, and a candidate is then worth whatever it can still find. That is the only mechanism on the page, and it is why the order pieces were chosen in is part of the model rather than an accident of the fit.

ending in widest = 3 positions × 3 occurrences = 9
ending in both words = 3 × (3 + 6) = 27
whole widest = 6 × 3 = 18

Run the rule on low, lower, newest and widest and the first turn goes to newest with its mark, six positions in a word seen six times, which covers 36. Its nearest rivals are ewest with the mark and newes, both five positions in the same six occurrences and worth 30, and then est with the mark, three positions across nine occurrences and worth 27.

Merging’s own first choice on this corpus is the pair e followed by s, which appears nine times; here that pair is not even a separate candidate, since every run containing it is one.

…

Drag the control and watch covered positions fill. The marked ending est loses the first turn to newest because the complete word covers more weighted positions.

newest = 6 × 6 = 36
marked est = 3 × 9 = 27

This choice comes from the coverage objective. It makes no judgment about which candidate is a meaningful word or suffix.

Once newest is selected, positions it covers no longer earn credit for overlapping candidates. The marked ending can now earn credit only in widest, so the next choice is the whole word. The remaining choices finish the coverage.

newest: 6 × 6 = 36
widest: 6 × 3 = 18
low:    3 × 5 = 15
lower:  5 × 2 = 10
total covered = 36 + 18 + 15 + 10 = 79

Those four selections cover every weighted symbol position in this corpus.

The fit then stops, at 16 tokens, however many were asked for. There is no candidate left that covers a position, so asking for 40 rows or 300 gives the same four pieces. That is the same shape of ceiling merging has, where the loop runs out of pairs seen twice, arrived at from a different direction. Here the ceiling is reached when the corpus is entirely covered.

To read a new word, spell it in symbols and apply the chosen pieces in rank order, exactly as the fit did. Whatever a piece claims is a token; whatever stays bare is a single symbol. So lower comes back as one piece, and the unseen unwidest comes back as u, then n, then widest with its mark, because the chosen piece really does occur inside it.

That is the structural difference between the two methods, and it is worth naming here rather than in the comparison, since it follows from the objective alone. Merging builds long pieces out of short ones and keeps every rung, so a word that fails to match the long piece still matches the rungs. Coverage buys pieces outright and buys no rungs, because a rung covers positions its parent already covers and is therefore worth nothing at the moment the parent is in.

Notice what the rule is an approximation to. The question we actually want answered is which set of k pieces covers the most positions, and that question has nothing greedy in it. Taking the best piece first is one way to build a set of k; there are many others, and no reason yet to think the first is the best.

The question is a known one and the answer is that it cannot be computed. Choosing k sets to cover as much of a universe as possible is weighted maximum coverage, whose decision form is the set covering problem on Karp’s 1972 list, and no method is known that answers it exactly without, in the worst case, examining a number of subsets that grows exponentially in the number of candidates.

The eighteen sentences supply 815 candidates and the rule runs for 69 turns on them, so the exact answer would mean weighing 815 things taken 69 at a time, which is not a search anybody runs.

What makes this particular approximation worth building a method on is that it is not merely a heuristic. Coverage is a monotone submodular function of a set of pieces, which means two things. Adding a piece never lowers the coverage, and a piece added to a larger set never covers more than the same piece added to a smaller one, since the larger set has already taken some of what it would have claimed.

For any function with those two properties, the greedy rule run for k turns reaches at least 1 − 1/e of what the best set of k could reach.

greedy coverage after k turns   ≥   (1 − 1/e) × best coverage any k pieces reach

That fraction is 0.632, and Feige’s 1998 result says no polynomial method improves on it in general. So the honest reading of the guarantee is narrow, and it is worth being exact about, because it is often quoted as though it said more. It is a worst case over every possible input, so it promises nothing about a typical corpus.

It bounds coverage and says nothing at all about sequence length, which is the quantity anything reading the pieces actually pays. And it compares the rule to the best set of the same size rather than to any absolute standard, so a problem on which every set is bad has a guarantee that is satisfied by something bad.

A worst-case fraction is easier to think about beside a case where the rule really does lose something, and two words are enough. Take costing three times and costly three times, which is 39 positions. The best single piece is cost, four positions in six word occurrences, worth 24, and nothing beats it, so the first turn is forced and correct. With two pieces to spend the rule takes cost and then the ending ing with its mark, and reaches 33.

…

The best pair, found by enumerating every pair of candidates rather than by another heuristic, is the two whole words, which cover all 39 between them. The rule reaches 84.6% of that, which is comfortably above the 63.2% the theorem allows and still a real loss, and the loss was locked in by a first move that was the best available at the time.

The cost in the currency that matters is larger than the cost in coverage. Under the two pieces the rule chose, the six word occurrences read as 15 pieces, since costly comes apart as cost, then l, then a marked y. Under the best pair they read as 6, one per word.

The objective says to cover the most text, and there are two defensible readings of what a covered amount of text is. One counts positions of the spelled word, so the marked final symbol of a word is one position like any other. The other counts characters, and then the marked final symbol stands for two things, the letter and the fact that a word ended, so it is worth two.

in positions    t⎵  is  1
in characters   t⎵  is  2, the letter and the boundary

Neither reading is wrong, and the difference is not uniform. It adds exactly one to every candidate that ends a word, once per occurrence, and nothing to a candidate that does not. So a short suffix gains proportionally more than a long word does, and the ordering of two candidates can change. Whether it does is a question about a corpus rather than about the rule.

I originally expected character counting to make the marked ending tie with newest. That counted the extra end marker for the ending but forgot to count it for the whole word.

marked est, counting characters = 4 × 9 = 36
marked newest, counting characters = 7 × 6 = 42

There is no tie. The longer word gains from the changed unit too. The marked ewest candidate also reaches 36, which still leaves it below newest.

…

The whole run comes out the same four pieces in the same order, at 42, 21, 20 and 12 rather than 36, 18, 15 and 10. So on this corpus the unit changes every number and no decision, and the claim I had written down does not reproduce. The arithmetic of why is worth following, since it says when the claim would have been right.

Both leading candidates end a word, so both collect one extra character per occurrence, which is worth 6 to newest and 9 to the ending. The ending does gain more, and the gap it had to close was 9, so closing it by 3 leaves it 6 behind.

The claim is repairable, and repairing it shows exactly what kind of corpus is needed. The extra character goes to word-final candidates only, so the flip needs a word-final candidate close behind a word-internal one. Take test, rest and best three times each, against stem, stop and stub five times each, which is 96 positions and 120 characters.

The second corpus exposes a difference that the first did not. The opening st occurs fifteen times, while the marked ending est occurs nine times. Counting the end marker as a separate character changes only the latter’s length.

symbol positions: st = 2 × 15 = 30; marked est = 3 × 9 = 27
characters:       st = 2 × 15 = 30; marked est = 4 × 9 = 36

The winner changes. Switch to the second corpus in the widget to compare both columns.

The consequence runs past the first turn. Counting positions the run is st at 30 then est with its mark at 27; counting characters it is est with the mark at 36 then st at 30. Both vocabularies end up holding both pieces, and they hold them in the opposite order, which matters because the order is what encoding replays. A word that contains both is cut differently by the two.

On the larger corpus the rule runs for 69 turns before nothing is left to cover, reaching 121 tokens in all, and it covers 576 of the 648 positions. The 72 that stay bare are positions no run of two or more symbols can reach any more, which are the leftovers between chosen pieces.

…

The shape of that profile is the submodularity of Part 3 made visible. Each piece chosen removes positions from every candidate still standing, so the value of the best remaining candidate can only fall, and the sequence 62, 42, 35, 34, 24, 21, 21, 16 is monotone all the way down to a tail of twos. The flat stretches are ties, runs where several pieces were each worth the same, and the longest of them is thirteen turns in a row each worth two.

Ask both methods for 100 tokens on this corpus and both learn 48 rows above the same 51-symbol alphabet, which makes the comparison a fair one. Twelve of the 96 rows are shared. The rest are not, and the difference has a clear shape rather than being scattered.

…

Eighteen of the 48 rows chosen by coverage are whole words of the corpus, against 8 of merging’s 48, and the mean piece is 3.77 characters long against 3.04. Merging’s vocabulary is full of the rungs it climbed, aly and analy and analysi on the way to analysis, ex and exp and ecte on the way to expected. Coverage holds analys and expecte and nothing else from either family, because once analys is in, no shorter piece inside it is worth anything.

Read the corpus the pieces were chosen from and coverage wins at every size, which it ought to, since covering that corpus is precisely what it was maximising. At 60 tokens it reads the 133 word occurrences in 475 pieces against merging’s 531; at 100 it is 296 against 344; at 121, where it has run out of positions, it is 267 against 295.

…

That is 56 pieces saved at 60 tokens, 48 at 100 and 28 at 121, and it is a direct consequence of buying long pieces. A row that covers six positions removes five pieces from the corpus every time it is used, where a row that covers two removes one. The two ceilings differ as well, since coverage stops at 121 tokens when the corpus is covered and merging continues to 137 before it runs out of pairs seen twice.

Switch the widget above to the sentence none of the eighteen contained and the ordering changes hands. Up to 65 tokens coverage is still ahead, reading the sentence in 35 pieces at 60 where merging needs 39. At 70 they have crossed, 35 against 32, and merging leads at every larger size, 32 against 28 at 80, 32 against 27 at 100, and 30 against 25 at 121.

This is the place on the page where the method is worse than the one it is offered against, and the margin is 5 pieces on a sentence of seven words.

Reading either pair of columns alone settles the question the wrong way. The corpus columns say coverage is better at every size and the sentence columns say merging is better from 70 onward, and both are correct measurements of different things. Which one to believe depends entirely on whether the text a model will read resembles the text the vocabulary was chosen from.

The reason for that reversal is one word, and switching the comparison widget to its second panel shows it. The corpus uses expected and never the bare stem, so coverage buys expecte, seven positions across five occurrences. Handed expected it answers two pieces. Handed expect, which the corpus does not contain, it answers e, x, p, e, c and the marked t, six single letters, because expecte is not inside expect and nothing shorter was ever bought.

Merging, at the same size, answers expect in three pieces, exp and ec and the marked t, all of which are rungs it climbed on the way to expected and kept. The same happens to analysis, which coverage reads as analys and the marked is where merging reads it whole. Counted across the running sentence, 24 of coverage’s 32 pieces are bare single symbols against 17 of merging’s 27.

So the length that wins on the training corpus is the same length that loses on new text, and it is one property rather than two. A piece of seven symbols covers seven positions wherever it occurs and occurs in fewer distinct words than a piece of three. Nothing in the objective values the ability to fall back gracefully, since falling back never happens on the corpus being covered.

The objective is a statement about positions and counts, and there is nothing else in it. It cannot prefer a piece that corresponds to a prefix, a stem or a syllable over one that does not, because it has no representation of any of those. A piece is a run of symbols that appears often enough and is long enough, and every run of symbols in the corpus is a candidate on equal terms.

That is not a complaint about the rule; it is the content of the definition. On the eighteen sentences the rule buys expecte, which is the stem expect with the first letter of its ending glued on, and analys, which is analysis with its last two letters missing. Both are correct answers to the question asked, and both would be rejected by anybody dividing those words by hand. The information that would settle it is not in the objective, and adding it means changing what is maximised rather than tuning anything.

Length and frequency enter the objective as a product, so they substitute for one another freely. A word of eight symbols seen a single time is worth 8, and a pair of symbols seen four times is worth 8 as well, and the rule cannot distinguish them. Merging can, and does, since its usual stopping condition refuses any pair seen fewer than twice.

Of the 72 distinct words in the eighteen sentences, 54 occur exactly once. At 100 tokens, 10 of the 48 rows coverage chose are whole words seen once, among them Tuesday with its full stop, Monday with its full stop, dropped, August and Nobody. At 121 tokens it is 13 of 69. Merging, at every one of those sizes, spends none.

Whether that is memorisation or good value is genuinely open, and the answer differs by which text is being read. On the corpus those rows earn their keep, since a whole word bought as one row removes every position of it but one. On any other text they are dead weight, and they are dead weight that displaced a shorter, commoner piece which would have earned something everywhere. Merging’s frequency floor is a decision about the same question, made in the other direction and made without measuring.

The last section suggests a repair, and it is worth measuring rather than assuming. Candidates are runs of two or more symbols with no upper limit, so if the limit is lowered the whole-word rows become unbuyable and the rule has to spend its budget on shorter pieces. Nothing in the objective says where that limit should be, and the two readings do not agree about where it should be either.

…

At the same 100 tokens, allowing pieces of any length reads the corpus in 296 pieces and the held-out sentence in 32. Capping at five symbols reads the corpus in 324 and the sentence in 28, which is 28 pieces worse on the corpus and 4 better on the sentence, and it cuts the rows spent on words seen once from 10 to 2.

Capping at three goes too far in that direction, 384 and 29. Past eight the ceiling stops binding at all, since the pieces the rule wanted were shorter than that anyway.

Gathered in one place, these are the inputs on which the method stops being defined rather than becoming approximate, together with what has to be decided in each case and what turns on the decision. Several are genuinely open questions with defensible answers on either side, and those are the ones worth attention, since they are the decisions anybody setting this up has to make and nothing in the mathematics makes them.