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

entropy Article Prediction and Evaluation of Zero Order Entropy Changes in Grammar-Based Codes Michal Vasinek * and Jan Platos Department of Computer Science, FEECS, VSB-Technical University of Ostrava, 17. listopadu 15/12172, Ostrava 708 33, Czech Republic; [email protected] *Correspondence: [email protected]; Tel.: +420-597-323-971 Academic Editor: Raúl Alcaraz Martínez Received: 30 January 2017; Accepted: 10 May 2017; Published: 13 May 2017 Abstract: The change of zero order entropy is studied over different strategies of grammar production rule selection. The two major rules are distinguished: transformations leaving the message size intact and substitution functions changing the message size. Relations for zero order entropy changes were derived for both cases and conditions under which the entropy decreases were described. In this article, several different greedy strategies reducing zero order entropy, as well as message sizes are summarized, and the new strategy MinEnt is proposed. The resulting evolution of the zero order entropy is compared with a strategy of selecting the most frequent digram used in the Re-Pair algorithm. Keywords: data compression; grammars; entropy; transformations; context; Re-Pair 1. Introduction Entropy is a key concept in the measurement of the amount of information in information theory [ 1 ]. From the data compression perspective, this amount of information represents the lower limit of the achievable compression of some information source. Due to the well-known work by Shannon [ 2 ], we know that using less bits than the amount given by entropy to represent a particular message or process would necessarily lead to the loss of some information and as a consequence our inability to properly recover the former structure of the message. This work is focused on the study of entropy in data compression, and therefore, our discussion will be restricted to only finite messages. These finite messages are formed by symbols, and in this perspective, the entropy can be understood as the lowest number of bits needed on average to uniquely represent each symbol in a message. There are messages for which the evaluation of entropy can be a very hard task, and so, we are often forced to satisfy ourselves with some approximation of entropy. The simplest approximation is the one based on the probability distribution of symbols in a particular message. In this case, the symbols are viewed as independent entities, and their mutual relationships are not taken into account. A better approximation of entropy is based on the conditional probabilities when we also take into account how symbols follow each other. We can also approximate entropy by computing bits per byte ratio of message encoded by state of the art data compression algorithms. In this article, we study entropy at the level of independent symbols. This approximation of entropy is often called zero order entropy. There are two major data compression algorithms in use that compress messages almost to the rate given by zero order entropy: Huffman [ 3 ] and arithmetic [ 4 ] coding. The zero order entropy can be computed using the Shannon equation: H(X) = −∑ x∈Σ p(x)log p(x)(1) Entropy 2017,19, 223; doi:10.3390/e19050223 www.mdpi.com/journal/entropy Entropy 2017,19, 223 2 of 23 where X stands for a random variable representing the probability distribution of symbols in the input message m and p(x) is the probability of symbol x from alphabet Σ . The expected length of the code for the particular symbol x is given by −log p(x) . If the expected length of the code is multiplied by its probability, we obtain the average number of bits needed to represent any symbol x∈Σ . The size of the message using the expected lengths of codes is given as a product of the length of the message |m|measured as a number of symbols and zero order entropy: |m|H=|m|H(X)(2) When we refer to the term entropic size of the message, we always mean the quantity given by Equation (2), and it will be denoted using a superscript as |m|H . We study how the entropic size of the message evolves when all occurrences of some m -gram are substituted for some other n -gram and vice versa. We study two such substitutions: transformations and compression functions. Transformations replace n -grams of the same length. Transformation leaves the message size intact, but since the probability of symbols changes, the value of zero order entropy also has to change. Compression functions replace m -grams for n -grams, where m>n , and leave the message size smaller, but the change in zero order entropy also occurs. The main idea behind the concept of transformations is the following: consider Huffman coding; more probable symbols are encoded by shorter or at least by the same length prefix codes than the lower probability ones, if the symbol β is more probable than the symbol γ , but in the context of some symbol α , γ is more frequent than β , then if these symbols following α are exchanged, the longer codes used for encoding γ will instead be encoded by shorter codes representing the encoding of β . Under this assumption, it is possible to pre-process data so that the frequency of more frequent symbols increases and the frequency of less frequent symbols decreases. 1.1. Notation and Terminology •The alphabet of the input message mof the size |m|is denoted by Σand its size by |Σ|. • Greek symbols are used to denote variables representing symbols in the input message. For instance, suppose two digrams αα , αβ and the alphabet Σ={ 0, 1 } . Then, αα ∈ { 00, 11 } and αβ ∈ {00, 01, 10, 11}. • When we refer to the term entropy, we always mean Shannon’s entropy defined by Equation (1). •All logarithms are to base two. • Any quantity Qi with a subscript i∈N denotes consecutive states of the quantity between substitutions. For instance, a quantity Q0 is a value of the quantity before any substitution is applied, and Q1is a value of the quantity after some substitution is applied. 1.2. Order of Context and Entropy 1.2.1. Zero Order Context When all symbols are interpreted as independent individual entities and no predecessors are taken into consideration, such a case is called zero order context. Zero order entropy is then computed as Shannon’s entropy of a random variable given by the probabilities of symbols in the input message. 1.2.2. N-th Order Context In a case where the probability distribution of symbols following a particular fixed length prefix w is taken into consideration, then if the length of the prefix is N , then the order of context is N , and the N-th order entropy is computed as Shannon’s entropy of the conditional distribution of symbols following all different prefixes wi. Entropy 2017,19, 223 3 of 23 2. Previous Work The class of algorithms dealing with exchanges of different n , m -grams are called grammar-based algorithms. Their purpose is to provide a set of production rules inferring the content of the message. Using the Chomsky hierarchy, we identify two classes of formal grammars used in data compression: context-free grammars (CFG) and context-sensitive grammars (CSG). Context transformations presented in Section 3belong to the CSG class; meanwhile, compression functions belong to the CFG class. The problem of the search for the most compact context-free grammar representation of a message is NP-hard, unless P=NP [ 5 ]. Instead of searching for the optimal solution, many heuristic and greedy algorithms were proposed. CFGs for data compression were first discussed by Nevill-Manning [ 6 ] followed by the proposal of the SEQUITUR algorithm [ 7 ]. SEQUITUR reads the sentence in the left-right manner so that each repeated pattern is transformed into a grammar rule. The grammar is utilized in such a way that the two properties are fulfilled: a digram uniqueness (no pair of adjacent symbols appear more than once in the grammar and a rule utility); every rule is used more than once. Kiefer and Yang [ 8 ] were the first who addressed data compression using CFGs from the information theoretic perspective; they showed that the LZ78 [ 9 ] algorithm can be interpreted as a CFG and that the proposed BISECTION algorithm forms a grammar-based universal lossless source code. BISECTION repeatedly halves the initial message into unique phrases of length 2k, where kis the integer. In the work of Yang and He [ 10 ], the context-dependent grammars (CDG) for data compression were introduced. In CSG, the context is present in both sides of production rules; meanwhile in CDG, the context is defined only on the left side of the production rule. One of the first concepts in greedy grammar-based codes was the byte pair encoding (BPE) [ 11 ]. The BPE algorithm selects the most frequent digram and replaces it with some unused symbol. The main weakness of this approach is that the algorithm is limited to an alphabet consisting only of byte values. The concept of byte pair encoding was later revised, and the limitation on the alphabet size used was generalized independently by Nakamura and Murashima [ 12 ] and by Larsson and Moffat [ 13 ]; the resulting approach is called Re-Pair [ 13 ]. Re-Pair stands for recursive pairing, and it is a very active field of research [ 14 , 15 ]. It iteratively replaces the most frequent digrams with unused symbols until there is no digram that occurs more than once. Unlike BPE that codes digrams using only byte values, Re-Pair expects that the symbols of the final message will be encoded using some entropy coding algorithm. Approaches derived from Re-Pair are usually greedy, since each iteration of the algorithm is dependent on a successful search of the extremal value of some statistical quantity related to the input message. The study of the Re-Pair from the perspective of ergodic sources is discussed in [ 16 , 17 ]. Neither BPE nor Re-Pair compress the message into the least possible size, but they rather form a trade-off between message and dictionary sizes. Re-Pair-like algorithms are off-line, in the sense that they need more than one pass through the input message; meanwhile, SEQUITUR incrementally builds the grammar in a single pass. The Re-Pair algorithm is an algorithm with O(n)time complexity; it is easy to implement using linked lists and a priority queue. Further, it was shown in [ 18 ] that it can compress an input message of length n over an alphabet of size |Σ|into at most 2Hk+o(nlog |Σ|)bits, where Hkis k-th order entropy. Our recent studies were focused on a special class of grammar transforms that leave the message size intact [ 19 , 20 ]. In the present paper, the class of grammar transformations is extended with a novel concept of higher order context transformation [ 21 ]. We shall provide examples of transformations and the evaluation of entropy resp. entropic size reduction to the class of grammar compression algorithms, and we compare the evolution of entropy, entropic size and the resulting number of dictionary entries for Re-Pair and our version of Re-Pair, called MinEnt, which is based on the selection of the pair of symbols reducing the entropic size of the message the most. Re-Pair finds application in areas such as searching in compressed data [ 22 ], compression of suffix arrays [ 23 ] or compression of inverted indexes [ 24 ], to name a few. These areas are also natural application fields for MinEnt. From the Entropy 2017,19, 223 4 of 23 perspective of the number of passes through the message, the approaches discussed in this paper belong to off-line algorithms. 3. Transformations and Compression Algorithms In this section, we will describe and evaluate several invertible transformations T and substitution functions F so that for any two consecutive states of the message, m0 and m1 , before and after application of Tor F, the following relation holds: |m1|H<|m0|H(3) The measure of the size of the message by the entropic size of the message is preferred, since using the arithmetic coding, one can achieve a compression rate very close to the zero order entropy, and so, the size |m|H is in theory accessible. Further, it allows the comparison of two distinct substitutions when their resulting sizes measured by the number of symbols are equal. The derivation of equations for the computation of |m1|H, resp. ∆|m|H=|m0|H− |m1|H, are provided in Section 4. 3.1. Transformations Consider transformation, where we replace all occurrences of some symbol β for some symbol γ and vice versa; such a transformation is called a symmetry transformation, because it does not modify any measurable quantities related to the amount of information. The information content is changed when the replacement is taken in the context of an other symbol α . Such a transformation corresponds to the exchange of all digrams αβ for αγ and vice versa. In this section, several different forms of transformation are distinguished and briefly described. Some properties of transformations and their proofs can be found in Appendix A. 3.1.1. Context Transformation The concept of context transformations was first proposed in [ 25 ], and the results were presented in [ 19 ]. It is the simplest transformation that assumes a pair of digrams beginning with the same symbol when one of the digrams is initially missing in the input message. Definition 1. Context transformation (CT) is a mapping CT(αβ →αγ , w):Σn→Σn that replaces all digrams αβ for αγ, where p(α,γ) = 0and β6=γ.Σis the alphabet of the input message w, and n is the length of w. Let CT← be the context transformation applied from the end of the message to the beginning and CT→ in the opposite direction. The context transformation CT→ is an inverse transformation of CT← . The proof of this property with an explanation for why it is the only pair of the function and its inverse is left to Appendix A. The application of two consecutive context transformations and their inverse functions is presented in the following example: Example 1. abcdabacd|CT←(ab →aa) aacdaaacd|CT←(cd →cc) aaccaaacc|CT→(cc →cd) aacdaaacd|CT→(aa →ab) abcdabacd| Entropy 2017,19, 223 5 of 23 3.1.2. Generalized Context Transformation Context transformations were restricted in cases where one of the digrams was missing in the input message. This restriction is removed by the introduction of the generalized context transformations first proposed in [20]. Definition 2. Generalized context transformation (GCT) is a mapping GCT(αβ ↔αγ , w):Σn→Σn that exchanges all occurrences of a digram αβ by a digram αγ and vice versa. Σ is the alphabet of the input message w, and n is the length of w. Example 2. aabcabab|GCT←(ab ↔aa) abacaaaa|GCT→(aa ↔ab) aabcabab Meanwhile, both transformations CT and GCT swap occurrences of two different digrams beginning with the same symbol; they differ in the way they are applied and how the inverse transformation is formed. GCT can be applied in both directions, and the inverse transformation GCT−1 is always applied in the opposite direction, than the forward transformation direction. The algorithm based on the CT and GCT works as follows: 1. Find and apply transformation T so that the change of the entropic size ∆|m|H=|m0|H− |m1|H is maximal. 2. Repeat Step 1 until no transformation can decrease the entropic size of the message. It is also possible to define a transformation and its inverse so that all symbols constituting replaced pairs differ, for instance ab ↔cd ; such a transformation is called generic transformation GT . In this article, we have not proposed algorithms based on GT , but because the set of all generalized context transformations is a subset of a set of generic transformations, the proof of the inverse transformation existence is the same for both GCT and GT. The reader can find the proof in Appendix A. 3.1.3. Higher Order Context Transformation Every time we apply any generalized context transformation GCT , we acquire knowledge about the positions of two distinct digrams in the message. We can either discard this knowledge or we can try to build on it. In the following definition, we define a transformation that is applied over positions where some other transformation was applied before: Definition 3. Let P(w , m) be a set of positions of the first symbol following the sub-message w in the message m and w[i]6=w[ 0 ] , i> 0. If β , γ6=w[ 0 ] , then the higher order context transformation (HOCT) is a mapping HOCT(wβ↔wγ , m , P(w , m)) :Σn→Σn that exchanges all sub-messages wβ for sub-messages wγand vice versa. The restriction that the sub-message w has to satisfy is w[ 0 ]6=w[i] , where i> 0 is closely related to the existence of the inverse transformation to HOCT . The properties related to the HOCT and their proofs are left to Appendix A. Let O=|w| be the size of the sub-message w from Definition 3, then O is an order of HOCT . Any GCT(αβ ↔αγ) is then the first order HOCT(αβ ↔αγ , m , P(α , m)) . Given that we just before applied some transformation m1=HOCT1(wβ↔wγ , m , P(w , m)) , we can decide to collect the positions of either w1=wβ or w2=wγ , collect the distribution of symbols in P(wi , m) and apply another HOCT(wiρ↔wiϕ , m1 , P(wi , m)) . In this sense, HOCT is not used only to interchange different Entropy 2017,19, 223 6 of 23 sub-messages, but it also allows one to proceed with some other transformation HOCT of a higher order. The application of two consecutive HOCT transformations is presented in the following example: Example 3. abcdabcd|HOCT(ab ↔ad,P(a,m) = {1, 5}) adcdadcd|HOCT(adc ↔add,P(ad,m) = {2, 6})) adddaddd| The HOCT transformation is a recursive application of GCT in the context of some prefix w . The steps of the algorithm are outlined as follows: 1. Find and apply HOCT(αβ ↔αγ) over the set of positions P(α) , so that the change of entropic size ∆|m|H=|m0|H− |m1|His maximal and ∆|m|H>Lim. 2. If the frequency of αβ resp. αγ is larger than one, then repeat Step 1 over the set of positions P(αβ) resp. P(αγ) , i.e., positions where HOCT from Step 1 was applied; otherwise, repeat Step 1 over positions P(α)or return if no more HOCT passes the entropic size reduction conditions. The algorithm above is iteratively called for symbols sorted from the most frequent one to the least frequent one. The Lim variable can be used to restrict transformations whose entropic size reduction is too small, so they cannot be efficiently stored in the dictionary. 3.2. Compression Functions In the preceding section, we described three types of transformations that leave message size intact. In this section, we will focus on a description of two approaches in the replacement of digrams for a new symbol. First, we describe basic principles of the well-known algorithm Re-Pair, and then, we will propose a modification of Re-Pair called MinEnt. 3.2.1. Re-Pair The main idea behind the Re-Pair algorithm is to repeatedly find the most frequent digram and replace all of its occurrences with a new symbol that is not yet present in the message. The algorithm can be described in the following steps: 1. Select the most frequent digram αβ in message m. 2. Replace all occurrences of αβ for new symbol γ. 3. Repeat Steps 1 and 2 until every digram appears only once. In Step 2 of the algorithm, the pair αβ together with a new symbol γ are stored in a dictionary. The implementation details of the Re-Pair algorithm are left to Section 3.2.2 regarding the proposed MinEnt algorithm. 3.2.2. MinEnt The MinEnt algorithm proposed in this article is derived from the Re-Pair algorithm. The main difference is in Step 1, where instead of the selection of the most frequent digram, we select a digram that minimizes |m1|Hfrom Equation (3): 1. Select digram αβ in message m0 so that the change of entropic size ∆|m|H=|m0|H− |m1|H is maximal. 2. Replace all occurrences of αβ for new symbol γ. 3. Repeat Steps 1 and 2 until every digram appears only once. Entropy 2017,19, 223 7 of 23 More precisely, let m1=MinEnt(m0 , αβ →γ) be the application of Step 1 and Step 2 of the MinEnt algorithm, then digram αβ fulfills: arg min α,β∈Σ0 |MinEnt(m0,αβ →γ)|H(4) where Σ0 is the alphabet of the message m0 . To demonstrate the difference between Re-Pair and MinEnt, consider the following example: Example 4. m0=aababcdcdb The entropic size of m0 is |m0|H= 19.71 bits. There are two non-overlapping digrams that occur twice: ab and cd. (m0,ab →e) = aeecdcdb (m0,cd →e) = aababeeb Based on the Re-Pair algorithm, we do not know which digram should be preferred, because both have the same frequency. In the MinEnt case, we can compute |m1|H for both cases, yielding |m1|H ab = 18 bits and |m1|H cd =12.49 bits, and so, the replacement cd →ewill be the preferred one. The MinEnt and the Re-Pair strategies of digram selection are evaluated using the algorithm described in [ 13 ]. In the initialization phase of the algorithm, the input file is transformed into the linked list, and each input byte is converted into the unsigned integer value. In the next step, the linked list is scanned, and the frequencies and positions of all digrams are recorded. Frequencies of digrams, resp. the change of the entropic size of the message measured in bytes, are used as indices for the priority queue. The size of the queue is limited to the maximal frequency, resp. in the case of the MinEnt algorithm, the maximum entropic size decrease. The algorithm iteratively selects the digram with the highest priority, replaces all occurrences of the digram with the newly-introduced symbol, decrements counts of neighboring digrams and increments counts of newly-introduced digrams. In the case of the MinEnt algorithm, we have to recompute the change of the entropic size of all digrams in the priority queue. We restrict the number of recomputed changes of the entropic size to the top 20 digrams with the highest priority, so that the time complexity of this additional step remains O( 1 ) . Both algorithms are accomplished in O(n) expected time; see [ 13 ] for details. The memory consumption is larger in the MinEnt case, because each digram has to be assigned with the additional quantity: the value of the change of the entropic size of the message. 3.3. Discussion of the Transformation and Compression Function Selection Strategies To demonstrate the behavior of aforementioned algorithms, we proposed strategies for the selection of transformations and compression algorithms. We compared the evolution of the entropy of the alphabet, the entropic size of the message and the final size of the message given as the sum of the entropic size of the message and the upper boundary on the size of the dictionary (Section 3.3.1). The following strategies are being compared: •GCT : selection of the generalized context transformation so that the decrease of entropy is maximal. •HOCT : selection of the higher order context transformation so that the decrease of entropy is maximal in the context of prefix w. •Re-Pair: selection of the most frequent digram and its replacement with an unused symbol. • MinEnt: selection of the most entropic size reducing digram and its replacement with an unused symbol. Entropy 2017,19, 223 8 of 23 3.3.1. The Upper Boundary on the Dictionary Entry Size All transformations and compression functions are usually stored as an entry in a dictionary. To be able to compare the effectiveness of transformations, we selected the worst case entropy of each symbol, given by log |Σi| , where Σi is an alphabet and subscript i denotes the number of applied transformations. In the GCT and HOCT strategies, the size of the alphabet will be constant, unless some symbols were completely removed, then the size of the alphabet decreases. Re-Pair and MinEnt algorithms, which introduce new symbols, have an increasing alphabet size. The upper boundary on the resulting size of each dictionary entry |D|for GCT and HOCT transformations is defined as: |D|=3 log |Σ0| where |Σ0| is the size of the initial alphabet. The Larsson and Moffat [ 13 ] version of the Re-Pair introduces several efficient ways of dictionary encoding: the Bernoulli model, literal pair enumeration and interpolative encoding. In our experiments with Re-Pair and MinEnt, we used interpolative encoding to encode dictionary. 3.3.2. Comparison of the Alphabet’s Entropy Evolution Even though the transformations and compression functions pursue the same objective, minimization of the entropic size of the message, they achieve that by a different evolution of zero order entropy. Transformation-based strategies minimize zero order entropy; meanwhile, both compression strategies introduce new symbols, and as a result, zero order entropy grows. The initial values of the quantities of the examined test file are summarized in Table 1. The example of the comparison of the zero order entropy evolution of different strategies is provided in Figure 1a. Table 1. Characteristics of the paper5 file from the Calgary corpus: the initial size of alphabet |Σ| , the initial file size |m0| measured in bytes, the initial entropy H0 measured in bits and the initial entropic size |m0|Hmeasured in bytes. File Name |Σ| |m0|H0|m0|H paper5 91 11 954 4.936 7 376 (a) (b) Figure 1. Comparison of zero order entropy evolution over the paper5 file from the Calgary corpus. ( a ) Evolution of zero order entropy for different strategies; ( b ) evolution of zero order entropy for different values of the limit (LIM) in the HOCT strategy. Both compression functions achieve a very similar resulting value of zero order entropy. The Re-Pair strategy begins with the highest growth of entropy, but the increase slows down with the number of iterations as the frequency of each consecutive digram drops. As will be discussed in Section 4.2.2, digrams consisting of symbols with a lower frequency will be preferred by MinEnt, Entropy 2017,19, 223 9 of 23 because they will be able to achieve a larger decrease of entropic size, and their replacement brings less costs in the zero order entropy increase. This behavior can be observed especially in later iterations of the Re-Pair and MinEnt algorithms. Both transformations reduce the value of zero order entropy. GCT initially drops faster, but in the end, it significantly slows down. The application of the HOCT strategy achieves the lowest resulting value of entropy, and the interesting fact is that it decreases at an almost constant rate. The behavior of entropy evolution for different values of the limit in HOCT is presented in Figure 1b. The unrestricted case (Lim =0) shows us the bottom limit of zero order entropy reduction using the HOCT strategy. 3.3.3. Comparison of Entropic Size Evolution The selection of the most frequent digram will produce the largest decrease of the number of symbols in each iteration. Surprisingly, the Re-Pair strategy does not necessarily have to converge to its minimum in the lower number of iterations than MinEnt. Figure 2presents this behavior for the paper5 file of the Calgary corpus. Both approaches end with a similar number of symbols in the resulting message. Figure 2. Comparison of Re-Pair and MinEnt algorithms: evolution of the message size measured in the number of symbols over the paper5 file from the Calgary corpus. The MinEnt strategy achieves the lowest entropic size of the message, and at each iteration, the entropic size of the message is lower than in the case of the Re-Pair strategy, see Figure 3. The overall efficiency depends on our ability to compress the resulting dictionary. Figure 3. Comparison of Re-Pair, MinEnt, GCT and HOCT algorithms: evolution of the entropic message size measured in bits per byte over the paper5 file from the Calgary corpus. A summary of different transformation strategies is provided in Table 2. A summary of compression functions is then given in Table 3. The least number of iterations was achieved by HOCT with LIM =|D| ; this strategy also leads to the least final size |mf| , but it should be emphasized that the resulting entropic size of the message |mf| is a very pessimistic estimate, due to the construction of the size of dictionary entries. Entropy 2017,19, 223 16 of 23 4.2.2. The Second Part: Symbols Participating in the Substitution Function In the second case, the frequencies of symbols and their total number will change. The equation for stretching factor c2will be derived in the following way: p1(x) = f1(x) |m1|=f0(x) + ∆f(x) |m0|+∆m f0(x) + ∆f(x) |m0|+∆m=c2 f0(x) |m0| The main difference in both cases is that c1 is a constant; meanwhile, c2 is a function of the particular symbol x. c2(x) = (f0(x) + ∆f(x))|m0| f0(x)(|m0|+∆m)=f0(x) + ∆f(x) f0(x)c1=F(x)c1(22) where in the last step, we made the substitution: F(x) = (f0(x) + ∆f(x))/f0(x) The rest of the derivation follows the derivation of Equation (19). H(p1(ΣT)) = −∑ x∈ΣT p0(x)c2(x)log c2(x)−∑ x∈ΣT c2(x)p0(x)log p0(x)(23) The behavior of Equation (23) for different values of p0(x) is visualized in Figure 6. The substitution of less frequent symbols leads to a lower increase of zero order entropy. Figure 6. Dependency of H(p1(ΣT)) on different values of c2 for three cases of p0(x)∈ { 0.05, 0.1, 0.2 } . The resulting entropic size simplifies given that: |m1|c2(x)p0(x) = f0(x) + ∆f(x) = f1(x)(24) yields: |m1|H=|m1|HT(p1) =−∑ x∈ΣT [f0(x) + ∆f(x)](log c2(x) + log p0(x)) (25) We now analyze both terms in (25) from the perspective of different values of c2(x) . We will be particularly interested in compression functions. We know that for compression function c1> 1, symbols with ∆f(x)<0, i.e., symbols whose frequency decreases, will have F(x)<1. The positivity or negativity of log c2then depends on the value of product F(x)c1. Entropy 2017,19, 223 17 of 23 The case when F(x)c1= 1 has a solution F(x) = 1 /c1 , then log c2(x) = 0. The term log p0(x) is always negative. The value of F(x) must be larger than 1 /c1 to decrease the zero order entropy conveyed by symbol x, since then, c2(x)>1 and, as a consequence, log c2(x)>0. F(x)>1 c1 f0(x) + ∆f(x) f0(x)>|m0|+∆m |m0| 1+∆f(x) f0(x)>1+∆m |m0| ∆f(x) f0(x)>∆m |m0| |∆f(x)| f0(x)<|∆m| |m0| |∆f(x)| |∆m|<f0(x) |m0|=p0(x) (26) The introduction of the absolute value in the middle step of the derivation of Inequality (26) is allowed since using compression functions values of ∆f(x) and ∆m can only be negative. Suppose now that we have a digram d=αβ , given that α6=β , and we replace it by the newly-introduced γ , then ∆m=∆f(α) = ∆f(β) . The left part of Inequality (26) becomes equal to one, so Inequality (26) cannot be satisfied, and log c2(x) in this case will be negative and will always increase the amount of information carried by the symbols αand β. Finally, we state the condition for the entropic size decrease: Corollary 2. The entropic size of the part of the message formed by symbol x decreases when: ∆f(x) f0(x)<−log c2(x) log c2(x) + log p0(x)(27) Proof. |m1|H<|m0|H [f0(x) + ∆f(x)][log c2(x) + log p0(x)] <f0(x)log p0(x) f0(x)log c2(x) + ∆f(x)log p0(x) + ∆f(x)log c2(x)<0 ∆f(x)(log p0(x) + log c2(x)) <−f0(x)log c2(x) ∆f(x) f0(x)<−log c2(x) log c2(x) + log p0(x) 4.2.3. Third Part: Introduced and Removed Symbols We begin with symbol x , which is completely removed from the message, so that initially, p0(x)6= 0, but p1(x) = 0. This case is trivial, and it has zero participation in the final value of the entropy and the entropic size of message. The remaining case we have to deal with is a case when initially symbol x has zero probability p0(x) = 0, but after substitution, its probability will increase to some p1(x)6=0. The final probability is given as: p1(x) = ∆f(x) |m0|+∆m(28) Entropy 2017,19, 223 18 of 23 Since the symbol x initially has zero participation in entropy and entropic size, it will always lead to the increase of both quantities. For the set ΣN of all such symbols, its portion on total entropy is then given by: H(p1(ΣN)) = −∑ x∈ΣN ∆f(x) |m0|+∆mlog ∆f(x) |m0|+∆m(29) and the corresponding final entropic size will be given by: |m1|H=|m1|HN(p1) =−∑ x∈ΣN ∆f(x)[log ∆f(x)−log (|m0|+∆m)] (30) It is important to remark that it does not make much sense to introduce more than one symbol in one substitution function, because both quantities would then add themselves twice. 4.3. Calculation of ∆|m|H At first glance, it seems that we need to evaluate all symbols to predict zero order entropy, but instead, it is possible to predict the exact change of the entropic size of the message after the application of the compression function by the evaluation of entropic sizes given by Equations (21), (25) and (30) dealing only with symbols x∈Σ\ΣI . In the particular case of the Re-Pair algorithm, there are only two symbols whose frequency knowledge is sufficient to evaluate the change of the entropic size of the message; suppose a compression function CF(αβ →γ) so that p1(α)6= 0, p1(β)6= 0 and p0(γ) = 0, then the resulting entropic size is given as: ∆|m|H=|m0|log c1−log c1∑ x∈{α,β} f0(x) +∑ x∈{α,β} f0(x)log c2(x) + ∆f0(x)log p0(x) + ∆f0(x)log c2(x) −∆f(γ)[log ∆f(γ)−log (|m0|+∆m)] (31) finally, for the Re-Pair, it holds that if α6=β , then ∆m=∆f(α) = ∆f(β) = ∆f(γ) = f(α , β) , and all ∆’s in (31) turn into f(αβ). If α=β, then ∆f(α)/2 =∆f(γ). 5. Conclusions We described three types of transformations for the preprocessing of messages so that the zero order entropy of messages drops so the resulting message can be more efficiently encoded using zero order entropy compression algorithms like Huffman or arithmetic coding. We presented relations that govern the change of the message size for transformations and compression functions. Transformations have the advantage that they do not modify the size of the alphabet, especially in the case of digram substitution used by Re-Pair and our proposal of the MinEnt strategy; the resulting size of the alphabet significantly grows, and it brings additional complexity in the storage of the entropy coding model, i.e., the storage of the output alphabet. The MinEnt strategy selects digrams to be replaced by the minimal entropic size of the resulting message, and it is shown that in most cases, the resulting message size is smaller than the one achieved by Re-Pair. We also showed that the two algorithms follow slightly different execution paths, as MinEnt prefers digrams that consist of less frequent symbols; meanwhile, Re-Pair does not take this into consideration. The compression functions take advantage of transformations as they achieve a better resulting compression ratio. In future work, we will focus on the storage of the dictionary that will be used in transformation algorithms, because this area can significantly improve the resulting compression ratio. Entropy 2017,19, 223 19 of 23 Further, we will focus on the description of the relation between the entropy coding model of the final message and the size of the final alphabet. Acknowledgments: This work was supported by the project SP2017/100 Parallel processing of Big Data IV, of the Student Grant System, VSB-Technical University of Ostrava. The costs for open access were covered. Author Contributions: Michal Vasinek realized this work, proposed and developed the implementation of the CT , GCT , HOCT and MinEnt algorithms. Jan Platos provided the guidance during the writing process and revised the paper. Conflicts of Interest: The authors declare no conflict of interest. Appendix A The following sections present properties of transformations. Specifically for each type of transformation we will provide a proof of the inverse transformation existence. Further we will describe how the frequencies of symbols will be altered if the particular transformation is going to be applied. Appendix A.1. CT—Proof of the Correctness This theorem defines the inverse transformation of the context transformation: Theorem A1. The context transformation CT−1≡CT→(αγ →αβ) is inverse transformation of the context transformation CT←(αβ →αγ). Proof. Let CT−1≡CT→ , if CT−1 is inverse then the following must be true for any message m : CT−1(CT(m)) = m . Suppose that we are passing message m from the end to the beginning and suppose that in positions i and i+ 1 digram αβ is located, this digram is replaced by αγ , the next pair of positions explored are i− 1 and i , but their value is independent of the preceding replacement, because the replacement has taken place in position i+ 1, so when CT−1 is applied in position i it will find there the digram αγ and reverts it back to αβ. Other combinations of directions do not form a pair of transformation and its inverse. We give an example for each case showing this property: CT→(αβ →αα) and CT−1 ← over the message m=αβα:CT→(αβα) = ααα but CT−1 ←(ααα) = αββ 6=αβα . Next consider CT→(αβ →αα) and CT−1 → over the message m=ααβ : CT→(ααβ) = ααα but CT−1 →(ααα) = αβα 6=ααβ . And in the last case let’s consider CT←(αβ →αα) and CT−1 ← over the message m=αβα : CT→(ααβ) = ααα but CT−1 →(ααα) = αββ 6=ααβ. Let f0(αγ , m) = 0 is a number of occurrences of particular digram αγ in a message m , then the following corollary tells us how many digrams αγ is introduced by context transformation CT→(αβ →αγ): Corollary A1. Under assumption that α6=γ the number of occurrences of digrams αγ and αβ after application of transformation CT→(αβ →αγ)is f1(αγ,CT(m)) = f0(αβ,m)and f1(αβ,CT(m)) = 0. Proof. A proof is a consequence of Theorem A1, since each replacement is independent of each other and so each digram αβ is replaced by αγ leaving f1(αβ) = 0 and f1(αγ) = f0(αβ). The corollary allows us to precisely predict not only the frequencies of the interchanged digrams αβ and αγ but also as a consequence the frequencies of individual symbols after transformation. The special case of transformations on a diagonal (see Definition A1) will be discussed in the next paragraph. Appendix A.2. Diagonal Context Transformation Diagonal transformation is a transformation where one of the digrams participating in the transformation is of the form αα . The resulting frequency of such a digram is unpredictable without Entropy 2017,19, 223 20 of 23 knowledge of the distribution of all n-grams of the form αn , where n≥ 2, but we show that for any diagonal CT , it is possible to predict frequencies of symbols α and β . The problems with predictability arise from the repetition of symbols. Definition A1. Diagonal context transformation is a context transformation of the form CT←(αα →αβ). Consider two transformations, CT1≡CT←(αα →αβ , ααα) = αββ and CT2≡CT←(αβ → αα , αβα) = ααα , if Corollary A1 would also be valid for diagonal transformations, then for instance in the case of CT1 , the frequency f1(αβ) = f0(αα) but this obviously is not true, instead we see that the new frequency f(β)of symbol βis f1(β) = f0(αα). Suppose we have a message s=αn , then CT1(s) = αβn−1 , we clearly see that the frequency f(αβ , CT1(s)) = 1 and f(ββ , CT1(s)) = n− 2, because the number of digrams in a message is given by the length of the message minus one. We can now express the frequency f(αβ , CT1(m)) of the newly introduced occurrences of digram αβ as a sum of all sub-messages enclosed in m in the form xsx , where x6=α for all n≥ 2. So we see that it is possible to precisely predict the change of frequency of αβ, but it demands knowledge of the distribution of all enclosed sub-messages s. From the other perspective, since each occurrence of digram αα in the former message is transformed into αβ we can see that the frequency f1(β , CT1(m)) = f0(β) + f0(αα) and f1(α,CT1(m)) = f0(α,m)−f0(αα). Very similar behavior is observed in the second case of CT2 . The problem is in the repetition of the pattern t= (αβ)n , then CT2(t) = α2n and f1(αα) = 2 n− 1. Again without knowledge of all sub-messages t enclosed in m we cannot predict the exact change of frequency of neither digram αα nor αβ , but since we know that each pair αβ in the former message will be transformed to αα , we can again precisely predict frequencies of individual symbols f1(α) = f0(α) + f0(α , β) and f1(β) = f0(β)−f0(αβ). With the knowledge of the preceding discussion and of Corollary A1 we conclude that for any context transformation CT we are able to compute the frequency and corresponding probability of arbitrary symbol after application of any CT from the knowledge of initial distribution of symbols and digrams. In [ 26 ] we showed that under certain conditions it is possible to process several context transformations simultaneously. Appendix A.3. GCT—Frequencies Alteration Corollary A2. Under assumption that α6=γ , α6=β and β6=γ the number of occurrences of digrams αγ and αβ after application of transformation GCT←(αβ ↔αγ) is f1(αγ , GCT(m)) = f0(αβ , m) and f1(αβ,GCT(m)) = f0(αγ,m). Proof. Since each digram αβ resp. αγ is replaced by αγ resp. αβ , and neither of the digrams influence the transformation of the other, their frequencies must interchange. Appendix A.4. Generic Transformation—Proof of Correctness Generic transformation GT exchanges any two digrams. In the design of algorithms, we prefer GCT over GT since the space from which generic transformations are selected is in this case of order the |Σ|4 and when alphabets of the large size are dealt with, the search in such a space would be computationally very expensive. Definition A2. Generic transformation (GT) is the mapping GT(αβ ↔γρ , w):Σn→Σn , Σ is the alphabet of the input message w and n is the length of the input message, that exchanges all digrams αβ for digram γρ and vice-versa. The inverse transformation of GCT and GT is defined by the following theorem: Entropy 2017,19, 223 21 of 23 Theorem A2. Generic transformation GT−1≡GT←(αβ ↔γρ) resp. GT−1≡GT→(αβ ↔γρ) is the inverse of generic transformation GT→(αβ ↔γρ)resp. GT←(αβ ↔γρ) Proof. First, we show that it is sufficient to prove that for any string s=xwx , it holds that GT−1(GT(s)) = s , where x/∈ΣGT ={α , β , γ , ρ} and w[i]∈ΣGT . Suppose that x is located in position p then for digrams d in positions (p− 1, p) and (p , p+ 1 ) it holds that GT(d) = d . So the first possible application of GT can occur in positions (p− 2, p− 1 ) and (p+ 1, p+ 2 ) and these are independent, i.e., non-overlapping. Next, we show that each replacement made in the forward transformation will be reverted back by inverse transformation. Take for example transformation GT←(αβ ↔γρ) the transformation is applied in the right to left direction. The last applied forward transformation in positions (r , r+ 1 ) replaces for instance digram αβ for γρ leaving w[r , r+ 1 ] = γρ , the inverse transformation, by definition the same transformation applied in the opposite direction, reverts digram γρ back to αβ . Now consider any triplet of positions (r− 1, r , r+ 1 ) in a transformed message, the input of the inverse transformation in (r , r+ 1 ) is dependent on the result of the inverse transformation in the preceding pair of positions, but as we saw the first applied inverse reverted digram back correctly so the state in positions (r+ 1, r+ 2 ) is exactly like the one of the state left by forward transformation in these positions, so any other digram will be reverted back correctly, because every preceding application of the inverse leaves the state of the digram in the state that was left by the forward transformation and this digram is trivially reverted back to initial state. The same rules are valid for GT in the opposite direction, since the transformation GT←(m) = GT→(mT), where mTis a mirror message of m. Appendix A.5. HOCT—Proof of the Correctness The following trivial Lemma will help us to formulate a theorem about inverse transformation to HOCT: Lemma A1. Let T=HOCT(wβ↔wγ , m , P(w , m)) is a higher order context transformation over the input message m, given that we possess the knowledge of w and positions P(w,m), then T−1=T. Proof. Because we don’t have to pass through the whole message either in the forward or inverse transformation case, but only through the set of positions P(w , m) , then the symbol in position i∈P(w , m) , for instance m[i] = β will switch by HOCT to m[i] = γ and by repeated application of HOCT it reverts back to m[i] = β. The Lemma A1 is trivial but comes into play when P(w , m) is a product of some other higher order context transformation, i.e., the one with an order lower by one. Theorem A3. Let m1=HOCT1(wα↔wβ , m , P(w , m)) and m2=HOCT2(wαγ ↔wαρ , m1 , P(wα , m1)) are two higher order context transformations. Let T(m) = HOCT2(HOCT1(m)) be a transformation composition of two higher order context transformations over input message m . Then HOCT−1 2(wαγ ↔ wαρ , m3 , P(wβ , m3)) , such that m3=HOCT1(m2)) then the transformation composition T−1≡ HOCT−1 2(HOCT1(m2)) = m is the inverse transformation of T. Several remarks to the formulation of Theorem A3: Transformations HOCT1 and HOCT2 are applied over two consecutive states of the message. The positions P(wα , m1) correspond to the positions P(wβ , m) , since sub-messages wα have been replaced by wβ in the application of HOCT1 . The inverse transformation by HOCT−1 2 is applied instead over positions P(wβ , m3) , since these positions have already been reverted back by HOCT1. The proof is based on the restriction that w[ 0 ]6=w[i] , i> 0, it can be viewed as we would split the input message m to sub-messages si separated by w[ 0 ] . For instance, suppose that w[ 0 ] is a space character in ordinary text, since, by Definition 3, no other character in w can be a space character, Entropy 2017,19, 223 22 of 23 it follows that the possible transformations are being applied on words following the space character. Now using the fact that si is enclosed by w[ 0 ] , i.e., they do not overlap, allows us to handle each sub-message siindependently. Proof. For the two sets of positions, it holds that P(w , m)∩P(wα , m1) = ∅ , because elements of the former are predecessors of the latter and s does not overlap. The locations of w in m and m2 are identical as they were not modified during HOCT , i.e., P(w , m) = P(w , m2) . When we apply HOCT1 again it will simply revert the symbols in positions given by P(w , m) back according to Lemma A1 yielding the message state m3 . In the forward transformation HOCT2 was applied over positions of P(wα , m1) , but these are the former positions of P(wβ , m) , that are already transformed back by the application of HOCT1 , so P(wα , m1) is equal to P(wβ , m3) and when HOCT2 is applied over positions P(wβ,m3)it exchanges symbols γand ρand eventually yields m. The recursive application of Theorem A3 leads to the conclusion that this process can be repeated until there is no other pair of symbols then these containing w[ 0 ] as one of the symbols α or β or we simply reach the end of the message. Corollary A2 about the prediction of frequencies in the case of GCT is also applicable in the case of HOCT, because the principle that the exact number of replacements is known is also valid and we are able to precisely compute the future probabilities of symbols before the arbitrary HOCT is applied. If we implement the inverse algorithm as a sequential algorithm operating in the left-right manner, it is possible to have one of the transformation symbols if β , γ is equal to w[ 0 ] . Suppose the following example: m=abcabc , P(a , m) = { 0, 3 } , HOCT1(ab ↔aa) and HOCT2(aac ↔aaa) yielding the output message m2=aaaaaa . Now applying inverse transformation sequentially from left to right, we first replace aa by ab yielding mi=abaaaa , then applying replacement aba for abc yielding mi+1=abcaaa , now because there is no other transformation that is induced from abc we know that the next a symbol is w[ 0 ] and we can repeat the preceding process again starting from this a . The sufficient condition for the introduction of w[ 0 ] as the transformation symbol β or γ is that w contains no other w[ 0 ] in w[i] , i> 0, because the inverse process removes all introduced w[ 0 ] symbols from the transformed message during left to right sequential inverse transformation. References 1. Cover, T.M.; Thomas, J.A. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing); Wiley-Interscience: New York, NY, USA, 2006. 2. Shannon, C.E. A Mathematical Theory of Communication. Bell Syst. Tech. J. 1948,27, 379–423. 3. Huffman, D.A. A Method for the Construction of Minimum-Redundancy Codes. Proc. Inst. Radio Eng. 1952 , 40, 1098–1101. 4. Witten, I.H.; Neal, R.M.; Cleary, J.G. Arithmetic Coding for Data Compression. Commun. ACM 1987 , 30, 520–540. 5. Charikar, M.; Lehman, E.; Lehman, A.; Liu, D.; Panigrahy, R.; Prabhakaran, M.; Sahai, A.; Shelat, A. The Smallest Grammar Problem. IEEE Trans. Inf. Theory 2005,51, 2554–2576. 6. Nevill-Manning, C.G. Inferring Sequential Structure. Ph.D. Thesis, University of Waikato, Hamilton, New Zealand, May 1996. 7. Nevill-Manning, C.G.; Witten, I.H. Identifying Hierarchical Structure in Sequences: A Linear-time Algorithm. J. Artif. Int. Res. 1997,7, 67–82. 8. Kieffer, J.C.; Yang, E.-H. Grammar Based Codes: A New Class of Universal Lossless Source Codes. IEEE Trans. Inf. Theory 2000,46, 737–754. 9. Ziv, J.; Lempel, A. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 1978,24, 530–536. 10. Yang, E.; He, D. Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform 2. With context models. IEEE Trans. Inf. Theory 2003,49, 2874–2894. 11. Gage, P. A New Algorithm for Data Compression. C Users J. 1994,12, 23–38. Entropy 2017,19, 223 23 of 23 12. Nakamura, H.; Marushima, S. Data Compression by Concatenation of Symbol Pairs. In Proceedings of the IEEE International Symposium on Information Theory and Its Applications, Paris, France, 13–17 September 1996; pp. 496–499. 13. Larsson, N.J.; Moffat, A. Off-line dictionary-based compression. Proc. IEEE 2000,88, 1722–1732. 14. Claude, F.; Farina, A.; Navarro, G. Re-Pair Compression of Inverted Lists. arXiv 2009 , arXiv:cs.IR/0911.3318. 15. Masaki, T.; Kida, T. Online Grammar Transformation Based on Re-Pair Algorithm. In Proceedings of the Data Compression Conference (DCC), Snowbird, UT, USA, 29 March–1 April 2016; pp. 349–358. 16. Grassberger, P. Data Compression and Entropy Estimates by Non-sequential Recursive Pair Substitution. Physics 2002, arXiv:physics/0207023. 17. Calcagnile, L.M.; Galatolo, S.; Menconi, G. Non-sequential recursive pair substitutions and numerical entropy estimates in symbolic dynamical systems. arXiv 2008, arXiv:cond-mat.stat-mech/0809.1342. 18. Navarro, G.; Russo, L. Re-pair Achieves High-Order Entropy. In Proceedings of the Data Compression Conference, DCC 2008, Snowbird, UT, USA, 25–27 March 2008; p. 537. 19. Vasinek, M.; Platos, J. Entropy Reduction Using Context Transformations. In Proceedings of the Data Compression Conference (DCC), Snowbird, UT, USA, 26–28 March 2014; p. 431. 20. Vasinek, M.; Platos, J. Generalized Context Transformations—Enhanced Entropy Reduction. In Proceedings of the Data Compression Conference (DCC), Snowbird, UT, USA, 7–9 April 2015; p. 474. 21. Vasinek, M.; Platos, J. Higher Order Context Transformations. arXiv 2017, arXiv:cs.IT/1701.01326. 22. Kida, T.; Matsumoto, T.; Shibata, Y.; Takeda, M.; Shinohara, A.; Arikawa, S. Collage System: A Unifying Framework for Compressed Pattern Matching. Theor. Comput. Sci. 2003,298, 253–272. 23. González, R.; Navarro, G. Compressed Text Indexes with Fast Locate. In Proceedings of the 18th Annual Conference on Combinatorial Pattern Matching, CPM’07, London, ON, Canada, 9–11 July; Springer: Berlin/Heidelberg, Germany, 2007; pp. 216–227. 24. Claude, F.; Farina, A.; Navarro, G. Re-Pair compression of inverted lists. arXiv 2009, arXiv:0911.3318. 25. Vasinek, M. Kontextove Mapy a Jejich Aplikace. Master’s Thesis, Vysoka Skola Banska—Technicka Univerzita Ostrava, Ostrava, Czech Republic, 2013. 26. Vasinek, M.; Platos, J. Parallel Approach to Context Transformations. Available online: http://ceur-ws.org/ Vol-1343/paper4.pdf (accessed on 11 May 2017). c  2017 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).