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.
