en opy
A icle
P edic ion and E alua ion o Ze o O de En opy
Changes in G amma -Based Codes
Michal Vasinek * and Jan Pla os
Depa men o Compu e Science, FEECS, VSB-Technical Uni e si y o Os a a, 17. lis opadu 15/12172,
Os a a 708 33, Czech Republic; [email p o ec ed]
*Co espondence: [email p o ec ed]; Tel.: +420-597-323-971
Academic Edi o : Raúl Alca az Ma ínez
Recei ed: 30 Janua y 2017; Accep ed: 10 May 2017; Published: 13 May 2017
Abs ac :
The change o ze o o de en opy is s udied o e di e en s a egies o g amma p oduc ion
ule selec ion. The wo majo ules a e dis inguished: ans o ma ions lea ing he message size in ac
and subs i u ion unc ions changing he message size. Rela ions o ze o o de en opy changes
we e de i ed o bo h cases and condi ions unde which he en opy dec eases we e desc ibed.
In his a icle, se e al di e en g eedy s a egies educing ze o o de en opy, as well as message
sizes a e summa ized, and he new s a egy MinEn is p oposed. The esul ing e olu ion o he
ze o o de en opy is compa ed wi h a s a egy o selec ing he mos equen dig am used in he
Re-Pai algo i hm.
Keywo ds: da a comp ession; g amma s; en opy; ans o ma ions; con ex ; Re-Pai
1. In oduc ion
En opy is a key concep in he measu emen o he amoun o in o ma ion in in o ma ion
heo y [
1
]. F om he da a comp ession pe spec i e, his amoun o in o ma ion ep esen s he lowe
limi o he achie able comp ession o some in o ma ion sou ce. Due o he well-known wo k by
Shannon [
2
], we know ha using less bi s han he amoun gi en by en opy o ep esen a pa icula
message o p ocess would necessa ily lead o he loss o some in o ma ion and as a consequence ou
inabili y o p ope ly eco e he o me s uc u e o he message.
This wo k is ocused on he s udy o en opy in da a comp ession, and he e o e, ou discussion
will be es ic ed o only ini e messages. These ini e messages a e o med by symbols, and in his
pe spec i e, he en opy can be unde s ood as he lowes numbe o bi s needed on a e age o uniquely
ep esen each symbol in a message. The e a e messages o which he e alua ion o en opy can be a
e y ha d ask, and so, we a e o en o ced o sa is y ou sel es wi h some app oxima ion o en opy.
The simples app oxima ion is he one based on he p obabili y dis ibu ion o symbols in
a pa icula message. In his case, he symbols a e iewed as independen en i ies, and hei
mu ual ela ionships a e no aken in o accoun . A be e app oxima ion o en opy is based on
he condi ional p obabili ies when we also ake in o accoun how symbols ollow each o he . We can
also app oxima e en opy by compu ing bi s pe by e a io o message encoded by s a e o he a da a
comp ession algo i hms.
In his a icle, we s udy en opy a he le el o independen symbols. This app oxima ion o
en opy is o en called ze o o de en opy. The e a e wo majo da a comp ession algo i hms in use
ha comp ess messages almos o he a e gi en by ze o o de en opy: Hu man [
3
] and a i hme ic [
4
]
coding. The ze o o de en opy can be compu ed using he Shannon equa ion:
H(X) = −∑
x∈Σ
p(x)log p(x)(1)
En opy 2017,19, 223; doi:10.3390/e19050223 www.mdpi.com/jou nal/en opy
En opy 2017,19, 223 2 o 23
whe e
X
s ands o a andom a iable ep esen ing he p obabili y dis ibu ion o symbols in he inpu
message
m
and
p(x)
is he p obabili y o symbol
x
om alphabe
Σ
. The expec ed leng h o he code
o he pa icula symbol
x
is gi en by
−log p(x)
. I he expec ed leng h o he code is mul iplied by
i s p obabili y, we ob ain he a e age numbe o bi s needed o ep esen any symbol
x∈Σ
. The size
o he message using he expec ed leng hs o codes is gi en as a p oduc o he leng h o he message
|m|measu ed as a numbe o symbols and ze o o de en opy:
|m|H=|m|H(X)(2)
When we e e o he e m en opic size o he message, we always mean he quan i y gi en by
Equa ion (2), and i will be deno ed using a supe sc ip as
|m|H
. We s udy how he en opic size o he
message e ol es when all occu ences o some
m
-g am a e subs i u ed o some o he
n
-g am and ice
e sa. We s udy wo such subs i u ions: ans o ma ions and comp ession unc ions. T ans o ma ions
eplace
n
-g ams o he same leng h. T ans o ma ion lea es he message size in ac , bu since he
p obabili y o symbols changes, he alue o ze o o de en opy also has o change. Comp ession
unc ions eplace
m
-g ams o
n
-g ams, whe e
m>n
, and lea e he message size smalle , bu he
change in ze o o de en opy also occu s.
The main idea behind he concep o ans o ma ions is he ollowing: conside Hu man coding;
mo e p obable symbols a e encoded by sho e o a leas by he same leng h p e ix codes han he
lowe p obabili y ones, i he symbol
β
is mo e p obable han he symbol
γ
, bu in he con ex o some
symbol
α
,
γ
is mo e equen han
β
, hen i hese symbols ollowing
α
a e exchanged, he longe
codes used o encoding
γ
will ins ead be encoded by sho e codes ep esen ing he encoding o
β
. Unde his assump ion, i is possible o p e-p ocess da a so ha he equency o mo e equen
symbols inc eases and he equency o less equen symbols dec eases.
1.1. No a ion and Te minology
•The alphabe o he inpu message mo he size |m|is deno ed by Σand i s size by |Σ|.
•
G eek symbols a e used o deno e a iables ep esen ing symbols in he inpu message.
Fo ins ance, suppose wo dig ams
αα
,
αβ
and he alphabe
Σ={
0, 1
}
. Then,
αα ∈ {
00, 11
}
and
αβ ∈ {00, 01, 10, 11}.
•
When we e e o he e m en opy, we always mean Shannon’s en opy de ined by Equa ion (1).
•All loga i hms a e o base wo.
•
Any quan i y
Qi
wi h a subsc ip
i∈N
deno es consecu i e s a es o he quan i y be ween
subs i u ions. Fo ins ance, a quan i y
Q0
is a alue o he quan i y be o e any subs i u ion is
applied, and Q1is a alue o he quan i y a e some subs i u ion is applied.
1.2. O de o Con ex and En opy
1.2.1. Ze o O de Con ex
When all symbols a e in e p e ed as independen indi idual en i ies and no p edecesso s a e
aken in o conside a ion, such a case is called ze o o de con ex . Ze o o de en opy is hen compu ed
as Shannon’s en opy o a andom a iable gi en by he p obabili ies o symbols in he inpu message.
1.2.2. N- h O de Con ex
In a case whe e he p obabili y dis ibu ion o symbols ollowing a pa icula ixed leng h p e ix
w
is aken in o conside a ion, hen i he leng h o he p e ix is
N
, hen he o de o con ex is
N
, and he
N- h o de en opy is compu ed as Shannon’s en opy o he condi ional dis ibu ion o symbols
ollowing all di e en p e ixes wi.
En opy 2017,19, 223 3 o 23
2. P e ious Wo k
The class o algo i hms dealing wi h exchanges o di e en
n
,
m
-g ams a e called g amma -based
algo i hms. Thei pu pose is o p o ide a se o p oduc ion ules in e ing he con en o he message.
Using he Chomsky hie a chy, we iden i y wo classes o o mal g amma s used in da a comp ession:
con ex - ee g amma s (CFG) and con ex -sensi i e g amma s (CSG). Con ex ans o ma ions
p esen ed in Sec ion 3belong o he CSG class; meanwhile, comp ession unc ions belong o he
CFG class. The p oblem o he sea ch o he mos compac con ex - ee g amma ep esen a ion o a
message is NP-ha d, unless
P=NP
[
5
]. Ins ead o sea ching o he op imal solu ion, many heu is ic
and g eedy algo i hms we e p oposed.
CFGs o da a comp ession we e i s discussed by Ne ill-Manning [
6
] ollowed by he p oposal
o he SEQUITUR algo i hm [
7
]. SEQUITUR eads he sen ence in he le - igh manne so ha each
epea ed pa e n is ans o med in o a g amma ule. The g amma is u ilized in such a way ha he
wo p ope ies a e ul illed: a dig am uniqueness (no pai o adjacen symbols appea mo e han once
in he g amma and a ule u ili y); e e y ule is used mo e han once. Kie e and Yang [
8
] we e he i s
who add essed da a comp ession using CFGs om he in o ma ion heo e ic pe spec i e; hey showed
ha he LZ78 [
9
] algo i hm can be in e p e ed as a CFG and ha he p oposed BISECTION algo i hm
o ms a g amma -based uni e sal lossless sou ce code. BISECTION epea edly hal es he ini ial
message in o unique ph ases o leng h 2k, whe e kis he in ege .
In he wo k o Yang and He [
10
], he con ex -dependen g amma s (CDG) o da a comp ession
we e in oduced. In CSG, he con ex is p esen in bo h sides o p oduc ion ules; meanwhile in CDG,
he con ex is de ined only on he le side o he p oduc ion ule.
One o he i s concep s in g eedy g amma -based codes was he by e pai encoding (BPE) [
11
].
The BPE algo i hm selec s he mos equen dig am and eplaces i wi h some unused symbol.
The main weakness o his app oach is ha he algo i hm is limi ed o an alphabe consis ing only o
by e alues. The concep o by e pai encoding was la e e ised, and he limi a ion on he alphabe
size used was gene alized independen ly by Nakamu a and Mu ashima [
12
] and by La sson and
Mo a [
13
]; he esul ing app oach is called Re-Pai [
13
]. Re-Pai s ands o ecu si e pai ing, and i is
a e y ac i e ield o esea ch [
14
,
15
]. I i e a i ely eplaces he mos equen dig ams wi h unused
symbols un il he e is no dig am ha occu s mo e han once.
Unlike BPE ha codes dig ams using only by e alues, Re-Pai expec s ha he symbols o he
inal message will be encoded using some en opy coding algo i hm. App oaches de i ed om Re-Pai
a e usually g eedy, since each i e a ion o he algo i hm is dependen on a success ul sea ch o he
ex emal alue o some s a is ical quan i y ela ed o he inpu message. The s udy o he Re-Pai
om he pe spec i e o e godic sou ces is discussed in [
16
,
17
]. Nei he BPE no Re-Pai comp ess he
message in o he leas possible size, bu hey a he o m a ade-o be ween message and dic iona y
sizes. Re-Pai -like algo i hms a e o -line, in he sense ha hey need mo e han one pass h ough he
inpu message; meanwhile, SEQUITUR inc emen ally builds he g amma in a single pass. The Re-Pai
algo i hm is an algo i hm wi h O(n) ime complexi y; i is easy o implemen using linked lis s and a
p io i y queue. Fu he , i was shown in [
18
] ha i can comp ess an inpu message o leng h
n
o e an
alphabe o size |Σ|in o a mos 2Hk+o(nlog |Σ|)bi s, whe e Hkis k- h o de en opy.
Ou ecen s udies we e ocused on a special class o g amma ans o ms ha lea e he message
size in ac [
19
,
20
]. In he p esen pape , he class o g amma ans o ma ions is ex ended wi h a no el
concep o highe o de con ex ans o ma ion [
21
]. We shall p o ide examples o ans o ma ions and
he e alua ion o en opy esp. en opic size educ ion o he class o g amma comp ession algo i hms,
and we compa e he e olu ion o en opy, en opic size and he esul ing numbe o dic iona y en ies
o Re-Pai and ou e sion o Re-Pai , called MinEn , which is based on he selec ion o he pai o
symbols educing he en opic size o he message he mos . Re-Pai inds applica ion in a eas such
as sea ching in comp essed da a [
22
], comp ession o su ix a ays [
23
] o comp ession o in e ed
indexes [
24
], o name a ew. These a eas a e also na u al applica ion ields o MinEn . F om he
En opy 2017,19, 223 4 o 23
pe spec i e o he numbe o passes h ough he message, he app oaches discussed in his pape
belong o o -line algo i hms.
3. T ans o ma ions and Comp ession Algo i hms
In his sec ion, we will desc ibe and e alua e se e al in e ible ans o ma ions
T
and subs i u ion
unc ions
F
so ha o any wo consecu i e s a es o he message,
m0
and
m1
, be o e and a e
applica ion o To F, he ollowing ela ion holds:
|m1|H<|m0|H(3)
The measu e o he size o he message by he en opic size o he message is p e e ed, since using
he a i hme ic coding, one can achie e a comp ession a e e y close o he ze o o de en opy, and so,
he size
|m|H
is in heo y accessible. Fu he , i allows he compa ison o wo dis inc subs i u ions
when hei esul ing sizes measu ed by he numbe o symbols a e equal. The de i a ion o equa ions
o he compu a ion o |m1|H, esp. ∆|m|H=|m0|H− |m1|H, a e p o ided in Sec ion 4.
3.1. T ans o ma ions
Conside ans o ma ion, whe e we eplace all occu ences o some symbol
β
o some symbol
γ
and ice e sa; such a ans o ma ion is called a symme y ans o ma ion, because i does no modi y
any measu able quan i ies ela ed o he amoun o in o ma ion. The in o ma ion con en is changed
when he eplacemen is aken in he con ex o an o he symbol
α
. Such a ans o ma ion co esponds
o he exchange o all dig ams
αβ
o
αγ
and ice e sa. In his sec ion, se e al di e en o ms o
ans o ma ion a e dis inguished and b ie ly desc ibed. Some p ope ies o ans o ma ions and hei
p oo s can be ound in Appendix A.
3.1.1. Con ex T ans o ma ion
The concep o con ex ans o ma ions was i s p oposed in [
25
], and he esul s we e p esen ed
in [
19
]. I is he simples ans o ma ion ha assumes a pai o dig ams beginning wi h he same
symbol when one o he dig ams is ini ially missing in he inpu message.
De ini ion 1.
Con ex ans o ma ion (CT) is a mapping
CT(αβ →αγ
,
w):Σn→Σn
ha eplaces all dig ams
αβ o αγ, whe e p(α,γ) = 0and β6=γ.Σis he alphabe o he inpu message w, and n is he leng h o w.
Le
CT←
be he con ex ans o ma ion applied om he end o he message o he beginning and
CT→
in he opposi e di ec ion. The con ex ans o ma ion
CT→
is an in e se ans o ma ion o
CT←
.
The p oo o his p ope y wi h an explana ion o why i is he only pai o he unc ion and i s in e se
is le o Appendix A. The applica ion o wo consecu i e con ex ans o ma ions and hei in e se
unc ions is p esen ed in he ollowing example:
Example 1.
abcdabacd|CT←(ab →aa)
aacdaaacd|CT←(cd →cc)
aaccaaacc|CT→(cc →cd)
aacdaaacd|CT→(aa →ab)
abcdabacd|
En opy 2017,19, 223 5 o 23
3.1.2. Gene alized Con ex T ans o ma ion
Con ex ans o ma ions we e es ic ed in cases whe e one o he dig ams was missing in he inpu
message. This es ic ion is emo ed by he in oduc ion o he gene alized con ex ans o ma ions
i s p oposed in [20].
De ini ion 2.
Gene alized con ex ans o ma ion (GCT) is a mapping
GCT(αβ ↔αγ
,
w):Σn→Σn
ha
exchanges all occu ences o a dig am
αβ
by a dig am
αγ
and ice e sa.
Σ
is he alphabe o he inpu message
w, and n is he leng h o w.
Example 2.
aabcabab|GCT←(ab ↔aa)
abacaaaa|GCT→(aa ↔ab)
aabcabab
Meanwhile, bo h ans o ma ions
CT
and
GCT
swap occu ences o wo di e en dig ams
beginning wi h he same symbol; hey di e in he way hey a e applied and how he in e se
ans o ma ion is o med.
GCT
can be applied in bo h di ec ions, and he in e se ans o ma ion
GCT−1
is always applied in he opposi e di ec ion, han he o wa d ans o ma ion di ec ion.
The algo i hm based on he CT and GCT wo ks as ollows:
1.
Find and apply ans o ma ion
T
so ha he change o he en opic size
∆|m|H=|m0|H− |m1|H
is maximal.
2. Repea S ep 1 un il no ans o ma ion can dec ease he en opic size o he message.
I is also possible o de ine a ans o ma ion and i s in e se so ha all symbols cons i u ing eplaced
pai s di e , o ins ance
ab ↔cd
; such a ans o ma ion is called gene ic ans o ma ion
GT
. In his
a icle, we ha e no p oposed algo i hms based on
GT
, bu because he se o all gene alized con ex
ans o ma ions is a subse o a se o gene ic ans o ma ions, he p oo o he in e se ans o ma ion
exis ence is he same o bo h GCT and GT. The eade can ind he p oo in Appendix A.
3.1.3. Highe O de Con ex T ans o ma ion
E e y ime we apply any gene alized con ex ans o ma ion
GCT
, we acqui e knowledge abou
he posi ions o wo dis inc dig ams in he message. We can ei he disca d his knowledge o we can
y o build on i . In he ollowing de ini ion, we de ine a ans o ma ion ha is applied o e posi ions
whe e some o he ans o ma ion was applied be o e:
De ini ion 3.
Le
P(w
,
m)
be a se o posi ions o he i s symbol ollowing he sub-message
w
in he message
m
and
w[i]6=w[
0
]
,
i>
0. I
β
,
γ6=w[
0
]
, hen he highe o de con ex ans o ma ion (HOCT) is a
mapping
HOCT(wβ↔wγ
,
m
,
P(w
,
m)) :Σn→Σn
ha exchanges all sub-messages
wβ
o sub-messages
wγand ice e sa.
The es ic ion ha he sub-message
w
has o sa is y is
w[
0
]6=w[i]
, whe e
i>
0 is closely ela ed
o he exis ence o he in e se ans o ma ion o
HOCT
. The p ope ies ela ed o he
HOCT
and hei
p oo s a e le o Appendix A.
Le
O=|w|
be he size o he sub-message
w
om De ini ion 3, hen
O
is an o de o
HOCT
.
Any
GCT(αβ ↔αγ)
is hen he i s o de
HOCT(αβ ↔αγ
,
m
,
P(α
,
m))
. Gi en ha we jus be o e
applied some ans o ma ion
m1=HOCT1(wβ↔wγ
,
m
,
P(w
,
m))
, we can decide o collec he
posi ions o ei he
w1=wβ
o
w2=wγ
, collec he dis ibu ion o symbols in
P(wi
,
m)
and apply
ano he
HOCT(wiρ↔wiϕ
,
m1
,
P(wi
,
m))
. In his sense,
HOCT
is no used only o in e change di e en

En opy 2017,19, 223 6 o 23
sub-messages, bu i also allows one o p oceed wi h some o he ans o ma ion
HOCT
o a highe o de .
The applica ion o wo consecu i e HOCT ans o ma ions is p esen ed in he ollowing example:
Example 3.
abcdabcd|HOCT(ab ↔ad,P(a,m) = {1, 5})
adcdadcd|HOCT(adc ↔add,P(ad,m) = {2, 6}))
adddaddd|
The
HOCT
ans o ma ion is a ecu si e applica ion o
GCT
in he con ex o some p e ix
w
.
The s eps o he algo i hm a e ou lined as ollows:
1.
Find and apply
HOCT(αβ ↔αγ)
o e he se o posi ions
P(α)
, so ha he change o en opic
size ∆|m|H=|m0|H− |m1|His maximal and ∆|m|H>Lim.
2.
I he equency o
αβ
esp.
αγ
is la ge han one, hen epea S ep 1 o e he se o posi ions
P(αβ)
esp.
P(αγ)
, i.e., posi ions whe e
HOCT
om S ep 1 was applied; o he wise, epea S ep 1
o e posi ions P(α)o e u n i no mo e HOCT passes he en opic size educ ion condi ions.
The algo i hm abo e is i e a i ely called o symbols so ed om he mos equen one o he leas
equen one. The
Lim
a iable can be used o es ic ans o ma ions whose en opic size educ ion is
oo small, so hey canno be e icien ly s o ed in he dic iona y.
3.2. Comp ession Func ions
In he p eceding sec ion, we desc ibed h ee ypes o ans o ma ions ha lea e message size
in ac . In his sec ion, we will ocus on a desc ip ion o wo app oaches in he eplacemen o dig ams
o a new symbol. Fi s , we desc ibe basic p inciples o he well-known algo i hm Re-Pai , and hen,
we will p opose a modi ica ion o Re-Pai called MinEn .
3.2.1. Re-Pai
The main idea behind he Re-Pai algo i hm is o epea edly ind he mos equen dig am and
eplace all o i s occu ences wi h a new symbol ha is no ye p esen in he message. The algo i hm
can be desc ibed in he ollowing s eps:
1. Selec he mos equen dig am αβ in message m.
2. Replace all occu ences o αβ o new symbol γ.
3. Repea S eps 1 and 2 un il e e y dig am appea s only once.
In S ep 2 o he algo i hm, he pai
αβ
oge he wi h a new symbol
γ
a e s o ed in a dic iona y.
The implemen a ion de ails o he Re-Pai algo i hm a e le o Sec ion 3.2.2 ega ding he p oposed
MinEn algo i hm.
3.2.2. MinEn
The MinEn algo i hm p oposed in his a icle is de i ed om he Re-Pai algo i hm. The main
di e ence is in S ep 1, whe e ins ead o he selec ion o he mos equen dig am, we selec a dig am
ha minimizes |m1|H om Equa ion (3):
1.
Selec dig am
αβ
in message
m0
so ha he change o en opic size
∆|m|H=|m0|H− |m1|H
is maximal.
2. Replace all occu ences o αβ o new symbol γ.
3. Repea S eps 1 and 2 un il e e y dig am appea s only once.
En opy 2017,19, 223 7 o 23
Mo e p ecisely, le
m1=MinEn (m0
,
αβ →γ)
be he applica ion o S ep 1 and S ep 2 o he
MinEn algo i hm, hen dig am αβ ul ills:
a g min
α,β∈Σ0
|MinEn (m0,αβ →γ)|H(4)
whe e
Σ0
is he alphabe o he message
m0
. To demons a e he di e ence be ween Re-Pai and
MinEn , conside he ollowing example:
Example 4.
m0=aababcdcdb
The en opic size o
m0
is
|m0|H=
19.71 bi s. The e a e wo non-o e lapping dig ams ha occu wice:
ab and cd.
(m0,ab →e) = aeecdcdb
(m0,cd →e) = aababeeb
Based on he Re-Pai algo i hm, we do no know which dig am should be p e e ed, because bo h ha e
he same equency. In he MinEn case, we can compu e
|m1|H
o bo h cases, yielding
|m1|H
ab =
18 bi s
and |m1|H
cd =12.49 bi s, and so, he eplacemen cd →ewill be he p e e ed one.
The MinEn and he Re-Pai s a egies o dig am selec ion a e e alua ed using he algo i hm
desc ibed in [
13
]. In he ini ializa ion phase o he algo i hm, he inpu ile is ans o med in o he
linked lis , and each inpu by e is con e ed in o he unsigned in ege alue. In he nex s ep, he linked
lis is scanned, and he equencies and posi ions o all dig ams a e eco ded. F equencies o dig ams,
esp. he change o he en opic size o he message measu ed in by es, a e used as indices o he
p io i y queue. The size o he queue is limi ed o he maximal equency, esp. in he case o he
MinEn algo i hm, he maximum en opic size dec ease.
The algo i hm i e a i ely selec s he dig am wi h he highes p io i y, eplaces all occu ences
o he dig am wi h he newly-in oduced symbol, dec emen s coun s o neighbo ing dig ams and
inc emen s coun s o newly-in oduced dig ams. In he case o he MinEn algo i hm, we ha e o
ecompu e he change o he en opic size o all dig ams in he p io i y queue. We es ic he numbe
o ecompu ed changes o he en opic size o he op 20 dig ams wi h he highes p io i y, so ha
he ime complexi y o his addi ional s ep emains
O(
1
)
. Bo h algo i hms a e accomplished in
O(n)
expec ed ime; see [
13
] o de ails. The memo y consump ion is la ge in he MinEn case, because each
dig am has o be assigned wi h he addi ional quan i y: he alue o he change o he en opic size o
he message.
3.3. Discussion o he T ans o ma ion and Comp ession Func ion Selec ion S a egies
To demons a e he beha io o a o emen ioned algo i hms, we p oposed s a egies o he
selec ion o ans o ma ions and comp ession algo i hms. We compa ed he e olu ion o he en opy
o he alphabe , he en opic size o he message and he inal size o he message gi en as he sum o
he en opic size o he message and he uppe bounda y on he size o he dic iona y (Sec ion 3.3.1).
The ollowing s a egies a e being compa ed:
•GCT
: selec ion o he gene alized con ex ans o ma ion so ha he dec ease o en opy
is maximal.
•HOCT
: selec ion o he highe o de con ex ans o ma ion so ha he dec ease o en opy is
maximal in he con ex o p e ix w.
•Re-Pai : selec ion o he mos equen dig am and i s eplacemen wi h an unused symbol.
•
MinEn : selec ion o he mos en opic size educing dig am and i s eplacemen wi h an
unused symbol.
En opy 2017,19, 223 8 o 23
3.3.1. The Uppe Bounda y on he Dic iona y En y Size
All ans o ma ions and comp ession unc ions a e usually s o ed as an en y in a dic iona y.
To be able o compa e he e ec i eness o ans o ma ions, we selec ed he wo s case en opy o
each symbol, gi en by
log |Σi|
, whe e
Σi
is an alphabe and subsc ip
i
deno es he numbe o applied
ans o ma ions.
In he
GCT
and
HOCT
s a egies, he size o he alphabe will be cons an , unless some symbols
we e comple ely emo ed, hen he size o he alphabe dec eases. Re-Pai and MinEn algo i hms,
which in oduce new symbols, ha e an inc easing alphabe size. The uppe bounda y on he esul ing
size o each dic iona y en y |D| o GCT and HOCT ans o ma ions is de ined as:
|D|=3 log |Σ0|
whe e
|Σ0|
is he size o he ini ial alphabe . The La sson and Mo a [
13
] e sion o he Re-Pai
in oduces se e al e icien ways o dic iona y encoding: he Be noulli model, li e al pai enume a ion
and in e pola i e encoding. In ou expe imen s wi h Re-Pai and MinEn , we used in e pola i e
encoding o encode dic iona y.
3.3.2. Compa ison o he Alphabe ’s En opy E olu ion
E en hough he ans o ma ions and comp ession unc ions pu sue he same objec i e,
minimiza ion o he en opic size o he message, hey achie e ha by a di e en e olu ion o ze o o de
en opy. T ans o ma ion-based s a egies minimize ze o o de en opy; meanwhile, bo h comp ession
s a egies in oduce new symbols, and as a esul , ze o o de en opy g ows. The ini ial alues o he
quan i ies o he examined es ile a e summa ized in Table 1. The example o he compa ison o he
ze o o de en opy e olu ion o di e en s a egies is p o ided in Figu e 1a.
Table 1.
Cha ac e is ics o he pape 5 ile om he Calga y co pus: he ini ial size o alphabe
|Σ|
, he
ini ial ile size
|m0|
measu ed in by es, he ini ial en opy
H0
measu ed in bi s and he ini ial en opic
size |m0|Hmeasu ed in by es.
File Name |Σ| |m0|H0|m0|H
pape 5 91 11 954 4.936 7 376
(a) (b)
Figu e 1.
Compa ison o ze o o de en opy e olu ion o e he pape 5 ile om he Calga y co pus.
(
a
) E olu ion o ze o o de en opy o di e en s a egies; (
b
) e olu ion o ze o o de en opy o
di e en alues o he limi (LIM) in he HOCT s a egy.
Bo h comp ession unc ions achie e a e y simila esul ing alue o ze o o de en opy.
The Re-Pai s a egy begins wi h he highes g ow h o en opy, bu he inc ease slows down wi h
he numbe o i e a ions as he equency o each consecu i e dig am d ops. As will be discussed
in Sec ion 4.2.2, dig ams consis ing o symbols wi h a lowe equency will be p e e ed by MinEn ,
En opy 2017,19, 223 9 o 23
because hey will be able o achie e a la ge dec ease o en opic size, and hei eplacemen b ings less
cos s in he ze o o de en opy inc ease. This beha io can be obse ed especially in la e i e a ions o
he Re-Pai and MinEn algo i hms.
Bo h ans o ma ions educe he alue o ze o o de en opy.
GCT
ini ially d ops as e , bu in he
end, i signi ican ly slows down. The applica ion o he
HOCT
s a egy achie es he lowes esul ing
alue o en opy, and he in e es ing ac is ha i dec eases a an almos cons an a e. The beha io o
en opy e olu ion o di e en alues o he limi in
HOCT
is p esen ed in Figu e 1b. The un es ic ed
case (Lim =0) shows us he bo om limi o ze o o de en opy educ ion using he HOCT s a egy.
3.3.3. Compa ison o En opic Size E olu ion
The selec ion o he mos equen dig am will p oduce he la ges dec ease o he numbe o
symbols in each i e a ion. Su p isingly, he Re-Pai s a egy does no necessa ily ha e o con e ge
o i s minimum in he lowe numbe o i e a ions han MinEn . Figu e 2p esen s his beha io o
he pape 5 ile o he Calga y co pus. Bo h app oaches end wi h a simila numbe o symbols in he
esul ing message.
Figu e 2.
Compa ison o Re-Pai and MinEn algo i hms: e olu ion o he message size measu ed in
he numbe o symbols o e he pape 5 ile om he Calga y co pus.
The MinEn s a egy achie es he lowes en opic size o he message, and a each i e a ion,
he en opic size o he message is lowe han in he case o he Re-Pai s a egy, see Figu e 3. The o e all
e iciency depends on ou abili y o comp ess he esul ing dic iona y.
Figu e 3.
Compa ison o Re-Pai , MinEn ,
GCT
and
HOCT
algo i hms: e olu ion o he en opic
message size measu ed in bi s pe by e o e he pape 5 ile om he Calga y co pus.
A summa y o di e en ans o ma ion s a egies is p o ided in Table 2. A summa y o comp ession
unc ions is hen gi en in Table 3. The leas numbe o i e a ions was achie ed by
HOCT
wi h
LIM =|D|
;
his s a egy also leads o he leas inal size
|m |
, bu i should be emphasized ha he esul ing
en opic size o he message
|m |
is a e y pessimis ic es ima e, due o he cons uc ion o he size
o dic iona y en ies.
En opy 2017,19, 223 16 o 23
4.2.2. The Second Pa : Symbols Pa icipa ing in he Subs i u ion Func ion
In he second case, he equencies o symbols and hei o al numbe will change. The equa ion
o s e ching ac o c2will be de i ed in he ollowing way:
p1(x) = 1(x)
|m1|= 0(x) + ∆ (x)
|m0|+∆m
0(x) + ∆ (x)
|m0|+∆m=c2
0(x)
|m0|
The main di e ence in bo h cases is ha
c1
is a cons an ; meanwhile,
c2
is a unc ion o he
pa icula symbol x.
c2(x) = ( 0(x) + ∆ (x))|m0|
0(x)(|m0|+∆m)= 0(x) + ∆ (x)
0(x)c1=F(x)c1(22)
whe e in he las s ep, we made he subs i u ion:
F(x) = ( 0(x) + ∆ (x))/ 0(x)
The es o he
de i a ion ollows he de i a ion o Equa ion (19).
H(p1(ΣT)) = −∑
x∈ΣT
p0(x)c2(x)log c2(x)−∑
x∈ΣT
c2(x)p0(x)log p0(x)(23)
The beha io o Equa ion (23) o di e en alues o
p0(x)
is isualized in Figu e 6.
The subs i u ion o less equen symbols leads o a lowe inc ease o ze o o de en opy.
Figu e 6.
Dependency o
H(p1(ΣT))
on di e en alues o
c2
o h ee cases o
p0(x)∈ {
0.05, 0.1, 0.2
}
.
The esul ing en opic size simpli ies gi en ha :
|m1|c2(x)p0(x) = 0(x) + ∆ (x) = 1(x)(24)
yields:
|m1|H=|m1|HT(p1)
=−∑
x∈ΣT
[ 0(x) + ∆ (x)](log c2(x) + log p0(x)) (25)
We now analyze bo h e ms in (25) om he pe spec i e o di e en alues o
c2(x)
. We will
be pa icula ly in e es ed in comp ession unc ions. We know ha o comp ession unc ion
c1>
1,
symbols wi h ∆ (x)<0, i.e., symbols whose equency dec eases, will ha e F(x)<1. The posi i i y
o nega i i y o log c2 hen depends on he alue o p oduc F(x)c1.

En opy 2017,19, 223 17 o 23
The case when
F(x)c1=
1 has a solu ion
F(x) =
1
/c1
, hen
log c2(x) =
0. The e m
log p0(x)
is always nega i e. The alue o
F(x)
mus be la ge han 1
/c1
o dec ease he ze o o de en opy
con eyed by symbol x, since hen, c2(x)>1 and, as a consequence, log c2(x)>0.
F(x)>1
c1
0(x) + ∆ (x)
0(x)>|m0|+∆m
|m0|
1+∆ (x)
0(x)>1+∆m
|m0|
∆ (x)
0(x)>∆m
|m0|
|∆ (x)|
0(x)<|∆m|
|m0|
|∆ (x)|
|∆m|< 0(x)
|m0|=p0(x)
(26)
The in oduc ion o he absolu e alue in he middle s ep o he de i a ion o Inequali y (26) is
allowed since using comp ession unc ions alues o
∆ (x)
and
∆m
can only be nega i e. Suppose now
ha we ha e a dig am
d=αβ
, gi en ha
α6=β
, and we eplace i by he newly-in oduced
γ
,
hen
∆m=∆ (α) = ∆ (β)
. The le pa o Inequali y (26) becomes equal o one, so Inequali y (26)
canno be sa is ied, and
log c2(x)
in his case will be nega i e and will always inc ease he amoun o
in o ma ion ca ied by he symbols αand β.
Finally, we s a e he condi ion o he en opic size dec ease:
Co olla y 2. The en opic size o he pa o he message o med by symbol x dec eases when:
∆ (x)
0(x)<−log c2(x)
log c2(x) + log p0(x)(27)
P oo .
|m1|H<|m0|H
[ 0(x) + ∆ (x)][log c2(x) + log p0(x)] < 0(x)log p0(x)
0(x)log c2(x) + ∆ (x)log p0(x) + ∆ (x)log c2(x)<0
∆ (x)(log p0(x) + log c2(x)) <− 0(x)log c2(x)
∆ (x)
0(x)<−log c2(x)
log c2(x) + log p0(x)
4.2.3. Thi d Pa : In oduced and Remo ed Symbols
We begin wi h symbol
x
, which is comple ely emo ed om he message, so ha ini ially,
p0(x)6=
0, bu
p1(x) =
0. This case is i ial, and i has ze o pa icipa ion in he inal alue o he
en opy and he en opic size o message. The emaining case we ha e o deal wi h is a case when
ini ially symbol
x
has ze o p obabili y
p0(x) =
0, bu a e subs i u ion, i s p obabili y will inc ease o
some p1(x)6=0. The inal p obabili y is gi en as:
p1(x) = ∆ (x)
|m0|+∆m(28)
En opy 2017,19, 223 18 o 23
Since he symbol
x
ini ially has ze o pa icipa ion in en opy and en opic size, i will always lead
o he inc ease o bo h quan i ies. Fo he se
ΣN
o all such symbols, i s po ion on o al en opy is
hen gi en by:
H(p1(ΣN)) = −∑
x∈ΣN
∆ (x)
|m0|+∆mlog ∆ (x)
|m0|+∆m(29)
and he co esponding inal en opic size will be gi en by:
|m1|H=|m1|HN(p1)
=−∑
x∈ΣN
∆ (x)[log ∆ (x)−log (|m0|+∆m)] (30)
I is impo an o ema k ha i does no make much sense o in oduce mo e han one symbol in
one subs i u ion unc ion, because bo h quan i ies would hen add hemsel es wice.
4.3. Calcula ion o ∆|m|H
A i s glance, i seems ha we need o e alua e all symbols o p edic ze o o de en opy,
bu ins ead, i is possible o p edic he exac change o he en opic size o he message a e he
applica ion o he comp ession unc ion by he e alua ion o en opic sizes gi en by Equa ions (21),
(25) and (30) dealing only wi h symbols
x∈Σ ΣI
. In he pa icula case o he Re-Pai algo i hm,
he e a e only wo symbols whose equency knowledge is su icien o e alua e he change o he
en opic size o he message; suppose a comp ession unc ion
CF(αβ →γ)
so ha
p1(α)6=
0,
p1(β)6=
0
and p0(γ) = 0, hen he esul ing en opic size is gi en as:
∆|m|H=|m0|log c1−log c1∑
x∈{α,β}
0(x)
+∑
x∈{α,β}
0(x)log c2(x) + ∆ 0(x)log p0(x) + ∆ 0(x)log c2(x)
−∆ (γ)[log ∆ (γ)−log (|m0|+∆m)]
(31)
inally, o he Re-Pai , i holds ha i
α6=β
, hen
∆m=∆ (α) = ∆ (β) = ∆ (γ) = (α
,
β)
, and all
∆’s in (31) u n in o (αβ). I α=β, hen ∆ (α)/2 =∆ (γ).
5. Conclusions
We desc ibed h ee ypes o ans o ma ions o he p ep ocessing o messages so ha he ze o
o de en opy o messages d ops so he esul ing message can be mo e e icien ly encoded using ze o
o de en opy comp ession algo i hms like Hu man o a i hme ic coding.
We p esen ed ela ions ha go e n he change o he message size o ans o ma ions and
comp ession unc ions. T ans o ma ions ha e he ad an age ha hey do no modi y he size o he
alphabe , especially in he case o dig am subs i u ion used by Re-Pai and ou p oposal o he MinEn
s a egy; he esul ing size o he alphabe signi ican ly g ows, and i b ings addi ional complexi y in
he s o age o he en opy coding model, i.e., he s o age o he ou pu alphabe .
The MinEn s a egy selec s dig ams o be eplaced by he minimal en opic size o he esul ing
message, and i is shown ha in mos cases, he esul ing message size is smalle han he one
achie ed by Re-Pai . We also showed ha he wo algo i hms ollow sligh ly di e en execu ion pa hs,
as MinEn p e e s dig ams ha consis o less equen symbols; meanwhile, Re-Pai does no ake his
in o conside a ion.
The comp ession unc ions ake ad an age o ans o ma ions as hey achie e a be e esul ing
comp ession a io. In u u e wo k, we will ocus on he s o age o he dic iona y ha will be used in
ans o ma ion algo i hms, because his a ea can signi ican ly imp o e he esul ing comp ession a io.
En opy 2017,19, 223 19 o 23
Fu he , we will ocus on he desc ip ion o he ela ion be ween he en opy coding model o he inal
message and he size o he inal alphabe .
Acknowledgmen s:
This wo k was suppo ed by he p ojec SP2017/100 Pa allel p ocessing o Big Da a IV, o he
S uden G an Sys em, VSB-Technical Uni e si y o Os a a. The cos s o open access we e co e ed.
Au ho Con ibu ions:
Michal Vasinek ealized his wo k, p oposed and de eloped he implemen a ion o he
CT
,
GCT
,
HOCT
and MinEn algo i hms. Jan Pla os p o ided he guidance du ing he w i ing p ocess and
e ised he pape .
Con lic s o In e es : The au ho s decla e no con lic o in e es .
Appendix A
The ollowing sec ions p esen p ope ies o ans o ma ions. Speci ically o each ype o
ans o ma ion we will p o ide a p oo o he in e se ans o ma ion exis ence. Fu he we will
desc ibe how he equencies o symbols will be al e ed i he pa icula ans o ma ion is going o
be applied.
Appendix A.1. CT—P oo o he Co ec ness
This heo em de ines he in e se ans o ma ion o he con ex ans o ma ion:
Theo em A1.
The con ex ans o ma ion
CT−1≡CT→(αγ →αβ)
is in e se ans o ma ion o he con ex
ans o ma ion CT←(αβ →αγ).
P oo .
Le
CT−1≡CT→
, i
CT−1
is in e se hen he ollowing mus be ue o any message
m
:
CT−1(CT(m)) = m
. Suppose ha we a e passing message
m
om he end o he beginning and
suppose ha in posi ions
i
and
i+
1 dig am
αβ
is loca ed, his dig am is eplaced by
αγ
, he nex pai
o posi ions explo ed a e
i−
1 and
i
, bu hei alue is independen o he p eceding eplacemen ,
because he eplacemen has aken place in posi ion
i+
1, so when
CT−1
is applied in posi ion
i
i will
ind he e he dig am αγ and e e s i back o αβ.
O he combina ions o di ec ions do no o m a pai o ans o ma ion and i s in e se. We gi e
an example o each case showing his p ope y:
CT→(αβ →αα)
and
CT−1
←
o e he message
m=αβα:CT→(αβα) = ααα
bu
CT−1
←(ααα) = αββ 6=αβα
. Nex conside
CT→(αβ →αα)
and
CT−1
→
o e he message
m=ααβ
:
CT→(ααβ) = ααα
bu
CT−1
→(ααα) = αβα 6=ααβ
. And in he las
case le ’s conside
CT←(αβ →αα)
and
CT−1
←
o e he message
m=αβα
:
CT→(ααβ) = ααα
bu
CT−1
→(ααα) = αββ 6=ααβ.
Le
0(αγ
,
m) =
0 is a numbe o occu ences o pa icula dig am
αγ
in a message
m
,
hen he ollowing co olla y ells us how many dig ams
αγ
is in oduced by con ex ans o ma ion
CT→(αβ →αγ):
Co olla y A1.
Unde assump ion ha
α6=γ
he numbe o occu ences o dig ams
αγ
and
αβ
a e applica ion
o ans o ma ion CT→(αβ →αγ)is 1(αγ,CT(m)) = 0(αβ,m)and 1(αβ,CT(m)) = 0.
P oo .
A p oo is a consequence o Theo em A1, since each eplacemen is independen o each o he
and so each dig am αβ is eplaced by αγ lea ing 1(αβ) = 0 and 1(αγ) = 0(αβ).
The co olla y allows us o p ecisely p edic no only he equencies o he in e changed dig ams
αβ
and
αγ
bu also as a consequence he equencies o indi idual symbols a e ans o ma ion. The special
case o ans o ma ions on a diagonal (see De ini ion A1) will be discussed in he nex pa ag aph.
Appendix A.2. Diagonal Con ex T ans o ma ion
Diagonal ans o ma ion is a ans o ma ion whe e one o he dig ams pa icipa ing in he
ans o ma ion is o he o m
αα
. The esul ing equency o such a dig am is unp edic able wi hou
En opy 2017,19, 223 20 o 23
knowledge o he dis ibu ion o all n-g ams o he o m
αn
, whe e
n≥
2, bu we show ha o any
diagonal
CT
, i is possible o p edic equencies o symbols
α
and
β
. The p oblems wi h p edic abili y
a ise om he epe i ion o symbols.
De ini ion A1. Diagonal con ex ans o ma ion is a con ex ans o ma ion o he o m CT←(αα →αβ).
Conside wo ans o ma ions,
CT1≡CT←(αα →αβ
,
ααα) = αββ
and
CT2≡CT←(αβ →
αα
,
αβα) = ααα
, i Co olla y A1 would also be alid o diagonal ans o ma ions, hen o ins ance in
he case o
CT1
, he equency
1(αβ) = 0(αα)
bu his ob iously is no ue, ins ead we see ha he
new equency (β)o symbol βis 1(β) = 0(αα).
Suppose we ha e a message
s=αn
, hen
CT1(s) = αβn−1
, we clea ly see ha he equency
(αβ
,
CT1(s)) =
1 and
(ββ
,
CT1(s)) = n−
2, because he numbe o dig ams in a message is gi en
by he leng h o he message minus one. We can now exp ess he equency
(αβ
,
CT1(m))
o he
newly in oduced occu ences o dig am
αβ
as a sum o all sub-messages enclosed in
m
in he o m
xsx
, whe e
x6=α
o all
n≥
2. So we see ha i is possible o p ecisely p edic he change o equency
o αβ, bu i demands knowledge o he dis ibu ion o all enclosed sub-messages s.
F om he o he pe spec i e, since each occu ence o dig am
αα
in he o me message
is ans o med in o
αβ
we can see ha he equency
1(β
,
CT1(m)) = 0(β) + 0(αα)
and
1(α,CT1(m)) = 0(α,m)− 0(αα).
Ve y simila beha io is obse ed in he second case o
CT2
. The p oblem is in he epe i ion
o he pa e n
= (αβ)n
, hen
CT2( ) = α2n
and
1(αα) =
2
n−
1. Again wi hou knowledge o all
sub-messages
enclosed in
m
we canno p edic he exac change o equency o nei he dig am
αα
no
αβ
, bu since we know ha each pai
αβ
in he o me message will be ans o med o
αα
, we can again p ecisely p edic equencies o indi idual symbols
1(α) = 0(α) + 0(α
,
β)
and
1(β) = 0(β)− 0(αβ).
Wi h he knowledge o he p eceding discussion and o Co olla y A1 we conclude ha o any
con ex ans o ma ion
CT
we a e able o compu e he equency and co esponding p obabili y o
a bi a y symbol a e applica ion o any
CT
om he knowledge o ini ial dis ibu ion o symbols
and dig ams. In [
26
] we showed ha unde ce ain condi ions i is possible o p ocess se e al con ex
ans o ma ions simul aneously.
Appendix A.3. GCT—F equencies Al e a ion
Co olla y A2.
Unde assump ion ha
α6=γ
,
α6=β
and
β6=γ
he numbe o occu ences o dig ams
αγ
and
αβ
a e applica ion o ans o ma ion
GCT←(αβ ↔αγ)
is
1(αγ
,
GCT(m)) = 0(αβ
,
m)
and
1(αβ,GCT(m)) = 0(αγ,m).
P oo .
Since each dig am
αβ
esp.
αγ
is eplaced by
αγ
esp.
αβ
, and nei he o he dig ams in luence
he ans o ma ion o he o he , hei equencies mus in e change.
Appendix A.4. Gene ic T ans o ma ion—P oo o Co ec ness
Gene ic ans o ma ion
GT
exchanges any wo dig ams. In he design o algo i hms, we p e e
GCT
o e
GT
since he space om which gene ic ans o ma ions a e selec ed is in his case o o de
he
|Σ|4
and when alphabe s o he la ge size a e deal wi h, he sea ch in such a space would be
compu a ionally e y expensi e.
De ini ion A2.
Gene ic ans o ma ion (GT) is he mapping
GT(αβ ↔γρ
,
w):Σn→Σn
,
Σ
is he alphabe
o he inpu message
w
and
n
is he leng h o he inpu message, ha exchanges all dig ams
αβ
o dig am
γρ
and ice- e sa.
The in e se ans o ma ion o GCT and GT is de ined by he ollowing heo em:
En opy 2017,19, 223 21 o 23
Theo em A2.
Gene ic ans o ma ion
GT−1≡GT←(αβ ↔γρ)
esp.
GT−1≡GT→(αβ ↔γρ)
is he
in e se o gene ic ans o ma ion GT→(αβ ↔γρ) esp. GT←(αβ ↔γρ)
P oo .
Fi s , we show ha i is su icien o p o e ha o any s ing
s=xwx
, i holds ha
GT−1(GT(s)) = s
, whe e
x/∈ΣGT ={α
,
β
,
γ
,
ρ}
and
w[i]∈ΣGT
. Suppose ha
x
is loca ed in
posi ion
p
hen o dig ams
d
in posi ions
(p−
1,
p)
and
(p
,
p+
1
)
i holds ha
GT(d) = d
. So he
i s possible applica ion o GT can occu in posi ions
(p−
2,
p−
1
)
and
(p+
1,
p+
2
)
and hese a e
independen , i.e., non-o e lapping.
Nex , we show ha each eplacemen made in he o wa d ans o ma ion will be e e ed back by
in e se ans o ma ion. Take o example ans o ma ion
GT←(αβ ↔γρ)
he ans o ma ion is applied
in he igh o le di ec ion. The las applied o wa d ans o ma ion in posi ions
(
,
+
1
)
eplaces o
ins ance dig am
αβ
o
γρ
lea ing
w[
,
+
1
] = γρ
, he in e se ans o ma ion, by de ini ion he same
ans o ma ion applied in he opposi e di ec ion, e e s dig am
γρ
back o
αβ
. Now conside any
iple o posi ions
( −
1,
,
+
1
)
in a ans o med message, he inpu o he in e se ans o ma ion in
(
,
+
1
)
is dependen on he esul o he in e se ans o ma ion in he p eceding pai o posi ions,
bu as we saw he i s applied in e se e e ed dig am back co ec ly so he s a e in posi ions
( +
1,
+
2
)
is exac ly like he one o he s a e le by o wa d ans o ma ion in hese posi ions,
so any o he dig am will be e e ed back co ec ly, because e e y p eceding applica ion o he in e se
lea es he s a e o he dig am in he s a e ha was le by he o wa d ans o ma ion and his dig am
is i ially e e ed back o ini ial s a e. The same ules a e alid o
GT
in he opposi e di ec ion,
since he ans o ma ion GT←(m) = GT→(mT), whe e mTis a mi o message o m.
Appendix A.5. HOCT—P oo o he Co ec ness
The ollowing i ial Lemma will help us o o mula e a heo em abou in e se ans o ma ion
o HOCT:
Lemma A1.
Le
T=HOCT(wβ↔wγ
,
m
,
P(w
,
m))
is a highe o de con ex ans o ma ion o e he inpu
message m, gi en ha we possess he knowledge o w and posi ions P(w,m), hen T−1=T.
P oo .
Because we don’ ha e o pass h ough he whole message ei he in he o wa d o in e se
ans o ma ion case, bu only h ough he se o posi ions
P(w
,
m)
, hen he symbol in posi ion
i∈P(w
,
m)
, o ins ance
m[i] = β
will swi ch by
HOCT
o
m[i] = γ
and by epea ed applica ion o
HOCT i e e s back o m[i] = β.
The Lemma A1 is i ial bu comes in o play when
P(w
,
m)
is a p oduc o some o he highe
o de con ex ans o ma ion, i.e., he one wi h an o de lowe by one.
Theo em A3.
Le
m1=HOCT1(wα↔wβ
,
m
,
P(w
,
m))
and
m2=HOCT2(wαγ ↔wαρ
,
m1
,
P(wα
,
m1))
a e wo highe o de con ex ans o ma ions. Le
T(m) = HOCT2(HOCT1(m))
be a ans o ma ion
composi ion o wo highe o de con ex ans o ma ions o e inpu message
m
. Then
HOCT−1
2(wαγ ↔
wαρ
,
m3
,
P(wβ
,
m3))
, such ha
m3=HOCT1(m2))
hen he ans o ma ion composi ion
T−1≡
HOCT−1
2(HOCT1(m2)) = m is he in e se ans o ma ion o T.
Se e al ema ks o he o mula ion o Theo em A3: T ans o ma ions
HOCT1
and
HOCT2
a e
applied o e wo consecu i e s a es o he message. The posi ions
P(wα
,
m1)
co espond o he
posi ions
P(wβ
,
m)
, since sub-messages
wα
ha e been eplaced by
wβ
in he applica ion o
HOCT1
.
The in e se ans o ma ion by
HOCT−1
2
is applied ins ead o e posi ions
P(wβ
,
m3)
, since hese
posi ions ha e al eady been e e ed back by HOCT1.
The p oo is based on he es ic ion ha
w[
0
]6=w[i]
,
i>
0, i can be iewed as we would spli
he inpu message
m
o sub-messages
si
sepa a ed by
w[
0
]
. Fo ins ance, suppose ha
w[
0
]
is a space
cha ac e in o dina y ex , since, by De ini ion 3, no o he cha ac e in
w
can be a space cha ac e ,

En opy 2017,19, 223 22 o 23
i ollows ha he possible ans o ma ions a e being applied on wo ds ollowing he space cha ac e .
Now using he ac ha
si
is enclosed by
w[
0
]
, i.e., hey do no o e lap, allows us o handle each
sub-message siindependen ly.
P oo .
Fo he wo se s o posi ions, i holds ha
P(w
,
m)∩P(wα
,
m1) = ∅
, because elemen s o he
o me a e p edecesso s o he la e and
s
does no o e lap. The loca ions o
w
in
m
and
m2
a e
iden ical as hey we e no modi ied du ing
HOCT
, i.e.,
P(w
,
m) = P(w
,
m2)
. When we apply
HOCT1
again i will simply e e he symbols in posi ions gi en by
P(w
,
m)
back acco ding o Lemma A1
yielding he message s a e
m3
. In he o wa d ans o ma ion
HOCT2
was applied o e posi ions o
P(wα
,
m1)
, bu hese a e he o me posi ions o
P(wβ
,
m)
, ha a e al eady ans o med back by he
applica ion o
HOCT1
, so
P(wα
,
m1)
is equal o
P(wβ
,
m3)
and when
HOCT2
is applied o e posi ions
P(wβ,m3)i exchanges symbols γand ρand e en ually yields m.
The ecu si e applica ion o Theo em A3 leads o he conclusion ha his p ocess can be epea ed
un il he e is no o he pai o symbols hen hese con aining
w[
0
]
as one o he symbols
α
o
β
o we
simply each he end o he message.
Co olla y A2 abou he p edic ion o equencies in he case o
GCT
is also applicable in he case
o HOCT, because he p inciple ha he exac numbe o eplacemen s is known is also alid and we
a e able o p ecisely compu e he u u e p obabili ies o symbols be o e he a bi a y
HOCT
is applied.
I we implemen he in e se algo i hm as a sequen ial algo i hm ope a ing in he le - igh manne ,
i is possible o ha e one o he ans o ma ion symbols i
β
,
γ
is equal o
w[
0
]
. Suppose he ollowing
example:
m=abcabc
,
P(a
,
m) = {
0, 3
}
,
HOCT1(ab ↔aa)
and
HOCT2(aac ↔aaa)
yielding he ou pu
message
m2=aaaaaa
. Now applying in e se ans o ma ion sequen ially om le o igh , we i s
eplace
aa
by
ab
yielding
mi=abaaaa
, hen applying eplacemen
aba
o
abc
yielding
mi+1=abcaaa
,
now because he e is no o he ans o ma ion ha is induced om
abc
we know ha he nex
a
symbol
is
w[
0
]
and we can epea he p eceding p ocess again s a ing om his
a
. The su icien condi ion o
he in oduc ion o
w[
0
]
as he ans o ma ion symbol
β
o
γ
is ha
w
con ains no o he
w[
0
]
in
w[i]
,
i>
0, because he in e se p ocess emo es all in oduced
w[
0
]
symbols om he ans o med message
du ing le o igh sequen ial in e se ans o ma ion.
Re e ences
1.
Co e , T.M.; Thomas, J.A. Elemen s o In o ma ion Theo y (Wiley Se ies in Telecommunica ions and
Signal P ocessing); Wiley-In e science: New Yo k, NY, USA, 2006.
2. Shannon, C.E. A Ma hema ical Theo y o Communica ion. Bell Sys . Tech. J. 1948,27, 379–423.
3.
Hu man, D.A. A Me hod o he Cons uc ion o Minimum-Redundancy Codes. P oc. Ins . Radio Eng.
1952
,
40, 1098–1101.
4.
Wi en, I.H.; Neal, R.M.; Clea y, J.G. A i hme ic Coding o Da a Comp ession. Commun. ACM
1987
,
30, 520–540.
5.
Cha ika , M.; Lehman, E.; Lehman, A.; Liu, D.; Panig ahy, R.; P abhaka an, M.; Sahai, A.; Shela , A.
The Smalles G amma P oblem. IEEE T ans. In . Theo y 2005,51, 2554–2576.
6.
Ne ill-Manning, C.G. In e ing Sequen ial S uc u e. Ph.D. Thesis, Uni e si y o Waika o, Hamil on,
New Zealand, May 1996.
7.
Ne ill-Manning, C.G.; Wi en, I.H. Iden i ying Hie a chical S uc u e in Sequences: A Linea - ime Algo i hm.
J. A i . In . Res. 1997,7, 67–82.
8.
Kie e , J.C.; Yang, E.-H. G amma Based Codes: A New Class o Uni e sal Lossless Sou ce Codes. IEEE T ans.
In . Theo y 2000,46, 737–754.
9.
Zi , J.; Lempel, A. Comp ession o indi idual sequences ia a iable- a e coding. IEEE T ans. In . Theo y
1978,24, 530–536.
10.
Yang, E.; He, D. E icien uni e sal lossless da a comp ession algo i hms based on a g eedy sequen ial
g amma ans o m 2. Wi h con ex models. IEEE T ans. In . Theo y 2003,49, 2874–2894.
11. Gage, P. A New Algo i hm o Da a Comp ession. C Use s J. 1994,12, 23–38.
En opy 2017,19, 223 23 o 23
12.
Nakamu a, H.; Ma ushima, S. Da a Comp ession by Conca ena ion o Symbol Pai s. In P oceedings o he
IEEE In e na ional Symposium on In o ma ion Theo y and I s Applica ions, Pa is, F ance, 13–17 Sep embe
1996; pp. 496–499.
13. La sson, N.J.; Mo a , A. O -line dic iona y-based comp ession. P oc. IEEE 2000,88, 1722–1732.
14.
Claude, F.; Fa ina, A.; Na a o, G. Re-Pai Comp ession o In e ed Lis s. a Xi
2009
, a Xi :cs.IR/0911.3318.
15.
Masaki, T.; Kida, T. Online G amma T ans o ma ion Based on Re-Pai Algo i hm. In P oceedings o he
Da a Comp ession Con e ence (DCC), Snowbi d, UT, USA, 29 Ma ch–1 Ap il 2016; pp. 349–358.
16.
G assbe ge , P. Da a Comp ession and En opy Es ima es by Non-sequen ial Recu si e Pai Subs i u ion.
Physics 2002, a Xi :physics/0207023.
17.
Calcagnile, L.M.; Gala olo, S.; Menconi, G. Non-sequen ial ecu si e pai subs i u ions and nume ical
en opy es ima es in symbolic dynamical sys ems. a Xi 2008, a Xi :cond-ma .s a -mech/0809.1342.
18.
Na a o, G.; Russo, L. Re-pai Achie es High-O de En opy. In P oceedings o he Da a Comp ession
Con e ence, DCC 2008, Snowbi d, UT, USA, 25–27 Ma ch 2008; p. 537.
19.
Vasinek, M.; Pla os, J. En opy Reduc ion Using Con ex T ans o ma ions. In P oceedings o he Da a
Comp ession Con e ence (DCC), Snowbi d, UT, USA, 26–28 Ma ch 2014; p. 431.
20.
Vasinek, M.; Pla os, J. Gene alized Con ex T ans o ma ions—Enhanced En opy Reduc ion. In P oceedings
o he Da a Comp ession Con e ence (DCC), Snowbi d, UT, USA, 7–9 Ap il 2015; p. 474.
21. Vasinek, M.; Pla os, J. Highe O de Con ex T ans o ma ions. a Xi 2017, a Xi :cs.IT/1701.01326.
22.
Kida, T.; Ma sumo o, T.; Shiba a, Y.; Takeda, M.; Shinoha a, A.; A ikawa, S. Collage Sys em: A Uni ying
F amewo k o Comp essed Pa e n Ma ching. Theo . Compu . Sci. 2003,298, 253–272.
23.
González, R.; Na a o, G. Comp essed Tex Indexes wi h Fas Loca e. In P oceedings o he 18 h
Annual Con e ence on Combina o ial Pa e n Ma ching, CPM’07, London, ON, Canada, 9–11 July; Sp inge :
Be lin/Heidelbe g, Ge many, 2007; pp. 216–227.
24. Claude, F.; Fa ina, A.; Na a o, G. Re-Pai comp ession o in e ed lis s. a Xi 2009, a Xi :0911.3318.
25.
Vasinek, M. Kon ex o e Mapy a Jejich Aplikace. Mas e ’s Thesis, Vysoka Skola Banska—Technicka
Uni e zi a Os a a, Os a a, Czech Republic, 2013.
26.
Vasinek, M.; Pla os, J. Pa allel App oach o Con ex T ans o ma ions. A ailable online: h p://ceu -ws.o g/
Vol-1343/pape 4.pd (accessed on 11 May 2017).
c

2017 by he au ho s. Licensee MDPI, Basel, Swi ze land. This a icle is an open access
a icle dis ibu ed unde he e ms and condi ions o he C ea i e Commons A ibu ion
(CC BY) license (h p://c ea i ecommons.o g/licenses/by/4.0/).