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?
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..)