arXiv:1701.04028v1 [] 15 Jan 2017

Using data-compressors for statistical analysis
of problems on homogeneity testing and
classification
Boris Ryabko

Andrey Guskov

Institute of Computational Technologies of SB RAS
Novosibirsk, Russian Federation

The State Public Scientific Technological
Library of SB RAS, Novosibirsk, Russian Federation

Irina Selivanova
The State Public Scientific Technological
Library of SB RAS, Novosibirsk, Russian Federation

Abstract—Nowadays data compressors are applied to
many problems of text analysis, but many such applications
are developed outside of the framework of mathematical
statistics. In this paper we overcome this obstacle and show
how several methods of classical mathematical statistics can
be developed based on applications of the data compressors.

keywords: data compression, hypothesis testing, homogeneity test, classification, universal code.
I. I NTRODUCTION
Data compression methods (or universal codes) were
discovered in the 1960’s and nowadays they are widely
used to compress texts for their storage or transmission.
In the last thirty years, it was recognized that data
compressors can be used for many purposes which are
far from file compaction. In particular, it was shown that
methods of data compression can be used for prediction
and hypothesis testing for time series in the framework of
classical mathematical statistics, see [15] and a review
there. Later, several authors applied data compressors
to problems which are close, in spirit, to homogeneity testing, estimation of correlation and covariance,
classifications, clustering and some others; see [3], [4],
[10], [11], [18]. The main idea of their approach can
be understood from the following example. Suppose
that there are three sequences of letters x1 x2 ...xn , y1
y2 ... yk , z1 z2 ...zm and a certain data-compressor ϕ.
The sequences x1 x2 ...xn , y1 y2 ... yk obey different
probability distributions, whereas z1 z2 ...zm obeys one of
them. The goal is to determine this distribution. (It is the
well-known “three samples problem”.) If x1 x2 ...xn and
z1 z2 ...zm obey the same probability distribution, then,
the sequence z1 z2 ...zm will be compressed better after
x1 x2 ...xn than after y1 ... yk . More precisely, if one

compresses sequences x1 x2 ...xn , y1 y2 ... yk and combined ones x1 x2 ...xn z1 z2 ...zm and y1 y2 ... yk z1 z2 ...zm ,
the difference |ϕ(x1 x2 ...xn z1 z2 ...zm )| − |ϕ(x1 x2 ...xn )|
will be less than |ϕ(y1 y2 ...yk z1 z2 ...zm )|−|ϕ(y1 y2 ...yk )|
(Here |U | is the length U .) For instance, let x1 x2 ...xn ,
z1 z2 ...zm be texts in English, whereas y1 y2 ... yk is
in German. Then the English text z1 z2 ...zm will be
compressed better after the text in the same language
(x1 x2 ...xn ) than after the text in German (y1 y2 ...yk ),
i.e. the first difference will be less than the second one.
This natural approach was used for diagnostic of the
authorship of literary and musical texts, for estimation
of closeness of DNA sequences, construction of phylogenetic trees and many other problems ( [3], [4],
[6], [10], [11], [18], [19]). Many papers (see [11] and
review there) were devoted to the measurement of the
interdependence between sequences (or the association,
similarity, closeness, etc.), because such measures plays
an important rule in clustering, classification and some
other methods of text analysis. It is important to note,
that their approaches are outside of the framework of
mathematical statistics and, in particular, do not give a
possibility to reason about consistency of estimates, tests,
classifiers, clustering, etc.
It is important that the modern data compressors
are based on so-called universal codes and the main
properties of universal codes are valid for them (as far
as asymptotic properties can be valid for a real computer
program). A formal definition of universal codes is
given in Appendix 1, but here we informally note that
universal codes can compress sequences generated by a
source with unknown statistics till its Shannon entropy,
which, in turn, is a lower limit on lossless compression.
Note that nowadays there are many classes of universal

III. T HE MAIN THEOREMS

codes which are based on different ideas and showed
their practical efficiency. Out of the most popular we
mention the PPM algorithm, which is used along with
the arithmetic code ( [1], [14]), Lempel-Ziv codes ( [20],
[21]), Borrows-Willer transformation ( [2], [12]) which
is used along with the “book stack” (or MTF) code (
[16], [17]) and some others (see for review ( [13], [15]).
In this paper we show how the idea of compression
of combined texts described above can be used for
solving problems of homogeneity testing, classification,
and estimation of a measure of interdependence, or the
association. A distinction of the suggested method from
other approaches is that it belongs to the framework of
mathematical statistics.

First we present a theorem which can be considered
as a theoretical basis for application of data compressors
for solving the problems described above. First, for two
words v1 ..vl and u1 ..us we define the following value:
|ϕ(v1 ..vl /u1 ..us )| = |ϕ(u1 ..us v1 ..vl )| − |ϕ(u1 ..us )|,
(1)
where s, l are integers. Informally, it is the length of the
codeword for v1 ..vl if it is encoded with the word u1 ..us .
Theorem 1. Let µx and µy be stationary ergodic sources
generating letters from a finite alphabet A and let their
memory be upper-bounded by a certain constant M .
Suppose that ...y−t y−t+1 ... y−1 y0 is generated by µy ,
whereas ...x−t x−t+1 ...x−1 x0 and w1 ...wm , m ≥ 1, are
generated by µx in such a way that all three sequences
are independent, and let ϕ be a universal code. Define

II. D EFINITIONS AND PROBLEM FORMULATIONS
First we briefly consider the main properties of socalled universal codes, paying the main attention to their
meaning whereas formal definitions of codes, stationary
ergodic sources and Shannon entropy are given in Appendix 1 and can be found in [5], [15].
Here we only note that we consider so-called lossless
codes ϕ which encode words over alphabet A using
words from the binary alphabet {0, 1} in such a way that
any word can be decoded without mistakes, i.e. there
exists a map ϕ−1 such that for any word w over A
ϕ−1 (ϕ(w)) = w. Let a code ϕ be applied to encode
sequences generated by a stationary ergodic source µ.
The value Rt (ϕ, µ) = 1t |ϕ(x1 ...xt )| − h∞ (µ) is called
the redundancy, where h∞ (µ) is the limit entropy, see
Appendix 1. (It is known that h∞ (µ) is an attainable
lower limit for lossless codes, that is why the difference
is called the redundancy.) By definition, the code ϕ is
called universal if the redundancy goes to 0 as t grows,
i.e. limt→∞ Rt (ϕ, µ) = 0 . (In other words, a universal
code compresses sequences generated by any stationary
ergodic source till the limit value.)
The main goal of the paper is to give a compressionbased solution for the following problems:
i) Homogeneity test, where there are several sequences
1
s
, ... y1s y2s ...ym
,
x11 x12 ...x1n1 , ..., xk1 xk2 ...xknk , y11 y21 ...ym
1
s
generated either by a single source or by two different
ones, and two corresponding hypotheses. We also consider the more general case where there are more than
two different sets of sequences.
ii) Classification problems, where there are samples
1
s
, ... y1s y2s ...ym
x11 x12 ...x1n1 , ..., xk1 xk2 ...xknk , y11 y21 ...ym
1
s
generated two different (but unknown) sources and
z1 ...zl is generated by one of the two. The goal is to
determine which of them generated z1 ...zl .
iii) Estimation of a so-called measurement of interdependence, or the association.

∆t,k,m = |ϕ(w1 ...wm /y−k y−k+1 ...y−1 y0 )|−
|ϕ(w1 ...wm /x−t x−t+1 ...x−1 x0 )|

(2)

where |ϕ(v1 ..vl /u1 ..us )| is defined in (1). Then there
exists such a constant λ and an integer m0 that for any
m > m0 there is such an integer L that, for any t >
m + L, k > m + L,
Eµx Eµy (∆t,k,m ) ≥ λ m + ◦(m) ,

(3)

and, if µx = µy then λ = 0, otherwise λ > 0. Here
Eν () is the expectation with respect to the measure ν.
The proof is given in Appendix 2, whereas here
we give some explanations of the theorem. The
theorem compares two cases: the word w1 ...wm is
compressed either together with x−t x−t+1 ...x−1 x0
or with y−k y−k+1 ...y−1 y0 . The word w1 ...wm is
generated by µx , hence, it should be compressed
better with x−t x−t+1 ...x−1 x0 and the value
|ϕ(w1 ...wt /x−t x−t+1 ...x−1 x0 )|(=
|ϕ(x−t x−t+1
... x−1 x0 w1 ...wt )|− |ϕ(x−t x−t+1 ...x−1 x0 )|) should be
less than |ϕ(w1 ...wt /y−k y−k+1 ...y−1 y0 )|. The theorem
shows, that, indeed, the word w1 ...wm is compressed
better together with x−t x−t+1 ...x−1 x0 if the lengths
of sequences w1 w2 ...wm , x−t x−t+1 ...x−1 x0 and
y−k y−k+1 ...y−1 y0 are sufficiently large.
Let there be two sets of sequences: X = { x11 x12 ...x1n1 ,
1
2 2
,
x1 x2 ...x2n2 , ..., xk1 xk2 ...xknk }, and Y = { y11 y21 ..., ym
1
2
s s
s
2 2
y1 y2 ...ym2 , ... y1 y2 ...yms }, generated by possibly different measures µx and µy . We consider two hypotheses
H0 = {µx = µy } and H1 = {µx 6= µy } and our goal
is to develop a statistical test for them using the sets
X and Y . First we give an informal description of the
suggested test, which will be based on data compression.
2

y, y ∗ ∈ Y the ratios |x|/|x∗ | and |y|/|y ∗ | are upperbounded by a certain constant, then, with probability 1,
the Type II error goes to 0.

Combine a half of the sequences from the set X into X ∗
bk/2c bk/2c
bk/2c
x2
...xnbk/2c
(say, x11 x12 ...x1n1 , x21 x22 ...x2n1 , ... , x1
2
1
, ...,
, y11 y22 ...ym
) and half of Y (say and y11 y21 ...ym
2
1
bs/2c bs/2c
bs/2c
∗
y1
y2
...ymbs/2c )) into Y . Then compress all other
sequences using a universal code ϕ along with X ∗ and
Y ∗ . If H0 is true, the values |ϕ(xi1 xi2 ...xini / X ∗ )| ,
j
i = bk/2c + 1, ..., k and |ϕ(y1j y2j ...ym
/ X ∗ )| , j =
j
bs/2c+1, ..., s should be evenly mixed. Otherwise, if H1
is true, then, on average, the numbers from the second
set should be larger than those from the first one, because the probability distributions of the sequences from
i
yji yji ...ym
and X ∗ are different, whereas the probability
j
distributions of the sequences xi1 xi2 ...xini and X ∗ are the
same (here and below |U | is the number of elements in
U ).
The test. A more formal description of the suggested
test is as follows: i) Denote the set X \ X ∗ by X̂ and
Y \ Y ∗ by Ŷ and calculate for any xi1 xi2 ...xini from X̂
the values
γi =

|ϕ(xi1 xi2 ...xini /Y ∗ )|

−

|ϕ(xi1 xi2 ...xini /X ∗ )|

The proof is given in Appendix 2, but here we give
some comments. First, note that there are many tests
of homogeneity for 2 × 2 tables and, in principle, any
of them can be used. That is why, we do not describe
the test Ψα on sizes of n1,1 , n1,2 , n2,1 , n2,2 . Second,
the described method can be easily extended from the
two-sample problem to the s-sample problem, s > 2.
Namely, let there be s, s > 2, sets V1 , V2 , ..., Vs of
sequences generated by stationary ergodic sources µ1 , µ2
..., µs . Let there be the hypotheses H0 = {µ1 = µ2
= ... = µs } and H1 = H̄0 . In this case we carry
out calculations based on the scheme described above
in order to obtain a so-called s × s table and then apply
a test for homogeneity, see ( [7]).
Measurement of the interdependence and association.
If the hypothesis of homogeneity is rejected, it is
natural to measure interdependence. We suggest to
measure interdependence between two sets of sequences
X and Y (and the corresponding sources) based on
the above described 2 × 2 tables. (In the case of
the s-sample problem, s > 2, the measures will be
based on the s × s table.) This problem is wellinvestigated in the mathematical statistics, see, for
example, ( [7], part 33). That is why, we mention such
measures only briefly. For 2 × 2 tables we mention the
coefficient of association, Q, defined by the equation
Q = (n1,1 n2,2 − n1,2 n2,1 )/n1,1 n2,2 + n1,2 n2,1 )
and
p the coefficient V = (n1,1 n2,2 − n1,2 n2,1 )/
(n1,1 + n2,2 )(n1,1 + n2,1 )(n1,2 + n2,2 )(n2,1 + n2,2 ),
see, ( [7], part 33). It is important to note that there are
well-known methods of building standard errors and
confidence interval for Q and V ( [7], part 33).

(4)

j
and for any y1j y2j ...ym
from Ŷ
j
j
j
δj = |ϕ(y1j y2j ...ym
/X ∗ )| − |ϕ(y1j y2j ...ym
/Y ∗ )| . (5)
j
j

Define
n1,1 = |{i : γi ≥ 0}|, n1,2 = |{i : γi < 0}|,
n2,1 = |{i : δi < 0}|, n2,2 = |{i : δi ≥ 0}| .

(6)

ii) Apply the test of the independence for the 2 × 2
table to
N2,2 =

n1,1
n2,1

n1,2
n2,2

.

A detailed analysis of this problem is carried out in [7],
part 33. In particular, there is a description of efficient
tests for homogeneity problem for the 2×2 table (see part
33.22). We denote this test as Ψα , where α is the level
of significance. Note, that there are some requirements
for values of n1,1 , n1,2 , n2,1 , n2,2 which should be valid
if Ψα is used (see [7]).

1
, ŵ2 =
Let there be sequences ŵ1 = w11 w21 ...wm
1
k
k
k k
..., ŵ = w1 w2 ...wmk , generated by
stationary ergodic sources ν1 , ..., νk , correspondingly,
where k ≥ 2. There is a new sequence û = u1 u2 ...un ,
n ≥ 2, and it is known beforehand that it is generated
by one of the sources from {ν1 , ..., νk }. The problem
of classification is to determine which source generated
the sequence û = u1 u2 ...un . By definition, a method of
classification is called asymptotically consistent if, with
probability 1, the method finds ν which generated the
sequence u1 u2 ...un when min(n, m1 , m2 , ..., mk ) goes
to infinity.
2
w12 w22 ...wm
,
2

Theorem 2. Let µx and µy be stationary ergodic measures whose memory is finite (but, possibly, unknown). If
the above described test is applied for testing H0 against
H1 along with the test Ψα and the requirements of Ψα
for values of n1,1 , n1,2 , n2,1 , n2,2 are valid, then for any
code ϕ the Type I error is not grater than α.
If ϕ is a universal code, |X| and |Y | go to infinity
and the lengths of all sequences from X and Y go to
infinity in such a way that for all sequences x, x∗ ∈ X,

Method of classification. We suggest the following method of classification: decide that the sequence
3

where P (b) and Q(b) are probability distributions over
alphabet B. It is known that for any distributions P and
Q the KL divergence is nonnegative and equals 0 if and
only if P (a) = Q(a) for all a .
Let us describe universal codes, or data compressors.
(A detailed description can be found, for example, in
[15].) First we note that (as is known in Information
Theory) sequences generated by a source p can be
”compressed” on average till the limit Shannon entropy
h∞ (p) and, on the other hand, there is no code ψ for
which the expected codeword length is less than h∞ (p);
see [5]. As defined above, a code ϕ is universal if it
compresses till this limit. We will consider universal
codes which can be applied to any word x1 ...xs , n > 0,
from a certain alphabet A and such that the following
natural property is valid: for any words u, v, |v| > 0,

u1 u2 ...un was generated the source νj for which
i
j = arg min |ϕ(u1 u2 ...un /w1i w2i ...wm
)| .
k
i=1,...,k

(7)

Theorem 3. Let ν1 , ..., νk be stationary ergodic measures whose memories are finite (but, possibly, unknown).
If ϕ is a universal code and the lengths of all sequences
û, ŵ1 , ŵ2 , ..., ŵk go to infinity in such a way that
lim |û|/ min |ŵj | = 0 ,

|û|→∞

j

(8)

then the described method is asymptotically consistent.
IV. A PPENDIX 1
Let τ be a stationary ergodic source generating letters
from a finite alphabet A. (Definitions can be found in
[5].) The m− order (conditional) Shannon entropy and
the limit Shannon entropy are defined as follows:
X
X
τ (v)
hm (τ ) = −
τ (a| v) log τ (a| v),
v∈Am

|ϕ(uv)| − |ϕ(u)| > 0 .

a∈A

h∞ (τ ) = lim hm (τ ).
m→∞

For any universal code ϕ we define a measure πϕ as
follows:

(9)

It is known that for any integer m
hm (τ ) ≥ hm+1 (τ ) ≥ h∞ (τ ),

(13)

πϕ (x1 x2 ...xt ) = 2−|ϕ(x1 x2 ...xt )| ,
(10)

(14)

where x1 x2 ...xt is a word over A. It is known that for
any t
X
πϕ (u) = 1 ,
(15)

see [5]. Now we define codes. Let A∞ be the set of
all infinite words x1 x2 . . . over the alphabet A. A data
compression method (or code) ϕ is defined as a set
of mappings ϕn such that ϕn : An → {0, 1}∗ , n =
1, 2, . . . and for each pair of different words x, y ∈ An
ϕn (x) 6= ϕn (y). Informally, it means that the code ϕ
can be applied for compression of each message of any
length n over the alphabet A and the message can be
decoded if its code is known. It is also required that each
sequence ϕn (u1 )ϕn (u2 )...ϕn (ur ), r ≥ 1, of encoded
words from the set An , n ≥ 1, can be uniquely decoded
into u1 u2 ...ur . Such codes are called uniquely decodable. For example, let A = {a, b}, the code ψ1 (a) =
0, ψ1 (b) = 00, obviously, is not uniquely decodable. It
is well known that if a code ϕ is uniquely decodable
then the lengths of the codewords satisfy the following
inequality (Kraft inequality): Σu∈An 2−|ϕ(u)| ≤ 1 ,
see, for ex., [5]. Moreover, if the sum Σu∈An 2−|ϕ(u)|
is less than 1, there exists such a code ϕ∗ that i)
∗
Σu∈An 2−|ϕ (u)| = 1 , and |ϕ∗ (u)| ≤ |ϕ(u)| for any
word u, [5]. (Informally, it means, that ϕ∗ compresses
better.) So, we can consider only codes for which

Note that this equation shows that the code ϕ estimates
the (unknown) probability precisely, where T grows.

Σu∈An 2−|ϕ(u)| = 1 .

V. A PPENDIX 2: PROOFS

u∈At

(see the Kraft inequality and (11)).
Now we consider an application of universal codes (or
data compressors) which is the main tool for solving the
problems mentioned in Introduction. From (1) and (14)
we immediately obtain that
|ϕ(v1 ..vl /u1 ..us )| = − log(πϕ (v1 ..vl |u1 ..us ))

(16)

and the right part is defined correctly, see (13). The
following property of universal codes will play an important role in what follows. Let µz be a stationary
ergodic source generating letters from an alphabet A
and ϕ be a universal code. For any integer m ≥ 1 and
w1 ...wm ∈ Am with probability 1
lim log

T →∞

(11)

We will use a so-called Kullback-Leibler (KL) divergence, which is defined by
X
P (b)
,
(12)
D(P ||Q) =
P (b) log
Q(b)

πϕ (w1 w2 ...wm |z−T ...z0 )
= 0.
µz (w1 w2 ...wm |z−T ...z0 )

(17)

Proof of Theorem 1. First we prove the following
Claim.
X
Eµx Eµy
µx (w1 w2 ...wm )
w1 w2 ...wm

b∈B

4

µx (w1 ...wm |x−t x−t+1 ...x0 )
= (m − M )λ + O(1) ,
µy (w1 ...wm |y−k y−k+1 ...y0 )
(18)
where M is a upper bound of memories of µx and µy ,
and λ is such a constant that λ = 0 if µx = µy and
λ > 0 otherwise.
Proof of the claim. The left side can be presented as
follows:
X
Eµx Eµy
µx (w1 w2 ...wm )

X

+... +

log

w1 ...wM

µx ((wM +1 |w1 ...wM )
µy ((wM +1 |w1 w2 ...wM )
X
+Eµx Eµy (
µx (w1 w2 ...wM −1 )
w1 w2 ...wM −1

X

µx (w1 ...wm |x−t x−t+1 ...x0 )
=
µy (w1 ...wm |y−k y−k+1 ...y0 )
X
Eµx Eµy (
µx (w1 w2 ...wm−1 )

µx ((wM |x0 w1 w2 ...wM −1 )
+ ...
µy ((wM |y0 w1 w2 ...wM −1 )

log
+

X

µx (w1 ) log

w1

w1 w2 ...wm−1

µx (w1 |x−M +1 x−M +2 ...x0 )
) . (20)
µy (w1 |y−M +1 y−M +2 ...y0 )

For any function ψ(ue+1 , ..., ue+b ) and any measure
ν(u1 u2 ...ue ue+1 ...ue+b )
X
ν(u1 u2 ...ue ue+1 ...ue+b )

µx (wm |w1 w2 ...wm−1 )

wm

µx (wm |x−t x−t+1 ...x0 w1 w2 ...wm−1 )
µy (wm |y−k y−k+1 ...y0 w1 w2 ...wm−1 )
X
+
µx (w1 w2 ...wm−2 )

u1 u2 ...ue ue+1 ...ue+b

ψ(ue+1 , ..., ue+b )
=

w1 w2 ...wm−2

X

µx (wM |x0 w1 w2 ...wM −1 )

wM

log

log

µx (wM +1 |w1 ...wM )

wM +1

log

w1 w2 ...wm

X

X

µx (w1 ...wM )

X

ν(ue+1 ...ue+b )ψ(ue+1 , ..., ue+b ) ,

ue+1 ...ue+b

µx (wm−1 |w1 w2 ...wm−2 )

where e and b are integers. Having taken into account
this equation, stationarity µx and µy , equations (V), (V)
and (V), we obtain
X
Eµx Eµy
µx (w1 w2 ...wm )

wm−1

µx (wm−1 |x−t x−t+1 ...x0 w1 w2 ...wm−2 )
µy (wm−1 |y−k y−k+1 ...y0 w1 w2 ...wm−2 )
X
µx (w1 |x−t x−t+1 ...x0 )
+... +
µx (w1 ) log
) . (19)
µ
y (w1 |y−k y−k+1 ...y0 )
w
log

w1 w2 ...wm

µx (w1 ...wm |x−t x−t+1 ...x0 )
=
µy (w1 ...wm |y−k y−k+1 ...y0 )
X
(m − M )
µx (w1 w2 ...wM )

1

log

It is supposed that the memory of µx and µy is
upper-bounded by M . Hence, by definition, it means
that µr (v|ui ui+1 ...uj ) = µr (v|uj−M +1 uj−M +2 ...uj ),
where j ≥ i+M −1. From this equation and the previous
one we obtain the following equation:
X
Eµx Eµy
µx (w1 w2 ...wm )

w1 w2 ...wm−2

X

µx (wM +1 |w1 w2 ...wM )

wM +1

w1 w2 ...wm

log

µx ((wM +1 |w1 w2 ...wM )
+ O(1) .
µy ((wM +1 |w1 w2 ...wM )

µx (w1 ...wm |x−t x−t+1 ...x0 )
=
µy (w1 ...wm |y−k y−k+1 ...y0 )
From properties of K-L divergence (see (12) ) we can
X
X
see that λ > 0 if µx 6= µy and, obviously, λ = 0, if
µx (w1 w2 ...wm−1 )
µx (wm |w1 w2 ...wm−1 )
µx = µy . The claim is proven.
w1 w2 ...wm−1
wm
Let us proceed with proof of the theorem. Having
µx (wm |wm−M ...wm−1 )
taken into account the definitions (16) and (1), we obtain
log
that
µy (wm |wm−M ...wm−1 )
X
X
Eµx Eµy (∆t,k,m ) =
+
µx (w1 ...wm−2 )
µx (wm−1 |w1 ...wm−2 )
X
X
X
log

w1 ...wm−2

wm−1

u−t u−t+1 ...u0 ∈At+1 v−k v−k+1 ...v0 ∈Ak+1 w1 w2 ...um ∈Am

µx (wm−M −1 ...wm−2 )
log
µy (wm−M −1 ...wm−2 )

µy (v−k v−k+1 ...v0 )µx (u−t u−t+1 ...u0 )µx (w1 w2 ...um )
5

log

πϕ (w1 ...wm |u−t u−t+1 ...u0 )
.
πϕ (w1 ...wm |v−k v−k+1 ...v0 )

[5] Cover, T. M., Thomas, J. A., 2006. Elements of information
theory. Wiley-Interscience, New York, NY, USA.
[6] Ferragina, P., Giancarlo, R., Greco, V., Manzini, G., Valiente, G.,
2007. Compression-based classification of biological sequences
and structures via the universal similarity metric: experimental
assessment. BMC bioinformatics 8 (1), 1.
[7] Kendall, M., Stuart, A., 1961. The advanced theory of statistics;
Vol.2: Inference and relationship. London.
[8] Khmelev, D. V., Teahan, W. J., 2003. A repetition based measure
for verification of text collections and for text categorization.
In: Proceedings of the 26th annual international ACM SIGIR
conference on Research and development in informaion retrieval.
ACM, pp. 104–110.
[9] Kieffer, J. C., Yang, E.-H., 2000. Grammar-based codes: a new
class of universal lossless source codes. IEEE Transactions on
Information Theory 46 (3), 737–754.
[10] Kukushkina, O. V., Polikarpov, A., Khmelev, D. V., 2001. Using literal and grammatical statistics for authorship attribution.
Problems of Information Transmission 37 (2), 172–184.
[11] Li, M., Chen, X., Li, X., Ma, B., Vitányi, P. M., 2004. The similarity metric. IEEE transactions on Information Theory 50 (12),
3250–3264.
[12] Manzini, G., 2001. An analysis of the burrowswheeler transform.
Journal of the ACM (JACM) 48 (3), 407–430.
[13] Rissanen, J., Jul. 1984. Universal coding, information, prediction,
and estimation. Information Theory, IEEE Transactions on 30 (4),
629 – 636.
[14] Rissanen, J., Langdon, G. G., 1979. Arithmetic coding. IBM
Journal of research and development 23 (2), 149–162.
[15] Ryabko, B., Astola, J., Malyutov, M., 2016. Compression-Based
Methods of Statistical Analysis and Prediction of Time Series.
Springer.
[16] Ryabko, B. Y., 1980. Data compression by means of a book stack.
Problemy Peredachi Informatsii 16 (4), 16–21.
[17] Ryabko, B., Horspool, N. R., Cormack, G. V., Sekar, S., Ahuja,
S. B., 1987. Technical correspondence. Communications of the
ACM 30 (9), 792–797.
[18] Teahan, W. J., Harper, D. J., 2003. Using compression-based
language models for text categorization. In: Language modeling
for information retrieval. Springer, pp. 141–165.
[19] Vitányi, P. M., 2011. Information distance in multiples. IEEE
Transactions on Information Theory 57 (4), 2451–2456.
[20] Ziv, J., Lempel, A., 1977. A universal algorithm for sequential
data compression. IEEE Transactions on information theory
23 (3), 337–343.
[21] Ziv, J., Lempel, A., 1978. Compression of individual sequences
via variable-rate coding. IEEE Transactions on Information Theory 24, 530–536.

(21)

The following equation is obvious:
log

πϕ (w1 ...wm |u−t u−t+1 ...u0 )
=
πϕ (w1 ...wm |v−k v−k+1 ...v0 )

log

µx (w1 ...wm |u−t u−t+1 ...u0 )
+
µy (w1 ...wm |v−k v−k+1 ...v0 )

log

πϕ (w1 ...wm |u−t u−t+1 ...u0 )
+
µx (w1 ...wm |u−t u−t+1 ...u0 )

log

µy (w1 ...wm |v−k v−k+1 ...v0 )
.
πϕ (w1 ...wm |v−k v−k+1 ...v0 )

(22)

The first term is estimated in the claim, see (V), whereas
the second and the third terms can be estimated based on
(17). So, from the claim and (17), we can see that, with
probability 1, Eµx Eµy (∆t,k,m ) = (m − M )λ + O(1) .
The theorem is proven.
Proof of the Theorem 2. First we consider the case
where H0 is true. It means that the sequences from X̂
and Ŷ obey the same distribution. Hence, γi (4) and
δj (5) have the same distribution, too, and the above
mentioned test Ψα from [7], part 33, can be applied.
Now we consider the case where H1 is true. In this
case the length of any sequence grows, so, the length
will be grater than m0 from Theorem 1. The number
of sequences grows to infinity and the total length of a
half of them goes to infinity in such a way that for any
integer L the total length will be grater than the sum
m + L from Theorem 1. From this theorem we can see
that n1,2 and n2,1 goes to 0 and, hence, the Type II error
goes to 0.
Proof of the Theorem 3. Suppose, that the sequence
u1 u2 ...un was generated by νj . Then, we can see
from Theorem 1 that, with probability 1, the value
i
|ϕ(u1 u2 ...un /w1i w2i ...wm
)| grows as λi n + ◦(n), λi >
k
i i
i
0, if i 6= j, (i.e. w1 w2 ...wm
) is generated by νi ). On
i
i
the other hand, |ϕ(u1 u2 ...un /w1i w2i ...wm
)| = ◦(n).
k
i
i
i
Hence, |ϕ(u1 u2 ...un / w1 w2 ... wmi )| is minimal when
i = j (i.o., u1 u2 ...un is generated by νj ). The theorem
is proven.
R EFERENCES
[1] Bell, T., Witten, I. H., Cleary, J. G., 1989. Modeling for text
compression. ACM Computing Surveys (CSUR) 21 (4), 557–
591.
[2] Burrows, M., Wheeler, D. J., 1994. A block-sorting lossless data
compression algorithm.
[3] Cilibrasi, R., Vitanyi, P., 2005. Clustering by compression. IEEE
Transactions on Information Theory 51, 1523–1545.
[4] Cilibrasi, R., Vitányi, P., De Wolf, R., 2004. Algorithmic clustering of music based on string compression. Computer Music
Journal 28 (4), 49–67.

6

