# Compression of non-adjacent structure using grammar

I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string and use recursive substitution with non-terminal symbols to achieve compression.

What I'm wondering is whether there are classes of grammar and inference methods that are able to exploit sequential patterns that are based on non-adjacent co occurrence.

Take the following input sequence:

XaXbXcYaYbYcZaZbZc

No two adjacent symbols co-occur more than once anywhere here, so the sequential compression techniques I mention will not compress this string any further, however there is a clear pattern to the sequence and it must be compressible. How is it possible to do so?

• Is the size of sequences fixed? If it is not fixed, I think it is not decidable at all. – orezvani Apr 8 '14 at 8:06
• No, not fixed @emab – Chris Cox Apr 8 '14 at 9:36
• What is not fixed? The number of small letters, or the number of capital ones? Why should it matter? You do not necessarily have to reuse the same encoding when size changes. cc @emab What is not decidable? – babou Apr 8 '14 at 16:20
• @babou finding such pattern in a string may not be decidable. I asked about the fixed size of substrings. – orezvani Apr 9 '14 at 1:32
• @emab "Decidable" is not a word to be used lightly, You have to be precise about the family of problems you are considering. The fact that a family of problems is undecidable does not imply it for a subfamily. Assuming a version of the problem is undecidable, if you relax the constraint of identifying all patterns, or the best ones, you can make the problem tractable. I do not believe that compression with CF grammars is optimal, and I am not sure that Sequitur is optimal among these algorithms. – babou Apr 9 '14 at 8:14

Note: This answer was written based on the description of Sequitur in wikipedia which is apparently grossly simplified, compared to another description I read in a more technical paper "Detecting Sequential Structure" by Nevill-Manning and Witten. Some of the techniques they use on strings (encoding w.r.t. immediate context) seem very similar to the ones I suggest for AS trees below. It seems however that this paper aims at identifying general grammar structures rather than simple compression of a given string. Hence I am not sure what is the reference to be used when replying to the question asked.

Asked in such a general way, the answer is most probably yes, there must be "a class grammars and inference methods that are able to exploit sequential patterns that are based on non-adjacent co occurrence". At least some such patterns, if you introduce appropriate operators. For example a distributive operator could handle your example. But we will try it below with context-free rules.

The question is more to determine which ones might be interesting in providing significantly better compression, and in what context, as it is most likely that they will be more costly in general, at least during compression.

However, a first remark to be made is that considering the grammar currently used as context-free (CF) is correct, but somewhat a misleading statement as they are a very small subset of CF grammars, since they do not use recursion.

So one question is whether a more powerful grammatical formalism will make a difference when recursion is removed from it. Is it really a grammatical issue, or something else, since the number of strings in the language will always be one?

Another point is that CF grammars can already handle non-adjacent co-occurrences, at least some types of such co-occurrences. There are designed for that. The problem the question raises sometimes lies with the inference method rather than with the grammatical formalism.

You state that the existing algorithms look for adjacent digrams. I have no idea whether they do only this, So I am assuming you are right. But CF-ness does not require such adjacency. If can match parentheses independently of what occurs in between. If you allow for non adjacent digrams, you can get parenthesizing which CF grammars handle very well. For example (considereing actually a trigram), if you consider HTML text, you could encode

    ... <script ..u.. > ..v.. </script> ...


with the rule:

    S -->  <script $1 >$2  </script>


and rewrite the string as

    ... S ..u.. ) ..v.. ) ...


where the closing parenthesis is a reserved symbol not in the text, common to all such discontinuous digrams or trigrams.

Of course, this assumes that you have an algorithm (actually a CF parser) to detect which closing elements go with the opening ones, when encoding the original string.

Having a unique closing parenthesis for all such rules may actually give some extra compression.

Whether that will buy you much more compression is a different issue. It is most likely that algorithms are kept simple because added sophistication will have diminishing returns, but not diminishing costs.

(The following is a natural extension of the above, though not a direct answer to the question)

More generally, some formal documents obey the constraints of a known grammatical structure. For example a program may be represented as an astract-syntax tree (AST). Then one way of encoding it is to start from the AST to first represent it as a big formula in prefix notation, which does away with all the keywords to begin with. Furthermore, you can save on the encoding size of operators (syntactic constructs) as the operators permitted in a given context are often only a small subset of all the syntactic operators of the language. Hence the operator encoding can be chosen with respect to this limiting context, reducing the number of necessary bits. This technique dates back to the 1970-ies.

This idea of using parenthesized context to reduce the size of some encoding symbols could possibly be used in the string oriented case as the HTML example above (which actually encodes a tree structure).

Compressing (?) the given example with our suggested extension

The string to be compressed is

    XaXbXcYaYbYcZaZbZc


Create the rule

    S --> $1$2 $1$3 $1$4


It allows to represent XaXbXcY as SX)a)b)c). Note that, being a common symbol, the ")" will be encoded with few bits. It can even be omitted if the length of an argument is fixed. The whole string becomes: SX)a)b)c)SY)a)b)c)SZ)a)b)c)
Then create as usual:

    A --> )a)b)c)
B --> AS


and the given string can be coded as:

    SXBYBZA


Of course, such a compression technique must be used only when the given pattern is frequent enough to justify the cost of creating the rules. On such a small example, the cost exceeds the benefit.

Note that this encoding imposes some constraints on the use order of rules for decoding, so that arguments are passed correctly to the rules. The idea is to avoid that the non-terminal of a non-adjacent rule misappropriate the wrong closing parentheses. One way is to make sure that the substrings used as arguments no longer contain non-terminals.

It seems difficult to proceed differently if multiple constituents have to be reinserted in distinct parts of the string.

• Thanks, that's all very insightful. I have a couple of questions. When you say: "considering the grammar currently used as context-free (CF) is correct, but somewhat a misleading statement as they are a very small subset of CF grammars, since they do not use recursion." - what do you mean? The example I give does not use any recursive rewrites but the CFG compression techniques I refer to both do, so the end result will be recursive. – Chris Cox Apr 8 '14 at 19:17
• Secondly, from what I understand of your answer, the language that would be created by the grammar you suggest (using recursive rewriting) would not be the language of the original sequence, but an intermediate language that would have to be post-processed in order to create the original sequence. Is that correct? – Chris Cox Apr 8 '14 at 19:18
• @ChrisCox I did not see recursive rules in the wikipedia description of Sequitur. Furthermore, recursive rules give you infinite languages (up to some details) and you have to encode a single string. I must have missed a point of the algorithm that is not described in wikipedia. How do you get recursive rules? – babou Apr 8 '14 at 20:31
• I am not sure I get your second point. In my mind, it does work essentially like (what I understand of) the Sequitur algorithm. However, it is probably essential that non-adjacent rules form a well parenthesized structure. And the decoding should avoid applying such rules as long as non-terminals remain in the part they are supposed to cover to avoid misappropriation of closing parenthesis. This was not intended as a fully worked out system, but as a suggestion of what could be attempted. The last example actually came as an afterthought. – babou Apr 8 '14 at 21:09

Grammar-based compression (context-free) is alwasy looking for repetitions and is blind for other "patterns"..
In your example "XaXbXcYaYbYcZaZbZc" a position based compression should be more senseful. For example the following "position rules" are generating your string..

i=0,1,2:
pos(X)=1+2i
pos(Y)=pos(X)+6
pos(Z)=pos(Y)+6
pos(a)=2+6i
pos(b)=pos(a)+2
pos(c)=pos(b)+2

Rules like that can be stored efficiently and they are easy to decompress.
(In general the best compression is not computable since the so-called Kolmogorov-complexity is not computable. It is always a question of the type of compression..)

Your aims in this case are a bit contradictory. Note that the patterns you are trying to compress are inherently context-sensitive, but you are trying to do so with context-free grammars.

• Could you explain how you could compactly encode the example using a context-sensitive grammar? – Chris Cox Apr 8 '14 at 10:36
• Hm, I haven't found a nice one yet. But I've also never really worked with context-sensitive grammars...I'll let you know as soon as I find one. – john_leo Apr 8 '14 at 12:01