```Sorting the matrix of two-sided contexts
Prologue
========

Were any wavelet-like ideas used for _lossless_ compression ?
For PPM or BlockSorting techniques ?
Either "practically no" or "not at all", but why ?

While compressing (=modeling =predicting) array of elements X[n],
if we are saving
Values_Of_Function_Of_Not_Only_Previous_But_Also_Future_Elements Z[i],
we can reconstruct (while decompressing) every next element X[j]
using not only previous elements X[i], but also these Z[i].

In ordinary case we save Values_Of_Function_Of_Previous_Elements Y[i],
and can't use them while decompressing every next element X[j],
because they all can be reconstructed with elements we already have:
Y[i]=Y(X[i],X[i-1],X[i-2],...,X).

I can't agree with people thinking "elegant algos don't work via backside".
Not only the past affects the present, but also the future does.

New(?) way
==========
Sorting the matrix of two-sided contexts
========================================

The original array is X[n].
The context of N-th element of X is the following sequence K:
K=X[N]   (the "prefix", or "parent" element)
K=X[N-1]
K=X[N+1]
K=X[N-2]
K=X[N+2]
K=X[N-3]
K=X[N+3]
...
and so on; array X is a ring:
after the last element - again the first:

X[Length]=X, X[Length+1]=X...

Let's take, for a short example, X="MABROKADABROF",
and form the matrix of all contexts of X:

M
A M
B A M
R B A M
O R B A M
K O R B A M
A K O R B AM
D A K O RMBA
A D A KMOARB
B A DMAAKBOR
R BMAADBARKO   Matrix of all contexts  Left-Right matrix: CM, but first
OMRABBARDOAK     of original array X:    column is moved to the end:
MFAOBRRBOAKDA          MFAOBRRBOAKDA          FAOBRRBOAKDAM
BARMOFKOARDBA          BARMOFKOARDBA          ARMOFKOARDBAB
RBOAKMAFDOARB          RBOAKMAFDOARB          BOAKMAFDOARBR
KOARDBAABMRFO          KOARDBAABMRFO          OARDBAABMRFOK
AKDOARBBRAOMF    =>    AKDOARBBRAOMF    =>    KDOARBBRAOMFA
DAAKBORROBFAM          DAAKBORROBFAM          AAKBORROBFAMD
BARDOAFKMOARB          BARDOAFKMOARB          ARDOAFKMOARBB
RBOAFDMAAKBOR          RBOAFDMAAKBOR          BOAFDMAAKBORR
FOMRABBARDOAK          FOMRABBARDOAK          OMRABBARDOAKF
MFAOBRRBOAKDA
B R OFKOARDBA        (Context Matrix)        (Left-Right Matrix)
R O K AFDOARB
O K A D AFBOR
K A D A B RFO
A D A B R O F
D A B R O F
A B R O F
B R O F
R O F
O F
F

Now, we sort the lines of LRM-matrix:
smaller to the top, bigger to the bottom:

AAKBORROBFAMD
ARDOAFKMOARBB
ARMOFKOARDBAB
BOAFDMAAKBORR
BOAKMAFDOARBR
DBARKOOFRMBAA
FAOBRRBOAKDAM
KDOARBBRAOMFA
OARDBAABMRFOK
OMRABBARDOAKF

(sLRM, sorted LRM-matrix)

Thus, the contexts are arranged so that all similar are grouped together,
and the last column contains the "parent" elements.

IMPORTANT:

(1) Having any line of sLRM, plus position of its last element in X, we
can reconstruct original array X. The same with any line of LRM and CM.

(2) Having the last column of sLRM and few extra bits, we can rebuild
the whole sLRM, and, getting one more index, the original X.

(3) The last column of sLRM is more redundant than in case of BWT.

(4) Does it look like we need to keep the whole matrix in memory ?
Fortunately, no. One pointer to an element of X defines a line of sLRM.
But now linear comparison is impossible: only element-by-element.

Practice will show how big is the gain.

RECONSTRUCTION:

We have the last column only.

Step 1 (having only 1 column):
======

We know that in the first column of sLRM -
are sorted elements of the last column,
and easily get the first column:

1)  A...........D
2)  A...........B
3)  A...........B
4)  B...........R
5)  B...........R
6)  D...........A
7)  F...........M
8)  K...........A
9)  M...........A
10)  O...........K
11)  O...........F
12)  R...........O
13)  R...........O

Step 2a (having only 2 columns, first and last, reconstruct column-2):
=======

column-1:        2:         column-Z:

1st       1st        the parent
left       right        element

1) a+ A    d    A     .....    D
2) a+ A    b    R     .....    B
3) a+ A    b    R     .....    B
4) b+ B    r    O     .....    R
5) b+ B    r    O     .....    R
6) d+ D    a (D?B?B?) .....    A
7) f+ F    m    A     .....    M
8) k+ K    a (D?B?B?) .....    A
9) m+ M    a (D?B?B?) .....    A
10) o+ O    k    A     .....    K
11) o+ O    f    M     .....    F
12) r+ R    o  (K?F?)  .....    O
13) r+ R    o  (K?F?)  .....    O

Legend of symbols:

Since after A (see column-1) only D,B,B are possible (see column-Z) =>
fill 2nd column, lines with "a", with this values, as in the table.
b+ : Since after B only R is possible (see columns 1 and Z) =>
fill 2nd column, lines with "b", with "R", as in the table.
d+ : Since after D only A is possible (...) => ...
f+ : Since after F only M is possible => ...
k+ : Since after K only A is possible => ...
m+ : Since after M only A is possible => ...
o+ : Since after O only K,F are possible => ...
r+ : Since after R only O is possible =>...see column-2, lines with "r".

Now, take into account (1) that lines of matrix are sorted.
Therefore in the 2nd column, in 12th line - F, in 13th - K.

Also, remember (2) that every line and every column of sLRM
contains all elements of the original array X, but they are rearranged.
We know the set of all elements of X from the only Z-th column received.
Therefore in the 2nd column, in 6th line - not D, but B,
because D is already present in the 6th line (in 1st column).

column-1:        2:         column-Z:

1st       1st        the parent
left       right        element

1) a+ A    d    A     .....    D
2) a+ A    b    R     .....    B
3) a+ A    b    R     .....    B
4) b+ B    r    O     .....    R
5) b+ B    r    O     .....    R
6) d+ D    a    B     .....    A
7) f+ F    m    A     .....    M
8) k+ K    a (D?B?)   .....    A
9) m+ M    a (D?B?)   .....    A
10) o+ O    k    A     .....    K
11) o+ O    f    M     .....    F
12) r+ R    o    F     .....    O
13) r+ R    o    K     .....    O

Step 2b (using only 2 columns, first and last, reconstruct column-3):
=======

column-1:        2:        3:            column-Z:

1st       1st       2nd           the parent
left       right    left             element

1) d- A         A       a (D?K?M?) .....    D
2) b- A         R       a (D?K?M?) .....    B
3) b- A         R       a (D?K?M?) .....    B
4) r- B         O       b  A       .....    R
5) r- B         O       b  A       .....    R
6) a- D         B       d  A       .....    A
7) m- F         A       f  O       .....    M
8) a- K      (D?B?)     k  O       .....    A
9) a- M      (D?B?)     m  F       .....    A
10) k- O         A       o  R       .....    K
11) f- O         M       o  R       .....    F
12) o- R         F       r  B       .....    O
13) o- R         K       r  B       .....    O

The sentence "about d-" sounds so:
Since before D only A is possible (see column-Z and column-1) =>
fill 3rd column, lines with "d", as in the table, with this value, A.
...
a-:  Since before A only D,K,M are possible (see columns Z and 1) =>...
fill 3rd column, lines with "a", as in the table, with this values.
And so on, all steps b-, f- etc. are filling column-3 using same logic.

Now, see that element in 3rd column, in 1st line, can't be D,
as D is already present in 1st line (in column Z).
Also, D can be in the 3rd line of 3rd column, because lines 2 and 3 are
sorted, and both K and M are bigger than D.
Thus, D can be only in the 2nd line. Now,

column-1:        2:        3:            column-Z:

1st       1st       2nd           the parent
left       right    left             element

1)  A         A         (K?M?)    .....    D
2)  A         R           D       .....    B
3)  A         R         (K?M?)    .....    B
4)  B         O           A       .....    R
5)  B         O           A       .....    R
6)  D         B           A       .....    A
7)  F         A           O       .....    M
8)  K      (D?B?)         O       .....    A
9)  M      (D?B?)         F       .....    A
10)  O         A           R       .....    K
11)  O         M           R       .....    F
12)  R         F           B       .....    O
13)  R         K           B       .....    O

Using two columns, we (partially) reconstructed four columns.
Only pair (column-1, column-Z) was viewed,
the distance between them is 1, i.e. these are neighbor columns.

Further:
========

Step 4.1a (using columns Z and 2, rebuild column-4 "2nd right element")
Step 4.1b (using columns 1 and 3, rebuild column-5 "3rd left element")
Why 4.1a and 4.1b:
Using four columns; distance=1; a - step to the right, b - to the left.

After every step, get more precise values, using that
(1) the lines of sLRM are sorted;
(2) every line and every column of sLRM - all elements of X rearranged.

Step 4.2a (using columns 1 and 2, rebuild column-6 "3rd right element")
Step 4.2b (using columns Z and 3, rebuild column-7 "4th left element")
Step 4.3a (using columns 2 and 3, rebuild column-8 "4th right element")
Step 4.3b (using columns 2 and 3, rebuild column-9 "5th left element")
Using four columns, partially reconstructed ten.

Further: steps 10.1a, 10.1b, 10.2a, 10.2b, 10.3a, 10.3b, 10.4a, 10.4b,
10.5a, 10.5b and so on, until all the columns are reconstructed.

When new values are written to an element of matrix, on top of some old,
for example, there were (F?B?), and new (D?M?F?) are added,
remain only those present in both old and new sets (F, in this example).

Indeed, it's rather inconvenient:
to rebuild the whole matrix each time, in such element-by-element way.
There certainly are appallingly effective optimizations.
Of course, not everything is now seen exceptionally precisely and clear.

Epilogue
========
Practice will show how big is the gain,
comparing to other (PPM or BlockSorting) techniques.

Does anybody know any analogues of suggested "new way"?

-------------------------------------------------------------
Correct me where I am wrong, expand me where I am incomplete.
-------------------------------------------------------------
http://geocities.com/eri32/slrm.htm
http://artest1.tripod.com/slrm.htm

With best kind regards,
A.Ratushnyak,
RAO Inc.
http://go.to/artest
go Back to main ARTest page

u="u331.44.spylog.com";d=document;nv=navigator;na=nv.appName;p=1;
bv=Math.round(parseFloat(nv.appVersion)*100);
n=(na.substring(0,2)=="Mi")?0:1;rn=Math.random(); z="p="+p+"&rn="+rn;y="";
y+="<a href='http://"+u+"/cnt?f=3&p="+p+"&rn="+rn+"' target=_blank>";
y+="<img src='http://"+u+"/cnt?"+z+
"&r="+escape(d.referrer)+ "&pg="+escape(window.location.href)+"' border=0 width=88 height=31 alt='SpyLOG'>";
y+="</a>"; d.write(y); if(!n) { d.write("<"+"!--"); } //--> <!--
if(!n) { d.write("--"+">"); }//-->

```