How much of this is new

A picture of repetition is a good thing to have and a poor thing to compare. Two matrices side by side cannot be ranked, and the question a listener actually asks — is this piece more repetitive than that one — needs a number.

There is an obvious way to get one, and it is not a musical idea at all. Repetition is redundancy, redundancy is what compression removes, and the size of a compressed description is therefore a measure of how much of a sequence was new. Hand the bars to a coder, count the bits, and divide by the bits the same bars would take with no compression at all.

The measurement is easy. What it means takes the rest of this essay.

The coder, in four lines #

The coder used here is LZ78, which is about as simple as a dictionary compressor gets and is the ancestor of most of the ones in daily use.

It walks the sequence holding a dictionary of phrases it has seen, starting with one empty phrase. At each step it reads the longest phrase already in the dictionary, then one more symbol. That pair — the index of the known phrase, plus the new symbol — is what it emits, and the extended phrase goes into the dictionary for next time.

The cost of the emission is the cost of an index into a dictionary of the current size, plus the cost of one symbol from the alphabet: $\log_2 D + \log_2 A$ bits. Against that sits the flat cost of just sending the symbols, which is $n\log_2 A$.

Nothing about the coder knows anything about music. It is being handed a list of chord names.

It is worth watching it work on eight bars, because the mechanism is unusual in being completely visible. Take the first eight bars of the AABA plan, which are the chords I, vi, ii, V, I, vi, ii7, V7. The coder emits I, then vi, then ii, then V — four phrases, all of them new, all of them expensive. Then it reads I again, finds it in the dictionary, extends to I vi, does not find that, and emits it as one phrase. Then ii7, then V7. Seven emissions for eight bars.

Now repeat those eight bars. The second time round the coder already holds I vi, so it extends to I vi ii and swallows three bars in one emission. The third time it holds that, and swallows four. The saving is not in the repetition itself but in the coder’s memory of it, which is why the numbers below depend so heavily on how long the sequence is allowed to run.

The first result is that the coder loses #

The hero figure plots the ratio — bits used over bits flat — against how many bars are sent, for five schemes.

At a single chorus, every scheme except the ostinato is above one. The coder does not compress them. It makes them bigger.

This is not a bug and it is not a fact about music. A dictionary coder is an asymptotic instrument: it pays for its dictionary up front and earns the money back over a long sequence. At thirty-two symbols it has barely built a dictionary, every index it sends is nearly as expensive as the symbol it saves, and the overhead swamps the saving. The same coder on the same music at 512 bars is at 0.62, and at 1,024 bars 0.52.

So the honest form of the statement “this music is 40 per cent redundant” is: this description of this music, coded with this coder, at this length, took 40 per cent fewer bits than a flat encoding of the same length. Three of those four qualifiers are usually dropped, and each of them changes the number.

The one scheme that compresses at every length is the ostinato, and it is worth looking at why.

The statistic that survives at a musical length #

A curve that only becomes meaningful at a thousand bars is not much use for talking about a thirty-two-bar song, which is one of the reasons the right-hand panel of the hero figure exists.

Count phrases instead of bits. Each phrase the coder emits is one thing it had not seen before, so new phrases per bar is a direct count of how often the piece introduced something. It needs no asymptotics, it is defined at any length, and it is monotone in the way one would want.

At a single chorus, under the chord-and-key description:

That ranking is defensible. The ostinato introduces almost nothing; the blues is three choruses of one twelve-bar idea; the rondo and the song form both spend a third of their length somewhere new.

And it is not stable.

The same music, described differently, ranks differently #

Every symbol above was a chord together with the key it is in. That is the finest description the encoding carries. There is a coarser one already sitting in the same data: the section letter.

The blues moves from 0.42 to 0.42 — unchanged, because its three sections and its three chords are the same partition. Everything else moves down, because a section letter is a coarser symbol and coarser symbols repeat more. The AABA plan falls from 0.59 to 0.38 and the verse-and-chorus from 0.47 to 0.38, and the blues, which did not move, ends up at the top of a list it was near the bottom of.

Nothing happened to the music. The description changed.

This is the result to carry away, and it is worth stating in its strongest form. A compression ratio is a measurement of a description. It is a perfectly good measurement — reproducible, checkable, and sensitive to exactly what it claims to be sensitive to — and the object it measures is the encoding, not the piece. Two pieces can be compared only if they are described the same way, and even then the comparison is a comparison of descriptions.

The site has met this shape before in a different field. Roughness is computed from a spectrum, and hand a different spectrum to the same model and the dissonance curve grows and loses wells; the model was never wrong, the input was different. Here the input is a way of writing music down, which makes the dependency easier to overlook and no less complete.

What is stable #

Something does survive, and it is worth being precise about what.

The ostinato is the extreme at every length and under every description. It is 0.25 phrases a bar either way, and its bit ratio is under one from the very first chorus. A measure that could not separate thirty-two bars of one chord from a rondo would be worthless, and this one separates them by a factor of two and a half at any setting.

The direction of the growth curve is stable. Every scheme’s ratio falls monotonically as the sequence lengthens, under both descriptions, and the fall is steep. That is a real property: it says these are pieces built from a small vocabulary used many times, which is what makes them forms rather than sequences.

And the gap between two schemes at a fixed length and description is stable, even when the ordering of the middle of the field is not. The ostinato and the AABA plan are separated by the same distance whichever way they are described.

Why the alphabet is doing half the work #

There is a specific mechanism behind the reordering, and naming it makes the result less mysterious and more useful.

The flat cost against which everything is compared is $n\log_2 A$, where $A$ is the size of the alphabet. Describe the blues in chords and its alphabet is three; describe it in section letters and its alphabet is still three, because in that scheme the sections and the chords partition the bars identically. Describe the AABA plan in chords and its alphabet is ten; in section letters it is two.

So the two schemes are not merely being coded differently, they are being compared against different baselines, and a scheme whose alphabet collapses from ten symbols to two has had its baseline cut by more than a factor of three. Its coded size falls, but the thing it is being divided by falls faster.

That is why the blues appears to move without moving. Its number is unchanged at 0.42 under both descriptions; everything else came down past it. A ranking in which the only fixed point looks like the one that moved is a ranking to be careful with.

The general lesson is one this site keeps arriving at from different directions. A ratio of two quantities is only as meaningful as the agreement about what is in the denominator, and the denominator here is a description that was chosen rather than measured.

Why a piece would not want to score low #

There is a temptation, once a number exists, to treat it as a quality. It is not one, and the reason is a fact about listening rather than about coding.

A sequence that compresses perfectly is one with nothing left to predict, and a sequence that does not compress at all is one where nothing can be predicted. Expectation is what a listener has been counting, and it needs both: enough regularity to build a prediction on, and enough departure for the prediction to be worth having.

Music sits in the middle of that range, and the schemes above sit close together in it — between 0.25 and 0.6 new phrases a bar, which looks like a narrow band on a scale that runs from 0 to 1.

The band is narrow because the coder is short-sighted #

That narrowness invites a reading — every one of these very different plans is doing about the same amount of repeating — and there is a null which decides whether the reading is about the music. Generate a random sequence of the same length over the same alphabet and count its phrases.

The band is narrow because random noise is in it. A sequence with no structure whatever, at these lengths, scores between 0.40 and 0.64 new phrases a bar — which is most of the range the five schemes occupy. Only the ostinato is decisively separated from chance. Four of the schemes sit under two standard deviations below their own null, which is a real difference and a small one, and the sixteen-bar period is three tenths of a standard deviation from random and therefore not distinguishable from it at all.

That last row confirms from the outside what the figure below already suspects from the inside. A statistic that ranks a sixteen-bar period as the least repetitive object in the collection is reporting its own warm-up, and the null says how much: 98 per cent of what a random string of the same shape would give.

So the finding to carry is not that the plans repeat by similar amounts. It is that at the length of a single chorus this statistic can separate an ostinato from noise and can barely separate anything else from anything. Every ranking earlier in this essay is a ranking of differences of one or two standard deviations, and the reordering that happens when the description changes is a reordering inside that margin.

Nothing about the coder is at fault. It is an asymptotic instrument being read at thirty-two symbols, which the first section said and the null now prices. What the null adds is that the price is nearly the whole measurement.

The picture of the blues says the same thing its number does. Laid out as a self-similarity matrix it is bright stripes at an offset of twelve — the same twelve bars, three times — and the count of new phrases a bar reports exactly that repetition and nothing else. What the picture will not do is rank, and what the number will not do is show where the repetition is. Each fails where the other does not, which is the argument for quoting both and for trusting neither alone at this length.

The rhythm field asked the same question first #

This is not the first time the site has put a number on how much of a pattern is a repeat of itself, and the earlier occasion is worth putting beside this one because it came out so much better.

A Euclidean rhythm is generated rather than transcribed: five onsets in twelve steps, spread as evenly as twelve allows, and the pattern that falls out is one already in use across four continents. That is a description in one line which reproduces the object exactly, and its description length is genuinely tiny — two integers.

The contrast with the present measurement is instructive. The Euclidean construction compresses a rhythm to almost nothing because it has a model of what the rhythm is. LZ78 has no model at all, which is why it needs a thousand bars to earn its keep, and also why it can be pointed at anything. The trade is the one that runs through the whole of this subject: a model that fits gives an enormous saving and only works where it fits, and a model-free method gives a small saving everywhere.

A well-chosen model for a chord scheme would compress the AABA plan to something like “eight bars, twice, then a bridge, then the eight bars again” — a handful of symbols for thirty-two bars, far beyond anything in the figures above. That description exists. It is the thing musicians call the form, and it is precisely what a compression measurement is being used as a substitute for.

What this cannot show #

The coder sees a sequence of symbols, so everything that is true of the matrix is true here and more so. No melody, no rhythm, no texture, no dynamics. A bar is one symbol.

It is also strictly literal, and the cost of that is measurable. Two phrases that are transposed versions of each other are, to this coder, entirely unrelated symbol strings — and transposition is the thing music does most. Move the second half of each scheme up a fifth, changing nothing else, and the phrase count rises by 27 per cent for the verse-and-chorus plan and 21 for the AABA, which is larger than the gap between any two schemes in the table above. The rondo rises by only four, because its second half shares little with its first either way. So a coder without a model of transposition mis-ranks these plans by more than it distinguishes them. Real compressors used on music are built to spot that; this one is not, deliberately, because a coder that finds transposed repeats needs a model of transposition and this essay is about what a model-free count can and cannot do.

The null in the section above bounds all of that at once, and it is the right place to end the list of limitations rather than to start it. A statistic whose observed values sit one or two standard deviations from what a random string of the same shape gives cannot support a ranking of five items, however carefully the ranking is described. It can support the one separation it makes decisively, which is an ostinato against everything else, and it can support the direction of the growth curve, which is a statement about long sequences where the coder is in its element.

And the bits themselves are not comparable to anybody else’s bits. A different coder gives a different number on the same input, and the ratio a modern general-purpose compressor gives would be different again. Only the comparisons made inside one figure, with one coder and one description, are comparisons at all.

Where the ladder goes #

Three rungs of this anchor have now measured repetition three ways — as a picture, as a set of boundaries, and as a count — and all three have taken the bar as their unit without asking whether it is the right one.

It is not obviously the right one. The unit a listener actually works in is the phrase, and a phrase turns out to have a length in seconds rather than in bars, which means the same eight bars are a different perceptual object at two tempos. Everything counted here would be counted differently if the unit followed the listener instead of the notation.

Beyond that lies the question all of this has been circling. Repetition explains why a piece hangs together; it does not explain why it stops. An ending is not a change and not a repeat, and none of the three methods in this ladder can see one.