Sequitur

Space is valuable, so it's often desirable to compress data — that is, to use less space to convey the same information. One common data compression strategy is to identify repeated patterns within the data and somehow consolidate these repetitions.¹ First, let's look at Sequitur, a fast compression algorithm that uses the repeated pattern strategy. The table below shows Sequitur running on the input “abcdbcabcd”, with its output at the very bottom:

¹ It just so happens that identifying repeated patterns in a human language can tell us a lot about how that language works. If you want to know more about how linguists (and especially computational linguists) use compression in language technologies, try problem (I), Non Sequitur, in this booklet. Be aware, however, that solving problem (I) will not give you any advantage in solving this problem.

H1. Fill in the blanks (marked with bolded letters) in the table above.

Next, take a look at Byte Pair Encoding (BPE), a widely used compression algorithm that also uses the repeated pattern strategy. Like in the previous example, BPE is running with an input of “abcdbcabcd”, and its output is shown at the bottom of the table:

H2. Fill in the blanks (marked with bolded letters) in the table above.

As you can see, for the input “abcdbcabcd”, Sequitur and BPE produce the same output! But this isn't always the case.

H3. For each of the following inputs, say whether Sequitur and BPE give the same or different outputs:

1. abcabdbcbc
2. abbcaddca
3. bacbcbabacbcba
4. ccdbccdbccacc
5. ccdbccdbccaccacca