Prediction and evaluation of zero order entropy changes in grammar-based codes

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